目录
一. 基础: hashCode()和equals()简介
- equals()方法用于比较两个对象是否相等, 它与"=="相等比较符有着本质的不同. 在万物皆对象的Java体系中, 系统把判断对象是否相等的权力交给程序员, 具体的措施是把equals()方法写入到Object类中, 并让所有类继承Object类. 这样程序员就能在类中自定义equals()方法, 从而实现自己的业务逻辑.
- 关于equals()和"=="的区别你可以--参考这篇文章--
- hashCode()的意思是哈希值, 哈希值是哈希函数运算后得到的结果, 哈希函数能够保证相同的输入能够得到相同的输出(哈希值), 但是不能够保证不同的输入总是能得出不同的输出. 当输入的样本量足够大时, 是会产生哈希冲突的, 也就是不同的输入产生了相同的输出.
- 暂且不谈冲突, 就相同的输入能够产生相同的输出这点而言, 是及其宝贵的. 它使得系统只需要通过简单的运算, 在时间复杂度O(1)的情况下就能得出数据的映射关系, 根据这种特性引申出了散列表这种数据结构.
- 一种主流的散列表实现是: 用数组作为哈希函数的输出域, 输入值经过哈希函数计算后得到哈希值, 然后根据哈希值在数组种找到对应的存储单元. 当发生冲突时, 对应的存储单元以链表的形式保存冲突的数据.
二. 漫谈: 引入hashCode()与equals()之间的关系
- 在大多数编程实践中, 归根结底会落实到数据的存取问题上. 在汇编语言时代, 你需要老老实实地对每个数据操作编写存取语句; 随着时代发展到今天, 我们都用类似Java这样的高级语言编写代码. Java除了拥有面向对象的核心思想外, 还给我们封装了一系列操作数据的api, 为编程工作提供了极大的便利.
- 但在我们对数据进行操作之前, 首先要把数据按照一定的数据结构保存到存储单元中, 否则操作数据将无从谈起. 然而不同的数据结构有各自的特点, 我们在存储数据的时候需要选择适合自己的数据结构进行存储. Java根据不同的数据结构提供了丰富的容器类, 方便程序员选择适合业务的容器类进行开发.
- 而Java的容器类被分为Collection和Map两大类, Collection又可以进一步分为List和Set. 其中Map和Set都是不允许元素重复的, 严格来说Map存储的是键值对, 它不允许重复的键值. 值得注意的是: Map和Set的绝大多数实现类的底层都会用到散列表结构.
- 讲到这里我们提取两个关键字不允许重复和散列表结构, 回顾hashCode()和equals()的特点, 你是否想到了些什么东西呢?
三. 解密: 深入理解hashCode()和equals()之间的关系.
- 上面提到Set和Map不存放重复的元素(key), 那么在存储元素的时候就必须对元素做出判断: 在当前的容器中有没有和新元素相同的元素?.
- 你可能会想: 这容易呀, 直接调用元素对象的equals()方法进行比较不就行了吗? 如果容器中的存储的对象数量较少, 这确实是个好主意, 但是如果容器中存放的对象达到了一定的规模, 要调用容器中所有对象的equals()方法和新元素进行比较就不是一件容易的事情了, 就算equals()方法的比较逻辑简单无比, 这也是一个时间复杂度为O(n)的操作啊.
- 但在散列表的基础上判断"新对象是否和容器中任一对象相同"就容易得多了. 由于每个对象都自带有hashCode(), 这个hashCode将会用作散列表哈希函数的输入, hashCode经过哈希函数计算后得到哈希值, 新对象根据哈希值存储到相应的内存的单元.
- 我们不妨假设两个相同的对象, hashCode()一定相同, 这么一来就体现出哈希函数的威力了, 由于相同的输入一定会产生相同的输出, 于是如果新对象和容器中已存在的对象相同, 新对象计算出的哈希值就会和已存在的对象的哈希值产生冲突, 这时容器就能判断: 这个新加入的元素已经存在, 需要另作处理(覆盖掉原来的元素(key)或舍弃).
- 按照这个思路, 如果这个元素计算出的哈希值所对应的地址没有产生冲突, 也就是没有重复的元素, 那么它就可以直接插入. 所以当运用hashCode()时, 判断是否有相同元素的代价只是一次哈希计算, 时间复杂度为O(1), 这极大地提高了数据的存储性能.
- 但是前面我们还提到: 当输入样本量足够大时, 不相同的输入是会产生相同输出的, 也就是形成哈希冲突. 这么一来就麻烦了, 原来我们设定的"如果产生冲突, 就意味着两个对象相同"的规则瞬间被打破, 产生冲突的很有可能是两个不同的对象!
- 而令人欣慰的是我们除了hashCode()方法, 还有一张王牌: equals()方法. 也就是说当两个不相同的对象产生哈希冲突后, 我们可以用equals()方法进一步判断两个对象是否相同. 这时equals()方法就相当重要了, 这个情况下它必须要能判定这两个对象是不相同的.
- 讲到这里就引出了Java程序设计中一些重要原则:
- 如果两个对象是相等的, 它们的equals()方法应该要返回true, 它们的hashCode()需要返回相同的结果.
- 但有时候面试题不会问得这么直接, 它会问你:两个对象的hashCdoe()相同, 它的equals()方法一定要返回true, 对吗?
- 那答案肯定不对. 因为我们不能保证每个程序设计者都会遵循编码规则, 有可能两个不同对象的hashCode()会返回相同的结果. 如果你理解上面的内容, 这个问题就很好解答: 两个对象的hashCode()相同, 将来会在散列表中产生哈希冲突, 但是它们不一定是相同的对象呀. 当产生哈希冲突时, 我们还得通过equals()方法进一步判断两个对象是否相同, equals()方法不一定会返回true.
- 这也是为什么Java官方推荐我们最好同时重写hashCode()和equals()方法的原因.
四. 验证: 结合HashMap的源码和官方文档, 验证两者的关系.
- 通过阅读JDK8的官方文档, 我们发现equals()方法介绍的最后有这么一段话:
- 官方文档提醒我们当重写equals方法的时候, 最好也要重写hashCode()方法. 也就是说如果我们通过重写equals方法判断两个对象相同时, 他们的hash code也应该相同, 这样才能让hashCode()方法发挥它的作用.
- 那它究竟能发会怎样的作用呢? 我们结合部分较为常用的HashMap源码进一步分析. (像HashSet底层也是通过HashMap实现)
- 在HashMap中用得最多无疑是put()方法了, 以下是put()的源码:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}- 我们可以看到put()方法实际调用的是putVal()方法, 继续跟进:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//在我们创建HashMap对象的时候, 内存中并没有为HashMap分配表的空间, 直到往HashMap中put添加元素的时候才调用resize()方法初始化表
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//同时确定了表的长度
//((n - 1) & hash)确定了要put的元素的位置, 如果要插入的地方是空的, 就可以直接插入.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//如果发生了冲突, 就要在冲突位置的链表末尾插入元素
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//关键!!!当判断新加入的元素是否与已有的元素相同, 首先判断的是hash值, 后面再调用equals()方法. 如果hash值不同是直接跳过的
e = p;
else if (p instanceof TreeNode)//如果冲突解决方案已经变成红黑树的话, 按红黑树的策略添加结点.
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//解决冲突的方式仍是链表
for (int binCount = 0; ; ++binCount) {//找到链表的末尾, 插入.
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//插入之后要判断链表的长度, 如果到达一定的值就可能要转换为红黑树.
break;
}//在遍历的过程中仍会不停地判定当前key是否与传入的key相同, 判断的第一条件仍然是hash值.
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;//修改map的次数增加
if (++size > threshold)//如果hashMap的容量到达了一定值就要进行扩容
resize();
afterNodeInsertion(evict);
return null;
}- 我们可以看到每当判断key是否相同的是否, 首先会判断hash值, 如果hash值相同(产生了冲突), 然后会判断key引用所指的对象是否相同, 最终会通过equals()方法作最后的判定.
- 如果key的hash值不同, 后面的判断将不会执行, 直接认定两个对象不相同.
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;- 讲到这里希望大家对hashCode()与equals()方法能有更深入的理解, 明白背后的设计思想与原理.
- 我之前有一个疑问, 可能大家看完这篇文章后也会有: equals()方法平时我会用到, 所以我知道它除了和hashCode()方法有密切联系外, 还有别的用途. 但是hashCode()呢, 它除了和equals()方法有密切联系外, 还有其他用途吗?
- 经过在互联网上一番搜寻, 我目前给出的答案是没有. 也就是说hashCode()仅在散列表中才有用，在其它情况下没用.
- 当然如果这个答案不正确, 或者你还有别的思考, 欢迎留言与我交流~
- 最后欢迎关注我的免费知识星球, 我会在星球中持续更新系统的Java后端面试题分析, 将会囊括Java基础知识到主流框架原理. 还会分享关于编程的趣味漫画.