Java面试题(九):hashcode与equals

1. hashcode与equals

1.1 hashcode介绍

hashcode()的作用是获取哈希码,也称为散列码;它实际上是返回一个int整数。这个哈希码的作用是确定该对象在哈希表中的索引位置。hashcode()定义在JDK的Object.java中,Java中的任何类都包含有hashcode()函数。散列码存储的是键值对,它的特点是:能根据键快速的检索出对应的值。这其中就利用到了散列码。(可以快速找到所需要的对象)

1.2 为什么要有hashcode

以hashset如何检查重复为例子来说明为什么要有hashcode:

对象加入hashset时,hashset会先计算对象的hashcode值来判断对象加入的位置,看该位置是否有值,如果没有,hashset会假设对象没有重复出现。但如果发现有值,这时会调用equals()方法来检查两个对象是否真的相同。如果两者相同,hashset就不会让其加入操作成功。如果不同,就会重新散列到其他位置。这样就大大减少了equals的次数,相应的大大提高了执行速度。

如果两个对象相等,则hashcode一定也是相同的。

两个对象相等,对两个对象分别调用equals方法都返回true。

两个对象有相同的hashcode,它们也不一定相等的。

因此,equals方法被覆盖过,则hashcode方法也必须被覆盖

hashcode()默认行为是对堆上的对象产生独特值。如果没有重写hashcode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

1.3 深入理解 hashCode() 和 equals() 之间的关系

1.3.1 equals() 会有力不从心的时候

上面提到 Set 和 Map 不存放重复的元素(key),这些容器在存储元素的时必须对元素做出判断:在当前的容器中有没有和新元素相同的元素?

你可能会想:这容易呀,直接调用元素对象的 equals() 方法进行比较不就行了吗?

如果容器中的存储的对象数量较少,这确实是个好主意,但是如果容器中存放的对象达到了一定的规模,要调用容器中所有对象的 equals() 方法和新元素进行比较,就不是一件容易的事情了。

就算 equals() 方法的比较逻辑简单无比,总的来说也是一个时间复杂度为 O(n) 的操作啊。

1.3.2 hashCode() 小力出奇迹

但在散列表的基础上,判断“新对象是否和已存在对象相同”就容易得多了。

由于每个对象都自带有 hashCode(),这个 hashCode 将会用作散列表哈希函数的输入,hashCode 经过哈希函数计算后得到哈希值,新对象会根据哈希值,存储到相应的内存的单元。

我们不妨假设两个相同的对象,hashCode() 一定相同,这么一来就体现出哈希函数的威力了。

由于相同的输入一定会产生相同的输出,于是如果新对象,和容器中已存在的对象相同,新对象计算出的哈希值就会和已存在的对象的哈希值产生冲突。

这时容器就能判断:这个新加入的元素已经存在,需要另作处理:覆盖掉原来的元素(key)或舍弃。

按照这个思路,如果这个元素计算出的哈希值所对应的内存单元没有产生冲突,也就是没有重复的元素,那么它就可以直接插入。

所以当运用 hashCode() 时,判断是否有相同元素的代价,只是一次哈希计算,时间复杂度为O(1),这极大地提高了数据的存储性能。

1.3.3 Java 设计 equals(),hashCode() 时约定的规则

前面我们还提到:当输入样本量足够大时,不相同的输入是会产生相同输出的,也就是形成哈希冲突。

这么一来就麻烦了,原来我们设定的“如果产生冲突,就意味着两个对象相同”的规则瞬间被打破,因为产生冲突的很有可能是两个不同的对象!

而令人欣慰的是我们除了 hashCode() 方法,还有一张王牌:equals() 方法。

也就是说当两个不相同的对象产生哈希冲突后,我们可以用 equals() 方法进一步判断两个对象是否相同。

这时 equals() 方法就相当重要了,这个情况下它必须要能判定这两个对象是不相同的。

  • 讲到这里就引出了 Java 程序设计中一个重要原则:

如果两个对象是相等的,它们的 equals() 方法应该要返回 true,它们的 hashCode() 需要返回相同的结果

但有时候面试不会问得这么直接,他会问你:两个对象的 hashCdoe() 相同,它的 equals() 方法一定要返回 true,对吗?

那答案肯定不对。因为我们不能保证每个程序设计者,都会遵循编码约定。

有可能两个不同对象的hashCode()会返回相同的结果,但是由于他们是不同的对象,他们的 equals() 方法会返回false。

如果你理解上面的内容,这个问题就很好解答,我们再回顾一下:

如果两个对象的 hashCode() 相同,将来就会在散列表中产生哈希冲突,但是它们不一定是相同的对象呀。

当产生哈希冲突时,我们还得通过 equals() 方法进一步判断两个对象是否相同,equals() 方法不一定会返回 true。

这也是为什么 Java 官方推荐我们在一个类中,最好同时重写 hashCode() 和 equals() 方法的原因。

上一篇:linux基本命令之stat


下一篇:【Java基础】Java拷贝