链接:https://www.sitepoint.com/how-to-implement-javas-hashcode-correctly/
译者:边城, sunnya05, 无若
大部分的数据结构使用equals去检查是否他们包含一个元素。例如:
boolean contains = list.contains("b");
这个捷径就是哈希码——从对象计算出来的一个能代表该对象的整数值。与哈希码相同的实例不必相等,但相等的实例一定有相同的哈希码。
(或者说应该有,我们稍后会对这个问题进行简单讨论)。这类的数据结构常常使用这种技术命名,在名称中加入 Hash 以便识别,其中最具代表性的就是 HashMap。
● 另一个不等同的元素如果具有相同的哈希码,它会被放在同一个桶中,与原来那个放在一起,比如把它们放在一个列表中。
● 如果传递一个实例给 contains 方法,会先计算它的哈希码来找到桶,只有同一个桶中的元素需要与这个实例进行比较。
将 equals、hashCode 定义在 Object 中。
这也是为什么,如果我们覆写 equals 方法,就必须创建一个匹配的 hashCode 实现!此外,实现 equal 应该是依据我们的实现而实现的,这可能会导致没有相同的哈希码,因为他们使用的是 Object 的实现。
● 在 Java 应用程序中,任何时候对同一对象多次调用 hashCode 方法,都必须一直返回同样的整数,对它提供的信息也用于对象的相等比较,且不会被修改。这个整数在两次对同一个应用程序的执行不中不需要保持一致。
● 如果两个对象通过 equals(Object) 方法来比较相等,那么这两个对象的 hashCode 方法必须产生同样的整型结果。
● 如果两个对象通过 equals(Object) 方法比较结果不等,这两个对象的 hashCode 不必产生同不整型结果。然而,开发者应该了解对不等的对象产生不同的整型结果有助于提高哈希表的性能。
public int hashCode() {
return Objects.hash(firstName, lastName);
}
所以用于计算哈希码的那些字段应该是用于相等性比较的那些字段的子集。默认情况下,它们会使用相同的字段,但有几个细节需要考虑。
正如我们在上面看到的那样,哈希码用于确定一个元素的桶,但是如果哈希相关的字段发生变化,并不会立即重新计算哈希码,而且内部的数组也不会更新。
这就意味着,再对一个相等的对象甚至同一个对象的查询会失败!这个数据结构会计算当前的哈希码,这个哈希码与实例存入时的哈希码并不相同,这直接导致找错了桶。
小结:最好不要用可变的字段来计算哈希码!
除非是使用了复杂的算法,或者使用的字段非常非常多,组合他们哈希码的计算成本可以忽略不计,因为这不可避免。但是应该考虑是否所有字段都需要包含在计算中!尤其应该以审视的眼光来看待集合,例如计算列表和集合中所有元素的哈希码。需要根据不同的情况来考虑是否需要它们参与计算。
如果性能是关键,使用 Object.hash 就可能不是最好的选择,因为它会为可变参数创建数组。
一般的优化原则是:谨慎处理!使用一个公共哈希算法的,可能需要放弃集合,并在分析可能的改进之后进行优化。
public int hashCode() {
return 0;
}
但是,想想我们提到的桶是什么?这种情况下所有实例会被装进同一个桶中!通常这会导致使用一个链表来容纳所有元素,这样的性能太糟糕了——比如,每次执行 contains 都会对列表进行线性扫描。
因此,我们得让每个桶里的内容尽可能的少!一个即使对非常相似的对象计算的哈希码也大不相同的算法,会是一个不错的开始。
如何取得,一定程度上取决于选择的字段。我们用于计算的细节,更多时候是为了生成不同的哈希码。注意,这与我们对性能的想法完全相反。结果很有趣,用太多或者太少字段都会导致性能不佳。
防止碰撞的算法是哈希算法的另一部分。
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;
注意,如果输入数据有着特定的模式,最好的哈希算法都可能出现异常频繁的碰撞。举个简单的例子,假设我们用一个点的 x 坐标和 y 坐标来计算哈希。一开始不太糟,直到我们发现这样一条直线上的点:f(x) = -x,这些点的 x + y = 0。就会发生大量的碰撞!
不过话说回来:如果没有分析说明一个公共算法不正确,就大胆的使用。
这意味着如果覆写了 equals 就必须覆写 hashCode。
实现 hashCode 时:
● 最好不要包含可变字段。
● 考虑不去调用集合的 hashCode。
● 使用公共算法,除非输入数据的模式严重影响这个算法的效果。
记住,hashCode 与效果相关,所以不要在上面浪费过多精力,除非分析结果指出优化的必要性。