3、哈希冲突与解决：什么是哈希冲突、开放地址法（线性探测、二次探测、双重哈希）、链地址法（拉链法）、再哈希法

好，咱们接着聊哈希表。上一章我讲了哈希函数怎么把键映射成下标。但有个问题你肯定想到了——万一两个不同的键，算出来同一个下标呢？

这就是哈希冲突。说白了，就是不同的输入，得到了相同的输出。你想想看，哈希表底层是个数组，数组长度是有限的，而你要存的键值对数量可能远超数组长度。就算哈希函数设计得再均匀，冲突也是不可避免的。

我在项目中遇到过好几次因为哈希冲突处理不当导致的性能事故。有一次线上服务突然变慢，查了半天发现是哈希表里大量元素挤在同一个桶里，查找退化成链表遍历。嗯，从那以后我对冲突解决策略就特别上心。

3.1 开放地址法

开放地址法的思路很直接：既然这个位置被人占了，那我就去找下一个空位。所有元素都存储在数组本身，不额外开辟空间。

查找的时候也一样：先算哈希值，如果那个位置存的不是我要的键，就按同样的规则继续往后找，直到找到或者遇到空位为止。

3.1.1 线性探测

线性探测是最简单的开放地址法。冲突了？那就往后挪一个位置。还冲突？再挪一个。用公式表示就是：

// 线性探测的探测序列
index = (hash(key) + i) % table_size   // i = 0, 1, 2, 3, ...

举个例子。假设哈希表大小是 7，哈希函数是 key % 7。依次插入 10、17、3：

• 10 % 7 = 3，下标 3 空着，直接放
• 17 % 7 = 3，下标 3 被占了，探测 i=1 → 下标 4，空着，放进去
• 3 % 7 = 3，下标 3 被占，下标 4 也被占，探测 i=2 → 下标 5，空着，放进去

你看，三个不同的键，最后挤在连续的位置上。这就是线性探测最大的问题——一次冲突容易引发一连串冲突，形成所谓的「聚集现象」。

3.1.2 二次探测

二次探测就是为了解决线性探测的聚集问题。它不再老老实实地挨个往后找，而是跳着找：

// 二次探测的探测序列
index = (hash(key) + i²) % table_size   // i = 0, 1, 2, 3, ...

探测的位置依次是：hash, hash+1, hash+4, hash+9, hash+16... 这样即使前面几个位置被占了，后面的位置也能快速跳过去，不容易形成连续聚集。

但二次探测也有自己的问题。你想想看，如果表大小选得不好，可能有些位置永远探测不到。比如表大小是 8，二次探测只能访问到一半的位置。所以二次探测要求表大小是质数，这样才能保证探测序列覆盖整个表。

3.1.3 双重哈希

双重哈希是我个人比较喜欢的一种开放地址法。它的思路是：用第二个哈希函数来决定探测的步长。

// 双重哈希的探测序列
index = (hash1(key) + i * hash2(key)) % table_size   // i = 0, 1, 2, 3, ...

这样一来，每个键的探测步长都不一样。就算两个键的 hash1 相同，只要 hash2 不同，它们的探测路径就完全不同。这能有效避免聚集。

我建议 hash2 的设计要注意几点：

• hash2(key) 不能等于 0，否则探测就卡住了
• hash2(key) 最好与表大小互质
• 一个常用的设计是：hash2(key) = prime - (key % prime)，其中 prime 是小于表大小的质数

3.2 链地址法（拉链法）

链地址法的思路完全不同。它不把元素硬塞进数组里，而是让数组的每个位置都挂一个链表。冲突了？没关系，直接往链表后面加就行。

用 C 语言描述大概是这样：

// 链地址法的基本结构
typedef struct Node {
    int key;
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node **buckets;  // 指针数组，每个元素指向一个链表
    int size;
} HashTable;

插入时：计算哈希值 → 找到对应的桶 → 在链表头部或尾部插入。

查找时：计算哈希值 → 找到对应的桶 → 遍历链表找 key。

链地址法有几个明显的优点：

• 负载因子可以大于 1，不像开放地址法那样受限于表大小
• 删除操作简单直接，不会像开放地址法那样需要特殊标记
• 实现起来比较直观，不容易出 bug

但缺点也很明显：链表节点需要额外分配内存，而且链表遍历的缓存局部性不好。如果某个桶里的链表特别长，查找性能就会退化。

3.3 再哈希法

再哈希法，说白了就是准备多套哈希函数。第一套冲突了，换第二套；第二套还冲突，换第三套……直到找到空位为止。

// 再哈希法的探测序列
index = hash_i(key)   // i = 0, 1, 2, 3, ...

你可以把双重哈希看作是再哈希法的一种特例——双重哈希用两个哈希函数组合出探测序列，而再哈希法直接换不同的哈希函数。

再哈希法在实际中用得不多。原因很简单：设计多个独立且均匀的哈希函数并不容易，而且每次冲突都要重新算一个完全不同的哈希值，计算开销比较大。

我个人觉得，再哈希法更适合理论分析，工程上还是链地址法和双重哈希更实用。

3.4 四种方法的对比

方法	核心思路	优点	缺点	适用场景
线性探测	冲突后依次往后找	实现简单，缓存友好	容易聚集，负载因子敏感	表较小、负载因子低的场景
二次探测	冲突后按平方步长跳	缓解聚集，实现较简单	表大小需为质数，可能漏位置	中等规模、对聚集敏感的场景
双重哈希	用第二个哈希决定步长	抗聚集能力强，分布均匀	多一次哈希计算	对性能要求较高的通用场景
链地址法	每个桶挂一个链表	负载因子灵活，删除简单	额外内存开销，缓存不友好	插入删除频繁、数据量大的场景

3.5 知识体系图

下面这张图帮你理清哈希冲突解决方法的整体脉络：

好了，哈希冲突的几种主流解决方法就讲到这里。每种方法都有自己的脾气，没有银弹。关键是你得理解它们的优缺点，然后根据实际场景做选择。下一章我会讲哈希表的动态扩容和缩容，到时候你会看到，冲突解决策略和扩容策略是紧密相关的。

---

公众号：蓝海资料掘金营，微信 deep3321