我在学位类(class)中听说,如果新的 Key 条目与另一个条目发生冲突,HashTable
会将一个新条目放入“下一个可用”存储桶中。
如果在使用冲突键调用返回时发生这种冲突,HashTable
如何仍然返回正确的值?
我假设 Keys
是 String
类型,而 hashCode()
返回由 Java 生成的默认值。
如果我实现自己的散列函数并将其用作查找表的一部分(即 HashMap
或 Dictionary
),有哪些策略可用于处理冲突?
我什至见过与素数有关的笔记!谷歌搜索的信息不太清楚。
最佳答案
哈希表以两种方式之一处理冲突。
选项 1: 通过让每个存储桶包含一个元素的链接列表,这些元素会散列到该存储桶。这就是为什么一个糟糕的哈希函数会使哈希表中的查找变得非常缓慢的原因。
选项 2: 如果哈希表条目都已满,则哈希表可以增加其拥有的桶数,然后重新分配表中的所有元素。哈希函数返回一个整数,哈希表必须获取哈希函数的结果,并根据表的大小对其进行修改,这样它就可以确保它会到达存储桶。因此,通过增加大小,它将重新散列并运行模计算,如果幸运的话,可能会将对象发送到不同的存储桶。
Java 在其哈希表实现中同时使用选项 1 和 2。
关于java - HashTables 如何处理冲突?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4980757/