散列表是什么?
散列表为每个对象计算一个整数，称为散列码，其由对象的实例域生成
- 如果自定义类，就要重写该类的hashcode()方法
- 如果a.equals(b)==true，则a和b拥有相同的散列码
为什么使用散列表
链表和数组可以指定元素的排列次序，但当查找某个元素又忘记其位置时，就需要遍历所有元素对比，而使用散列表可以快速查找元素
散列表数据结构
在Java中，散列表用链表数组实现，如图
每个链表称为桶，当需要查找元素时，先计算其散列码，再与桶数求余即得到元素存放的位置
若桶为空则直接插入，如桶被占满（散列冲突），则要将新对象与桶中所有对象比较，查看对象是否存在
Tips：
- Java8后，桶满会从链表转为平衡二叉树
- 桶数应设置为预计元素总数的75%~150%，且最好为素数
- java类库中的桶数为2的幂，默认为16，设置的桶数会自动转为2的下一次幂
- 若散列满太满，则需要再散列，转移旧元素。装填因子默认为0.75，即表中75%位置已被占，则会用双倍桶数再散列