data-structures - 哈希表中的链接和探测有什么区别？

Question

它们是如何工作的？它们的主要区别是什么？他们各自的权衡是什么？它们的类型是什么(如果有的话)？什么时候一个人比另一个人更喜欢(如果有的话)？

PS:我已经过了Anagrams - Hashing with chaining and probing in C和 Why do we use linear probing in Hash tables when there is separate chaining linked with lists? ，但这两种方法似乎都没有形成对比。

Answer 1

Hashtables 中使用链式和开放式寻址(一种基于线性探测的简单实现)来解决冲突。每当两个不同键的哈希函数指向同一位置来存储值时，就会发生冲突。

为了使用不同的键存储在同一位置的两个值，链接和开放寻址采用不同的方法:链接通过创建具有相同哈希值的链表来解决冲突；开放寻址尝试尝试找到不同的位置来存储具有相同哈希值的值。

用于解决开放寻址冲突的线性探测的一个有趣替代方法是所谓的双散列。

出现的主要区别在于在不同条件下检索散列值的速度。

让我们从 chaining 开始作为冲突解决。这里注意，在为 Lisa 计算哈希函数后，需要从列表中获取第一个元素才能得到所需的值。因此，您访问指向列表头部的指针，然后访问值:2 次操作。

另一方面，使用开放寻址，例如 linear-probing ，当没有碰撞时，您立即获得您正在寻求的值。也就是说，您只需要 1 次操作，速度更快。

然而，当你的 HashTable 开始变满时，你有一个高 load factor ，由于冲突发生得更频繁，探测将要求您在找到所需的实际值之前检查更多的 Hashtable 位置。在大约 0.8 的负载因子时，由于多次碰撞，链接开始变得更有效率:您必须探测大量空单元格才能通过探测找到您想要的实际值，而通过链接，您有一个值列表具有相同的哈希键。

这只是一个快速概述，因为实际数据、 key 的分布、使用的哈希函数以及冲突解决的精确实现都会影响您的实际速度。