一些散列表方案,例如cuckoo hashing或dynamic perfect hashing,依赖于universal hash functions的存在以及获取表现出冲突的数据集合并通过从通用散列函数族中选取新的散列函数来解决这些冲突的能力。
不久前,我试图用Java实现一个由布谷鸟散列支持的哈希表,结果遇到了麻烦,因为虽然所有的Java对象都有一个hashCode
函数,但hashCode
返回的值对于每个对象都是固定的(当然,除非对象发生了变化)。这意味着如果用户不提供通用散列函数的外部系列,就不可能构建依赖于通用散列的散列表。
最初,我认为我可以通过将通用散列函数直接应用于对象的hashCode
来解决这个问题,但这不起作用,因为如果两个对象具有相同的hashCode
,那么应用于这些散列代码的任何确定性函数,即使是随机选择的散列函数,都会产生相同的值,从而导致冲突。
看起来这对Java的设计是不利的。这意味着完全禁止HashMap
和其他散列容器使用基于通用散列的表,即使语言设计者可能认为这样的表在语言设计中是合适的。这也使得第三方库设计者更难构建这种哈希表。
我的问题是:选择设计 hashCode
而没有考虑使用多个散列函数对对象进行散列的可能性有什么原因吗?我理解许多好的散列方案,如链式散列或二次探测并不需要它,但似乎这个决定使得在Java对象上使用某些类的算法变得困难。
发布于 2011-03-05 19:46:31
Simplicity。Java允许类设计者提供他们自己的hashCode
,正如您所提到的,这对于“普通的”哈希表来说已经足够好了,并且可以被hard enough理解。
此外,在设计Java Collections API时,在标准库中使用泛型哈希表已经够大胆的了。C从未拥有过它们。C++在标准语言中将它们作为hash_set
和hash_map
,但它们并没有成为标准。直到现在,在C++0x中,哈希表才再次被考虑标准化。
发布于 2011-03-06 06:30:18
我认为正常的hashCode
方法在创建时并没有考虑到“恶意输入”的情况。此外,正如larsmann所写的,它的契约比通用散列函数更容易理解和实现。
这里有一个关于如何做的想法:
https://stackoverflow.com/questions/5203326
复制相似问题