它们是如何工作的？他们的主要区别是什么？他们各自的取舍是什么？它们的类型是什么（如果有的话）？什么时候比另一个更喜欢（如果有的话）？
PS：我已经阅读过Anagrams - Hashing with chaining and probing in C以及当有单独的链接与列表链接时，为什么我们在哈希表中使用线性探测？，但似乎都没有在这两种方法之间形成对比。
问问题
14585 次
1 回答
18
哈希表中使用链接和开放寻址（基于线性探测的简单实现）来解决冲突。每当两个不同键的哈希函数指向相同的位置来存储值时，就会发生冲突。
为了存储这两个值，使用不同的键存储在同一位置，链接和开放寻址采用不同的方法：链接通过创建具有相同哈希值的链接列表来解决冲突；开放寻址尝试尝试找到不同的位置来存储具有相同哈希值的值。
用于解决开放寻址冲突的线性探测的一个有趣的替代方法是所谓的双散列。
出现的主要区别在于检索在不同条件下散列的值的速度。
让我们从链接作为冲突解决开始。此处注意，计算完 Lisa 的哈希函数后，需要从列表中获取第一个元素才能得到所需的值。因此，您访问指向列表头部的指针，然后是 value:2 操作。
另一方面，使用开放寻址，例如线性探测，当没有冲突时，您立即获得您正在寻找的值。也就是说，您只需要 1 次操作，速度更快。
但是，当您的 HashTable 开始变满并且您的负载系数很高时，由于更频繁地发生冲突，探测将需要您检查更多 Hashtable 位置，然后才能找到所需的实际值。在负载因子约为 0.8 时，由于多次碰撞，链接开始变得更加高效：您必须探测大量空单元格才能通过探测找到所需的实际值，而通过链接，您可以获得值列表具有相同的哈希键。
这只是一个简单的概述，因为实际数据、键的分布、使用的哈希函数以及冲突解决的精确实现都会影响您的实际速度。
于 2016-04-10T14:54:30.537 回答