为什么要重写hashCode与equals()方法?

为什么要重写equals()方法？

在比较数值类型的变量或者null时，我们常用==来进行比较两者是否相同。这样比较的背后逻辑是比较两者的内存地址，如果两者指向的内存地址相同，显然地，这两者肯定就是一个东西肯定也就是相同的。

那如果比较的是引用类型的数据呢，比如String、自定义的Student类呢？

这时我们就不能用==或者Object类（所有类的超类）的equals()方法来直接比较他们的内存地址。因为即使是相同的字符串内容，他们也可能有着不同的内存地址，比如使用了clone()创建的一个新变量。而对于自定义的类实例化对象来说，只要他们所拥有的属性都是相同的，我们一般是认为他们两个对象是相等的，因为我们看重的就是这些对象的属性，但是此时不同的对象的内存地址肯定是不相同的。

这样一来，一种新的比较方法就需要被提供，即重写equals方法，使得我们只关注String的内容与自定义类的属性值。而具体的equals如何重写便又是一个新的问题了，因为涉及到OOP的多态特性，以及null等等情况。

什么是hashCode？

hashCode是通过hash算法根据一些参数（内存地址、随机数、指定值等等）输出的一个整数。

什么是hash算法？ 哈希（hash）算法又称为散列算法，通过hash算法，可以将任意长度的信息转换成一个固定长度的二进制数据，我们经常会使用十六进制值来表示转换后的信息。 不同的信息，理论上得到的hashCode不同，我们称之为“无碰撞”，或者发生“碰撞”的概率非常小。而相同的信息一定会得到相同的hashCode。我们把得到的hashCode作为这个对象的签名。

比如，String类的hashCode()函数的内容是：

public int hashCode() {
        // 起到缓存的效果, 防止反复计算 hashCode
        int h = hash;  
        // 如果 h != 0, 说明已经计算过 hashCode 了, 直接返回缓存值即可
        if (h == 0 && value.length > 0) {
            char val[] = value;

            // 计算的核心步骤是这个 for 循环
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
}

由于 hashCode方法定义在 Object类中，因此每个对象都有一个默认的hashCode，其值为对象的存储地址。

介绍半天hashCode，他到底有什么用呢？

hashCode的用处

我们先复习数据结构里的一个知识点：在一个长度为n（假设是10000）的线性表（假设是ArrayList）里，存放着无序的数字；如果我们要找一个指定的数字，就不得不通过从头到尾依次遍历来查找，这样的平均查找次数是n除以2。

我们再来观察Hash表。它的平均查找次数接近于1，代价相当小，关键是在Hash表里，存放在其中的数据和它的存储位置是用Hash函数关联的。我们假设一个Hash函数是x*x%5，Hash表是一个长度是11的线性表。关于hash表，可以看下面这篇文章：

习翔宇：哈希表(Hashtable)17 赞同 · 0 评论文章

如果我们要把6放入其中，那么我们首先会对6用Hash函数计算一下，结果是1，所以我们就把6放入到索引号是1这个位置。同样如果我们要放数字7，经过Hash函数计算，7的结果是4，那么它将被放入索引是4的这个位置。这个效果如下图所示。

这样做的好处非常明显。比如我们要从中找6这个元素，我们可以先通过Hash函数计算6的索引位置，然后直接从1号索引里找到它了。

不过我们会遇到“碰撞”问题。比如经过Hash函数计算后，7和8会有相同的Hash值4，对此Java的HashMap对象采用的是”链地址法“的解决方案。效果如下图所示。

具体的做法是，为所有Hash值是i的对象建立一个同义词链表。假设我们在放入8的时候，发现4号位置已经被占，那么就会新建一个链表结点放入8。同样，如果我们要找8，那么发现4号索引里不是8，那会沿着链表依次查找。

hashCode就只是为了减少查找元素的耗时？

其实不止，我们知道HashMap的特性是不允许存放相同的key值，而当我们将String或者自定义的类对象作为key值并且向Map中加入元素时，HashMap会首先计算要加入的元素的hashCode，并且从hash表中查询是否此hashCode已经存在，如果已经存在，HashMap将会继续调用对象的equals方法来比较相同hashCode的两个元素是否相等，如果相等的话，这个元素就不会被放入到HashMap中；如果不相等的话，说明我们虽然碰到了hashCode碰撞问题，但实际上两个元素并不相同，可以将后来者放入到HashMap。显然，他俩是在一个索引处，此时采用的是”链地址法“的解决方案。如果一开始hash表中就不存在与后者hashCode相同的元素，说明HashMap中还没有这个元素，可以放入。

为什么要重写hashCode()方法？

上面提到首先会调用要加入的元素的的hashCode()方法来计算它的hashCode，而如果没有进行hashCode()方法重写，调用hashCode方法默认返回的是对象的内存地址，这样一来内存地址那肯定是一个东西，内存地址不一样的东西我们也不一定认为他们就是完全不同的，因为我们关注的是自定义类的属性值是否相等，String的内容是否相等，而非他们的内存地址是否一致，所以有必要重写作为key值的自定义类的hashCode()，具体的重写逻辑肯定考虑的是自定义类的属性值相关的算法。

此处没有说重写String类的hashCode()方法，是因为： 根据上面的hashCode()方法，我们可以知道，String类的equals方法已经被重写过，此时的equals()注重的是组成字符串的每一个字符内容

另外，上面提到过，HashMap会继续调用equals方法来比较hashCode相同的两个作为key的两个元素是否完全一致，请注意，equals在没有被重写之前，都是Object类的实现方式，即比较两者的内存地址，显然，回到了一开始我们关于为什么要重写equals的场景分析，此时我们关注的是自定义类的属性值是否相等，String的内容是否相等，而非他们的内存地址是否一致！所以此时重写equals方法便显得迫在眉睫。

总结

如果要把自定义的类的实例化对象作为HashMap的key，一定要重写这个类的equals()方法和hashCode()方法。

hashCode相同的两个对象不一定相等，但是相等的两个对象的hashCode一定相等，不相等的两个对象的hashCode一般是不相等的，但是不排除数字溢出等情况。

在重写equals方法的时候可以把判断两个对象的hashCode作为第一步以此来加速比较逻辑。

在hashmap中是通过hashcode决定元素放入哪个索引（桶）中，然后通过equals判断和索引中对应链表中的每个元素是否相同，如果有相同的 ->不放，如果没有相同的 -> 放 （ jdk version >8尾插法、<8头插法）

如果不重写hashcode方法，hash值就是地址值；重写hashcode方法，hash值是根据对象中的成员变量值经过一系列的算法求得。如果不重写equals方法，调用equals方法默认走地址值；重写equals方法后调用equals是一般通过比较成员变量值。

如果在hashmap中如果只重写了hashcode没重写equals：

如果我们添加两个相同内容的User对象放入hashmap，添加完第一个User后，添加第二个User时，hash值和第一个User相同，会走equals到同一个索引中找是否存在相同的元素，此时我们因为没重写equals，比较的是地址值（两个虽然内容相同的对象地址值是不同的），因此第二个相同的User也插入到了同一个索引中。

如果在hashmap中如果只重写了equals没重写hashcode：

两个虽然内容相同的对象地址值是不同的，因为没重写hashcode，hash值是地址值 ===> 两个相同内容的对象地址值不同，hash值也不同 ===> 他们两个被放到了hashmap不同的索引中。