目录
一.基础:hashCode() 和 equals() 简介
在学习 hashCode() 和 equals() 之间的关系之前, 我们有必要先单独地了解他俩的特点.
equals()
equals() 方法用于比较两个对象是否相等,它与 == 相等比较符有着本质的不同。
在万物皆对象的 Java 体系中,系统把判断对象是否相等的权力交给程序员。具体的措施是把 equals() 方法写到 Object 类中,并让所有类继承 Object 类。 这样程序员就能在自定义的类中重写 equals() 方法, 从而实现自己的比较逻辑.
关于 equals() 和 == 的区别你可以--参考这篇文章--
hashCode()
hashCode() 的意思是哈希值, 哈希值是经哈希函数运算后得到的结果,哈希函数能够保证相同的输入能够得到相同的输出(哈希值),但是不能够保证不同的输入总是能得出不同的输出。
当输入的样本量足够大时,是会产生哈希冲突的,也就是说不同的输入产生了相同的输出。
暂且不谈冲突,就相同的输入能够产生相同的输出这点而言,是及其宝贵的。它使得系统只需要通过简单的运算,在时间复杂度O(1)的情况下就能得出数据的映射关系,根据这种特性,散列表应运而生。
一种主流的散列表实现是:用数组作为哈希函数的输出域,输入值经过哈希函数计算后得到哈希值。然后根据哈希值,在数组种找到对应的存储单元。当发生冲突时,对应的存储单元以链表的形式保存冲突的数据。
二. 漫谈:初识 hashCode() 与 equals() 之间的关系
下面我们从一个宏观的角度讨论 hashCode() 和 equals() 之间的关系。
在大多数编程实践中,归根结底会落实到数据的存取问题上。 在汇编语言时代,你需要老老实实地对每个数据操作编写存取语句。
而随着时代发展到今天,我们都用更方便灵活的高级语言编写代码,比如 Java。
Java 以面向对象为核心思想,封装了一系列操作数据的 api,降低了数据操作的复杂度。
但在我们对数据进行操作之前,首先要把数据按照一定的数据结构保存到存储单元中,否则操作数据将无从谈起。
然而不同的数据结构有各自的特点,我们在存储数据的时候需要选择合适的数据结构进行存储。 Java 根据不同的数据结构提供了丰富的容器类,方便程序员选择适合业务的容器类进行开发。
通过继承关系图我们看到 Java 的容器类被分为 Collection 和 Map 两大类,Collection 又可以进一步分为 List 和 Set。 其中 Map 和 Set 都是不允许元素重复的,严格来说Map存储的是键值对,它不允许重复的键值。
值得注意的是:Map 和 Set 的绝大多数实现类的底层都会用到散列表结构。
讲到这里我们提取两个关键字不允许重复和散列表结构,回顾 hashCode() 和 equals() 的特点,你是否想到了些什么东西呢?
三. 解密:深入理解 hashCode() 和 equals() 之间的关系
equals() 会有力不从心的时候
上面提到 Set 和 Map 不存放重复的元素(key),这些容器在存储元素的时必须对元素做出判断:在当前的容器中有没有和新元素相同的元素?
你可能会想:这容易呀,直接调用元素对象的 equals() 方法进行比较不就行了吗?
如果容器中的存储的对象数量较少,这确实是个好主意,但是如果容器中存放的对象达到了一定的规模,要调用容器中所有对象的 equals() 方法和新元素进行比较,就不是一件容易的事情了。
就算 equals() 方法的比较逻辑简单无比,总的来说也是一个时间复杂度为 O(n) 的操作啊。
hashCode() 小力出奇迹
但在散列表的基础上,判断“新对象是否和已存在对象相同”就容易得多了。
由于每个对象都自带有 hashCode(),这个 hashCode 将会用作散列表哈希函数的输入,hashCode 经过哈希函数计算后得到哈希值,新对象会根据哈希值,存储到相应的内存的单元。
我们不妨假设两个相同的对象,hashCode() 一定相同,这么一来就体现出哈希函数的威力了。
由于相同的输入一定会产生相同的输出,于是如果新对象,和容器中已存在的对象相同,新对象计算出的哈希值就会和已存在的对象的哈希值产生冲突。
这时容器就能判断:这个新加入的元素已经存在,需要另作处理:覆盖掉原来的元素(key)或舍弃。
按照这个思路,如果这个元素计算出的哈希值所对应的内存单元没有产生冲突,也就是没有重复的元素,那么它就可以直接插入。
所以当运用 hashCode() 时,判断是否有相同元素的代价,只是一次哈希计算,时间复杂度为O(1),这极大地提高了数据的存储性能。
Java 设计 equals(),hashCode() 时约定的规则
前面我们还提到:当输入样本量足够大时,不相同的输入是会产生相同输出的,也就是形成哈希冲突。
这么一来就麻烦了,原来我们设定的“如果产生冲突,就意味着两个对象相同”的规则瞬间被打破,因为产生冲突的很有可能是两个不同的对象!
而令人欣慰的是我们除了 hashCode() 方法,还有一张王牌:equals() 方法。
也就是说当两个不相同的对象产生哈希冲突后,我们可以用 equals() 方法进一步判断两个对象是否相同。
这时 equals() 方法就相当重要了,这个情况下它必须要能判定这两个对象是不相同的。
- 讲到这里就引出了 Java 程序设计中一个重要原则:
如果两个对象是相等的,它们的 equals() 方法应该要返回 true,它们的 hashCode() 需要返回相同的结果。
但有时候面试不会问得这么直接,他会问你:两个对象的 hashCdoe() 相同,它的 equals() 方法一定要返回 true,对吗?
那答案肯定不对。因为我们不能保证每个程序设计者,都会遵循编码约定。
有可能两个不同对象的hashCode()会返回相同的结果,但是由于他们是不同的对象,他们的 equals() 方法会返回false。
如果你理解上面的内容,这个问题就很好解答,我们再回顾一下:
如果两个对象的 hashCode() 相同,将来就会在散列表中产生哈希冲突,但是它们不一定是相同的对象呀。
当产生哈希冲突时,我们还得通过 equals() 方法进一步判断两个对象是否相同,equals() 方法不一定会返回 true。
这也是为什么 Java 官方推荐我们在一个类中,最好同时重写 hashCode() 和 equals() 方法的原因。
四. 验证:结合 HashMap 的源码和官方文档,验证两者的关系
以上的文字,是我经过思考后得出的,它有一定依据但并非完全可靠。下面我们根据 HashMap 的源码(JDK1.8)和官方文档,来验证这些推论是否正确。
通过阅读JDK8的官方文档,我们发现 equals() 方法介绍的最后有这么一段话:
Note that