一些哈希表方案,例如布谷鸟哈希 http://en.wikipedia.org/wiki/Cuckoo_hashing or 动态完美哈希 http://en.wikipedia.org/wiki/Dynamic_perfect_hashing,依赖于存在通用哈希函数 http://en.wikipedia.org/wiki/Universal_hash_function以及通过从通用哈希函数系列中选择新的哈希函数来获取存在冲突的数据集合并解决这些冲突的能力。
不久前,我试图用 Java 实现一个由布谷鸟哈希支持的哈希表,但遇到了麻烦,因为虽然所有 Java 对象都有一个hashCode
函数,值hashCode
每个对象的返回值都是固定的(当然,除非对象发生变化)。这意味着,如果用户不提供外部通用哈希函数系列,就不可能构建依赖于通用哈希的哈希表。
最初我认为我可以通过将通用哈希函数应用于对象的来解决这个问题hashCode
直接,但这不起作用,因为如果两个对象具有相同的hashCode
, then any您应用于这些哈希码的确定性函数,即使是随机选择的哈希函数,也会产生相同的值,从而导致冲突。
看起来这对 Java 的设计是有害的。代表着HashMap
和其他哈希容器完全禁止使用基于通用哈希的表,即使语言设计者可能认为此类表适合语言设计。这也使得第三方库设计者更难构建这种类型的哈希表。
我的问题是:Java 选择这样设计有什么原因吗?hashCode
不考虑使用多个哈希函数对对象进行哈希处理的可能性?我知道许多好的哈希方案(例如链式哈希或二次探测)不需要它,但似乎这个决定使得在 Java 对象上使用某些类算法变得困难。
简单。 Java 允许类设计者提供自己的hashCode
,正如您提到的,这对于“普通”哈希表来说已经足够好了,并且可以是有够难 https://stackoverflow.com/questions/5110376/hashset-contains-problem-with-custom-objects/5110405#5110405去理解。
此外,当设计 Java Collections API 时,在标准库中拥有通用哈希表就已经是一个足够大胆的举动了。 C 从来没有拥有过它们。 C++ 在 STL 中将它们作为hash_set
and hash_map
,但那些并没有纳入标准。直到现在,在 C++0x 中,哈希表才再次被考虑标准化。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)