一些哈希表方案,例如cuckoo hashing或dynamic perfect hashing,依赖于universal hash functions的存在,并且能够通过从通用哈希函数族中选择新的哈希函数来获取表现出冲突的数据集合并解决这些冲突 .
前一段时间我试图在由cuckoo散列支持的Java中实现哈希表并遇到麻烦,因为虽然所有Java对象都有 hashCode
函数,但 hashCode
返回的值对于每个对象都是固定的(当然,除非对象发生变化) ) . 这意味着如果没有用户提供外部通用散列函数系列,则无法构建依赖于通用散列的散列表 .
最初我认为我可以通过直接对对象的 hashCode
应用通用哈希函数来解决这个问题,但这不起作用,因为如果两个对象具有相同的 hashCode
,那么您应用于这些哈希码的任何确定性函数,甚至是随机选择的散列函数,将导致相同的值,从而导致冲突 .
看起来这对Java的设计是不利的 . 这意味着完全禁止 HashMap
和其他哈希容器使用基于通用哈希的表,即使语言设计者可能认为这样的表适合语言设计 . 它还使第三方库设计者更难以构建此类哈希表 .
我的问题是: is there a reason that Java opted to design hashCode without considering the possibility of hashing objects with multiple hash functions? 我理解许多好的散列方案,如链式散列或二次探测都不需要它,但似乎这个决定使得在Java对象上使用某些类算法变得困难 .
2 回答
我认为正常的
hashCode
方法是在没有"malicious inputs"案例的情况下创建的 . 此外,正如larsmann所写,它的 Contract 比通用哈希函数更容易理解和实现 .这里有一个关于做什么的想法:
使用依赖于外部哈希函数的 Map 实现(比如我在几个小时前提到的HashableEquivalenceRelation)
然后使用这种实现的通用族(或允许更改参数以切换到该族的另一个成员的实现) .
Simplicity . Java允许类设计者提供他们自己的
hashCode
,正如你所提到的那样"ordinary"哈希表就足够了,并且可以hard enough来理解 .此外,在设计Java Collections API时,标准库中的通用哈希表已经足够大胆了 . C从来没有过它们 . C在STL中将它们作为
hash_set
和hash_map
,但那些没有成为标准 . 只是现在,在C 0x中,哈希表再次被考虑用于标准化 .