为何重写equals()必须重写hashCode()？

发表于 Changyan： 
1
2
3
4
5
6
7
8
public class Object {
    public boolean equals(Object obj) {
        return (this == obj);
    }
    
	public native int hashCode();
    
}

为了重写equals()必须重写hashCode()？

1 重写规则

官方重写规则：

  1. 如果重写了equals方法，那么一定要重写hashCode方法。如果只是重写hashCode方法，那么不必须重写equals方法。你可以理解为equals方法比较娇贵，每次自己有变化，都要拉hashcode方法下水。

  2. 如果你只是重写了hashcode方法而没有重写equals方法（前面说过，这是允许的），那么也要受限于以下原则：

    • 在equals方法没被修改的前提下，多次调用同一对象的hashcode方法返回的值必须是相同的整数；

    • 如果两个对象互相equals，那么这两个对象的hashcode值必须相等；

    • 为不同对象生成不同的hashcode可以提升哈希表的性能；

2 equals() && hashcode()

在开始之前，你必须了解这两个方法各自的含义，这两个概念并不难，网上已经说烂了，我也不想再赘述。但是有些博客会犯一个错误，那就是将Object中的hashcode()与HashMap中的hash()混为一谈。然而实际上，hashcode方法是Object的方法，hash()是HashMap或HashSet中的方法，二者并须相同。

1
2
3
4
5
6
7
8
public class Object {
    public boolean equals(Object obj) {
        return (this == obj);
    }
    
	public native int hashCode();
    
}

HashMap从Object继承了equals方法和hashcode方法，并且自身又添加了属于自己的hash方法。而hash方法才是真正用来计算元素在hash数组中的定位的，并不是hashcode方法。

1
2
3
4
5
6
public class HashMap {
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}

3 为何一起重写？

equals()和hashCode()一起重写的规则，与Java中涉及到Hash运算的容器类，例如HashSet、HashMap有密不可分的关系。这里以HashSet为代表，从问题出发讲解为什么重写equals必须重写hashcode。因此，在这之前，建议你先对Set实现元素唯一性有足够的了解。

3.1 跑不掉的Set唯一性检查

Java中的Collection有两类，一类是List，一类是Set。List内的元素是有序的，元素可以重复。Set元素无序，但元素不可重复。要想保证元素不重复，我们最首先能想到的最简单粗暴的方式就是用Object.equals方法。但若每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。也就是说若集合中已有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。于是为了提升Set的唯一性检查的效率，Java引入了了哈希表的特性，这就是Set的一个实现：HashSet。当然，你也可能会想到用别的方法进行唯一性检查，比如二叉排序树将比较的时间复杂度降到 lgn？好巧不巧，Java团队也想到了！除了用Hash思想来提高Set唯一性检查的性能外，Java官方也想到了引入二叉排序树的思想，于是又有了Set的另一个实现：TreeSet。但是我们今天先只看HashSet，对于TreeSet，你只需要清楚，这两个只不过是为了提高Set唯一性检查的性能采用了不同的手段，又导致了不同的特性。

​

当Set接收一个元素时根据，会对该对象的hashCode方法产生的结果（以后称其为hash值）进行进一步的hash()运算，这个hash才是真正的寻位hash，寻位hash的结果将决定这个对象存储到哪一个链表上，再在这个链表里调用equeals方法来检查唯一性，这样就大幅降低了插入元素时需要进行比较的次数：从全局元素比较变成只跟一条拉链上的元素比较。

​

3.2 提高性能带来的问题

上面方法确实提高了效率。但一个面临问题：hashSet原理是先按hashcode的hash()结果分，假如，重写了equals却没有重写hashcode()，两个对象equals相等，hashcode却不同（如果你不重写hashcode()，那就是默认使用对象内存地址，不同对象的内存地址必不相同）。那么这两个对象会被存到不同的拉链上，根本不会触发equals方法，结果都被放进HashSet了。给我们的感觉就是，两个在逻辑上equals的对象，却被Set全都存入了，逻辑与实际矛盾。

​

3.3 解决方法

那当然就是重写equals一定要重写hashcode了！修改equals方法一定要修改hashcode（），不要不以为意！默认的hashcode（）是对象的地址，而如果我们重写了euqals（）使得两个地址不同的对象具有逻辑上（也就是equals（））的相等性。那么对这种元素使用set【必定】会出bug。因为两个对象的地址一定是不一样的，默认hashcode（）使用地址的情况下，set必定会将任意两个使用默认hash’code（）的对象认为是不相同的。

4 总结

  • hashcode的存在就是为了hash表（hashmap或者hashset）没别的用。

  • 在hashset中，判断元素不唯一的标准是：先要落在同一条拉链上（hashcode相同），再用equals方法判断唯一性。如果没落在同一个拉链上（hashcode不相等），就不会触发equals相等的情况。Set 认为他们不一样。

  • 为什么set在判断两个对象是否相等的时候，要落到同一个拉链上再进行equals比较呢，为什么不直接就进行比较呢？因为set里面元素如果很多，来一个元素直接跟set中所有的对象挨个遍历进行比较，会极其耗时。所以先用hashcode（） 进行定位，就可以将比较equals的范围缩短到这一条拉链上，极大提高效率。所以这个先hashcode（）再equals的初衷其实是为了提高性能。

  • 官方要求保证”*equals***相等一定要hashcode相等，hashcode相等不一定equals相等“的原因就是 3。