一些散列表方案,例如cuckoo hashing或dynamic perfect hashing,依赖于universal hash functions的存在以及获取表现出冲突的数据集合并通过从通用散列函数族中选取新的散列函数来解决这些冲突的能力。
不久前,我试图用Java实现一个由布谷鸟散列支持的哈希表,结果遇到了麻烦,因为虽然所有的Java对象都有一个hashCode
函数,但hashCode
返回的值对于每个对象都是固定的(当然,除非对象发生了变化)。这意味着如果用户不提供通用散列函数的外部系列,就不可能构建依赖于通用散列的散列表。
最初,我认为我可以通过将通用散列函数直接应用于对象的hashCode
来解决这个问题,但这不起作用,因为如果两个对象具有相同的hashCode
,那么应用于这些散列代码的任何确定性函数,即使是随机选择的散列函数,都会产生相同的值,从而导致冲突。
看起来这对Java的设计是不利的。这意味着完全禁止HashMap
和其他散列容器使用基于通用散列的表,即使语言设计者可能认为这样的表在语言设计中是合适的。这也使得第三方库设计者更难构建这种哈希表。
我的问题是:选择设计 hashCode
而没有考虑使用多个散列函数对对象进行散列的可能性有什么原因吗?我理解许多好的散列方案,如链式散列或二次探测并不需要它,但似乎这个决定使得在Java对象上使用某些类的算法变得困难。
https://stackoverflow.com/questions/5203326
复制相似问题