Java-容器-一文详解HashMap

Map 类集合

Java Map 类集合，与 Collections 类集合存在很大不同。它是与 Collection 类平级的一个接口。

在集合框架中，通过部分视图方法这一根 微弱的线联系起来。

（在之后的分享中，我们会讨论到 Collections 框架的内容）

Map 类集合中的存储单位是 K - V 键值对，就是 使用一定的哈希算法形成一组比较均匀的哈希值作为 Key，Value 值挂在 Key 上。

Map 类 的特点：

• 没有重复的 Key，可以具有多个重复的 Value
• Value 可以是 List/Map/Set 对象
• KV 是否允许为 null，以实现类的约束为准

Map 集合类	Key	Value	Super	JDK	说明
Hashtable	不允许为 null	不允许为 null	Dictionary	1.0	（过时）线程安全类
ConcurrentHashMap	不允许为 null	不允许为 null	AbstractMap	1.5	锁分段技术或 CAS（JDK8 及以上）
TreeMap	不允许为 null	允许为 null	AbstractMap	1.2	线程不安全（有序）
HashMap	允许为 null	允许为 null	AbstractMap	1.2	线程不安全（resize 死链问题）

从 jdk1.0-1.5，这几个重点 KV 集合类，见证了 Java 语言成为工业级语言的成长历程。

知识点：

1. Map 类 特有的三个方法是 keySet()、values()、entrySet()，其中values() 方法返回的视图的集合实现类是Values extends AbstractCollection<V>，没有实现 add 操作，实现了 remove/clear 等相关操作，调用 add 方法时会抛出异常。
2. 在大多数情况下，直接使用 ConcurrentHashMap 替代 HashMap 没有任何问题，性能上面差别不大，且线程安全。
3. 任何 Map 类集合中，都要尽量避免 KV 设置为 null 值。
4. Hashtable – HashMap – ConcurrentHashMap 之间的关系 大致相当于 Vector – ArrayList – CopyOnWriteArrayList 之间的关系，当然 HashMap 和 ConcurrentHashMap 之间性能差距更小。

一、hashCode()

哈希算法 哈希值

在 Object 类中，hashCode()方法是一个被 native 修饰的类，JavaDoc 中描述的是返回该对象的哈希值。

那么哈希值这个返回值是有什么作用呢？

主要是保证基于散列的集合，如 HashSet、HashMap 以及 HashTable 等，在插入元素时保证元素不可重复，同时为了提高元素的插入删除便利效率而设计；主要是为了查找的便捷性而存在。

拿 Set 进行举例，

众所周知，Set 集合是不能重复，如果每次添加数据都拿新元素去和集合内部元素进行逐一地 equal()比较，那么插入十万条数据的效率可以说是非常低的。

所以在添加数据的时候就出现了哈希表的应用，哈希算法也称之为散列算法，当添加一个值的时候，先去计算出它的哈希值，根据算出的哈希值将数据插入指定位置。这样的话就避免了一直去使用 equal()比较的效率问题。

具体表现在：

• 如果指定位置为空，则直接添加
• 如果指定位置不为空，调用 equal() 判断两个元素是否相同，如果相同则不存储

上述第二种情况中，如果两个元素不相同，但是 hashCode()相同，那就是发生了我们所谓的哈希碰撞。

哈希碰撞的概率取决于 hashCode()计算方式和空间容量的大小。

这种情况下，会在相同的位置，创建一个链表，把 key 值相同的元素存放到链表中。

在 HashMap 中就是使用拉链法来解决 hashCode 冲突。

总结

hashCode 是一个对象的标识，Java 中对象的 hashCode 是一个 int 类型值。通过 hashCode 来指定数组的索引可以快速定位到要找的对象在数组中的位置，之后再遍历链表找到对应值，理想情况下时间复杂度为 O(1)，并且不同对象可以拥有相同的 hashCode。

HashMap 底层实现

带着问题

1. HashMap 的长度为什么默认初始长度是 16，并且每次 resize()的时候，长度必须是 2 的幂次方？
2. 你熟悉 HashMap 的扩容机制吗？
3. 你熟悉 HashMap 的死链问题吗？
4. Java 7 和 Java 8 HashMap 有哪些差别？
5. 为什么 Java 8 之后，HashMap、ConcurrentHashMap 要引入红黑树？

0. 简介

1. HashMap 基于哈希表的 Map 接口实现的，是以 Key-Value 存储形式存在；
2. 非线程安全；
3. key value 都可以为 null；
4. HashMap 中的映射不是有序的；
5. 在 JDK1.8 中，HashMap 是由 数组 + 链表 + 红黑树构成，新增了红黑树作为底层数据结构；
6. 当一个哈希桶存储的链表长度大于 8 会将链表转换成红黑树，小于 6 时则从红黑树转换成链表；
7. 1.8 之前和 1.8 及以后的源码，差别较大

1. 存储结构

在 JDK1.8 中，HashMap 是由 数组 + 链表 + 红黑树构成，新增了红黑树作为底层数据结构。

通过哈希来确认到数组的位置，如果发生哈希碰撞就以链表的形式存储，但是这样如果链表过长来的话，HashMap 会把这个链表转换成红黑树来存储，阈值为 8。

下面是 HashMap 的结构图：

2. 重要属性

2.1 table

      /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

在 JDK1.8 中我们了解到 HashMap 是由数组加链表加红黑树来组成的结构其中 table 就是 HashMap 中的数组。

2.2 size

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

HashMap 中 键值对存储数量。

2.3 loadFactor

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

负载因子。负载因子是权衡资源利用率与分配空间的系数 。当 元素总量 > 数组长度 * 负载因子 时会进行扩容操作。

2.4 threshold

    /**
     * The next size value at which to resize (capacity * load factor).
     *
     * @serial
     */
    // (The javadoc description is true upon serialization.
    // Additionally, if the table array has not been allocated, this
    // field holds the initial array capacity, or zero signifying
    // DEFAULT_INITIAL_CAPACITY.)
    int threshold;

扩容阈值。threshold = 数组长度 * 负载因子。超过后执行扩容操作。

2.5 TREEIFY_THRESHOLD/UNTREEIFY_THRESHOLD

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

树形化阈值。当一个哈希桶存储的链表长度大于 8 会将链表转换成红黑树，小于 6 时则从红黑树转换成链表。

3. 增加元素

    public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
    }

3.1 hash()

可以看到实际执行添加元素的是 putVal()操作，在执行 putVal()之前，先是对 key 执行了 hash()方法，让我们看下里面做了什么

    static final int hash(Object key) {
        int h;
        // key.hashCode()：返回散列值也就是 hashcode
        // ^：按位异或
        // >>>: 无符号右移，忽略符号位，空位都以 0 补齐
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

key==null说明，HashMap 中是支持 key 为 null 的情况的。

同样的方法在 Hashstable 中是直接用 key 来获取 hashCode，没有 key==null 的判断，所以 Hashstable 是不支持 key 为 null 的。

再回来说这个 hash()方法。这个方法用专业术语来称呼就叫做 扰动函数。

使用 hash()也就是扰动函数，是 为了防止一些实现比较差的 hashCode()方法 。换句话来说， 就是为了减少哈希碰撞。

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。我们再看下 JDK1.7 中是怎么做的。

        // code in JDK1.7
        static int hash(int h) {
            // This function ensures that hashCodes that differ only by
            // constant multiples at each bit position have a bounded
            // number of collisions (approximately 8 at default load factor).
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

​

知识延伸外链：JDK 源码中 HashMap 的 hash 方法原理是什么？– 胖君的回答 – 知乎
https://www.zhihu.com/questio…

3.2 putVal()

再来看真正执行增加元素操作的 putVal()方法，

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 当数组为空或长度为 0，初始化数组容量（resize() 方法是初始化或者扩容用的）if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 计算数组下标 i = (n-1) & hash
        // 如果这个位置没有元素，则直接创建 Node 并存值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            // 这个位置已有元素
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // hash 值、key 值相等，用 e 变量获取到当前位置这个元素的引用，后面用于替换已有的值
                e = p;
            else if (p instanceof TreeNode)
                // 当前是以红黑树方式存储，执行其特有的 putVal 方法 -- putTreeVal
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 当前是以链表方式存储，开始遍历链表
                for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {
                        // 这里是插入到链表尾部！p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 超过阈值，存储方式转化成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // onlyIfAbsent 如果为 true - 不覆盖已存在的值
                    // 把新值赋值进去
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 记录修改次数
        ++modCount;
        // 判断元素数量是否超过阈值 超过则扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

3.3 HashMap 的长度为什么默认初始长度是 16，并且每次 resize()的时候，长度必须是 2 的幂次方？

这是一个常见的面试题。这个问题描述的设计，实际上为了服务于从 Key 映射到数组下标 index 的 Hash 算法。

前面提到了，我们为了让 HashMap 存储高效，应该尽量减少哈希碰撞，也就是说，应该让元素分配得尽可能均匀。

Hash 值的范围值 -2147483648 到2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。

所以才需要一个映射的算法。这个计算方式就是 3.2 中有出现的(n - 1) & hash。

我们来进一步演示一下这个算法：

1. 假设有一个key="book"
2. 计算 book 的 hashCode 值，结果为十进制的 3029737，二进制的 101110001110101110 1001。
3. 假定 HashMap 长度是默认的 16，计算 Length- 1 的结果为十进制的 15，二进制的 1111。
4. 把以上两个结果做 与运算，101110001110101110 1001 & 1111 = 1001，十进制是 9，所以 index=9。

通过这种 与运算 的方式，能够和取模运算一样的效果hashCode % length，在上述例子中就是3029737 % 16=9。

并且通过位运算的方式大大提高了性能。

可能到这里，你还是不知道为什么长度必须是 2 的幂次方，也是因为这种位运算的方法。

长度 16 或者其他 2 的幂，Length- 1 的值是所有二进制位全为 1，这种情况下，index 的结果等同于 HashCode 后几位的值。只要输入的 HashCode 本身分布均匀，Hash 算法的结果就是均匀的。如果 HashMap 的长度不是 2 的幂次方，会出现某些 index 永远不会出现的情况，这个显然不符合均匀分布的原则和期望。所以在源码里面一直都在强调 power-of-two expansion 和size must be power of two。

另外，HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

4. HashMap 扩容

接下来我们来讲讲 HashMap 扩容相关的知识。

4.1 扩容

HashMap 的初始长度是 16，假设 HashMap 中的键值对一直在增加，但是 table 数组容量一直不变，那么就会发生哈希碰撞，查找的效率肯定会越来越低。所以当键值对数量超过某个阈值的时候，HashMap 就会执行扩容操作。

那么扩容的阈值是怎么计算的呢？

阈值 = 数组长度 * 负载因子

threshold = capacity * loadFactor

每次扩容后，threshold 加倍

上述计算就出现在 resize()方法中。下面会详细解析这个方法。我们先继续往下讲。

loadFactor 这个参数，我们之前提到过，负载因子是权衡资源利用率与分配空间的系数。至于为什么是 0.75 呢？这个实际上就是一个作者认为比较好的权衡，当然你也可以通过构造方法手动设置负载因子。public HashMap(int initialCapacity, float loadFactor) {...)。

接下去再来到这里的主角 resize()方法

    final Node<K,V>[] resize() {
        // 旧数组引用
        Node<K,V>[] oldTab = table;
        // 旧数组长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 旧阈值
        int oldThr = threshold;
        // 新数组长度、新阈值
        int newCap, newThr = 0;
        if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {
                // 旧数组已经超过了数组的最大容量
                // 阈值改成最大，直接返回旧数组，不操作了
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // newCap 变成原来的 两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 执行扩容操作，新阈值 = 旧阈值 * 2
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            // 初始阈值被手动设置过
            // 数组容量 = 初始阈值
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 初始化操作
            // 数组容量 = 默认初始容量
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 初始阈值 = 容量 * 默认负载因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 如果在前面阈值都没有被设置过
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 更新阈值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            // 创建数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 更新 table 引用的数组
        table = newTab;
        if (oldTab != null) {
            // 扩容
            for (int j = 0; j < oldCap; ++j) {
                // 遍历旧数组
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    // 取出这个位置的头节点
                    // 把旧引用取消，方便垃圾回收
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 红黑树的处理
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        ....
                    }
                }
            }
        }
        return newTab;
    }

                        // 链表的处理  这个链表处理实际上非常的巧妙
                        // 定义了两条链
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }

上述代码红黑树和链表的处理不知道大家看懂了没有，我反正在第一次看的时候有点晕乎。但是理解了之后有感觉非常的巧妙。

拿链表处理打比方，它干的就是把在遍历旧的 table 数组的时候，把该位置的链表分成 high 链表和 low 链表。具体是什么意思呢？看下下面的举例。

1. 有一个 size 为 16 的 HashMap。有 A /B/C/D/E/ F 六个元素，其中 A /B/ C 的 Hash 值为 5，D/E/ F 的 Hash 值为 21，我们知道计算数组下标的方法是 与运算（效果相当于取模运算），这样计算出来，A/B/C/D/E/ F 的 index = 5，都会被存在 index= 5 的位置上中。
2. 假设它们是依次插入，那么在 index 为 5 的位置上，就会有 A->B->C->D->E->F 这样一个链表。
3. 当这个 HashMap 要进行扩容的时候，此时我们有旧数组 oldTable[]，容量为 16，新数组 newTable[]，容量为 32（扩容数组容量加倍）。
4. 当遍历到旧数组 index= 5 的位置的时候，进入到上面提到的链表处理的代码段中，对链表上的元素进行 Hash & oldCapacity 的操作，Hash 值为 5 的 A /B/ C 计算之后为 0，被分到了 low 链表，Hash 为 21 的 D /E/ F 被分到了 high 链表。
5. 然后把 low 链表放入新数组的 index= 5 的位置，把 high 链表放入到新数组的 index=5+16=21 的位置。

红黑树相关的操作虽然代码不同，但是实际上要干的事情是一样的。就是把 相同位置的不同 Hash 大小的链表元素在新 table 数组中进行分离。希望讲到这里你能听懂。

4.2 HashMap 死链问题

Java7 的 HashMap 会存在死循环的问题，主要原因就在于，Java7 中，HashMap 扩容转移后，前后链表顺序倒置，在转移过程中其他线程修改了原来链表中节点的引用关系，导致在某 Hash 桶位置形成了环形链表，此时 get(key)，如果 key 不存在于这个 HashMap 且 key 的 Hash 结果等于那个形成了循环链表的 Hash 位置，那么程序就会进入死循环；

Java8 在同样的前提下并不会引起死循环，原因是Java8 扩容转移后前后链表顺序不变，保持之前节点的引用关系。

void resize(int newCapacity) {Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    // JDK8 移出了 hashSeed 计算，因为计算时会调用 Random.nextInt()，存在性能问题
    // 很重要的 transfer()
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 在此步骤完成之前，旧表上依然可以进行元素的增加操作，这就是对象丢失原因之一
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 寥寥几行，却极为重要
void transfer(Entry[] newTable, boolean rehash) {
    // newCapacity 是旧表的两倍，这个扩容大小
    int newCapacity = newTable.length;
    // 使用 foreach 方式遍历整个数组下标
    for (Entry<K,V> e : table) {
        // 如果在这个 slot 上面存在元素，则开始遍历上面的链表，知道 e ==null，退出循环
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            // 当前元素总是直接放在数组下标的 slot 上，而不是放在链表的最后
            // 倒序插入新表
            // 这里是形成死链的关键步骤
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

延伸阅读。

https://www.yuque.com/docs/sh…

5. Java 8 与 Java 7 对比

1. 发生 hash 冲突时，Java7 会在链表头部插入，Java8 会在链表尾部插入
2. 扩容后转移数据，Java7 转移前后链表顺序会倒置，Java8 还是保持原来的顺序
3. 引入红黑树的 Java8 极大程度地优化了 HashMap 的性能‘
4. put 操作达到阈值时，Java7 中是先扩容再新增元素，Java8 是先新增元素再扩容；
5. Java 8 改进了 hash() 扰动函数，提高了性能

6. 为什么要使用红黑树？

很多人可能都会答上一句，为了提高查找性能，但更确切地来说的话，采用红黑树的方法是为了提高 在极端哈希冲突的情况 下提高 HashMap 的性能。

极端哈希冲突的情况下，去测量 Java7 和 Java8 版本的 HashMap 的查询性能差距。

Java 7 的结果是可以预期的。HashMap.get()的性能损耗与 HashMap 本身的大小成比例增长。由于所有键值对都在一个巨大的链表中的同一个桶中，查找一个条目需要平均遍历一半这样的列表（大小为 n）。因此 O(n)复杂性在图上可视化。

与此相对的是 Java8，性能提高了很多，发生灾难性哈希冲突的情况下，在 JDK 8 上执行的相同基准测试会产生 O（logn）最差情况下的性能。

关于此处的算法优化实际上在 JEP-180 中有描述到，

另外如果 Key 对象如果不是 Comparable 的话，那么发生重大哈希冲突时，插入和删除元素的效率会变很差。（因为底层实现时红黑树，需要通过 compare 方法去确定顺序）

当 HashMap 想要为一个键找到对应的位置时，它会首先检查新键和当前检索到的键之间是否可以比较（也就是实现了 Comparable 接口）。如果不能比较，它就会通过调用 tieBreakOrder(Objecta,Object b) 方法来对它们进行比较。这个方法首先会比较两个键对象的类名，如果相等再调用 System.identityHashCode 方法进行比较。这整个过程对于我们要插入的 500000 个元素来说是很耗时的。另一种情况是，如果键对象是可比较的，整个流程就会简化很多。因为键对象自身定义了如何与其它键对象进行比较，就没有必要再调用其他的方法，所以整个插入或查找的过程就会快很多。值得一提的是，在两个可比的键相等时（compareTo 方法返回 0）的情况下，仍然会调用 tieBreakOrder 方法。

又可能会有人说了，哪有这么极端的哈希冲突？

这个实际上是一个安全性的考虑，虽然在正常情况下很少有可能发生很多冲突。但是想象一下，如果 Key 来自不受信任的来源（例如从客户端收到的 HTTP 头名称），那么就有可能收到伪造 key 值，并且这种做法不难，因为哈希算法是大家都知道的，假设有人有心去伪造相同的哈希值的 key 值，那么你的 HashMap 中就会出现上述这种极端哈希冲突的情况。现在，如果你去对这个 HashMap 执行多次的查询请求，就会发现程序执行查询的效率会变得很慢，cpu 占用率很高，程序甚至会拒绝对外提供服务。

延伸外链：https://www.yuque.com/docs/sh…