澳门新葡萄京官网首页如何正确实现Java中的hashCode方法

本文由码农网 –
漠北空城原创翻译,转载请看清文末的转载要求,欢迎参与我们的付费投稿计划!

Java.lang.Object
有一个hashCode()和一个equals()方法,这两个方法在软件设计中扮演着举足轻重的角色。在一些类中重写这两个方法以完成某些重要功能。

原文出处:
开源中国

你知道一个对象的唯一标志不能仅仅通过写一个漂亮的equals来实现

  • 为什么要用 hashCode()?
    集合Set中的元素是无序且不可重复的,那判断两个元素是否重复的依据是什么呢?
    有人说:比较对象是否相等当然用Object.equal()了。但是,Set中存在大量对象,后添加到集合Set中的对象元素比较次数会逐渐增多,大大降低了程序运行效率。
    Java中采用哈希算法(也叫散列算法)来解决这个问题,将对象(或数据)依特定算法直接映射到一个地址上,对象的存取效率大大提高。
    这样一来,当含有海量元素的集合Set需要添加某元素(对象)时,先调用这个元素的hashCode(),就能一下子定位到此元素实际存储位置,如果这个位置没有元素,说明此对象是第一次存储到集合Set,
    直接将此对象存储在此位置上;若此位置有对象存在,调用equal()看看这两个对象是否相等,相等就舍弃此元素不存,不等则散列到其他地址。
    这也是为什么set集合存储对象类型数据的时候,要不仅仅重写对象的hashCode()方法还要重写equals()方法的原因。
  • HOW use hashCode()?
    hashCode()的返回值和equals()的关系

 

太棒了,不过现在你也必须实现hashCode方法。

  1. 如果a.equals(b)返回“true”,那么a和b的hashCode()一定相等。
  2. 如果a.equals(b)返回“false”,那么a和b的hashCode()有可能相等,也有可能不等。
    下面是一个例子。在实际的软件开发中,最好重写这两个方法。

相等 和 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”是不相同的实例(此外,忽略字符串驻留),但是他们是相等的。

通过比较实例的每个元素,然后将比较结果赋值给contains是比较浪费的,虽然整个类的数据结构进行了优化,能够提升性能。

他们通过使用一种快捷的方式(减少潜在的实例相等)进行比较,从而代替通过比较实例所包含的每个元素。而快捷比较仅需要比较下面这些方面:

快捷方式比较即通过比较哈希值,它可以将一个实例用一个整数值来代替。哈希码相同的实例不一定相等,但相等的实例一定具有有相同的哈希值。(或应该有,我们很快就会讨论这个)这些数据结构经常通过这种这种技术来命名,可以通过Hash来识别他们的,其中,HashMap是其中最著名的代表。

它们通常是这样这样运作的

  • 当添加一个元素,它的哈希码是用来计算内部数组的索引(即所谓的桶)
  • 如果是,不相等的元素有相同的哈希码,他们最终在同一个桶上并且捆绑在一起,例如通过添加到列表。
  • 当一个实例来进行contains操作时,它的哈希码将用来计算桶值(索引值),只有当对应索引值上存在元素时,才会对实例进行比较。

因此equalshashCode是定义在Object类中。

public class Employee {
    int        employeeId;
    String     name;

    @Override
    public boolean equals(Object obj)
    {
        if(obj==this)
            return true;
        Employee emp=(Employee)obj;
        if(employeeId.equals(emp.getEmployeeId()) && name==emp.getName())
            return true;
        return false;
    }

    @Override
    public int hashCode() {
        int hash = 1;
        hash = hash * 17 + employeeId;
        hash = hash * 31 + name.hashCode();
        return hash;
    }
}

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

散列法的思想

如果hashCode作为快捷方式来确定相等,那么只有一件事我们应该关心:相等的对象应该具有相同的哈希码,这也是为什么如果我们重写了equals方法后,我们必须创建一个与之匹配的hashCode实现的原因!

否则相等的对象是可能不会有相同的哈希码的,因为它们将调用的是Object's的默认实现。

equals()和hashCode()方法是用来在同一类中做比较用的,尤其是在容器里如set存放同一类对象时用来判断放入的对象是否重复。

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

boolean contains = list.contains("b");

HashCode 准则

引用自官方文档

hashCode通用约定:
*
调用运行Java应用程序中的同一对象,hashCode方法必须始终返回相同的整数。这个整数不需要在不同的Java应用程序中保持一致。
*
根据equals(Object)的方法来比较,如果两个对象是相等的,两个对象调用hashCode方法必须产生相同的结果。
*
根据equals(Object)的方法是比较,如果两个对象是不相等的,那么两个对象调用hashCode方法并不一定产生不同的整数的结果。但是, class=”wp_keywordlink”>程序员应该意识到给不相等的对象产生不同的整数结果将有可能提高哈希表的性能。

第一点反映出了相等的一致性属性,第二个就是我们上面提出的要求。第三个阐述了一个重要的细节,我们将在稍后讨论。

这里我们首先要明白一个问题:
equals()相等的两个对象,hashcode()一定相等,equals()不相等的两个对象,却并不能证明他们的hashcode()不相等。换句话说,equals()方法不相等的两个对象,hashCode()有可能相等。
在这里hashCode就好比字典里每个字的索引,equals()好比比较的是字典里同一个字下的不同词语。就好像在字典里查“自”这个字下的两个词语“自己”、“自发”,如果用equals()判断查询的词语相等那么就是同一个词语,比如equals()比较的两个词语都是“自己”,那么此时hashCode()方法得到的值也肯定相等;如果用equals()方法比较的是“自己”和“自发”这两个词语,那么得到结果是不想等,但是这两个词都属于“自”这个字下的词语所以在查索引时相同,即:hashCode()相同。如果用equals()比较的是“自己”和“他们”这两个词语的话那么得到的结果也是不同的,此时hashCode()
得到也是不同的。
反过来:hashcode()不等,一定能推出equals()也不等;hashcode()相等,equals()可能相等,也可能不等。

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

HashCode实现

下面是非常简单的Person.hashCode的实现

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

person’s是通过多个字段结合来计算哈希码的。都是通过Objecthash函数来计算。


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

选择字段

但哪些字段是相关的吗?需求将会帮助我们回答这个问题:如果相等的对象必须具有相同的哈希码,那么计算哈希码就不应包括任何不用于相等检查的字段。(否则两个对象只是这些字段不同但是仍然有可能会相等,此时他们这两个对象哈希码却会不相同。)

所以用于哈希组字段应该相等时使用的字段的子集。默认情况下都使用相同的字段,但有一些细节需要考虑。

在object类中,hashcode()方法是本地方法,返回的是对象的地址值,而object类中的equals()方法比较的也是两个对象的地址值,如果equals()相等,说明两个对象地址值也相等,当然hashcode()
也就相等了。

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

一致性

首先,有一致性的要求。它应该相当严格。虽然它允许如果一些字段改变对应的哈希码发生变化(对于可变的类是不可避免的),但是哈希数据结构并不是为这种场景准备的。

正如我们以上所见的哈希码用于确定元素的桶。但如果hash-relevant字段发生了改变,并不会重新计算哈希码、也不会更新内部数组。

这意味着以后通过相等的对象,甚至同一实例进行查询也会失败,数据结构计算当前的哈希码与之前存储实例计算的哈希码并不一致,并是错误的桶。

结论:最好不要使用可变字段计算哈希码!


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

性能

哈希码最终计算的频率与可能调用equals差不多,那么这里将是影响性能的关键部分,因此考虑此部分性能也是非常有意义的。并且与equals相比,优化之后又更大的上升空间。

除非使用非常复杂的算法或者涉及非常多的字段,那么计算哈希码的运算成本是微不足道的、同样也是不可避免的。但是也应该考虑是否需要包含所有的字段来进行运算。集合需要特别警惕的对待。以Listssets为例,将会包含集合里面的每一个元素来计算哈希码。是否需要调用它们需要具体情况具体分析。

如果性能是至关重要的,使用Objects.hash因为需要为varargs创建一个数组也许并不是最好的选择。但一般规则优化是适用的:不要过早地使用一个通用的散列码算法,也许需要放弃集合,只有优化分析显示潜在的改进。

既然equals比较元素相等更准确,那么为什么还要用hashCode( )方法呢?
因为hash算法对于查找元素提供了很高的效率,如果想查找一个集合中是否包含有某个对象,大概的程序代码怎样写呢?
你通常是逐一取出每个元素与要查找的对象进行比较,当发现某个元素与要查找的对象进行equals方法比较的结果相等时,则停止继续查找并返回肯定的信息,否则,返回否定的信息,如果一个集合中有很多个元素,比如有一万个元素,并且没有包含要查找的对象时,则意味着你的程序需要从集合中取出一万个元素进行逐一比较才能得到结论。

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

碰撞

总是关注性能,这个实现怎么呢?

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

快是肯定的。相等的对象将具有相同的哈希码。并且,没有可变的字段!

但是,我们之前说过的桶呢?!这种方式下所有的实例将会有相同的桶!这将会导致一个链表来包含所有的元素,这样一来将会有非常差的性能。每次调用contains将会触发对整个list线性扫描。

我们希望尽可能少的元素在同一个桶!一个算法返回变化多端的哈希码,即使对于非常相似的对象,是一个好的开始。

怎样才能达到上面的效果部分取决于选取的字段,我们在计算中包含更多的细节,越有可能获取到不同的哈希码。注意:这个与我们所说的性能是完全相反的。因此,有趣的是,使用过多或者过少的字段都会导致糟糕的性能。

防止碰撞的另一部分是使用实际计算散列的算法。


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

计算Hsah

最简单的方法来计算一个字段的哈希码是通过直接调用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,将会有大量的碰撞。

但是:我们可以使用一个通用的算法,只到分析表明并不正确,才需要对哈希算法进行修改。

Object类中定义了一个hashCode()方法来返回每个Java对象的哈希码,当从HashSet集合中查找某个对象时,Java系统首先调用对象的hashCode()方法获得该对象的哈希码表,然后根据哈希吗找到相应的存储区域,最后取得该存储区域内的每个元素与该对象进行equals方法比较;这样就不用遍历集合中的所有元素就可以得到结论,可见,HashSet集合具有很好的对象检索性能
但是,HashSet集合存储对象的效率相对要低些,因为向HashSet集合中添加一个对象时,要先计算出对象的哈希码和根据这个哈希码确定对象在集合中的存放位置为了保证一个类的实例对象能在HashSet正常存储,要求这个类的两个实例对象用equals()方法比较的结果相等时,他们的哈希码也必须相等;也就是说,如果obj1.equals(obj2)的结果为true,那么以下表达式的结果也要为true:obj1.hashCode() == obj2.hashCode()

将 equals、hashCode 定义在 Object 中。

总结

我们了解到计算哈希码就是压缩相等的一个整数值:相等的对象必须有相同的哈希码,而出于对性能的考虑:最好是尽可能少的不相等的对象共享相同的哈希码。

这就意味着如果重写了equals方法,那么就必须重写hashCode方法

当实现hashCode

  • 使用与equals中使用的相同的字段(或者equals中使用字段的子集)
  • 最好不要包含可变的字段。
  • 对集合不要考虑调用hashCode
  • 如果没有特殊的输入特定的模式,尽量采用通用的哈希算法

记住hashCode性能,所以除非分析表明必要性,否则不要浪费太多的精力。


关于哈希的一些思考

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

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

换句话说:当我们重写一个对象的equals方法,就必须重写他的hashCode方法,不重写他的hashCode方法的话,Object对象中的hashCode方法始终返回的是一个对象的hash地址,而这个地址是永远不相等的。所以这时候即使是重写了equals方法,也不会有特定的效果的,因为hashCode方法如果都不想等的话,就不会调用equals方法进行比较了,所以没有意义了。

hashCode 约定

从原文档引用:

对于 hashCode 的一般约定:

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

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

  • 大多数的数据结构通过equals方法来判断他们是否包含一个元素,例如:

实现 hashCode

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

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

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

选择字段

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

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

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

一致性

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

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

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

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

这个变量contains结果是true,因为,虽然”b”是不相同的实例(此外,忽略字符串驻留),但是他们是相等的。
他们通过使用一种快捷的方式(减少潜在的实例相等)进行比较,从而代替通过比较实例所包含的每个元素。而快捷比较仅需要比较下面这些方面:
快捷方式比较即通过比较哈希值,它可以将一个实例用一个整数值来代替。哈希码相同的实例不一定相等,但相等的实例一定具有有相同的哈希值。(或应该有,我们很快就会讨论这个)这些数据结构经常通过这种这种技术来命名,可以通过Hash来识别他们的,其中,HashMap是其中最著名的代表。

性能

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

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

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

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


碰撞

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

@Override

public int hashCode() {

return 0;

}

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

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

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

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

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

它们通常是这样这样运作的:
当添加一个元素,它的哈希码是用来计算内部数组的索引(即所谓的桶)
如果是,不相等的元素有相同的哈希码,他们最终在同一个桶上并且捆绑在一起,例如通过添加到列表。
当一个实例来进行contains操作时,它的哈希码将用来计算桶值(索引值),只有当对应索引值上存在元素时,才会对实例进行比较。
因此equals,hashCode是定义在Object类中。

计算哈希

计算字段的哈希码最简单的办法就是直接调用这个字段的
`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。就会发生大量的碰撞!


如果hashCode作为快捷方式来确定相等,那么只有一件事我们应该关心:相等的对象应该具有相同的哈希码,这也是为什么如果我们重写了equals方法后,我们必须创建一个与之匹配的hashCode实现的原因!
否则相等的对象是可能不会有相同的哈希码的,因为它们将调用的是Object’s的默认实现。
引用自官方文档

hashCode通用约定:
调用运行Java应用程序中的同一对象,hashCode方法必须始终返回相同的整数。这个整数不需要在不同的Java应用程序中保持一致。根据equals(Object)的方法来比较,如果两个对象是相等的,两个对象调用hashCode方法必须产生相同的结果。
根据equals(Object)的方法是比较,如果两个对象是不相等的,那么两个对象调用hashCode方法并不一定产生不同的整数的结果。但是,程序员应该意识到给不相等的对象产生不同的整数结果将有可能提高哈希表的性能。

  • HashCode实现
    下面是简单的person.hashcode()的实现:

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

person’s是通过多个字段结合来计算哈希码的。都是通过Object的hash函数来计算。

  • 选择字段
    但哪些字段是相关的呢?需求将会帮助我们回答这个问题:
    如果相等的对象必须具有相同的哈希码,那么计算哈希码就不应包括任何不用于相等检查的字段。(否则两个对象只是这些字段不同但是仍然有可能会相等,此时他们这两个对象哈希码却会不相同。)所以用于哈希组字段应该相等时使用的字段的子集。默认情况下都使用相同的字段,但有一些细节需要考虑。
  • 总结
    我们了解到计算哈希码就是压缩相等的一个整数值:相等的对象必须有相同的哈希码,而出于对性能的考虑:最好是尽可能少的不相等的对象共享相同的哈希码。
    这就意味着如果重写了equals方法,那么就必须重写hashCode方法
    当实现hashCode使用与equals中使用的相同的字段(或者equals中使用字段的子集)
    最好不要包含可变的字段。对集合不要考虑调用hashCode,如果没有特殊的输入特定的模式,尽量采用通用的哈希算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注