为什么Java的hashCode不支持通用哈希?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (16)

一些哈希表方案,如杜鹃散列dynamic perfect hashing,依靠的存在通用散列函数,并采取展示的碰撞数据的收集和来自家庭的通用散列函数选择一个新的Hash函数解决这些冲突的能力。

前一段时间,我试图在Java中实现哈希表,并以杜鹃散列为后盾,并且遇到了麻烦,因为尽管所有Java对象都有一个hashCode函数,但是hashCode返回的值对每个对象都是固定的(当然,除非对象发生更改)。这意味着如果用户不提供外部通用散列函数系列,就不可能构建依赖于通用散列函数的散列表。

起初,我认为我可以通过将通用散列函数hashCode直接应用于对象的s 来解决这个问题,但这不起作用,因为如果两个对象具有相同的属性hashCode,那么您将应用于这些散列代码的任何确定性函数,选择的散列函数将导致相同的值,从而导致冲突。

看起来这对Java的设计是不利的。这意味着HashMap即使语言设计者可能认为这样的表格在语言设计中是适当的,但其他哈希容器也完全禁止使用基于通用哈希的表格。这也使得第三方库设计者更难以构建这种哈希表。

我的问题是:Java选择设计时hashCode没有考虑使用多个散列函数散列对象的可能性吗? 我明白,像链式哈希或二次探测这样的许多好的哈希方案并不需要它,但似乎决定使得很难在Java对象上使用某些类别的算法。

提问于
用户回答回答于

Simplicity。Java允许类设计者提供他们自己的hashCode,正如你所提到的,对于“普通”散列表来说足够好,并且可以很难理解。

此外,当设计Java Collections API时,标准库中的通用哈希表已经足够大胆了。C从来没有过他们。C ++让他们在STL为hash_sethash_map,但这些并没有使之成为标准。直到现在,在C ++ 0x中,再次考虑用于标准化的散列表。

用户回答回答于

我认为正常的hashCode方法是在没有“恶意投入”的情况下创建的。而且,如larsmann所写,其合约比通用散列函数更容易理解和实施。

这里有一个关于怎么做的想法:

  • 使用一个依赖于外部散列函数的映射实现
  • 然后使用这种实现的通用系列(或允许更改参数以切换到家族的另一个成员的实现)。

扫码关注云+社区