th3*_*aly 3 hashtable probing data-structures
他们是如何工作的？他们的主要区别是什么？他们各自的权衡取舍是什么？他们的类型是什么(如果有的话)？什么时候比另一个更好(如果有的话)？
PS:我已经浏览过Anagrams - 使用链接进行散列并使用C语言进行探测,为什么在与列表链接的单独链接时,我们在哈希表中使用线性探测？,但似乎都没有在两种方法之间形成对比.
在Hashtables中使用链接和开放寻址(其简单实现基于线性探测)来解决冲突.只要两个不同键的散列函数指向同一位置来存储值,就会发生冲突.
为了存储两个值,使用不同的密钥存储在同一位置,链接和开放寻址采用不同的方法:链接通过创建具有相同散列的值的链接列表来解决冲突; open-addressing尝试尝试查找不同的位置以使用相同的哈希值存储值.
用于开放寻址冲突解决的线性探测的有趣替代方案是所谓的双重散列.
产生的主要差异在于检索在不同条件下散列的值的速度.
让我们从链接开始作为碰撞解决方案.请注意,在计算Lisa的哈希函数之后,您需要从列表中获取第一个元素以获取所需的值.因此,您可以访问指向列表头部的指针,然后访问值:2操作.
另一方面,通过开放寻址,例如线性探测,当没有碰撞时,您立即获得您正在寻找的值.也就是说,您只需要1次操作,这样会更快.
但是,当您的HashTable开始变满,并且您的负载因子很高时,由于更频繁地发生冲突,探测将要求您在找到所需的实际值之前检查更多Hashtable位置.在大约0.8的负载系数下,由于多次冲突,链接开始变得更有效:你必须探测很多空单元以便通过探测找到你想要的实际值,而使用链接你有一个值列表具有相同的哈希键.
这只是一个快速概述,因为实际数据,键的分布,使用的散列函数以及碰撞分辨率的精确实现将对您的实际速度产生影响.
