0 结论

哈希冲突是不可避免的，处理它的主流方法有链地址法和开放定址法。

链地址法是最常用的方法，STL 的 unordered_map 就采用它。它将每个桶实现为一个链表，所有哈希到同一位置的元素都放在这个链表里。这种方法实现简单，性能稳定，但需要额外的指针空间。
开放定址法则将所有元素都存放在数组中，发生冲突时通过线性探测、平方探测或双重散列等策略寻找下一个空槽位。这种方法存储效率高，对缓存友好，但负载因子不能太高，且删除操作比较麻烦。

无论采用哪种方法，当哈希表元素过多导致性能下降时，都会通过重哈希操作，即创建一个更大的新表，并重新插入所有元素，来维持高效的性能。

1 什么是哈希冲突

哈希冲突是指两个或多个不同的关键字（key）通过哈希函数计算后，得到了相同的哈希值，从而需要被映射到哈希表的同一个桶（bucket）或槽位（slot）中。

由于哈希函数的输出范围是有限的（例如，对数组大小取模），而输入范围是近乎无限的，所以冲突是不可避免的。一个好的哈希表设计并非为了完全避免冲突，而是为了高效地处理冲突。

这是最常用、最经典的方法，也是 C++ STL 中 std::unordered_map, std::unordered_set 所采用的方法。

原理：哈希表的每个桶（数组的一个元素）不直接存储键值对，而是存储一个链表的头指针。所有映射到同一个桶的键值对都会通过链表连接起来。
操作：
- 插入：计算键的哈希值找到对应桶，然后将新键值对插入到该桶的链表头部（或尾部）。
- 查找：计算键的哈希值找到桶，然后遍历该桶的链表，用key进行比较。
- 删除：类似查找，找到目标节点后从链表中删除。
优点：
- 实现简单，逻辑清晰。
- 有效处理冲突，随着数据增多性能下降较平缓。
- 可以存储超过哈希表数组大小的数据。
缺点：
- 需要额外的指针空间，存储效率稍低。
- 如果链表变得非常长，查找会退化为O(n)。
- 对CPU缓存不友好，因为链表节点在内存中可能不连续。

C++ STL 的优化：当链表长度超过一定阈值时，可能会将链表转换为一颗小型红黑树，以确保最坏情况下的性能为O(log n)。

这种方法的所有元素都直接存放在哈希表的数组之中（每个桶最多一个元素）。当发生冲突时，会按照某种探测策略（Probing Sequence）在数组中寻找“下一个”空槽位。

优点：
- 所有数据都存储在数组中，存储效率高，无需额外指针。
- 数据在内存中连续分布，对CPU缓存友好。
缺点：
- 实现比链地址法复杂。
- 哈希表的负载因子（Load Factor，已装填元素数/表大小）不能达到1，必须保持在0.7-0.8以下，否则性能会急剧下降。这意味着有更多的空间被浪费。
- 删除操作非常麻烦，不能简单地将槽位置空，否则会中断探测序列。通常采用“懒删除”（标记为已删除）的方式。

了解一下常见的探测策略：

1 线性探测 (Linear Probing)：

2 平方探测 (Quadratic Probing)：

公式：new_index = (hash(x) + i²) % TableSize，i = 1, 2, 3, ... (或者 ±1², ±2², ±3²...)
优点：缓解了初级聚集。
缺点：可能产生次级聚集（Secondary Clustering），即具有相同哈希值的键采用同样的探测序列。并且不能保证一定能找到空槽位（即使表未满）。

3 双重散列 (Double Hashing)：

无论使用哪种方法，当哈希表变得过于拥挤时（即负载因子过高），性能都会下降。此时必须进行 重哈希（Rehash）。

操作：
1. 创建一个新的、更大的哈希表（通常是原大小的两倍左右，并且通常是一个质数）。
2. 遍历旧表中的每一个元素（包括链地址法中的整个链表或开放定址法中的每个槽位）。
3. 用新的哈希函数（因为表大小变了，hash(key) % new_size 的结果也变了）将每个元素重新计算哈希值，并插入到新表中。
4. 释放旧表的内存。
触发条件：通常当负载因子超过某个阈值时（例如，链地址法可能设为1.0，开放定址法可能设为0.75），插入操作会自动触发重哈希。在C++中，可以通过 load_factor() 和 max_load_factor() 成员函数来查询和设置这个阈值。

负载因子是衡量哈希表拥挤程度的指标。高负载因子意味着发生哈希冲突的概率显著增加，但性能下降的具体机制因解决冲突的方法而异：

对于链地址法（如 C++ std::unordered_map），高负载因子会导致每个桶的平均链表长度变长。这使得查找、插入操作需要遍历更多节点，平均时间复杂度从 O(1) 趋向 O(n)。
对于开放定址法（如线性探测），高负载因子意味着空闲槽位稀少，导致探测序列急剧变长。平均探测次数约与 1/(1-λ) 成正比，当负载因子接近 1 时，性能会灾难性地退化为 O(n)。

因此，所有哈希表实现都会通过重哈希机制来监控负载因子。一旦超过阈值，就自动扩容，创建一个更大的新表并重新插入所有数据，从而将负载因子降低到一个健康的水平，保证操作的平均高效性。