c++ - C++ 散列：开放寻址和链接

Question

对于链接：

有人可以向我解释这个概念并提供一个理论示例和一个简单的代码吗？

我得到了“每个表位置都指向散列到该位置的项目的链表（链）”的想法，但我似乎无法说明实际发生了什么。

假设我们有 h(x)（散列函数）= x/10 mod 5。现在散列 12540、51288、90100、41233、54991、45329、14236，会是什么样子？

对于开放寻址（线性探测、二次探测和每个 R 位置的探测），有人也可以向我解释一下吗？我试着用谷歌搜索，但我似乎更困惑了。

Answer 1

链接可能是最明显的散列形式。哈希表实际上是一个最初为空的链表数组。通过在项目的计算表索引处将新节点添加到链表来插入项目。如果发生冲突，则将新节点链接到链表的前一个尾节点。（实际上，实现可以对列表中的项目进行排序，但让我们保持简单）。这种模式的一个优点是哈希表永远不会“满”，一个缺点是你经常在内存中跳转，你的 CPU 缓存会讨厌你。

开放寻址试图利用散列表可能是稀疏填充的事实（条目之间的大间隙）。哈希表是一个项目数组。如果发生冲突，算法不会将项目添加到该位置的当前项目的末尾，而是在哈希表中搜索下一个空白空间。但是，这意味着您不能仅依靠哈希码来查看项目是否存在，如果哈希码匹配，您还必须比较内容。“探测”是算法在尝试找到下一个空闲槽时遵循的策略。一个问题是表可能会变满，即不再有空槽。在这种情况下，需要调整表的大小并更改散列函数以考虑新的大小。表中的所有现有项目也必须重新插入，因为一旦更改散列函数，它们的散列码将不再具有相同的值。可能还要等一下。

这是一个哈希表的Java 动画。

Answer 2

因为你做了 mod 5，你的桌子会有 5 个位置

位置 0：90100

因为结果90100/10 mod 5是 0

出于同样的原因，您有：

位置 1：无

位置2：45329

位置3：51288->41233->14236

位置 4：12540->54991

你可以在维基百科上查看更多信息

Answer 3

在开放寻址中，我们必须使用任何技术将元素存储在表中（负载因子小于等于一）。

但是在链接哈希表的情况下只存储 Linklist 的头指针，因此负载因子可以大于一。