解决hash冲突的四种方法

引言

散列函数，又称为散列算法，哈希函数。常见的比如MD4，MD5，SHA-0，SHA-1等。构造散列函数时应注意：

散列函数的定义域必须包括存储的全部元素的关键字，如果散列表允许有m个地址时，散列函数的值域应该是[0, m-1]。
散列函数计算出来的地址应该能均匀分布在整个地址空间中，若key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取0到m-1中的每一个值。
散列函数应该是简单的，能在较短的时间内计算出结果。

在Java1.7中HashMap的底层源码中哈希函数的实现其实是分开写的。下面是HashMap中put方法的源码。他是先计算了key的一个hash数值。
解决hash冲突的四种方法
下面是HashMap中hash函数的实现，请注意，这里的hash与本篇文章说的哈希函数不同，因为HashMap中的哈希函数是分两步实现的。

下面是哈希函数在HashMap源码中实现的第二部分。

所以，HashMap的哈希函数可以表示为：
Hash(key) = hash(key) & (length-1)，这个式子也可以写为：
Hash(key) = hash(key) % length
一般来说，哈希函数的定义域是无限大的，而值域是有限的，如果不同的key计算出来的哈希值是一样的，我们称此时发生了哈希冲突。
通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决哈希冲突是面试中经常被问到的一个问题。我自己面试都遇到过不止两次，一般面试官都会先问懂不懂HashMap的实现原理？HashMap是如何解决哈希冲突的？（我们都知道是链地址法），你知道还有哪些解决哈希冲突的方法？
一般有四种方法。

开放地址法

当哈希值p = H(key)出现冲突时，以p为基础，产生另一个哈希值，如果p1仍然冲突，再以p为基础，产生另一个哈希值p2，…，直到找到一个不冲突的还行值，表示为：
H_i = (H₀ + d_i) % m

其中H₀表示第一次计算的哈希值，H_i表示第i次计算的哈希值。m为数组的长度。di为增量序列，根据增量序列的取值不同，又分为三种。

线性探测法

d_i = 1，2，3，4，5，6，…，m-1
这种方法是在发生冲突时，顺序查看表中的下一个单元，直到找出一个空单元或查遍全表。

二次探测法

d_i = 1²，-1²，2²，-2²，…(i = 1，2，3，4，…，(m-1)/2)
这种方法在发生冲突时，在表的左右进行跳跃式探测，比较灵活。

伪随机探测法

d_i = 伪随机数序列

双散列函数探测法

H_i = (H₀+i*ReHash(key))%m
其中第一个散列函数按照key计算出H₀，一旦发生冲突，使用上述公式，第二个散列函数计算位移量。

再哈希法

就是同时构造多个不同的哈希函数，第一个冲突了用第二个，第二个也冲突了用第三个…。这样增加了计算时间。

链地址法

这个就是HashMap使用的方法，用链表解决哈希冲突，在Java1.7中是链表，使用头插法。在Java1.8中使用的是链表加红黑树，链表是尾插法，当链表的长度增加到8时，转换成红黑树。

建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。