如何正确实现 Java 中的 HashCode

标签: 基础技术 hashCode | 发表时间:2017-09-19 02:34 | 作者:TiuVe2
分享到:
出处:http://www.importnew.com

相等 和 Hash Code

从一般角度来看,Equality 是不错的,但是 hash code 更则具技巧性。如果我们在 hash code上多下点功夫,我们就能了解到 hash code 就是用在细微处去提升性能的。

大部分的数据结构使用equals去检查是否他们包含一个元素。例如:

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

这个变量 contains 是true。因为他们是相等的,虽然b的实例化(instance)虽然不完全一样(再说一次,忽略String interning)。

将传递给 contains 的实例与每个元素进行比较很浪费时间。还好,整个这类数据结构使用了一种更高效的方法。它不会将请求的实例与每个元素比较,而是使用捷径,找到可能与之相等的实例,然后只比较这几项。

这个捷径就是哈希码——从对象计算出来的一个能代表该对象的整数值。与哈希码相同的实例不必相等,但相等的实例一定有相同的哈希码。(或者说应该有,我们稍后会对这个问题进行简单讨论)。这类的数据结构常常使用这种技术命名,在名称中加入 Hash 以便识别,其中最具代表性的就是 HashMap。

一般情况下它们会这样进行:

  • 添加一个元素的时候,使用它的哈希码来计算存放在内部数组(称为桶)中的位置(序号)。
  • 另一个不等同的元素如果具有相同的哈希码,它会被放在同一个桶中,与原来那个放在一起,比如把它们放在一个列表中。
  • 如果传递一个实例给 contains 方法,会先计算它的哈希码来找到桶,只有同一个桶中的元素需要与这个实例进行比较。

使用这种方法实现 contains 的情况很少,在理想的状态下根本不需要 equals 比较。

将 equals、hashCode 定义在 Object 中。

关于哈希的一些思考

如果把 hashCode 作为一种快捷方式取决于其是否相等,那么只有一件事情我们需要关心:相等的对象应该有一致的哈希码。

这也是为什么,如果我们覆写 equals 方法,就必须创建一个匹配的 hashCode 实现!此外,实现 equal 应该是依据我们的实现而实现的,这可能会导致没有相同的哈希码,因为他们使用的是 Object 的实现。

hashCode 约定

从原文档引用:

对于 hashCode 的一般约定:

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

第一条反映了 equals 的一致性。第二条是我们在上面提到的要求。第三条陈述了我们下面要讨论的一个重要细节。

实现 hashCode

Person.hashCode 有个很简单的实现:

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

通过计算相关字段的哈希码,再把这些哈希码组合起来得到 person 的哈希码。它们用 Object 的工具函数 hash 来参与计算。

选择字段

然而什么字段才是相关的?这些要求有助于回答这个问题:如果相等的对象必须有相同的哈希码,那么在计算哈希码的时候就不应该使用那些不用于相等性检查的字段。(否则,如果两个对象只有那些字段不同的话,它们会相等但哈希码不同。)

所以用于计算哈希码的那些字段应该是用于相等性比较的那些字段的子集。默认情况下,它们会使用相同的字段,但有几个细节需要考虑。

一致性

第一是一致性要求。它应该经过非常严格的计算。如果有字段产生了变化,哈希码也应该允许变化(对于可变类来说,这往往是不可避免的),依赖哈希的数据结构并未准备应付这种情况。

正如我们在上面看到的那样,哈希码用于确定一个元素的桶,但是如果哈希相关的字段发生变化,并不会立即重新计算哈希码,而且内部的数组也不会更新。

这就意味着,再对一个相等的对象甚至同一个对象的查询会失败!这个数据结构会计算当前的哈希码,这个哈希码与实例存入时的哈希码并不相同,这直接导致找错了桶。

小结:最好不要用可变的字段来计算哈希码!

性能

哈希码可能最终会在每次调用 equals 的时候计算,这可能正好发生在代码中性能极为关键的部分,所以考虑性能是很有意义的。相比之下 equals 的优化空间就非常小。

除非是使用了复杂的算法,或者使用的字段非常非常多,组合他们哈希码的计算成本可以忽略不计,因为这不可避免。但是应该考虑是否所有字段都需要包含在计算中!尤其应该以审视的眼光来看待集合,例如计算列表和集合中所有元素的哈希码。需要根据不同的情况来考虑是否需要它们参与计算。

如果性能是关键,使用 Object.hash 就可能不是最好的选择,因为它会为可变参数创建数组。

一般的优化原则是:谨慎处理!使用一个公共哈希算法的,可能需要放弃集合,并在分析可能的改进之后进行优化。

碰撞

如果只关注性能,下面这个实例怎么样?

@Override
public int hashCode() {
return 0;
}

毫无疑问,它很快。而且相等的对象会有相同的哈希码,这也让我们觉得不错。还有个亮点,它不涉及可变的字段!

但是,想想我们提到的桶是什么?这种情况下所有实例会被装进同一个桶中!通常这会导致使用一个链表来容纳所有元素,这样的性能太糟糕了——比如,每次执行 contains 都会对列表进行线性扫描。

因此,我们得让每个桶里的内容尽可能的少!一个即使对非常相似的对象计算的哈希码也大不相同的算法,会是一个不错的开始。

如何取得,一定程度上取决于选择的字段。我们用于计算的细节,更多时候是为了生成不同的哈希码。注意,这与我们对性能的想法完全相反。结果很有趣,用太多或者太少字段都会导致性能不佳。

防止碰撞的算法是哈希算法的另一部分。

计算哈希

计算字段的哈希码最简单的办法就是直接调用这个字段的 `hashCode`。可以手工来进行合并。一个公共算法是从任意的某个数开始,让它与另一个数(通常是一个小素数)相乘,再加上一个字段的哈希码,然后重复:

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 坐标来计算哈希。一开始不太糟,直到我们发现这样一条直线上的点:f(x) = -x,这些点的 x + y = 0。就会发生大量的碰撞!

相关文章

相关 [正确 java hashcode] 推荐:

如何正确实现 Java 中的 HashCode

- - ImportNew
相等 和 Hash Code. 从一般角度来看,Equality 是不错的,但是 hash code 更则具技巧性. 如果我们在 hash code上多下点功夫,我们就能了解到 hash code 就是用在细微处去提升性能的. 大部分的数据结构使用equals去检查是否他们包含一个元素. 这个变量 contains 是true.

java中的hashcode作用

- - 编程语言 - ITeye博客
根据API文档,java中的hashcode事实上是跟equals是有着密切联系的,hashcode是为了提高哈希表的性能. public int hashCode()返回该对象的哈希码值. 支持此方法是为了提高哈希表(例如 java.util.Hashtable 提供的哈希表)的性能. 说明是一个本地方法,它的实现是根据本地机器相关的.

【转】java中hashcode()和equals()的详解

- - 互联网 - ITeye博客
首先equals()和hashcode()这两个方法都是从object类中继承过来的. equals()方法在object类中定义如下: . 很明显是对两个对象的地址值进行的比较(即比较引用是否相同). 但是我们必需清楚,当String 、Math、还有Integer、Double. 等这些封装类在使用equals()方法时,已经覆盖了object类的equals()方法.

[转]《Effective Java》中推荐的hashCode算法

- - 荒岛码农
Google首席Java架构师Joshua Bloch在他的著作《Effective Java》中提出了一种简单通用的hashCode算法:. 初始化一个整形变量,为此变量赋予一个非零的常数值,比如int result = 17;. 选取equals方法中用于比较的所有域,然后针对每个域的属性进行计算:.

深入解析Java对象的hashCode和hashCode在HashMap的底层数据结构的应用

- - 编程语言 - ITeye博客
对比对象实例的内存地址(也即对象实例的ID),来判断是否是同一对象实例;又可以说是判断对象实例是否物理相等;. 对比两个对象实例是否相等. 当对象所属的类没有重写根类Object的equals()方法时,equals()判断的是对象实例的ID(内存地址),是否是同一对象实例;该方法就是使用的等号(==)的判断结果.

关于hashcode与equal函数

- - 编程语言 - ITeye博客
hashcode:独一无二地代表了一个对象,并且通过hashcode可以找到这个对象. 在java.lang.Object的规范中,对hasCode有如下的约定:.  1 在一个应用程序执行期间,如果一个对象的equals方法做比较所用到的信息没有被修改的话,那么对该对象调用多次hashCode方法,它必须返回相同的整数.

hashCode equal避免的几个误区

- - ITeye博客
对于hashcode方法和equals方法,我们需要注意以下几点:. 1.equals方法所需要的几个特性.    ?什么情况下进行equals的比较. 答案是用equals比较的只是值本身,对于equals方法,读者需要记住按照两种情况来运用,一比较基本类型的值的比较,二比较的是对象. equals比较的只是值或者对象的内容.

hashCode()方法的性能优化

- - 并发编程网 - ifeve.com
原文链接, 译文链接,原文作者: Robert Nystrom,译者:有孚. 本文主要讨论下不同的hashCode()的实现对应用程序的性能影响. hashCode()方法的主要目的就是使得一个对象能够成为hashMap的key或者存储到hashset中. 这种情况下对象还得实现equals(Object)方法,它的实现和hashCode()必须是一致的:.

为什么要重写equles和hashcode

- - 编程语言 - ITeye博客
  经过网上查阅资料得出如下结论.                      大家知道,Java中的集合(Collection)有两类,一类是List,再有一类是Set. 前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复. 那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢.

hashcode和equals区别和联系

- - Java - 编程语言 - ITeye博客
[size=x-small]HashCode和equal方法的区别和联系[/size]. HashCode 和 equal方法重载. 1、 为什么要重载equal方法. 答案:因为Object的equal方法默认是两个对象的引用的比较,意思就是指向同一内存,地址则相等,否则不相等;如果你现在需要利用对象里面的值来判断是否相等,则重载equal方法.