哈希表怎么解决冲突?

朱雀 2024-03-17 12:20 64阅读 0赞

#### 文章目录 ####

*   *  0 链地址法
     *  1 线性探测法
     *  2 二次探测法
     *  3 双重散列法
     *  装载因子是什么

![039664f124f14444834dc6680170da15.png][]

### 0 链地址法 ###

链地址法(Chainin):即在哈希表中使用链表来存储冲突的元素，同一个哈希值对应的元素被存储到同一个桶中的链表上。  
当需要查询或删除某个元素时，首先根据哈希值找到对应的桶，然后搜索链表找到对应的元素。  
链地址法是最常见的冲突解决方法，可适用于任何哈希函数。  
![e45b61732fc645b7b3e2a66d4bc28185.png][]  
开放地址法(Open Addressing): 即在哈希表中寻找另一个空槽来存储冲突的元素。  
最常见的开放地址法有三种实现方式

### 1 线性探测法 ###

线性探测法(Linear Probing): 若原哈希函数得到的槽为且已经被占用，则尝试存储到 i + 1 i+1 i\+1、 i + 2 i+2 i\+2等位置，直到找到一个空槽为止;

### 2 二次探测法 ###

当发生冲突时，二次探测法通过使用二次探测序列来寻找下一个空闲的桶。二次探测序列是一个与哈希值相关的数列，它可以根据以下公式计算得出：

h ( k , i ) = ( h ( k ) + c 1 ∗ i 2 + c 2 ∗ i ) % t a b l e S i z e h(k, i) = (h(k) + c1 \* i^2 + c2 \* i) \\% tableSize h(k,i)=(h(k)\+c1∗i2\+c2∗i)%tableSize

其中，`h(k, i)` 是通过二次探测法计算出的下一个桶的位置，`h(k)` 是键的哈希值，`i` 是探测的步长（第几次探测），`c1` 和 `c2` 是常数，`tableSize` 是哈希表的大小。

通过不断增加探测步长 `i`，可以遍历哈希表的下一个位置，直到找到一个空闲的桶或者达到了某个停止条件（如哈希表已满），然后将冲突的元素插入或查找位置。注意，哈希表的大小应该为一个素数，以保证探测序列能够覆盖整个哈希表。

二次探测法相对于线性探测法（逐个查找下一个桶）具有一定的优势，它可以更好地分散冲突元素，减少聚集现象，并且能够更高效地利用哈希表中的空间。

然而，二次探测法也存在一些问题，比如容易产生二次探测的聚集现象，并且需要解决负载因子过高时的填充问题。

### 3 双重散列法 ###

哈希表的双重散列法（Double Hashing）是一种用于解决哈希冲突的方法。它在插入或查找键值对时，通过应用两个不同的哈希函数来计算步长，以找到下一个可用的桶。

双重散列法的实现步骤如下：

1.  首先，选择两个不相同的哈希函数 `hash1` 和 `hash2`。这两个哈希函数应该能够将键值对均匀地映射到哈希表的桶上。
2.  当需要插入或查找一个键值对时，首先使用 `hash1` 计算键的哈希值。
3.  如果对应的哈希桶为空，即未发生冲突，直接在该桶中存储或查找键值对。
4.  如果发生冲突，在哈希表的桶中进行第一次探索，计算第一步探索的步长。可以使用以下公式计算：
    
        step = hash2(key)
    
    其中 `hash2` 是第二个哈希函数。步长 `step` 应该始终大于0。
5.  在发生冲突的桶上进行第二次探索，并计算第二步探索的位置。使用以下公式计算：
    
        position = (hash1 + i * step) % tableSize
    
    其中 `i` 是探索的步数（第几次探索），`tableSize` 是哈希表的大小。
6.  重复步骤5，直到找到一个空闲桶或达到停止条件（如哈希表已满），然后在该桶中插入或查找对应的键值对。

双重散列法的优点是它能够有效地分散冲突，避免聚集现象，并且不需要额外的空间来存储其他的探测序列。此外，双重散列法通常与合适的哈希函数一起使用，能够提供较低的冲突率和较好的查询性能。

### 装载因子是什么 ###

在哈希表中，装填因子（Load Factor）是指哈希表当前存储的元素数量与哈希表容量（桶数）的比例。装填因子用来衡量哈希表的填充程度，即哈希表中已经存储的元素在哈希表容量中所占的比例。

通常情况下，装填因子用小数表示，取值范围在 0 到 1 之间。例如，装填因子为 0.75 表示哈希表中已存储元素的数量是哈希表容量的 75%。

装填因子的计算公式如下：

装填因子 = 元素数量 / 哈希表容量 装填因子 = 元素数量 / 哈希表容量 装填因子=元素数量/哈希表容量

为什么装填因子很重要？

根据装填因子的大小，哈希表会采取不同的策略。当装填因子超过某个阈值时，通常会触发哈希表的扩容操作，重新调整哈希表的容量，以保持装填因子在一个合适的范围内。例如，Java中的 `HashMap` 类在装填因子超过默认阈值（0.75）时，会自动进行扩容。

一般来说，在装填因子较低时，哈希表会占用更多的内存空间，但查找效率较高；  
而在装填因子较高时，哈希表的内存利用率更高，但查找效率可能会降低。

[039664f124f14444834dc6680170da15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8df3f28b939f4978a17519b5fdfa46a9.png
[e45b61732fc645b7b3e2a66d4bc28185.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/226176bef1cd48a7835e350c92476613.png