哈希 - 用于处理冲突的开放寻址法

我们已经讨论过

• 哈希是一种众所周知的搜索方法。
• 当新键的哈希值与哈希表中已占用的桶匹配时，就会发生冲突。

开放寻址处理冲突

与链式寻址类似，开放寻址是一种处理冲突的技术。在开放寻址中，所有元素都只存储在哈希表中。因此，表的尺寸必须始终大于或等于键的总数（请注意，如果需要，我们可以通过复制旧数据来增加表尺寸）。此策略通常称为封闭哈希。这个过程的整个基础是探测。我们稍后将了解几种探测形式。

• 插入 (k)： 继续探测，直到找到一个空槽。将 k 放入找到的第一个空槽。
• 搜索 (k)： 继续探测，直到找到一个空槽或槽的键不再等于 k。
• 删除 (k)： 一个有趣的删除过程。如果我们只删除一个键，搜索可能会失败。因此，删除的键槽会特别标记为“已删除”。

尽管可以将项目插入到已删除的槽中，但搜索会在槽变空后继续。

注意-

• 插入时，“已删除”的桶与任何其他空桶的处理方式相同。
• 搜索时，当遇到“已删除”的桶时，搜索不会停止。
• 只有当找到所需的键或空桶时，搜索才会结束。

开放寻址

开放寻址是当

• 所有键都保存在哈希表内，这与链式寻址不同。
• 哈希表只包含键信息。

开放寻址的方法如下

• 线性探测
• 二次探测
• 双重散列

开放寻址使用以下技术

(a) 线性探测

在线性探测中，哈希表从哈希的初始点开始系统地检查。如果收到的位置已被占用，我们会寻找另一个位置。

重新哈希函数如下：表大小 = (n+1)% rehash(key)。从下面的示例可以看出，两个探测之间的通常间隔是 1。

设 S 为表的尺寸，设 hash(x) 为使用哈希算法计算的槽索引。

让我们使用“key mod 7”作为简单的哈希函数，使用以下键：50、700、76、85、92、73、101。

线性探测问题

• 主聚集： 主聚集是线性探测的问题之一。许多连续的项目形成簇，使得难以找到空槽或搜索元素。
• 次聚集： 次聚集不那么严重，只有当两个记录从同一位置开始时，它们才能共享一个冲突链（也称为探测序列）。

优点-

• 计算简单。

缺点-

• 聚集是线性探测的基本问题。
• 组由几个相邻的部分组成。
• 此后，搜索元素或空桶需要时间。

时间复杂度

在线性探测中搜索元素的最坏时间是 O（表尺寸）。这是因为

• 即使所有其他元素都不存在，也只有一个元素。
• 哈希表的“已删除”标记会强制进行全表搜索。

(b) 二次探测

如果您仔细观察，您会发现哈希值将导致探测之间的间隔增加。上述讨论的聚集问题可以通过二次探测技术解决。此方法也被称为中平方方法。我们使用此策略在第 i 次迭代中搜索第 i² 个槽。我们总是从哈希生成的地方开始。如果位置被占用，我们检查其他槽。

c) 双哈希

另一个哈希函数计算探测之间存在的间隙。双哈希能最优地减少聚集。此方法使用不同的哈希函数来生成探测序列的增量。我们使用另一个哈希算法 hash2(x) 在第 i 次旋转中搜索槽 i*hash2(x)。

前三者的比较

• 线性探测提供了最佳的缓存性能，但聚集是一个问题。线性探测的优点还在于计算简单。
• 在聚集和缓存性能方面，二次探测介于两者之间。
• 尽管双哈希没有聚集，但它在缓存中表现不佳。由于需要计算两个哈希函数，双哈希计算时间更长。

由于我们通过在计算机内存中从一个节点跳到下一个节点来遍历链表，因此链式寻址的缓存效率很低。正因为如此，CPU 无法缓存尚未访问的节点，这对我们不利。然而，由于使用开放寻址时数据不会分散，如果 CPU 注意到内存的特定区域经常被访问，它可以缓存信息以实现快速访问。

开放寻址的性能：与链式寻址类似，哈希的性能可以评估，假设每个键被哈希到表的任何槽的概率相等（简单均匀哈希）

负载因子 (α)-

负载因子 (α) 定义为-

开放寻址中的负载因子值始终介于 0 和 1 之间。这是因为

• 在开放寻址中，哈希表包含所有键。
• 因此，表的尺寸始终大于或至少等于其存储的键的数量。

结论-

• 线性探测实现了最佳缓存性能，但聚集是一个问题。
• 在聚集和缓存性能方面，二次探测介于两者之间。
• 尽管没有聚集，但双哈希的缓存性能较差。