HashMap源码简单理解：put

电玩女神 2022-11-04 01:41 188阅读 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> { 
        // key 的哈希码。
        final int hash;
        // key 值。
        final K key;
        // value 值。
        V 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;
        }

扩容

/** 扩容。做了三件事情： 1. 修改 capacity。 2. 修改 threshold。 3. 修改 Node<K,V>[] table 数组。 */ 
    Node<K,V>[] resize(){ 
        /** 场景1：原始 hashMap 是空。 newCap = DEFAULT_INITIAL_CAPACITY = 16； newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) = (int)(0.75 * 16) = 12 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; return newTab; 场景2：原始 hashMap 不为空。 newCap = oldCap << 1; capacity 扩大为原来 2 倍。 newThr = oldThr << 1; threshold 扩大为原来 2 倍。 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 因为 oldTable 不为空，所以还需要将 oldTable 中的元素复制到 newTable。 e 是 oldTable 中的某个元素，因为 newTable 的 length 变大了，所以当 e 复制到 newTable 中时，它的位置也会发生变换。 newTab[e.hash & (newCap - 1)] = e 接下来再判断 e 下面是 链表还是红黑树，按照之前的顺序复制。 return newTab。 */
    }

[image-20210301143033580]: /images/20221023/27a0019779d448599dffbdedc81e7c34.png