HashMap的实现原理以及重写equals方法需同时重写hashCode方法

参考文章（本文图文均来自此）：

• https://www.cnblogs.com/jing99/p/11330341.html

本文是在参考文章的基础上自己总结，因为觉得不亲手总结一下不好消化。也请多去原文查看，原文内容比本文生动，有图有代码。如果侵权，请联系我删除！！

前叙：

先看看其他数据结构在查询、新增和删除这几个方面的性能：

• 数组：采用连续的存储空间来存储数据。对于指定下标的查找，时间复杂度为O(1)。对于给定的值的查找，时间复杂度为O(n)，因为要遍历数组，寻找值相等项。但是，对于有序数组的查找，可以使用二分等算法，时间复杂度降为O(logn)；对于一般的插入操作，由于要移动数组元素，所以平均时间复杂度为O(n)。
• 线性链表：对于新增和删除操作（这里指在找到新增和删除的位置后），仅需要处理节点即可，时间复杂度为O(1)；对于查询操作，则需要遍历链表，时间复杂度为O(n)。
• 二叉树：对于有序的平衡二叉树，查找、删除和新增的时间复杂度为O(logn)。
• 哈希表：在哈希表中进行添加，删除，查找等操作，性能很高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。

数据存储的物理结构映射到最底层就是两种：顺序存储结构和链式存储结构。

哈希表的主干是数组，当需要查询某个元素，只需要通过哈希函数将当前关键字映射到数组的对应下标处，然后通过数组下标取值一次即可完成。

哈希冲突：当两个哈希函数计算的地址相同怎么处理？？这就会产生哈希冲突。解决哈希冲突的方法有：开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法。而HashMap即是采用了链地址法，也就是数组+链表的方式。

一、 HashMap的实现原理

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

因此，HashMap的整体结构如下：

HashMap是由数组+链表组成的，数组是HashMap的主体，链表是为了解决哈希冲突而存在的。如果定位到的数组位置不含链表，则查找、添加操作很快，实践复杂度为O(1)。如果定位到数组包含链表，对应于添加操作，时间复杂度为O(1)，对于查找操作时间复杂度就不是O(1)，因为要遍历链表部分。所以，HashMap中链表越少越好，也就是冲突越少越好。
几个重要字段：

//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

中间看源码那一部分先跳过

贴几个重要源码片段

//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
 
        h ^= k.hashCode();
 
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

/**
    * 返回数组下标
    */
   static int indexFor(int h, int length) {
       return h & (length-1);
   }

二、 为什么HashMap的数组长度一定是2的次幂？

数组的索引位置的计算是通过对key的值的hashcode进行hash扰乱运算后，再通过和length-1进行位运算得到最终数组索引位置。

hashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。

从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，这里按作者理解就行。

还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀：

上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。

如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。

三、重写equals方法需同时重写hashCode方法

hashCode()介绍

hashCode()的作用是获取哈希码，也称为散列码；返回一个int整数。这个哈希码的作用就是确定该对象在哈希表中的索引位置。hashCode()定义在JDK的Object.java中，这就意味着Java中的任何类都包含有hashCode()函数.

散列表存储的是键值对(key-value).它的特点是：能根据“键”快速的检索出对应的“值”。这其中就利⽤到了散列码！

hashCode()的作用

当把对象加入HashSet时，HashSet会首先计算对象的hashCode来判断对象加入的位置，同时也会与该位置其它已经加入的对象的hashCode值作比较，如果没有相符的hashCode，则表示要加入的对象没有重复出现。但是如果发现相同的hashCode值的对象，这时就会调用equals()方法来检查hashCode相等的对象是否真的相同。如果两个真的相同，HashSet就不会将其加入操作。如果不同，就会重新排列到其它位置。

所以，hashCode()的作用就是获取哈希码，也称为散列码；它实际上是返回一个int整数。这个哈希码的作用是确定在哈希表中的索引位置。

hashCode()与equals()相关规定

1. 在java应用程序执行期间，如果在equals方法比较中所用的信息没有被修改，那么在同一个对象上多次调用hashCode方法时必须一致地返回相同的整数。如果多次执行同一个应用时，不要求该整数必须相同
2. 如果两个对象通过调用equals方法是相等的，那么这两个对象调用hashCode方法必须返回相同的整数。
3. 如果两个对象通过调用equals方法是不相等的，不要求这两个对象调用hashCode方法必须返回不同的整数。

在Object类中，hashCode方法是通过Object对象的地址计算出来的。因为Object对象只与自身相等，所以同一个对象的地址总是相等的，计算的哈希码也必然相等。对于不同的对象，地址不同，所获得的哈希码自然也不会相等。如果重写了equals()方法，但是没有重写hashCode方法，违反了第二条规定。

示例代码

package equals.src;

import java.util.HashMap;
import java.util.Map;

public class App {
    public static void main(String[] args) {
        Map<String, Value> map1 = new HashMap<String, Value>();
        String s1 = new String("key");
        String s2 = new String("key");
        Value value = new Value(2);
        map1.put(s1, value);    // 把s1和value放到hashMap
        System.out.println("s1.equals(s2):" + s1.equals(s2)); // s1.equals(s2):true
        System.out.println("map1.get(s1):" + map1.get(s1)); // map1.get(s1):类Value的值－－>2
        System.out.println("map1.get(s2):" + map1.get(s2)); // map1.get(s2):类Value的值－－>2

        Map<Key, Value> map2 = new HashMap<Key, Value>();
        Key k1 = new Key("A");
        Key k2 = new Key("A");
        map2.put(k1, value);
        System.out.println("k1.equals(k2):" + k1.equals(k2));   // k1.equals(k2):true
        System.out.println("map2.get(k1):" + map2.get(k1));     // map2.get(k1):类Value的值－－>2
        System.out.println("map2.get(k2):" + map2.get(k2));     // map2.get(k2):null
    }

    static class Key {
        private String k;

        public Key(String key) {
            this.k = key;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Key) {
                Key key = (Key) obj;
                return k.equals(key.k);
            }
            return false;
        }
    }

    static class Value {
        private int v;

        public Value(int v) {
            this.v = v;
        }

        @Override
        public String toString() {
            return "类Value的值－－>" + v;
        }
    }

}

上述代码中：Key这个类重写了equals()方法，但是没有重写hashCode()方法。String类重写了equals方法和hashCode方法。

所以，map1可以得到s1和s2的值，因为String类比较的是内容，它的hashCode也是根据内容获取的哈希码。

map2只能获取k1的值，不能获取到k2的值。这是为什么？？因为Key只重写了equals方法，并没有重写hashCode方法。这样的话，equals方法比较的是内容，所以打印为true。但是hashCode没有被重写，所以就调用超类Object的hashCode方法，而这个方法返回的是一个地址（是根据地址来获取hashcode的）。而k1和k2又是不同的对象，它们的地址肯定不同，所以获得的hashcode也不同。因为k2返回为null

参考文章

• https://blog.csdn.net/javazejian/article/details/51348320
• https://www.cnblogs.com/qianguyihao/p/3929585.html
• https://www.cnblogs.com/jing99/p/11330341.html
• https://www.cnblogs.com/skywang12345/p/3324958.html

本文地址：https://blog.csdn.net/weixin_43207025/article/details/109525431