HashMap源码简单理解：put

本是古典何须时尚 2022-10-15 04:51 165阅读 0赞

还是要做笔记的！还是要做笔记的！还是…! 重要的事情说三遍。

之前梳理过，但这会记忆已经很模糊了，

这次写个笔记，

要是忘了，

来这找！

# 1.数据放在那里了？ #

HashMap 常用的打开方式如下：

HashMap<String,Ingeter> hashmap = new HashMap<>();
    hashmap.put("diego",1);
    hashmap.put("amos",2);
    // ........ //

那存入的两个键值对到底放在那里了？是以何种格式存放的？

// HashMap.java
    transient Node<K,V>[] table;

hashmap 的元素均存放在 table 数组中，数组的每个元素都是 Node 类型的。

// HashMap.java
    static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash;	// key 的哈希码。
        final K key;	// key 值。
        V value;		// value 值。
        Node<K,V> next;	// 指向下一个节点的引用。
    	// 构造函数。
        Node(int hash, K key, V value, Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey()        {  return key; }
        public final V getValue()      {  return value; }
        public final String toString() {  return key + "=" + value; }
    
        public final int hashCode() { 
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) { }
        public final boolean equals(Object o) { }
    }

别想简单了，如果只是数组里存放 node 元素，那跟 ArrayList 底层数组结构有什么区别呢？table 中的每个元素都是 Node 类型的，它可能是个单向链表的初始节点，还有可能是棵树的根节点。

table 最终的样子是这样的：

![image-20210301143033580][]

hashMap中的数据是以这种样子存储的。在 JDK 1.8 以前 hashMap 底层是 数组 + 链表；JDk1.8 以后 hashMap 底层是 数组 + 链表 + 红黑树。

# 2.数据是怎么插入的？ #

看看源码的 put 方法。

/** 添加元素 */
    public V put(K key, V value) { 
        // 真正的添加在这里。
        return putVal(hash(key), key, value, false, true);
    }

先计算 key 的 哈希值。之所以要无符号右移 16 为，是为了让哈希码的高位也参与后面的数组位置计算，最终的目的还是想让数组中的元素分部均匀些。

/** * 计算元素的 hash 值。 * 正在存入的元素到底放在 table 的几号 index 上呢？这个要计算的。 * 有个规定：table.length 是 2 的次幂，这里假设是 16。 * hashCode() 是 native 方法，返回 32 位的二进制数。 * * 假如 index 计算函数为：index = key.hashCode() & (table.length -1) * 当多个元素的 hashcode 高 16 位不同而低 16 位相同时，得到的 index 是相同的。 * 此时发生了哈希碰撞，没将元素均匀分布在 table 中。 * * 假如 index = ((h = key.hashCode()) ^ (h >>> 16)) & (table.length -1) * 依旧是多个元素的 hashcode 高 16 位不同，低 16 位相同，因为执行了 * ((h = key.hashCode()) ^ (h >>> 16)) ，高 16 位与低 16 位执行了异或， * 并将结果保存在低 16 位上，也就是说此时低 16 位上保存了高 16 位的信息。 * 这几个元素经过异或计算后，低 16 位就变得不一样了，再 &(table.length -1) * 就会得到不同的 index，从而避免了 hash 碰撞。实现元素均匀分布。 * */
        static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

真正的添加元素。`(n - 1) & hash` 与 `hash % n` 是等价的，位运算比除法的效率高。

/** * hash: 待插元素 key 的 hashcode。 * key：待插元素 key 值。 * value：待插元素 value 值。 * onlyIfAbsent：key 值相同，是否替代。true，不替代。 */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            // 如果 table 还没有初始化，那就先分配空间。
            // 使用时再分配空间，防止空间浪费，所以在第一次调用 putVal 的时候为其分配空间。
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
    
            // (n - 1) & hash: 计算 key 对应的索引 i。恰好这个地方是空的。
            // 直接 k-v --> Node,存放到 table[i]。(这是最简单的情况)
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else { 
                //此时，i 位置不为空。
                // e：用来临时保存散列表中与当前要插入的 k-v，同 key 值的元素。
                // 如果 e == null，表示在 i 位置的链表(或树)中找不到与 k-v，有相同 key 的元素。
                Node<K,V> e; K k;
                p = table[i]
                // 如果 p 的 hash、key 分别等于 待插元素的 hash、key。
                // 说明在散列表中找到了与待插元素相同 key 的元素。
                // 先将其保存到 e 中，后面可能要替换值。
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                // 如果 p 与 待插元素的 key 不相同。那么：
                // 1) 如果 i 位置是红黑树，待插素追加到红黑树 或者 替换红黑树中的某个节点。
                // 2) 如果 i 位置是链表，待插元素追加到链表末尾 或者 替换链表中的某个节点。
                else if (p instanceof TreeNode)
                    // i 位置是红黑树，执行红黑树逻辑。
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { 
                    // i 位置是链表，执行链表逻辑。
                    for (int binCount = 0; ; ++binCount) { 
                        // 如果 p.next == null,说明 p 是链表的最后一个节点。
                        if ((e = p.next) == null) { 
                            // k-v --> Node, 追加到链表的末尾。
                            p.next = newNode(hash, key, value, null);
                            // binCount + 1 = 此时链表中元素的个数。
                            // 当链表中元素个数等于 TREEIFY_THRESHOLD(8) 时，链表要树化。
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        // e = p.next, 判断(下一个节点)e 与待插入节点的 hash、key是否分别相等。
                        // 如果相等，待插入节点的值可能要替换 e 的值。
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        // e = p.next; p = e; 下一轮循环 e = p.next; p = e; 第三轮...
                        // 双指正交替遍历整个链表。
                        p = e;
                    }
                }
                // e!=null, 表示在 i 位置的链表(或树)中找到了与 k-v 有相同 key 的元素。
                // 此时，如果允许替代，新 value 要覆盖老 value。
                if (e != null) {  // existing mapping for key
                    // 拿出老值。
                    V oldValue = e.value;
                    // 如果允许替换。
                    if (!onlyIfAbsent || oldValue == null)
                        // 新值替换老值。
                        e.value = value;
                    // HashMap 中这个方法是空的。
                    // LinkedMap 重写了这个方法。
                    afterNodeAccess(e);
                    // 返回被替代的老值。putVal 方法执行结束。
                    return oldValue;
                }
            }
            // 能执行到这里，说明上面执行的结果是插入了新元素，而不是替代。
            ++modCount;
            // 散列表中元素总个数 +1，再判断是否超过阈值。
            // 如果超过了，要扩容。
            if (++size > threshold)
                resize();
            // 该方法在 HashMap 中是空方法，
            // LinkedMap 重写了该方法。
            afterNodeInsertion(evict);
            // 返回 null，putVal 方法执行结束。
            return null;
        }

# 3.扩容 #

// 扩容主要做了三件事情：
        // 1. 扩大容量，
        // 2. 扩大阈值，
        // 3. 重新分布散列表中的元素(如果有)。
        final Node<K,V>[] resize() { 
            // 扩容前的 table。
            Node<K,V>[] oldTab = table;
            // 扩容前的容量(当前容量)，再具体点：扩容前 table 数组的长度。
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 扩容前的阈值(当前阈值)。
            int oldThr = threshold;
            // newCap: 扩容后的容量(新容量)，扩容后 table 数组的长度。
            // newThr: 下一次扩容的阈值(新阈值)。
            int newCap, newThr = 0;
            // 如果散列表非空，即：table != null,(正常 put 键值对时，会触发这里)。
            if (oldCap > 0) { 
                // 如果当前容量已经是极限了(2^30次幂)，阈值设置为 int 最大值。
                if (oldCap >= MAXIMUM_CAPACITY) { 
                    threshold = Integer.MAX_VALUE;
                    // 直接返回散列表，(因为散列表长度已经是极限了，不再扩大，
                    // 所以里面的元素不需要重新分布)。
                    return oldTab;
                }
                // 如果散列表容量没达到极限。
                // 1) 如果 老容量扩大两倍后依旧没有超上限，则：新容量 = 老容量 * 2。
                // 2) 如果 老容量 >= 默认容量(16)，则：下次扩容阈值 = 当前扩容的阈值 * 2
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            // 能到这里，说明此时散列表是空的。
            // table == null，oldThr > 0，什么情况会出现？
            // 1) 调用构造函数 HashMap(initialCapacity,loadFactor) 会出现；
            // 2) 调用构造函数 HashMap(int initialCapacity) 时会出现；
            // 3) 调用构造函数 HashMap(Map<? extends K, ? extends V> m) 时会出现。
            else if (oldThr > 0) // initial capacity was placed in threshold
                // 这种场景下，直接设定 扩容后的 table 长度为阈值的大小。
                newCap = oldThr;
            // 能到这里，说明此时，table == null，oldThr == 0
            // 调用无参构造函数 HashMap()时会出现。
            else {                // zero initial threshold signifies using defaults
                // 新容量采用默认的初始容量，大小是 16。
                newCap = DEFAULT_INITIAL_CAPACITY;
                // 下次扩容阈值 = 负载因子 * 默认初始容量 = 0.75 * 16 = 12。
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            // 什么情况下会出现？
            // 1) table != null 且 table.length < 16 时，会出现 newThr == 0。
            // 2) table == null 且 oldThr > 0 时，会出现 newThr == 0。
            // 所以在还要为这两种情况设定下一次扩容的阈值。
            if (newThr == 0) { 
                // ft = 新容量 * 负载因子(默认是0.75)
                float ft = (float)newCap * loadFactor;
                // 上限判断，如果没有超上限，那下一次扩容的阈值就是 ft。(一般不会超)
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            // 下一次扩容的阈值定了，那就将其赋值给成员变量。
            threshold = newThr;
            // 以新容量位长度，创建table。
            @SuppressWarnings({ "rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            // 如果 oldTable != null，说明这不是第一次插入数据，
            // 那还得想原先 table 中的元素“移动”到新 table中。
            if (oldTab != null) { 
                // 遍历 oldCap
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;
                    // 如果 j 位置出元素不为空，将该元素赋给临时变量 e。
                    if ((e = oldTab[j]) != null) { 
                        // oldTab 中该位置设置null，
                        oldTab[j] = null;
                        // 如果 e.next == null, 说明 j 位置处只有一个node。
                        if (e.next == null)
                            // 计算该 node 在新 table 中的索引，直接赋值。
                            newTab[e.hash & (newCap - 1)] = e;
                        // 到这里，说明 j 位置不只一个 node。
                        // 那这个位置可能是链表，可能是红黑树。得分开考虑。
                        else if (e instanceof TreeNode)
                            // j 位置是红黑树。
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else {  // preserve order
                            // j 位置是链表。
                            // 扩容后 table 的长度变成了原来的两倍，从中间切成两个数组。
                            // j 桶中的元素也许在前半数组中，也许在后半数组中。
                            // 所以 j 桶中的元素也能拆成两个子链表。
    
                            // 保存将会放到前半数组中的元素。
                            Node<K,V> loHead = null, loTail = null;
                            // 保存将会放到后半数组中的元素。
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do { 
                                next = e.next;
                                // 如果 e 将会被保存到前半数组。
                                if ((e.hash & oldCap) == 0) { 
                                    // 如果保存前半数组元素的链表是空的。
                                    if (loTail == null)
                                        // e 是该链表的第一个节点。
                                        loHead = e;
                                    else
                                        // 保存前半数组元素的链表非空，e 追加到该链表中。
                                        loTail.next = e;
                                    // 该链表尾指针指向 e。
                                    loTail = e;
                                }
                                else { 
                                    // 如果 e 将会被保存到后半数组。
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            // 如果保存前半数组元素的链表不为空
                            if (loTail != null) { 
                                // 链表中最后一个 node 的 next 置null。(该node可能之前指向了别的node)
                                loTail.next = null;
                                // 该链表中的数据，依旧放在原来的桶中。
                                newTab[j] = loHead;
                            }
                            // 如果保存后半数组元素的链表不为空
                            if (hiTail != null) { 
                                // 链表中最后一个 node 的 next 置null。(该node可能之前指向了别的node)
                                hiTail.next = null;
                                // 该链表中的数据放在后半数组中。
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            // 返回扩容后的 table。
            return newTab;
        }

## 3.1 容量和阈值的关系 ##

容量：散列表的长度，即：`table.length`。

阈值：通过容量计算出来的一个数字，计算公式：阈值 = 容量\*负载因子，负载因子默认是0.75。

阈值有什么用呢？

当 table 中的元素越来越多时，出现哈希碰撞的几率也愈来愈大，table 中的链表或者树就越来越多，导致查找效率变低。在 table 中元素数量越来越多的情况下，适当的增加 table 长度，就可以减少哈希碰撞，从而尽量维持 O(1) 的查询效率。

频繁增加 table 长度会浪费内存，增加不及时会降低查询效率，那什么时候增加长度才是“恰当的”时间？

**当 table 中总元素的个数大于阈值时，给 table 增加长度**，简单说，阈值就是用来衡量啥时间给散列表扩容的。

## 3.2 容量和阈值的修改规则 ##

上面的源码中，看着扩容规则好乱，不过整理一下还是能理清楚的。

容量：capacity。阈值：threshold。

先想想调用扩容的时机：

1）刚 new 了HashMap 对象，现在向其中 put 键值对。

2）HashMap 对象里面已经有键值对了，现在还要再 put 。

### 时机1： ###

此时已经调用了构造函数，有些构造函数中会初始化 threshold，但 table 是空的，所以 capacity == 0。

（1）调用默认构造函数：`HashMap()` （常用的）

此时 oldCapacity == 0，oldThreshold == 0，再执行扩容：

**newCapacity = 默认初始容量 = 16，newThreshold = 默认负载因子 \* 默认初始容量 = 0.75 \* 16 = 12。**

（2）调用下列构造函数：

*  `HashMap(int initialCapacity)`
 *  `HashMap(int initialCapacity, float loadFactor)`
 *  `HashMap(Map<? extends K, ? extends V> m)`

此时，oldCapacity == 0，oldThreshold = `tableSizeFor(initialCapacity)` , initialCapacity 是手动给定的 table 容量，tableSizeFor(initialCapacity) 返回的结果是大于或等于 initialCapacity 的最小的 2 的 n 次幂。

再执行扩容：

**newCapacity = oldThreshold，newThreshold = newCapacity \* 0.75。**

### 时机2： ###

此时 oldCapacity > 0，再执行扩容：

*  **如果 oldCapacity >= 2^30，则 newCapacity = oldCapacity，newThreshold =`Integer.MAX_VALUE`。**
 *  **如果 oldCapacity \* 2 < 2^30 且 oldCapacity < 16，则 newCapacity = oldCapacity \* 2 ，newThreshold = newCapacity \* 0.75。**
 *  **如果 oldCapacity \* 2 < 2^30 且 oldCapacity >= 16，则 newCapacity = oldCapacity \* 2 ，newThreshold = oldThreshold \* 2。**

## 3.3 为什么 table 的容量总是 2 的 n 次幂？ ##

因为在构造函数中：

*  如果没有手动给定容量，在第一次扩容时，newCapacity = 默认初始容量 = 16。
 *  如果手动给定了容量，构造函数中会把阈值计算出来：`threshold = tableSizeFor(initialCapacity)`, 而且 threshold 是大于或等于 initialCapacity 的最小 2 的 n 次幂。在第一第扩容时，newCapacity = threshold。

在第二次以及以后的扩容中，每次扩容，容量都是翻倍的。所以 table 的容量总是 2 的 n 次幂。

## 3.4 扩容后，元素是怎么重新分布的？ ##

如果是第一次扩容，说明原 table 是空的，不会涉及元素重新分布的事情，扩容后直接返回就可以了。

当原 table 不为空时，扩容才需要重新分布元素。

遍历 oldTable 中的每一个元素，计算元素在 newTable 中的索引，再给赋值到 newTable 中就可以了。思路很简单，看下细节上的执行：

oldTable 中 j 位置的元素 :`e = oldTable[j]`，它可能是单个node，可能是链表的头节点，也可能是红黑树的根节点。

（1）单个 node：`newTable[e.hash & (newCap - 1)] = e;`，一行代码就搞定了，原理也很简单。

（2）e 是 链表的头节点，这种情况的处理方式，说是增加了效率，但感觉也降低了可读性。再贴一遍这部分代码。

// ------
    else{ 
        // 保存将会放到前半数组中的元素。
        Node<K,V> loHead = null, loTail = null;
        // 保存将会放到后半数组中的元素。
        Node<K,V> hiHead = null, hiTail = null;
        Node<K,V> next;
        do { 
            next = e.next;
            // 如果 e 将会被保存到前半数组。
            if ((e.hash & oldCap) == 0) { 
                // 如果保存前半数组元素的链表是空的。
                if (loTail == null)
                    // e 是该链表的第一个节点。
                    loHead = e;
                else
                    // 保存前半数组元素的链表非空，e 追加到该链表中。
                    loTail.next = e;
                // 该链表尾指针指向 e。
                loTail = e;
            }
            else { 
                // 如果 e 将会被保存到后半数组。
                if (hiTail == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
            }
    } while ((e = next) != null);
    // 如果保存前半数组元素的链表不为空
    if (loTail != null) { 
        // 链表中最后一个 node 的 next 置null。(该node可能之前指向了别的node)
        loTail.next = null;
        // 该链表中的数据，依旧放在原来的桶中。
        newTab[j] = loHead;
    }
    // 如果保存后半数组元素的链表不为空
    if (hiTail != null) { 
        // 链表中最后一个 node 的 next 置null。(该node可能之前指向了别的node)
        hiTail.next = null;
        // 该链表中的数据放在后半数组中。
        newTab[j + oldCap] = hiHead;
    }

![image-20210523154025155][]

图片中展示了这段代码的效果。原理如下：

先看 oldTable，这四个元素之所以能分到一个桶里面，是因为 用 `e.hash & (8 - 1)` 算出了相同的索引，导致哈希碰撞了。

我这里假设每个元素的哈希码与他们数值的二进制是相同的，只是为了将原理说清楚。

5: 0101		13: 1101      21: 0001 0101      29: 0001 1101
    &7: 0111		 7: 0111       7: 0000 0111       7: 0000 0111
    -----------------------------------------------------------------
    	0101            0101          0000 0101          0000 0101   == 5

也就是说，每个元素的哈希码具体是多少，这并不是关键，因为要执行 `hashcode & 7`， 所有后三位相同的 hashcode 都能计算出相同的结果，这些 hashcode对应的元素就发生了碰撞，将会被放在同一个桶里面。

扩容后，capacity = 16，再计算这四个元素的索引: `e.hash & (16 - 1)`

5: 0101		13: 1101      21: 0001 0101      29: 0001 1101
    &15: 1111		15: 1111      15: 0000 1111      15: 0000 1111
    -----------------------------------------------------------------
    	 0101           1101          0000 0101          0000 1101
    -----------------------------------------------------------------
    	  5	             13                5                13

计算出了不同的结果，为什么会这样呢，因为`capacity - 1 == 15 == 0b1111` 因为 13 和 29 hashcode 的倒数第4位是 1，剩下那两个依旧是 0。

更重要的是二进制要么是 1 要么是 0，没有别的状态。所以这四个元素中，如果倒数第四为是 0，那么执行 hashcode & 15，得到的结果不会变化，依旧是 5。如果倒数第四位是 1，计算结果就变了。

所以我要重新分布这四个元素，直接看他们hashcode 的倒数第四位是不是 1 就可以了。是 0，依旧在原索引位，是1，则放到新的索引位上。

那怎么只计算元素 hashcode 的倒数第4位呢？

if ((e.hash & oldCap) == 0) { .....} // oldCap == 8 == 0b1000

这样代码的作用是就是为了干这事。

> 有人可能觉得这么说太具象了，会不会是凑巧呢？应该有公式推导什么的。这个不是凑巧，真是这样的。
> 
> 仔细想想，不去考虑超上界。扩容每次都是翻倍。8、16、32、64 … ，对换到二进制上就是 每次1左移一位，右边补零。
> 
> 扩容前分布在同一个桶里的元素必然 hashcode 的后n位是相同的。
> 
> 重新分布，只需要判断倒数第 n-1 位是否相同，就能确定谁和谁会继续在一个桶里。
> 
> 恰好 newCapacity = oldCapacity << 1。
> 
> 这不是巧合。

那接下来就是将四个元素拆分 `e.hash & oldCap) == 0` 放在一个链表中， `e.hash & oldCap) == 1` 放在一个另一个链表中。

// 保存将会放到前半数组中的元素。 保存满足 e.hash & oldCap) == 0 的元素
    Node<K,V> loHead = null, loTail = null;
    // 保存将会放到后半数组中的元素。 保存满足 e.hash & oldCap) == 1 的元素
    Node<K,V> hiHead = null, hiTail = null;

接下来会构建出一个或两个链表。

最后一步，这两个链表该放在 newTable 哪个索引上？ （假设有两个链表）

其实上面已经给出答案了，元素 hashcode 的倒数第四位是0，`(hashcode & 0b1111) == (hashcode & 0b0111) == 5` 所以即便扩容，还在原索引位置上。元素 hashcode 的倒数第四位是1 `(hashcode & 0b1111) == (hashcode & 0b0111) + 2^3 == 13` , 所以新的位置是：`newTab[j + oldCap] = hiHead;`。

（3）e 是红黑树的根节点，这个不写了，那个东西得写好长。删除一个节点、树变链表、构建链表、链表变树或者直接构建树。内容不止一点点。

[image-20210301143033580]: /images/20221014/2bdb147a299a4c1bb023dc2048b17970.png
[image-20210523154025155]: https://raw.githubusercontent.com/diego1109/pictures/main/20210523154025.png