HashTables如何处理碰撞？

Question

我在学位课程中听说,HashTable如果新的Key条目与另一个条目相撞,它会在"下一个可用"桶中放入一个新条目.

HashTable如果在使用碰撞密钥调用一个碰撞时发生这种碰撞,仍将如何返回正确的值？

我假设Keys是String类型,hashCode()返回默认由Java生成.

如果我实现自己的散列函数并将其用作查找表(即a HashMap或Dictionary)的一部分,那么处理冲突的策略是什么？

我甚至看过有关素数的注释!Google搜索中的信息不太明确.

Answer 1

哈希表以两种方式之一处理冲突.

选项1:使每个存储桶包含一个链接的元素列表,这些元素被散列到该存储桶.这就是错误的哈希函数可以使哈希表中的查找非常慢的原因.

选项2:如果哈希表条目全部填满,则哈希表可以增加它拥有的桶的数量,然后重新分配表中的所有元素.哈希函数返回一个整数,哈希表必须获取哈希函数的结果,并根据表的大小对其进行修改,这样就可以确定它将进入存储区.因此,通过增加大小,它将重新运行并运行模数计算,如果幸运的话,可以将对象发送到不同的桶.

Java在其哈希表实现中使用选项1和2.

Answer 2

当你谈到"如果新的Key条目与另一个条目发生碰撞时,Hash Table将在'下一个可用'桶中放置一个新条目.",你所说的是哈希表的冲突解决的开放寻址策略.

哈希表有几种解决冲突的策略.

第一种大方法要求将键(或指向它们的指针)与相关值一起存储在表中,其中还包括:

• 单独链接

• 开放式寻址

• 合并散列
• 杜鹃哈希
• 罗宾汉哈希
• 2选择哈希
• 跳房子哈希

处理碰撞的另一个重要方法是动态调整大小,它还有几种方法:

• 通过复制所有条目来调整大小
• 增量调整大小
• 单调键

编辑:以上是从wiki_hash_table借来的,你应该去看看获取更多信息.

Answer 3

有多种技术可用于处理碰撞.我会解释一些

链接: 在链接中,我们使用数组索引来存储值.如果第二个值的哈希码也指向同一个索引,那么我们用链表替换该索引值,指向该索引的所有值都存储在链表中,实际数组索引指向链表的头部.但是,如果只有一个哈希码指向数组的索引,那么该值将直接存储在该索引中.检索值时应用相同的逻辑.这在Java HashMap/Hashtable中使用以避免冲突.

线性探测:当表中的索引多于要存储的值时,使用此技术.线性探测技术适用于保持递增的概念,直到找到空槽.伪代码如下所示:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

双散列技术:在这种技术中,我们使用两个散列函数h1(k)和h2(k).如果h1(k)处的时隙被占用,则第二个散列函数h2(k)用于递增索引.伪代码如下所示:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

线性探测和双重散列技术是开放寻址技术的一部分,只有在可用的时隙超过要添加的项目数时才能使用它.它比链接占用更少的内存,因为这里没有使用额外的结构,但由于大量的移动发生直到我们找到一个空槽,它的速度很慢.同样在开放寻址技术中,当一个项目从一个插槽中移除时,我们放置一个墓碑,表明该项目已从此处移除,这就是为什么它是空的.

有关更多信息,请访问此站点.

Answer 4

我强烈建议你阅读最近出现在HackerNews上的博客文章: HashMap如何在Java中运行

简而言之,答案是

如果两个不同的HashMap密钥对象具有相同的哈希码,会发生什么？

它们将存储在同一个存储桶中,但不存储链接列表的下一个节点.密钥equals()方法将用于在HashMap中识别正确的键值对.

Answer 5

我在学位课程中听说,如果新的Key条目与另一个条目冲突,HashTable会在"下一个可用"桶中放入一个新条目.

实际上并非如此,至少对于Oracle JDK(它是一个实现细节,可能因API的不同实现而异).相反,每个存储桶包含一个链接的条目列表.

那么如果在使用碰撞键调用一个碰撞时发生这种碰撞,HashTable如何仍然返回正确的值？

它使用它equals()来查找实际匹配的条目.

如果我实现自己的散列函数并将其用作查找表(即HashMap或Dictionary)的一部分,那么处理冲突的策略是什么？

存在各种具有不同优点和缺点的碰撞处理策略. Wikipedia在哈希表上的条目提供了很好的概述.

Answer 6

自Java 8以来的更新: Java 8使用自平衡树进行冲突处理,从而将最坏情况从O(n)改为O(log n)以进行查找.在Java 8中引入了自平衡树的使用,作为链接的改进(直到java 7使用),它使用链表,并且具有最坏的O(n)用于查找(因为它需要遍历)列表)

要回答问题的第二部分,插入是通过将给定元素映射到散列图的基础数组中的给定索引来完成的,但是,当发生冲突时,仍必须保留所有元素(存储在辅助数据结构中) ,而不只是在底层数组中替换).这通常通过使每个阵列组件(槽)成为辅助数据结构(也称为桶)来完成,并且该元素被添加到驻留在给定阵列索引上的桶中(如果桶中的密钥尚未存在,则它被替换的情况).

在查找期间,将密钥散列到其对应的数组索引,并对与给定存储桶中的(精确)密钥匹配的元素执行搜索.由于存储桶不需要处理冲突(直接比较密钥),因此解决了冲突问题,但这样做的代价是必须在辅助数据结构上执行插入和查找.关键点在于,在散列映射中,密钥和值都被存储,因此即使散列发生冲突,也会直接比较密钥的相等性(在桶中),因此可以在桶中唯一地标识密钥.

碰撞处理带来了O(1)插入和查找的最坏情况性能,在没有碰撞处理的情况下,O(n)用于链接(链表用作辅助数据结构)和O(log n)为自平衡的树.

参考文献:

在高冲突的情况下,Java 8对HashMap对象进行了以下改进/更改.

• Java 7中添加的备用String散列函数已被删除.

• 包含大量碰撞键的存储桶将在达到特定阈值后将其条目存储在平衡树中而不是链接列表中.

在最坏的情况下,上述更改可确保O(log(n))的性能(https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)