Java集合—HashMap之梳理put方法逻辑

2. 源码解析

上一篇文章 Java集合—HashMap之hash优化算法已经讲了 HashMap 的 hash 优化算法，在讲优化算法的时候提到了 put 方法，这个最核心，最复杂的方法。这一篇我们来详细梳理下 put 方法的逻辑。

2.3 梳理put方法逻辑

我们先贴出来 put 方法的代码：

1
2
3

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

最核心的还是调用了 putVal 方法。其中 onlyIfAbsent 表示是否替换相同 key 的旧 value 值，默认都是替换。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    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))))
            e = p;
        else if (p instanceof TreeNode)
            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)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

在详细分析源码之前，我们先画一张图。

这张图中画出了大致的流程图，涉及到树结构的没有详细画出来，后面会专门写一篇文章处理的。结合这张图，我们再来看看代码。建议看这篇文章的时候打开 idea, 跟着我一起看 HashMap 的 put 方法的源码。

源码很长，有的讲源码的博客文章会在代码中写注释，但是我觉得很多东西一两行注释说不清楚。但是我这样写又会导致在看说明的时候还得往上翻看对应的哪一行代码，所以建议大家看的时候开两个窗口，一个看代码，一个看说明。

第 4 行代码，判断 table 是否为空，为空的话进行初始化扩容。 resize 方法后面详解。

第 6 行代码，根据传入的 key 算出对应的数组位置的 Node，即 p （p 这个 Node 在后面用处比较大）。如果为空，新建一个 Node 放在该位置，然后代码就执行到 37 行，判断是否需要扩容，直接返回。这一块代表的就是没有出现 hash 冲突，新增的元素直接放在一个空的数组位置上。

如果进入到第 8 行代码，八成就说明出现 hash 冲突了，会生成链表或者红黑树了。第 10 行代码，p 的 hash 就是当前存储值的 hash，比较 p 的 hash 和传入的 hash ，如果相等，再比较 key 值。

小插曲：思考一个问题，如果 p 的 hash 和传入的 hash 相等，一定能证明是同一个 key 吗？

答案是不一定，看过上一篇文章的同学应该知道，这个 hash 是 (h = key.hashCode()) ^ (h >>> 16) 算出来的。hash 相等并不意味着 key 相同。所以这里判断了 hash 相等之后依旧要判断 key 是否相等。

我们回到 key 值的比较，第 11 行代码，如果 key 值相等，把 p 赋值给 e，然后直接跳到第 29 行代码，很明显 e 不为空，接着执行，将旧的值赋值给 oldValue ，判断 onlyIfAbsent ，这个我们之前说过，我们默认的是覆盖旧值，所以执行第 32 行代码，用新的值覆盖旧值。这一块代码代表的是传入的 key 和之前数组某个位置的 key 相同。

如果不是同一个 key ，进入第 13 行代码，判断是否为树结构，之后执行树结构的相关逻辑，后面我们单独来讲。

如果既不是同一个 key ，也不是树结构，说明就是链表结构了，此时就会进入 15 行代码的分支。首先进入一个死循环，这个死循环依赖于 break 进行退出。这个循环的逻辑就是对链表进行遍历，binCount 依次增加。

数组转链表的分析是这篇文章的一个重点，所以下面我们边看源码边画图。来上图：

第 17 行代码，判断 p 的下一个节点是否为空，并把 p.next 赋值给 e 。

我们假设是 tab[i] 第一次 hash 冲突，那么此时肯定是空，如图 A 所示。然后我们以传入的 key、value、hash 新建一个 Node ，此时就会如图 B 所示。然后第 19 行代码判断是否需要转化为树结构，这里我们跳过，后面细讲。因为是第一次 hash 冲突，此时不会树化，然后执行第 21 行代码，退出循环。

我们假设 tab[i] 进入第二次 hash 冲突，进入到第 17 行代码，此时 p.next 就不为空了，就会进入到第 23 行代码的判断，我们假设不是同一个 key ，这个时候执行第 26 行代码，p 指针指向 e ，如图 C 所示。

我们假设 tab[i] 进入第三次 hash 冲突，进入到第 17 行代码，我们看看图 C ，这个时候，p.next 又为空了，这个时候就和第一次 hash 冲突类似了。来，上图：

第 17 行执行完毕如图 D，18 行执行完如图 E 。

然后第四次 hash 冲突，这次执行逻辑和第二次 hash 冲突的逻辑一样，执行完之后如图 F 。如此这样周而复始的执行，链表的长度不断增长。

第 29 ~ 34 行代码处理返回的旧值，就不用深究了。

第 37 ~ 41 行代码处理扩容，后面我们会单独讲。

这一篇文章已经大致将 put 方法的流程讲完了，剩余的链表转树结构，扩容方法后面单独讲。