Hash表(二)——散列冲突

散列冲突

在Hash表(一)——Hash函数已经分析了散列冲突产生的原因，我们一般使用开放寻址法和链表法来解决。

开放寻址法

开放寻址法的主要思想是当出现散列冲突时，我们去重新寻找下一个位置，直到找到空闲位置为止，将数据放置到找到的空闲位置。那么如何去寻找空闲位置呢？一般有线性探测法、二次探测法和双重散列法。

线性探测法

如上图所示，就是使用线性探测法进行寻址。 table部分红色区域表示该部分已经存储数据，当号码牌 060702通过 Hash函数进行散列后，得到的区域已经存储了数据，因此需要从当前为止开始依次向后查找，遇到空闲的位置即为找到存储数据的位置。

在 Hash表中进行查找元素的过程与插入的过程相似。首先通过 Hash函数进行散列后求出对应的散列值，然后比较数组中的该位置的元素是否与要查找的元素相等，若相等，则找到对应的元素；若不想等，则依次向后查找。如果遍历数组时，遇到空闲位置还没找到，则说明散列表中没有对应的元素。

通过插入和查找过程可以发现，当散列表中的数据越来越多时，散列冲突会越来越大，数组中的空闲位置会越来越少，线性探测的时间会越来越久。最坏的时间复杂度为 O(n)。

二次探测法

将线性探测的寻址方法表示出来即为： hash(key)+0， hash(key)+1， hash(key)+2......

二次探测法与线性探测法很类似，只是步长由原来的1变为二次方即 hash(key)+0， hash(key)+1^2， hash(key)+2^2......

双重散列法

双重散列是指我们不仅仅使用一个散列函数，而是使用一组散列函数。如 hash1(key)， hash2(key)， hash3(key)......我们先用第一个散列函数计算，如果存储位置已经被占用，则使用第二个散列函数，以此类推直到找到空余的存储位置即可。

链表法

链表法比开放寻址法更为常用，在 JDK8以前的 HashMap底层源码就是使用链表法进行实现的。其结构图如下所示：

如上图所示，在散列表中每个桶或者槽会对应一条链表，所有散列相同的元素会在存储在同一槽中对应的链表中。

在插入时，通过 Hash函数计算出对应的槽位，然后将其插入到对应的链表中即可；当查找时，也是通过 Hash函数计算出相应的槽位，然后查找相应的元素即可。