数据结构——散列表

• 散列表是什么?
• 为什么使用散列表
• 散列表数据结构

散列表为每个对象计算一个整数，称为散列码，其由对象的实例域生成

• 如果自定义类，就要重写该类的hashcode()方法
• 如果a.equals(b)==true，则a和b拥有相同的散列码

链表和数组可以指定元素的排列次序，但当查找某个元素又忘记其位置时，就需要遍历所有元素对比，而使用散列表可以快速查找元素

在Java中，散列表用链表数组实现，如图

每个链表称为桶，当需要查找元素时，先计算其散列码，再与桶数求余即得到元素存放的位置

若桶为空则直接插入，如桶被占满（散列冲突），则要将新对象与桶中所有对象比较，查看对象是否存在

Tips：

• Java8后，桶满会从链表转为平衡二叉树
• 桶数应设置为预计元素总数的75%~150%，且最好为素数
• java类库中的桶数为2的幂，默认为16，设置的桶数会自动转为2的下一次幂
• 若散列满太满，则需要再散列，转移旧元素。装填因子默认为0.75，即表中75%位置已被占，则会用双倍桶数再散列