摘要：我们来详细讲解 HashMap 源码中的put 操作以及其中涉及的哈希寻址算法。put 操作是 hashMap 最核心的操作之一，理解它的实现原理对于掌握 HashMap 的工作方式至关重要。
我们来详细讲解 HashMap 源码中的 put 操作 以及其中涉及的 哈希寻址算法。put 操作是 hashMap 最核心的操作之一，理解它的实现原理对于掌握 HashMap 的工作方式至关重要。
1. put 操作概述
put(K key, V value) 方法用于向 HashMap 中添加一个键值对 (key-value pair)。如果 HashMap 中已经存在相同的键，则会更新该键对应的值。如果键不存在，则会添加新的键值对。
2. put(K key, V value) 方法入口
HashMap 的 put 方法非常简洁，它直接调用了 putVal 方法，并将键的哈希值计算出来作为参数传递给 putVal。
java复制代码 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}hash(key): 调用之前我们详细分析过的 hash(key) 方法，计算键 key 的哈希值。这个哈希值会用于后续的哈希寻址和冲突处理。putVal(hash(key), key, value, false, true): 调用真正的 put 操作实现方法 putVal。3. putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 方法详解
putVal 方法是 HashMap 中 put 操作的核心实现。我们来逐步分析 putVal 方法的源码逻辑：
java复制代码 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node tab; Node p; int n, i;// 1. 检查哈希表是否为空或未初始化，如果是则进行初始化 (resize)if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize).length; // 调用 resize 方法初始化或扩容，并获取新的哈希表长度 n// 2. 计算哈希桶索引 (哈希寻址算法核心步骤)if ((p = tab[i = (n - 1) & hash]) == null) {// 3. 如果计算出的索引位置 (桶) 为空，则直接创建新节点并放入桶中tab[i] = newNode(hash, key, value, null); // 创建新的 Node 节点，作为链表头节点或红黑树根节点} else {// 4. 如果计算出的索引位置 (桶) 不为空，则发生哈希冲突，需要处理冲突Node e; K k;if (p.hash == hash && // 5a. 检查桶的第一个节点 (链表头节点或红黑树根节点) 的键是否与要插入的键相同((k = p.key) == key || (key != null && key.equals(k)))) {// 5b. 如果键相同，则找到了要更新的节点，将 p 赋值给 ee = p;} else if (p instanceof TreeNode) {// 6. 如果桶的第一个节点是 TreeNode 类型 (红黑树节点)，则在红黑树中查找或插入节点e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); // 调用 TreeNode 的 putTreeVal 方法} else {// 7. 如果桶的第一个节点是链表节点，则遍历链表for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {// 8a. 如果遍历到链表尾部，仍未找到键相同的节点，则创建新节点并添加到链表尾部p.next = newNode(hash, key, value, null);// 8b. 添加新节点后，检查链表长度是否达到树形化阈值，如果达到则尝试将链表转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash); // 调用 treeifyBin 方法尝试树形化break; // 结束链表遍历}if (e.hash == hash && // 9a. 检查链表中的当前节点 e 的键是否与要插入的键相同((k = e.key) == key || (key != null && key.equals(k))))// 9b. 如果键相同，则找到了要更新的节点，跳出循环break; // 跳出链表遍历循环p = e; // 将 p 指向下一个节点，继续遍历链表}}if (e != null) { // 10. 如果 e 不为 null，说明找到了要更新的节点 (在步骤 5b, 6 或 9b 中找到)V oldValue = e.value; // 获取旧值if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent 为 false 或旧值为 null 时才更新值 (onlyIfAbsent 用于 putIfAbsent 方法)e.value = value; // 更新节点的值afterNodeAccess(e); // LinkedHashMap 的钩子方法，HashMap 中为空实现return oldValue; // 返回旧值}}++modCount; // 11. 结构修改次数 + 1if (++size > threshold) // 12. 键值对数量 + 1，并检查是否超过扩容阈值resize; // 如果超过阈值，则进行扩容afterNodeInsertion(evict); // LinkedHashMap 的钩子方法，HashMap 中为空实现return null; // 如果是新插入的键值对，则返回 null (表示没有旧值)}putVal 方法的核心步骤分解:
哈希表初始化检查:if ((tab = table) == null || (n = tab.length) == 0): 检查 HashMap 的哈希表 table 是否为空 (null) 或者长度为 0。这通常发生在第一次 put 操作时，或者在显式调用 clear 方法后。n = (tab = resize).length;: 如果哈希表为空或未初始化，则调用 resize 方法进行初始化。resize 方法不仅负责初始化哈希表，也负责扩容。初始化时，resize 会根据默认初始容量 DEFAULT_INITIAL_CAPACITY (16) 或用户指定的初始容量创建哈希表。resize 方法会返回新的哈希表，并更新 n 为新的哈希表长度。哈希寻址算法 (计算哈希桶索引):if ((p = tab[i = (n - 1) & hash]) == null): 这是 哈希寻址算法 的核心步骤。i = (n - 1) & hash: 根据键的哈希值 hash 和当前哈希表长度 n，计算出键值对应该存储在哈希表数组 table 中的索引位置 i。 (n - 1) & hash 位运算等价于 hash % n (当 n 为 2 的幂次方时)，但位运算效率更高。p = tab[i]: 根据计算出的索引 i，获取哈希表 table 中索引为 i 的桶 (bucket)，并将桶的头节点赋值给 p。如果 tab[i] 为 null，表示该桶为空。桶为空 (没有哈希冲突):tab[i] = newNode(hash, key, value, null);: 如果步骤 2 中计算出的索引位置 tab[i] 为空 (p == null)，说明该位置还没有任何键值对，没有发生哈希冲突。此时，直接创建一个新的 Node 节点，并将键值对 (key, value) 存储到新节点中，然后将新节点设置为 tab[i] 位置的桶的头节点。桶不为空 (发生哈希冲突):else { ... }: 如果步骤 2 中计算出的索引位置 tab[i] 不为空 (p != null)，说明该位置已经存在键值对了，发生了哈希冲突。需要进一步处理冲突。检查第一个节点是否为要更新的键:if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))): 检查桶的第一个节点 p (链表头节点或红黑树根节点) 的键是否与要插入的键 key 相同。判断键是否相同需要同时比较哈希值和键的 equals 方法。e = p;: 如果键相同，说明是要更新已存在的键的值，将 p 赋值给 e，后续会更新 e 的值。如果第一个节点是红黑树节点:else if (p instanceof TreeNode): 如果桶的第一个节点 p 是 TreeNode 类型，说明该桶位置已经树形化，使用红黑树来处理哈希冲突。e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);: 调用 TreeNode 的 putTreeVal 方法，在红黑树中查找或插入键值对。putTreeVal 方法会返回找到的相同键的节点，或者在插入新节点后返回 null。如果第一个节点是链表节点:else { ... }: 如果桶的第一个节点 p 是链表节点，说明该桶位置使用链表来处理哈希冲突。遍历链表: 使用 for (int binCount = 0; ; ++binCount) 循环遍历链表。if ((e = p.next) == null): 如果遍历到链表尾部 (p.next == null)，说明链表中没有找到与要插入的键相同的节点。p.next = newNode(hash, key, value, null);: 在链表尾部创建一个新的 Node 节点，并将键值对存储到新节点中，然后将新节点设置为链表尾节点的 next 引用。链表树形化检查:if (binCount >= TREEIFY_THRESHOLD - 1): 在添加新节点后，检查当前链表长度 binCount 是否达到树形化阈值 TREEIFY_THRESHOLD - 1 (因为 binCount 从 0 开始计数，所以实际链表长度达到 TREEIFY_THRESHOLD 时，binCount 为 TREEIFY_THRESHOLD - 1)。treeifyBin(tab, hash);: 如果链表长度达到阈值，则调用 treeifyBin 方法尝试将链表转换为红黑树。break;: 结束链表遍历循环。if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))): 在链表遍历过程中，检查当前节点 e 的键是否与要插入的键 key 相同。break;: 如果键相同，说明找到了要更新的节点，跳出链表遍历循环。p = e;: 将 p 指向下一个节点 e，继续遍历链表。更新值 (如果找到相同键的节点):if (e != null): 如果 e 不为 null，说明在步骤 5b, 6 或 9b 中找到了与要插入的键相同的节点 (可能是链表节点或红黑树节点)。V oldValue = e.value;: 获取找到的节点的旧值。if (!onlyIfAbsent || oldValue == null): 判断是否需要更新值。onlyIfAbsent 参数用于 putIfAbsent 方法，如果 onlyIfAbsent 为 true，则只有在旧值为 null 时才更新值。对于普通的 put 操作，onlyIfAbsent 为 false，总是更新值。e.value = value;: 更新找到的节点的值为新的 value。afterNodeAccess(e);: LinkedHashMap 的钩子方法，HashMap 中为空实现，用于在节点被访问后进行一些操作 (例如，更新访问顺序)。return oldValue;: 返回被更新节点的旧值。更新结构修改次数和检查扩容:++modCount;: HashMap 的结构被修改，结构修改次数 modCount 加 1。if (++size > threshold): 键值对数量 size 加 1，并检查是否超过扩容阈值 threshold。resize;: 如果 size 超过了 threshold，则调用 resize 方法进行扩容。返回 null (如果是新插入的键值对):return null;: 如果整个 putVal 操作是成功插入了一个新的键值对 (而不是更新已存在的键的值)，则返回 null (表示没有旧值)。4. 哈希寻址算法总结
HashMap 的哈希寻址算法主要包括以下步骤：
计算哈希值: 使用 hash(key) 方法计算键 key 的哈希值。计算哈希桶索引: 使用位运算 (n - 1) & hash 将哈希值映射到哈希表数组的索引范围 [0, n-1]。定位哈希桶: 根据计算出的索引，找到哈希表数组中对应的桶 tab[i]。处理哈希冲突:如果桶为空，直接将新节点放入桶中。如果桶不为空，则根据桶中第一个节点的类型 (链表节点或红黑树节点) 进行不同的冲突处理：链表: 遍历链表，查找或添加到链表尾部，并可能进行链表树形化。红黑树: 在红黑树中查找或插入节点。5. 示例说明
假设我们有一个初始容量为 16 的 HashMap，我们要 put 键值对 (“apple”, 1)。
计算哈希值: 假设 hash("apple") 计算得到哈希值 h1 = 12345。计算哈希桶索引: 哈希表长度 n = 16，n - 1 = 15 (二进制 0000 1111)。 i = 15 & 12345 (假设结果为索引 i = 5)。定位哈希桶: 找到 table[5] 桶。检查 table[5] 是否为空: 假设 table[5] 当前为空。桶为空，直接插入: 创建新的 Node 节点存储 (“apple”, 1)，并将 table[5] 指向这个新节点。如果后续我们要 put 键值对 (“banana”, 2)，假设 hash("banana") 计算得到的哈希值 h2 经过 (n - 1) & h2 计算后，索引也是 5 (哈希冲突)。
计算哈希值: hash("banana") 得到 h2。计算哈希桶索引: 索引仍然是 5。定位哈希桶: 找到 table[5] 桶。检查 table[5] 是否为空: table[5] 不为空 (已经有 “apple” 的节点)。处理哈希冲突 (链表): 假设 table[5] 的第一个节点是链表节点。遍历 table[5] 的链表，查找是否已存在键为 “banana” 的节点。假设链表中没有 “banana” 节点，则在链表尾部添加新的 Node 节点存储 (“banana”, 2)。通过这个例子，可以看到 put 操作如何使用哈希寻址算法找到键值对的存储位置，以及如何处理哈希冲突，将键值对存储在链表或红黑树中。
在后续的 HashMap 源码分析中，我们将继续深入探讨 resize 扩容方法、get 获取方法、remove 删除方法，以及红黑树相关的操作。
来源：科技蜜谈
