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

Question

一些哈希表方案（例如cuckoo hashing或dynamic perfect hashing）依赖于存在通用哈希函数并能够通过从通用哈希函数族中选择新的哈希函数来解决具有冲突的数据集中的冲突。

前段时间，我试图在Java中实现一个使用cuckoo hashing支持的哈希表，但遇到了麻烦，因为尽管所有Java对象都有一个hashCode函数，但hashCode返回的值对于每个对象都是固定的（除非对象发生改变）。这意味着，如果用户没有提供外部的通用哈希函数族，则无法构建依赖于通用哈希的哈希表。

起初，我认为可以通过直接将通用哈希函数应用于对象的hashCode来解决这个问题，但这行不通，因为如果两个对象具有相同的hashCode，则对这些哈希码应用任何确定性函数，即使是随机选择的哈希函数，也会导致相同的值，从而引起冲突。

这似乎对Java的设计是有害的。这意味着HashMap和其他哈希容器完全禁止使用基于通用哈希的表，即使语言设计者认为这样的表在语言设计中是合适的。这也使得第三方库设计人员难以构建这种类型的哈希表。

我的问题是：Java是否有理由考虑使用多个哈希函数对对象进行哈希而没有选择设计hashCode？我知道许多好的哈希方案，如链式哈希或二次探测，不需要它，但似乎这个决策使得很难在Java对象上使用某些类别的算法。

- templatetypedef

---

这应该如何实现？要求每个人都实现十几个哈希函数吗？哈希表更容易通过检测冲突并解决它们来使其工作。 - user395760

@delnan- 我更倾向于hashCode接收一些位串，然后在生成哈希函数时进行解释。例如，如果您正在对整数进行哈希处理，您可以将位串视为一系列8位值，您可以使用这些值来扩大数字中的各个八位字节。 - templatetypedef

Cuckoo哈希不依赖于通用哈希函数，有多种简单的变体可以解决这个问题。最简单的方法是当哈希表可以简单地增长时（这通常是Java应用程序的情况）。 - MSalters

@MSalters- 你能详细解释一下吗？我认为通用哈希是必要的，因为如果两个Java对象具有相同的哈希码，则无论表有多大，它们都会发生冲突。我找不到任何其他建议的来源。 - templatetypedef

我一直认为通用哈希是用于证明而非系统构建的。我很想看到你能否举出一个需要多个不同哈希函数的例子，但盐化版本的cityhash不足以胜任，而通用哈希函数可以胜任的情况。 - Rob Neuhaus

@rrenaud- 通用哈希函数就是一组哈希函数，预期上使得每对不同元素的哈希值不同。盐值哈希很可能是一组通用的哈希函数族。 - templatetypedef

Answer 1

简单性。Java允许类设计者提供自己的hashCode，这对于“普通”的哈希表已经足够好了，并且可能很难理解。

此外，在设计Java集合API时，将通用哈希表放入标准库中已经是一个大胆的举动。C从来没有这样做过。C++在STL中有hash_set和hash_map，但它们没有被纳入标准。只有现在，在C++0x中，哈希表才被考虑重新标准化。

- Fred Foo

---

+1 感谢您提供出色的答案。历史背景确实有助于解释事情。 - templatetypedef

Answer 2

我认为普通的hashCode方法是没有考虑到“恶意输入”情况而创建的。此外，正如larsmann所写的那样，它的契约比通用哈希函数更容易理解和实现。

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

• 使用依赖于外部哈希函数的映射实现（例如我在这里几个小时前介绍的HashableEquivalenceRelation）
• 然后使用这些实现的通用族（或允许更改参数以切换到族中的另一个成员的实现）。

- Paŭlo Ebermann