编写equals和hashCode
以HashMap为例,观察下面的代码:
之所以能根据key
直接拿到value
,原因是它内部通过空间换时间的方法,用一个大数组存储所有value
,并根据key直接计算出value
应该存储在哪个索引:
┌───┐
0 │ │
├───┤
1 │ ●─┼───> Person("Xiao Ming")
├───┤
2 │ │
├───┤
3 │ │
├───┤
4 │ │
├───┤
├───┤
6 │ ●─┼───> Person("Xiao Jun")
├───┤
7 │ │
└───┘
如果key
的值为"a"
,计算得到的索引总是1
,因此返回value
为Person("Xiao Ming")
,如果key
的值为"b"
,计算得到的索引总是5
,因此返回value
为Person("Xiao Hong")
,这样,就不必遍历整个数组,即可直接读取key
对应的value
。
当我们使用key
存取value
的时候,就会引出一个问题:
我们放入Map
的key
是字符串"a"
,但是,当我们获取Map
的value
时,传入的变量不一定就是放入的那个key
对象。
换句话讲,两个key
应该是内容相同,但不一定是同一个对象。测试代码如下:
因为在Map
的内部,对key
做比较是通过equals()
实现的,这一点和List
查找元素需要正确覆写equals()
是一样的,即正确使用Map
必须保证:作为key
的对象必须正确覆写equals()
方法。
我们经常使用String
作为key
,因为String
已经正确覆写了equals()
方法。但如果我们放入的key
是一个自己写的类,就必须保证正确覆写了equals()
方法。
我们再思考一下HashMap
为什么能通过key
直接计算出value
存储的索引。相同的key
对象(使用equals()
判断时返回true
)必须要计算出相同的索引,否则,相同的key
每次取出的value
就不一定对。
通过key
计算索引的方式就是调用key
对象的hashCode()
方法,它返回一个int
整数。HashMap
正是通过这个方法直接定位key
对应的value
的索引,继而直接返回value
。
因此,正确使用Map
必须保证:
作为的对象必须正确覆写
equals()
方法,相等的两个key
实例调用equals()
必须返回true
;作为
key
的对象还必须正确覆写hashCode()
方法,且hashCode()
方法要严格遵循以下规范:
- 如果两个对象相等,则两个对象的
hashCode()
必须相等; - 如果两个对象不相等,则两个对象的
hashCode()
尽量不要相等。
即对应两个实例a
和b
:
- 如果
a
和b
相等,那么a.equals(b)
一定为true
,则a.hashCode()
必须等于b.hashCode()
; - 如果
a
和b
不相等,那么a.equals(b)
一定为false
,则a.hashCode()
和b.hashCode()
尽量不要相等。
而第二条如果尽量满足,则可以保证查询效率,因为不同的对象,如果返回相同的hashCode()
,会造成Map
内部存储冲突,使存取的效率下降。
正确编写equals()
的方法我们已经在编写equals方法一节中讲过了,以Person
类为例:
public class Person {
String firstName;
String lastName;
}
把需要比较的字段找出来:
- firstName
- lastName
- age
然后,引用类型使用Objects.equals()
比较,基本类型使用==
比较。
在正确实现equals()
的基础上,我们还需要正确实现hashCode()
,即上述3个字段分别相同的实例,hashCode()
返回的int
必须相同:
注意到String
类已经正确实现了hashCode()
方法,我们在计算Person
的hashCode()
时,反复使用31*h
,这样做的目的是为了尽量把不同的Person
实例的hashCode()
均匀分布到整个int
范围。
和实现equals()
方法遇到的问题类似,如果firstName
或lastName
为null
,上述代码工作起来就会抛NullPointerException
。为了解决这个问题,我们在计算hashCode()
的时候,经常借助Objects.hash()
来计算:
int hashCode() {
return Objects.hash(firstName, lastName, age);
}
所以,编写equals()
和hashCode()
遵循的原则是:
equals()
用到的用于比较的每一个字段,都必须在hashCode()
中用于计算;equals()
中没有使用到的字段,绝不可放在hashCode()
中计算。
另外注意,对于放入HashMap
的value
对象,没有任何要求。
既然HashMap
内部使用了数组,通过计算key
的hashCode()
直接定位value
所在的索引,那么第一个问题来了:hashCode()返回的int
范围高达±21亿,先不考虑负数,HashMap
内部使用的数组得有多大?
实际上HashMap
初始化时默认的数组大小只有16,任何key
,无论它的有多大,都可以简单地通过:
int index = key.hashCode() & 0xf; // 0xf = 15
把索引确定在0~15,即永远不会超出数组范围,上述算法只是一种最简单的实现。
第二个问题:如果添加超过16个key-value
到HashMap
,数组不够用了怎么办?
添加超过一定数量的key-value
时,HashMap
会在内部自动扩容,每次扩容一倍,即长度为16的数组扩展为长度32,相应地,需要重新确定hashCode()
计算的索引位置。例如,对长度为32的数组计算hashCode()
对应的索引,计算方式要改为:
Map<String, Integer> map = new HashMap<>(10000);
虽然指定容量是10000
,但HashMap
内部的数组长度总是2n,因此,实际数组长度被初始化为比10000
大的16384
(214)。
最后一个问题:如果不同的两个key
,例如"a"
和"b"
,它们的hashCode()
恰好是相同的(这种情况是完全可能的,因为不相等的两个实例,只要求hashCode()
尽量不相等),那么,当我们放入:
map.put("a", new Person("Xiao Ming"));
map.put("b", new Person("Xiao Hong"));
时,由于计算出的数组索引相同,后面放入的"Xiao Hong"
会不会把"Xiao Ming"
覆盖了?
当然不会!使用Map
的时候,只要key
不相同,它们映射的value
就互不干扰。但是,在HashMap
内部,确实可能存在不同的key
,映射到相同的hashCode()
,即相同的数组索引上,肿么办?
我们就假设"a"
和"b"
这两个key
最终计算出的索引都是5,那么,在HashMap
的数组中,实际存储的不是一个Person
实例,而是一个List
,它包含两个Entry
,一个是"a"
的映射,一个是"b"
的映射:
在查找的时候,例如:
Person p = map.get("a");
HashMap内部通过"a"
找到的实际上是List<Entry<String, Person>>
,它还需要遍历这个List
,并找到一个Entry
,它的key
字段是"a"
,才能返回对应的Person
实例。
我们把不同的key
具有相同的hashCode()
的情况称之为哈希冲突。在冲突的时候,一种最简单的解决办法是用List
存储hashCode()
相同的key-value
。显然,如果冲突的概率越大,这个List
就越长,Map
的get()
方法效率就越低,这就是为什么要尽量满足条件二:
如果两个对象不相等,则两个对象的hashCode()尽量不要相等。
hashCode()
方法编写得越好,HashMap
工作的效率就越高。
要正确使用HashMap
,作为key
的类必须正确覆写equals()
和hashCode()
方法;
一个类如果覆写了equals()
,就必须覆写hashCode()
,并且覆写规则是:
如果
equals()
返回true
,则hashCode()
返回值必须相等;如果
equals()
返回false
,则hashCode()
返回值尽量不要相等。
实现hashCode()
方法可以通过辅助方法实现。