java中hashCode和equals的使用

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

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()有可能相等,也有可能不等。
    下面是一个例子。在实际的软件开发中,最好重写这两个方法。

让我们看看为什么和怎么做才是正确的。

相等和哈希码

相等是从一般的方面来讲,哈希码更加具有技术性。如果我们在理解方面存在困难,我们可以说,他们通过只是一个实现细节来提高了性能。

大多数的数据结构通过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;
    }
}

散列法的思想

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

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

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

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()可能相等,也可能不等。

HashCode实现

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

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

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


选择字段

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

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

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

一致性

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

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

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

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


性能

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

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

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

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

碰撞

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

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

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

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

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

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

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


计算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方法

当实现hashCode

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

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


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