Loading... # HashMap 源码剖析 - put 流程 `HashMap` 是 Java 集合框架中的一个重要数据结构,用于存储键值对。它具有快速的查找、插入和删除性能。本文将深入剖析 `HashMap` 的 `put` 方法流程,帮助读者理解其内部实现原理。 ![](https://www.8kiz.cn/usr/uploads/2024/07/4182582355.png) ## 一、`put` 方法概述 `put` 方法用于将指定的键值对插入到 `HashMap` 中,如果键已经存在,则更新其对应的值。其源码定义如下: ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } ``` ### 1.1 主要参数 - `hash(key)`:计算键的哈希值。 - `key`:要插入的键。 - `value`:要插入的值。 - `onlyIfAbsent`:如果为 `true`,则仅当键不存在时才插入。 - `evict`:与内部缓存机制相关,普通情况下为 `true`。 ## 二、`putVal` 方法解析 `put` 方法内部调用了 `putVal` 方法。以下是 `putVal` 方法的详细实现: ```java 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) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } ``` ### 2.1 详细流程 1. **检查并初始化表**: ```java if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; ``` 如果哈希表未初始化或大小为 0,则调用 `resize` 方法进行初始化。 2. **计算插入位置**: ```java if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); ``` 通过 `(n - 1) & hash` 计算键对应的数组索引 `i`。如果 `tab[i]` 为空,则创建一个新节点并插入。 3. **处理哈希冲突**: ```java 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) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } ``` 如果 `tab[i]` 不为空,说明发生哈希冲突,需要处理冲突: - 如果当前节点 `p` 的哈希值和键与新插入的相同,则更新该节点的值。 - 如果当前节点是 `TreeNode`,则调用 `putTreeVal` 方法处理。 - 否则,遍历链表或树,找到插入位置或更新已有节点。 4. **更新节点值**: ```java if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } ``` 如果找到已有节点 `e`,则更新其值,并返回旧值。 5. **插入新节点并调整大小**: ```java ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; ``` 如果是插入新节点,更新 `modCount` 和 `size`。如果 `size` 超过阈值 `threshold`,则调用 `resize` 方法扩容。 ## 三、`resize` 方法 `resize` 方法用于初始化或扩容哈希表。 ```java final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; } else if (oldThr > 0) newCap = oldThr; else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; } ``` ### 3.1 详细流程 1. **计算新容量和新阈值**: 根据旧容量和旧阈值计算新的容量 `newCap` 和阈值 `newThr`。 2. **初始化新表**: 分配新的哈希表 `newTab`。 3. **重新哈希旧节点**: 遍历旧哈希表中的每个节点,并将其重新哈希到新哈希表中。 ## 四、总结 `HashMap` 的 `put` 流程包括计算哈希值、初始化哈希表、处理哈希冲突、更新节点值以及必要时的扩容操作。通过深入理解这些步骤,可以 更好地掌握 `HashMap` 的内部实现原理,提高编写高效代码的能力。掌握这些原理不仅有助于优化性能,还可以帮助解决实际开发中的问题。 最后修改:2024 年 07 月 13 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏