06-散列表

定义：

散列表(Hash table) 也叫哈希表，借助散列函数对数组进行扩展，利用的是数组支持按照下标随机访问元素的特性。

基本特点：

散列非常高效，使用散列将耗费O(1)时间来查找、插入以及删除一个元素。

散列函数：

存储了值的数组称为散列表(hash table)，将键映射到散列表中的索引上的函数称为散列函数(hash function)。

散列码：

典型的散列函数首先将搜索键转换成一个称为散列码的整数值，然后将散列码压缩为散列表中的索引。

基本类型的散列码：

  • byte,short,int,char将被转换成int

  • float将使用Float.floatToIntBits(key)作为散列码，返回一个int值，该值的比特表示与浮点数f的比特表示相同。

  • long类型需要拆为前后两个32比特，并执行异或操作将两部分结合（称为折叠folding)

int hashCode = (int)(key ^ (key >> 32)); // ^是比特异或操作， >>按位右移操作符，左边补零

  • double类型首先使用Double.doubleToLongBits方法转化为long，再进行折叠

long bits = Double.doubleToLongBits(key);

int hashCode = (int)(bits ^ (bits >> 32));

字符串类型的散列码：

字符串的散列码会根据字符的unicode和位置得出如下的多项式散列码

(...((s0​×b+s1​)b+s2​)+...+sn−2​)b+sn−1​(...((s 0 ​ ×b+s 1 ​ )b+s 2 ​ )+...+s n−2 ​ )b+s n−1 ​

Si为s.charAt(i)，实验显示，b的最好取值为31，33，37，39和41。String类中的hashCode方法b的值为31。

散列冲突：

  • 开放定址法：如果出现了散列冲突，就重新探测一个空闲位置。根据重新探测的方式，又可以分为线性探测、二次探测、双重哈希三种。

    • 线性探测(Linear Probing)：从发生冲突位置依次往后查找空闲位置。线性探测会导致数据集中到某一块区域。

    • 二次探测(Quadratic probing)：如果说线性探测每次探测的步长是 1，即线性探测的下标序列就是 hash(key) + 0，hash(key) + 1，hash(key) + 2……。而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key) + 0²，hash(key) + 1²，hash(key) + 2²……。

    • 双重哈希(Double hashing)：前面的两种探测方式都只使用一个散列函数，而双重哈希则会使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

  • 拉链法(chaining)：链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。使用链表将所有散列值相同的元素我们都放到相同槽位对应的链表中。当然，这个链表可能为简单链表，也可能是红黑树，如 HahMap。

开放定址法 vs 拉链法：

开放寻址法和链表法。这两种冲突解决办法在实际的软件开发中都非常常用。比如，LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。

开放寻址法优缺点：

优点：

  • 散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。

  • 数组实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。你可不要小看序列化，很多场合都会用到的。

缺点：

  • 用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。

  • 在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。

  • 装载因子的上限不能太大，导致这种方法比链表法更浪费内存空间。

总结： 当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。

拉链法优缺点：

优点：

  • 首先，链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。

  • 链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

  • 可以将链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。

缺点：

  • 链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。但如果我们存储的是大对象，此时存储对象远远大于指针大小（4 byte 或 8 byte），那链表中指针的内存消耗在大对象面前就可以忽略了。

  • 因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响。

装载因子：

不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子来表示空位的多少。计算公式如下：

散列表的装载因子 = 表中的元素个数 / 散列表的长度

Previous05-栈Next07-树

Last updated