逐行分析 HashMap 的 put() 方法源码

HashMap 是底层结构是数组 + 链表，数组是存放 Node(Entry)的数组 Entry[]，链表是 Node 组成的链表，充分利用了 Node 的特性。链表的头结点存放在数组中。

put 方法的大致思路

1. 调用 hash(key) 方法，根据 key 对象的 hashCode 计算出 kay 的 hash，根据 hash 计算出其在 tab 数组中的 index，将键和值放入 Node(Entry) 中；
2. 如果 index 位置的 Node 为空，称为没碰撞，直接 Node 放入数组中；
3. 如果碰撞（index 位置存在 Node），先跟头结点比较，key 不相等时，循环链表比较，如果 key 已经存在，替换 old value，否则将 Node 链接到链表最后。
4. 如果碰撞导致链表的长度大于等于 7，将链表的结构转换为红黑树。
5. 如果 bucket 存放的 current capacity（当前容量）超过容量的 load factor（0.75），就 resize，容量扩大为两倍。

源码分析

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

static final int hash(Object key) {
    int h;
    // 使用 16 位无符号右位移 (>>>) 异或 (^) 混合生成一个 hash，替代 key 的 hashCode，hash 混合 hashCode 的高位和低位，以此来加大低位的随机性，用于减少碰撞。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * @param onlyIfAbsent 如果为 true，不改变已经存在的 value
 * @param evict 如果为 false, 该表处于创建模式。
 * @return 先前的值，或者为 null 如果没有
 */    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
        Node<K,V>[] tab; // 存放链表头结点的数组，数组的每个元素相当于一个桶，好像这个链表就存放于一个元素的空间中
        Node<K,V> p; // 存放于数组 i 处的（头）节点
        int n；// 数组 tab 的长度
        int i; // 数组 tab 的下标值
        // 刚开始 table 是 null 或空的时候，调用 resize() 方法，初始化一个长度为 16 的 tab
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 用 (n - 1) & hash 计算出插入点在数组的下标。如果插入点为 null，将此节点存放于此。（& 为长运算符，使用在计算 boolean 表达式时，会强制计算 & 两边的算式。此处用作位运算，即将 n-1 及 hash 均转为二进制数，相加，同为 1 则结果为 1，否则为 0，结果始终在 [0,n-1]）
        //（第 2 个 key 跟第 1 个 key 相同时，必定 hash 值相同，index 也相同）
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);// 键值对的 next 为空
        // 否则就会发生碰撞
        else {
            Node<K,V> e; // 相当于一个 temp，一个暂时存放键值对的节点
            K k; // 一个 temp，暂时存放 key 的值
            // 跟数组头结点 p 比较，如果 key 的 hash 值相等，key 对象也相等。为什么要两者都满足，因为根据不同 key 对象的 hashCode 计算出来的 hash 可能相等，所以还需要通过比较引用 ("==") 或者比较对象 ("equals") 的方式判断。
            // 你可能要说那可以直接比较 key 对象就行，因为 key 相同，hash 肯定相同。我们根据 hash 不同（p.hash == hash 为 false），可以判断出不是同一个 key，我们知道符号 "&&" 有短路功能，所以整体为 false，不用每次都去比较 key，提高了效率。
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;// 我们将数组的头结点 p 赋给 e，用于更改头结点的 value
            // 我们可以从下一个 else 中知道，一个桶只能存放 8 个节点，大于八个将转成红黑树存储。根据桶中的 Entry 数，判断 p 的类型是否是 TreeNode 类的实例
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 如果是，使用 putTreeVal 方法插入 Entry
            // 碰撞后，满足与桶中的第一个 entry 不等，且此时桶中 Entry 小于等于 8 个
            else {
                for (int binCount = 0; ; ++binCount) {// 没有条件，通过 break 跳出循环
                    if ((e = p.next) == null) {// 当 p 后没有节点时满足条件，此时桶中就一个 Entry；或者此时 p 为桶中最后一个 Entry
                        p.next = newNode(hash, key, value, null);// 新建 Entry 链接上，此时 e 为 null
                        if (binCount >= TREEIFY_THRESHOLD - 1) //-1 for 1st// 当桶中存放第 8 个元素时，将链表转换成红黑树。
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 上面的 if 判断是否跟桶中的第一个 Entry 相等，而这个 if 是依次跟桶中的 Entry 比较
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;// 如果此时桶中有多个 Entry, 执行完两个 if 后还没跳出循环，e=p.next, 相当于 p=p.next. 继续循环。这个 else 最重要的一点是要理解 --- 利用 e, 依次比较桶中的 Entry.
                }
            }
            if (e != null) { //existing mapping for key//e 不等于 null 的条件是桶中存在相同的 Entry 提前跳出循环
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)//onlyIfAbsent 默认为 false,oldValue 可以为 null
                    e.value = value;// 替换 value
                afterNodeAccess(e);//LinkedHashMap 继承 HashMap, 此方法在 LinkedHashMap 中被重写。在这里没什么用，但是在 LinkedHashMap 中此处调用此方法将节点链接到有序链表的最后.
                return oldValue;// 存在相同 Entry 时返回 oldValue. 我原来使用 put 方法时没想到还有返回值，所以还是要看看源码
            }
        }
        //HashMap 继承 Serializable, 当 HashMap 被序列化时，transient 变量不会被序列化
        ++modCount;//（当前元素的格式）modCout 是 transient 变量
        //size 也是 transient 变量，指 Map 中包含的键值对的数量。threshold 默认为 16*0.75
        if (++size > threshold)// 如果数组中的 Entry 大于等于 length*0.75
            resize();// 调用 resize 方法将 tab 数组扩大为两倍
        afterNodeInsertion(evict);//LinkedHashMap 继承 HashMap，此方法在 LinkedHashMap 中被重写.
        return null;// 默认返回空
}

测试代码

public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        for (int i = 0; i <= 20; i++) {
            String key = "key" + i;
            String value = "value" + i;
            map.put(key, value);
        }
        for (int i = 10; i <= 20; i++) {
            String key = "key" + i;
            String value = "value" + i + 1;
            map.put(key, value);
        }

        for (int i = 0; i <= 20; i++) {
            String key = "key" + i + 1;
            String value = "value" + i + 1;
            map.put(key, value);
        }
}

参考

• Java 1.8 HashMap 源码中 put() 方法详解
• JDK 源码中 HashMap 的 hash 方法原理是什么？