什么是开放寻址法？哈希表的实现-js教程-PHP中文网

开放寻址法通过探测策略在哈希表内部解决冲突，不依赖链表等外部结构，核心在于使用线性探测、二次探测或双重散列等方法寻找空位；线性探测简单且缓存友好但易产生主聚集，二次探测缓解主聚集但可能导致次聚集且探测不完整，双重散列分布最均匀、性能最优但实现复杂；与链表法相比，开放寻址法节省空间、缓存命中率高，但删除操作需标记为逻辑删除且对负载因子敏感，适合数据量稳定、内存敏感、查询频繁的场景，而链表法适合动态数据、频繁增删、负载变化大的场景；其性能瓶颈主要在于高负载因子导致探测链变长和聚集效应影响效率，因此需通过扩容（如负载因子超阈值时重建更大表并重新哈希）来维持性能，缩容虽可行但因开销大和震荡风险较少使用，合理设置初始容量和负载因子是保障开放寻址法高效运行的关键。

什么是开放寻址法？哈希表的实现

开放寻址法，说白了，就是哈希表处理冲突的一种策略。当两个不同的键通过哈希函数计算出同一个存储位置时，我们不额外引入链表或数据结构，而是尝试在哈希表的其他位置找到一个空闲的“家”来存放新的数据。它把所有元素都直接存储在哈希表（一个数组）本身里，不依赖额外的指针结构，挺有意思的。

解决方案

开放寻址法的核心思想在于“探测”：如果哈希函数计算出的位置已经被占用了，那就按照某种预设的规则，一步步地去寻找下一个可用的空位。这个过程就像在停车场找车位，一个位置满了，就看看旁边是不是有空的。

具体来说，当我们要插入一个键值对

(key, value)

登录后复制

时，首先计算它的哈希值

h(key)

登录后复制

。如果

table[h(key)]

登录后复制

是空的，那直接放进去。如果被占用了，我们就开始探测序列：

h(key), h(key)+step1, h(key)+step2, ...

登录后复制

直到找到一个空位。查找和删除操作也遵循同样的探测序列。

这里面最关键的就是这个“探测步长”怎么定，也就是

step1, step2

登录后复制

这些值怎么来。常用的探测方法有三种：

线性探测 (Linear Probing): 这是最直观的，步长固定为1。如果
```
h(key)
```
登录后复制
登录后复制
被占，就尝试
```
h(key)+1
```
登录后复制
，再被占就尝试
```
h(key)+2
```
登录后复制
，以此类推，直到找到空位或遍历完整个表（通常是模运算回到开头）。它的优点是实现简单，而且因为访问的内存地址是连续的，对CPU缓存很友好。但缺点也很明显，容易产生“主聚集”现象，就是大量数据扎堆在一起，导致后续的查找和插入效率急剧下降。
二次探测 (Quadratic Probing): 为了缓解线性探测的聚集问题，二次探测的步长是二次的，比如
```
h(key)+1^2, h(key)+2^2, h(key)+3^2...
```
登录后复制
。这能有效避免主聚集，但可能会引发“次聚集”，即哈希到同一个初始位置的键，会沿着相同的探测序列移动。而且，如果表的大小不是素数，或者负载因子过高，可能无法探测到所有位置，甚至找不到空位。
双重散列 (Double Hashing): 这是最复杂的，但也通常是效果最好的。它引入了第二个哈希函数
```
h2(key)
```
登录后复制
登录后复制
来决定探测步长。探测序列变成
```
h(key), h(key)+h2(key), h(key)+2*h2(key), h(key)+3*h2(key)...
```
登录后复制
。这样，每个键都有自己独特的探测步长，大大减少了聚集现象，使得数据分布更均匀。当然，你需要设计两个好的哈希函数，并且确保
```
h2(key)
```
登录后复制
登录后复制
永远不会是0。

开放寻址法与链表法有何不同，各自适用场景是什么？

开放寻址和链表法（或称拉链法）是哈希表处理冲突的两种基本思路，它们就像硬币的两面，各有取舍，没有绝对的优劣，只有更适合的场景。

在我看来，开放寻址法最直观的特点就是“节省空间”，因为它不需要为每个冲突的元素额外分配节点和存储指针。所有数据都规规矩矩地躺在一个数组里，这带来了显著的缓存优势。CPU在访问连续内存区域时效率更高，因为数据局部性好，更容易命中缓存。想象一下，你查一个东西，所有相关线索都在同一页纸上，这比线索分散在好几本书里要快得多。但是，它也有个明显的痛点：删除操作很麻烦。你不能简单地把一个元素删掉就完事儿，因为这个被删除的位置可能是一个探测序列上的关键节点，如果直接清空，后续依赖它才能找到的元素就“失联”了。所以，通常我们会做“逻辑删除”，也就是把这个位置标记为“已删除”，而不是真正清空。这会引入一些“幽灵”数据，查找时还得跳过它们，效率会受影响。而且，开放寻址法对负载因子（已存储元素数量 / 哈希表总容量）非常敏感，一旦负载因子过高（比如超过0.7或0.8），性能会急剧下降，因为找到空位的概率越来越小，探测链会变得非常长。

而链表法呢，它在每个哈希桶里挂一个链表（或者其他动态数据结构，比如红黑树，Java 8里的HashMap就是这样），冲突的元素就都挂在这个链表上。它的优点是实现简单，删除操作直接在链表里移除节点就行，不影响其他元素的查找。而且它对负载因子不那么敏感，即使负载因子超过1，也能正常工作（只是每个链表会变长）。缺点是每个链表节点都需要额外的指针空间，这会增加内存开销。同时，由于数据可能散落在内存的各个角落，缓存命中率会相对低一些。

所以，它们的适用场景也就呼之欲出了：

开放寻址法： 适合那些数据量相对固定、对内存空间和缓存性能要求较高、且删除操作不那么频繁的场景。比如，你有一个固定大小的字典，或者你特别在意每次查找的响应速度。当你知道你的数据不会频繁增删，并且能预估好数据量时，开放寻址法能提供非常高效的查询。
链表法： 更适合数据量动态变化、增删操作频繁、对内存开销不太敏感的场景。比如，我们平时用的各种HashMap、HashTable，它们在底层大多采用链表法（或其变体），因为它更通用，更能适应各种复杂的业务需求，尤其是负载因子变化大的情况。

开放寻址法常见的冲突解决策略有哪些，各自优缺点如何？

前面已经提到了一些，但我们再深入一点，聊聊这些策略背后的一些“味道”和它们各自的“脾气”。

线性探测 (Linear Probing):
- 优点： 简单粗暴，容易实现，而且因为总是在相邻的内存位置探测，CPU的缓存利用率极高，这在现代计算机体系结构中是个不小的优势。如果你插入的数据量不大，或者哈希函数特别优秀，冲突很少，那线性探测的表现会非常棒。
- 缺点： 最大的问题就是“主聚集”（Primary Clustering）。想象一下，停车场里一个车位满了，大家就都往旁边挪一个，结果就是一整排车位都满了，形成一个长长的“车龙”。这导致后续的插入和查找都需要遍历很长的序列，性能直线下降。而且，一旦某个位置被删除（即使是逻辑删除），这个“空洞”也会影响后续的探测效率。
二次探测 (Quadratic Probing):
- 优点： 它的设计初衷就是为了解决线性探测的主聚集问题。通过平方步长跳跃，它能更“分散”地寻找空位，避免了长长的连续占用区。这就像你找车位，发现第一个满了，不是往旁边挪一格，而是跳过几格再看，这样能有效避开“车龙”。
- 缺点： 虽然解决了主聚集，但它引入了“次聚集”（Secondary Clustering）。如果多个键的初始哈希值相同，它们会沿着完全相同的探测序列进行探测。这就像几辆车都想停在同一个区域，虽然它们不会排成一排，但它们会按照相同的“跳跃路线”去寻找，最终还是会互相影响。此外，二次探测还有个潜在问题：如果哈希表的大小不是素数，或者负载因子过高，它可能无法探测到哈希表中的所有位置，甚至可能找不到空位，即使表里还有空闲位置。
双重散列 (Double Hashing):
- 优点： 这是开放寻址法中公认的“高性能选手”。它通过引入第二个哈希函数来动态决定每次探测的步长，使得每个键都有一个独一无二的探测序列。这就像每个司机都有一套自己找车位的“秘籍”，大大减少了聚集现象，使得数据分布最均匀。它的性能表现最接近理想的均匀分布。
- 缺点： 复杂性最高，你需要设计两个好的哈希函数，并且要确保第二个哈希函数计算出的步长永远不会是0，并且要和表的大小互质，否则可能无法探测到所有位置。这在实际工程中需要更多的思考和测试。

选择哪种策略，往往是性能和实现复杂度的权衡。对于大多数通用场景，如果哈希表负载因子控制得好，线性探测可能因为其缓存优势而表现不错；但如果需要更高的性能稳定性和更强的抗聚集能力，双重散列无疑是更好的选择。

开放寻址法的性能瓶颈在哪里？如何有效管理哈希表的扩容与缩容？

开放寻址法在实际应用中，性能瓶颈主要集中在两个方面：负载因子和聚集效应。

首先，负载因子是开放寻址法的“命门”。负载因子是已存储元素数量与哈希表总容量的比值。一旦这个值过高，比如超过0.7或0.8，哈希表就会变得非常“拥挤”。每一次插入、查找或删除操作，都需要经历更长的探测序列才能找到目标位置或空位。这就像在一个几乎停满的停车场找车位，你得绕好几圈才能找到一个，时间成本急剧上升。极端情况下，如果负载因子接近1，性能会急剧退化，甚至可能陷入无限循环（如果找不到空位）。

其次，聚集效应是性能的另一个大敌。无论是线性探测的主聚集，还是二次探测的次聚集，它们都会导致部分区域的数据密度远高于平均水平，从而使得这些区域的访问效率非常低。即使哈希表整体负载因子不高，局部聚集也会形成性能热点。双重散列虽然能很大程度上缓解这个问题，但它也无法完全消除聚集。

那么，面对这些瓶颈，我们如何有效管理哈希表的扩容（Resizing）与缩容呢？

扩容是解决高负载因子问题的核心手段。当哈希表的负载因子达到预设的阈值（比如0.75）时，我们就需要进行扩容。这个过程通常是这样的：

创建新表： 分配一个更大的新哈希表，通常是原表大小的两倍（或者选择一个更大的素数）。
重新哈希（Rehashing）： 这是最关键也是最耗时的一步。你需要遍历旧表中的所有元素，并使用新的哈希表大小，重新计算它们的哈希值，然后将它们插入到新表中。注意，这里不是简单地复制，因为哈希函数通常依赖于表的大小，所以每个元素的哈希位置都会发生变化。
替换旧表： 新表构建完成后，用它替换掉旧表，并释放旧表的内存。

这个过程听起来简单，但实际上是一个O(N)的操作，其中N是旧表中的元素数量。这意味着在扩容期间，哈希表的服务会暂时中断或性能急剧下降。在对实时性要求高的系统中，这可能是一个需要特别考虑的“卡顿点”。所以，选择合适的扩容时机和扩容策略至关重要。一些高级实现会采用“渐进式扩容”，即每次只迁移一小部分数据，将扩容的开销分摊到多次操作中，避免一次性的大开销。

至于缩容，它的原理和扩容类似，也是创建更小的表并重新哈希。但在实际应用中，缩容相对不那么常见。原因有几点：