Map (二) HashMap put()方法详细解刨

程序员文章站 2022-05-25 15:33:32

...

创建 HashMap 我们的即可开始往里面存键值对啦。我们来一步一步的看看 HashMap 是如何存储！

我们要模拟一下存储时的多种场景，后场景是在前场景不匹配的情况下的场景(如有遗漏请评论提醒)：

我们先理解3个主要参数：

hash （通过 key 计算出的 int 值）
key （传入的 key）
value （传入的 value）

我们模拟 hash 计算结果是每个场景下都存入的到坐标为 0 的 Node数组中。
先粗略的看一下各个场景是如何做到值的添加和覆盖，最后附上源码详细流程：

场景1：存储时 HashMap 的 Node 数组未初始化

Map (二) HashMap put()方法详细解刨

场景2：当前坐标下不存在值

Map (二) HashMap put()方法详细解刨

场景3：当前坐标下只有一个值并且存储的 key 相等

Map (二) HashMap put()方法详细解刨

场景4：当前坐标下只有一个值并且存储的 key 不相等

Map (二) HashMap put()方法详细解刨

场景5：当前坐标下有多数值(小于8)且其中有一个值和新传入的 key 相同

Map (二) HashMap put()方法详细解刨

场景6：当前坐标下有多数值(小于8)且 key 都不相同

Map (二) HashMap put()方法详细解刨

补充：链表长度大于等于8的时候，当前数组长度大于64时才会转换成红黑树。

场景7：当前坐标下有多数值(大于等于8)，即数据结构已经变为红黑树了。

……该场景已经涉及课外知识，后期详细讲的讲述并附上链接，敬请期待……

上述的七种场景已经包含了绝大多数情况。
我们还需要知道，不论任何场景下做完赋值操作后都会判断当前的容量值是否大于最大容量值*负载因子的值，如果大于即要调用 resize() ，进行扩容操作。

下面我们来看看具体的源代码和流程图(流程图画的比较复发- -请谅解)
流程图中会有 1⃣️2⃣️3⃣️4⃣️ 四个标示，都表示具体的实现步骤会在后面拿出来讲并附上链接。

    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;
    }

Map (二) HashMap put()方法详细解刨