英文原文:How to Implement Java’s hashCode Correctly

相等性和Hash Code

从一般角度来看,相等是有意义的,但HashCode从技术层面上来说更加复杂。如果我们多花点功夫去研究hash code,我们就能够发现HashCode就是一个用来提升性能的细节实现。
大部分的数据结构使用equals方法去检查它们是否包含一个元素。例如:

1
2
List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

变量contains的值为true,因为"b"list中的"b"是相等的,虽然"b"的实例不完全相等(再次声明,这里忽略String Interning)。(译者注:关于JavaString intern,感兴趣的可以自己去了解,主要是一个字符串常量池的概念)
将传入contains方法的实例参数与容器中的每个元素进行比较是比较浪费资源的,不过整个数据结构类采用了更加高性能的方法。这种方法使用一种捷径去减少可能相等的实例的数量并只比较它们而不是将请求的实例与容器中包含的每个元素进行比较。

这个捷径就是hash code,它能够把一个对象的相等性归结为一个整数。具有相同hash code的实例不一定相等,但相等的实例必定具有相同的hash code(或者说应该具有,我们将会对这个问题进行简短的探讨)。这类的数据结构通常被赋予以这种技术开头的名称,在名称中加入Hash使之易于识别,其中最具有代表性的就是HashMap

下面描述Hash通常是如何工作的:

  • 当一个元素被添加时,它的hash code会被用于计算它在内部数组(称为桶)中的索引。
  • 如果其他不相等的元素具有相同的hash code,他们最终会被置于相同的桶中并且一定会被绑定在一起,例如通过把它们添加到一个list中。
  • 传递一个实例到contains方法中,它的hash code会被用于计算桶的位置,只有同一个桶中的元素会与这个实例进行比较。
    通过这种方式实现的contains方法,在理想情况下,只需要进行很少的相等性对比。
    equals方法、hashCode方法被定义在Object类中。

关于Hash的思考

如果把hashCode方法作为决定两个实例是否相等的捷径,那么这里我们只需要关心一件事:相等的对象应该具有相同的hash code
这也是为什么如果我们重写equals方法就必须要创建一个匹配的hashCode实现的原因。另外,根据我们实现的equals方法而相等的对象可能没有相同的hash code,因为他们使用的是Object类的实现。

hashCode的约定

官方文档引用:

hashCode的一般约定如下:

  • Java应用程序的一次执行期间,任何时候对同一个对象多次调用hashCode方法,假如用于相等比较的信息没有被修改,都必须始终如一的返回一个相同的整数。对于同一个应用程序,这个整数不需要在两次执行期间保持一致。
  • 如果两个对象通过equals方法(Object)比较是相等的,那么对这两个对象调用hashCode方法必须产生相同的整型结果。
  • 如果两个对象通过equals方法(Object)比较是不相等的,那么不要求对这两个对象调用hashCode方法必须产生不相同的整型结果。然而,开发者应该了解不相等的对象产生不相同的整型结果有助于提高哈希表的性能。

第一点反应了equals的一致性,第二点是我们在第一点的基础上提出的要求,第三点陈述了我们下面马上就要讨论的一个重要细节。

实现hashCode

Person.hashCode的一个非常简单的实现如下:

1
2
3
4
@Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}

Person类的hash code是通过计算相关字段的hash code并将它们关联起来得到的。它们都是用Object类的工具方法hash实现的。

选择字段

然而哪些字段是相关的?下面这些要求有助于回答这个问题:如果相等的对象必须要具有相同的hash code,那么hash code的计算不应该包含任何在相等性检查中没有用到的字段。(否则,如果两个对象只有那些字段(指的是相等检查中没有用到的字段)不同,那么它们会相等但是会有不同的hash code

因此,用于计算hash code的字段集合应该是用于相等检查的字段集合的子集,默认情况下它们会使用相同的字段,但是这里有几个细节需要考虑。

一致性

第一是一致性要求。它应该被解释的十分严格。然而,如果一些字段发生改变(对于可变类来说,这通常是不可避免的),hash code也允许发生改变,哈希数据结构没有准备好应对这种情况。

正如我们在上面看到的,hash code被用来确定一个元素的桶的位置。但是如果参与hash计算的相关字段发生变化,hash code不会马上被重新计算,内部的数组也不会更新。

这意味着之后用一个相等的对象或相同的实例进行查询会发生失败。这个数据结构计算实例当前的hash code,得到的结果与实例存入时计算得到的hash code不同,这直接导致找错了桶的情况。

结论:最好不要使用可变的字段去计算hash code

性能

hash code可能会在每次equals方法被调用时进行计算。这可能恰好发生在代码中对性能要求十分苛刻的部分,所以考虑性能是很有意义的。它不像equals方法那样只有很小的优化空间。

除非是使用了复杂的算法或是包含了大量的字段,算法中组合字段的hash code的开销可以忽略不计,因为这是无法避免的。但是我们需要考虑是否有将所有的字段包含进来计算hash code的必要。尤其应该用怀疑的眼光来看待集合。例如对于列表和集合,将会计算它们每一个元素的hash code。是否要将所有的字段包含进来进行hash code的计算需要具体情况具体分析。

如果对性能有苛刻的要求,使用Objects.hash可能不是一个最好的选择,因为它会要求为可变参数创建一个数组。

但是优化的一般原则如下:不要过早的优化。采用一个常用的hash code算法,也许不需要考虑在集合调用的情况,并且只在对代码的分析展现出改善的可能性之后才进行优化。

碰撞

如果只考虑性能,下面这个实现怎么样?

1
2
3
4
@Override
public int hashCode() {
return 0;
}

毫无疑问,这种实现非常快。并且相等的对象也具有相同的hash code,我们对此也很满意。另外它还有一个亮点,不涉及可变字段。

但是,还记得我们我们提到的桶吗?在这种方式下,所有的实例都会被定位到同一个桶中,这通常会导致所有元素都被放置到同一个链表中,这样一来性能就太糟糕了。例如,每次调用contains方法都会触发对链表的线性扫描。

因此,我们想要的是同一个桶中元素尽可能的少。如果能够设计出一个算法,即使对于十分相似的对象,它也能够返回有很大差异的hash code,这将会是一个很好的开始。

如何达到这一目的部分取决于所选择的字段。包含越多的细节参与计算,那么我们就越有可能得到不同的hash code。注意这和我们关于性能的想法完全相反,这很有趣,使用过多或多少的字段都会导致性能不佳。

另外一部分防止碰撞的方法取决于实际使用的用来计算hash code的算法。

计算Hash

计算一个字段的hash code的最简单的方法就是直接调用它的hashCode方法,我们可以手工将所有的hash code组合起来。通常的哈希算法以任意一个数字开始,然后将它与一个其他数字(通常是一个较小的素数)相乘,最后加上一个字段的hash code,重复多次这样的操作。

1
2
3
4
5
int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;

这样的做法可能导致溢出,但这不会造成什么大问题,因为在Java中,这不会产生异常。

值得注意的是,就算是一个极好的哈希算法也会因为一些特定模式的输入数据而导致异常频繁的碰撞。举一个简单的例子,假设我们通过相加一个点的x坐标和y坐标作为该点的hash code,这看起来并不会太坏直到我们认识到我们经常处理f(x) = -x图像上的点,这意味着该直线上的所有点的hash code的计算结果都是 x + y == 0,这就会导致大量的碰撞。

总结

我们可以看到,计算hash code就像把相等性浓缩成一个整数:相等的对象具有相同的hash code,并且出于性能的原因,最好让尽可能少的不相等的对象享有相同的hash code

这意味着在equals方法被重写的情况下,hashCode方法也必须要重写。

当我们要实现一个hashCode方法:

  • 使用和equals方法中相同的字段(或其子集)
  • 最好不要包含可变字段
  • 考虑不要在集合中调用hashCode方法
  • 使用一个常见的哈希算法除非特定模式的输入数据与之相抵触

我们要记住,hashCode方法关乎性能,所以不要在它上面浪费太多资源除非分析指出这是必要的。