一些哈希表方案,如cuckoo hashing或 dynamic perfect hashing ,依赖universal hash functions的存在以及通过从通用哈希函数系列中选择一个新的哈希函数来收集显示冲突的数据并解决这些冲突的能力。
前段时间,我试图在 Java 中实现一个由 cuckoo 哈希支持的哈希表,但遇到了麻烦,因为虽然所有 Java 对象都有一个 hashCode
函数,但 hashCode
返回对于每个对象都是固定的(当然,除非对象发生变化)。这意味着如果用户不提供通用散列函数的外部系列,就不可能构建依赖于通用散列的散列表。
最初我认为我可以通过将通用哈希函数直接应用于对象的 hashCode
来解决此问题,但这不起作用,因为如果两个对象具有相同的 hashCode
,然后任何确定性函数应用于这些哈希码,即使是随机选择的哈希函数,也会产生相同的值,从而导致冲突。
这似乎不利于 Java 的设计。这意味着 HashMap
和其他散列容器完全禁止使用基于通用散列的表,即使语言设计者可能认为这样的表在语言设计中是合适的。这也让第三方库设计者更难构建此类哈希表。
我的问题是:Java 选择设计 hashCode
是否有理由不考虑使用多个散列函数散列对象的可能性? 我知道许多好的散列方案像链式散列或二次探测不需要它,但似乎该决定使得在 Java 对象上使用某些类的算法变得困难。
最佳答案
简单。 Java 允许类设计者提供他们自己的 hashCode
,正如您所提到的,这对于“普通”哈希表来说已经足够好了,并且可以是 hard enough理解。
此外,在设计 Java Collections API 时,在标准库中使用通用哈希表已经足够大胆了。 C从未拥有过它们。 C++ 将它们作为 hash_set
和 hash_map
在 STL 中,但这些并没有成为标准。直到现在,在 C++0x 中,才再次考虑将哈希表标准化。
关于java - 为什么 Java 的 hashCode 不支持通用散列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5203326/