某些哈希表方案(例如布谷鸟哈希或动态完美哈希)依赖于通用哈希函数的存在以及能够收集表现出冲突的数据并通过从通用哈希函数系列中选择一个新的哈希函数来解决这些冲突的能力。 。
不久前,我试图在以杜鹃哈希为后盾的Java中实现哈希表,并遇到了麻烦,因为尽管所有Java对象都有一个hashCode函数,但hashCode返回的值对于每个对象都是固定的(当然,除非对象更改)。这意味着如果没有用户提供外部家族的通用哈希函数,就不可能构建依赖于通用哈希的哈希表。
hashCode
最初,我以为可以通过直接将通用哈希函数应用于对象的hashCodes 来解决此问题,但这不起作用,因为如果两个对象具有相同的hashCode,那么您将应用于这些哈希代码的 任何 确定性函数,甚至是随机的- 选择的哈希函数,将导致相同的值,从而导致冲突。
看来这将不利于Java的设计。这意味着HashMap完全禁止其他哈希容器使用基于通用哈希的表,即使语言设计人员可能认为这样的表在语言设计中是适当的。这也使第三方库设计人员更难建立这种哈希表。
HashMap
我的问题是: Java是否选择了hashCode不考虑使用多个哈希函数对对象进行哈希处理的可能性的原因? 我知道许多好的哈希方案(例如链式哈希或二次探查)都不需要它,但是似乎该决定使在Java对象上使用某些类的算法变得困难。
简单性 。Java允许类设计者提供自己的hashCode,正如您所提到的,对于“普通”哈希表已经足够了,并且很难理解。
此外,在设计Java Collections API时,在标准库中具有通用哈希表已经足够大胆了。C从来没有他们。C 让他们在STL为hash_set和hash_map,但这些并没有使之成为标准。只是现在,在C 0x中,再次考虑将哈希表标准化。
hash_set
hash_map