Q64：Hash表的散列冲突

我会带着你远行 2021-12-14 15:45 322阅读 0赞

### Hash表的冲突解决 ###

对于散列冲突而言，一般有两种解决办法：

*  开放寻址法
 *  链表法

### 开放寻址法 ###

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

**线性探测法：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 1]  
如图所示，在上表中红色区域表示已经存储了数据，当号码牌 060702通过 Hash函数进行散列后，得到的区域已经存储了数据，因此需要从当前为止开始依次向后查找，遇到空闲的位置即为找到存储数据的位置。

在 Hash表中进行查找元素的过程与插入的过程相似。

首先通过 Hash函数进行散列后求出对应的散列值，然后比较数组中的该位置的元素是否与要查找的元素相等，若相等，则找到对应的元素；若不想等，则依次向后查找。

如果遍历数组时，遇到空闲位置还没找到，则说明散列表中没有对应的元素。

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

最坏的时间复杂度为 O(n)。

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

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

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

### 链表法 ###

链表法比开放寻址法更为常用，在 JDK8以前的 HashMap底层源码就是使用链表法进行实现的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 2]  
如上图所示，在散列表中每个桶或者槽会对应一条链表，所有散列相同的元素会在存储在同一槽中对应的链表中。

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70]: /images/20211214/fbedc3dd13024f608fb91ac7bb0a77fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 1]: /images/20211214/861d60d55d1845c88918e26e3e9d70ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x5bTk0MDkyOA_size_16_color_FFFFFF_t_70 2]: /images/20211214/e51395cfc75d41518d86edc53c4ec7b3.png