HashMap 是 Java 集合框架中最重要的实现类之一，位于 java.util 包下，实现了 Map 接口。它用于存储键值对（key-value）映射关系，通过哈希表（Hash Table）数据结构实现，能够提供高效的插入、删除和查找操作。
键值对映射关系如下图：
我们可以通过键（key）id、name、age、email 和 job 快速找到它们对应存储的值。
注意：
（1）HashMap 允许使用 null 作为键（key）和值（value），其中键只能有一个 null，而值可以有多个 null。
（2）HashMap 是非线程安全的集合，在多线程环境下使用需要额外的同步处理。
HashMap 在实际编码中使用频率很高，了解它的特性非常重要，主要特性如下：
HashMap 基于哈希表结构（由数组作为主体，结合链表或红黑树处理哈希冲突）实现。在 JDK 1.8 及之后的版本中，为优化长链表带来的查询性能损耗，引入了红黑树机制：当链表长度超过 8 时，会自动将链表转为红黑树，以此将查询时间复杂度从链表的 O (n) 降低至红黑树的 O (log n)，提升整体操作效率。
哈希表（Hash Table）是一种高效的数据结构，它通过哈希函数将键（Key）映射到对应的存储位置（数组索引），从而实现快速的插入、查询和删除操作。
其核心原理是：
首先有一个底层数组作为存储空间
对要存储的键值对（Key-Value），通过哈希函数计算 Key 的哈希值
将哈希值映射为数组的索引位置，直接把 Value 存储到该位置
如下图：
在理想情况下，插入、查询、删除的时间复杂度可达到 O (1)（常数级），无需像数组那样遍历元素，也无需像链表那样逐个查找，直接通过下标访问。
但实际中可能出现哈希冲突（不同的 Key 通过哈希函数计算出相同的索引），如下图：
HashMap 中为了解决哈希冲突问题，将哈希冲突的键（key）对应的所有值使用链表进行存储，如下图：
当链表长度超过 8 时，会自动将链表转为红黑树，如下图：
无序性：存储的元素顺序与插入顺序无关，也不保证元素顺序的稳定性，即多次访问 HashMap，得到的顺序可能会有所差异。
键唯一性：键（key）不能重复，若插入相同键的键值对，新值会覆盖旧值。
允许 null：允许一个 null 键和多个 null 值。
非线程安全：多线程环境下并发修改可能导致数据不一致，需使用 Collections.synchronizedMap() 或 ConcurrentHashMap 替代，根据业务场景自行选择。
性能特性：理想情况下（即无哈希冲突），get 和 put 操作的时间复杂度为 O (1)。如果哈希冲突严重时（即所有 Key 的哈希值都一样，这下知道哈希函数的重要性了吧），性能可能退化至 O (n)，红黑树优化后可提升至 O (log n)。
HashMap 的初始容量与负载因子分别为：
初始容量默认为 16（必须是 2 的幂）
负载因子默认为 0.75，当元素数量超过容量 × 负载因子时会触发扩容（容量翻倍）
下面是 HashMap 的常用方法：
V put(K key, V value) 向集合中添加或更新键值对。若集合中已存在指定键，则用新值覆盖旧值，并返回被覆盖的旧值；若不存在该键，则新增键值对，返回 null。
V get(Object key) 根据指定的键获取对应的值。若集合中存在该键，则返回关联的值；若不存在该键，则返回 null。
V remove(Object key) 删除集合中指定键对应的键值对。若集合中存在该键，则移除键值对并返回被删除的值；若不存在该键，则返回 null。
boolean containsKey(Object key) 判断集合中是否包含指定的键。若存在该键，返回 true；否则返回 false。
boolean containsValue(Object value) 判断集合中是否包含指定的值。若存在至少一个键关联此值，返回 true；否则返回 false。
int size() 返回当前集合中包含的键值对的数量。
boolean isEmpty() 判断集合是否为空。若集合中没有任何键值对（size () 为 0），返回 true；否则返回 false。
void clear() 清空集合中所有的键值对，执行后集合变为空（size () 为 0）。
Set<K> keySet() 返回一个包含集合中所有键的 Set 视图。该 Set 与原集合关联，对 Set 的修改会影响原集合，反之亦然。
Collection<V> values() 返回一个包含集合中所有值的 Collection 视图。该 Collection 与原集合关联，对 Collection 的修改会影响原集合，反之亦然。
Set<Map.Entry<K,V>> entrySet() 返回一个包含集合中所有键值对（Map.Entry 对象）的 Set 视图。每个 Entry 对象代表一个键值对，通过该视图可遍历、修改集合中的键值对（修改 Entry 的值会影响原集合）。
void putAll(Map<? extends K,? extends V> m) 将参数 m 中所有的键值对添加到当前集合中。若存在相同的键，则用 m 中的值覆盖当前集合中的值。
下面同一个简单示例演示 HashMap 的基本用法：
package com.hxstrive.java_collection.hashMap;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Collection;
public class HashMapDemo {
public static void main(String[] args) {
// 创建 HashMap 实例
HashMap<String, Integer> scores = new HashMap<>();
// 1. 添加元素 (put 方法)
scores.put("Alice", 90);
scores.put("Bob", 85);
scores.put("Charlie", 95);
scores.put("David", 88);
// 添加重复的键会覆盖原有值
scores.put("Bob", 87);
System.out.println("HashMap 中的内容: " + scores);
// 2. 获取元素 (get 方法)
int aliceScore = scores.get("Alice");
System.out.println("Alice 的分数: " + aliceScore);
// 3. 判断是否包含键/值
boolean hasCharlie = scores.containsKey("Charlie");
boolean hasScore90 = scores.containsValue(90);
System.out.println("是否包含 Charlie: " + hasCharlie);
System.out.println("是否包含分数 90: " + hasScore90);
// 4. 获取集合大小
System.out.println("元素数量: " + scores.size());
// 5. 遍历 HashMap
System.out.println("\n通过 keySet 遍历:");
Set<String> names = scores.keySet();
for (String name : names) {
System.out.println(name + ": " + scores.get(name));
}
System.out.println("\n通过 entrySet 遍历:");
Set<Map.Entry<String, Integer>> entries = scores.entrySet();
for (Map.Entry<String, Integer> entry : entries) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 6. 获取所有值
System.out.println("\n所有分数: " + scores.values());
// 7. 删除元素
scores.remove("David");
System.out.println("删除 David 后的内容: " + scores);
// 8. 清空集合
scores.clear();
System.out.println("清空后是否为空: " + scores.isEmpty());
}
}运行结果：
HashMap 中的内容: {Bob=87, Alice=90, Charlie=95, David=88}
Alice 的分数: 90
是否包含 Charlie: true
是否包含分数 90: true
元素数量: 4
通过 keySet 遍历:
Bob: 87
Alice: 90
Charlie: 95
David: 88
通过 entrySet 遍历:
Bob: 87
Alice: 90
Charlie: 95
David: 88
所有分数: [87, 90, 95, 88]
删除 David 后的内容: {Bob=87, Alice=90, Charlie=95}
清空后是否为空: true
HashMap 的底层采用 “数组 + 链表 + 红黑树” 的复合结构，具体如下：
（1）数组（哈希表主体）数组被称为 table，每个元素是一个 桶（Bucket），用于存储键值对。数组的索引通过键的哈希值计算得到，这是实现快速访问的基础。源码如下：
/** * 哈希表的底层数组，在首次使用时初始化，并根据需要进行扩容 * * 当数组被分配内存时，其长度始终是2的幂次方，这是为了: * 1. 优化哈希值与数组索引的映射计算（使用位运算替代取模操作） * 2. 确保扩容时元素能够均匀分布到新的数组中 * * 该数组存储的是链表或红黑树的头节点，当链表长度超过阈值时，会转换为红黑树以提高查询效率 */ transient Node<K,V>[] table;
（2） 链表（解决哈希冲突）当不同的键通过哈希计算得到相同的数组索引时，会产生哈希冲突。此时，冲突的键值对会以链表的形式存储在同一个桶中，即每个桶的元素是链表的头节点。源码如下：
/**
* 基础哈希桶节点，用于存储大多数键值对条目
*/
static class Node<K,V> implements Map Map.Entry<K,V> {
// 键的哈希值
final int hash;
// 键对象（不可修改，确保哈希值稳定性）
final K key;
// 值对象（可修改）
V value;
// 指向链表中下一个节点的引用（用于处理哈希冲突时的链式存储）
Node<K,V> next;
/**
* 构造哈希桶节点
* @param hash 键的哈希值
* @param key 键对象
* @param value 对应的值对象
* @param next 链表中的下一个节点
*/
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
/**
* 获取当前节点的键
* @return 键对象
*/
public final K getKey() { return key; }
/**
* 获取当前节点的值
* @return 值对象
*/
public final V getValue() { return value; }
/**
* 重写toString方法，返回键值对的字符串表示
* @return 格式为"key=value"的字符串
*/
public final String toString() { return key + "=" + value; }
/**
* 计算当前节点的哈希值
* 由键的哈希值与值的哈希值通过异或运算得到
* @return 节点的哈希值
*/
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* 设置节点的新值，并返回旧值
* @param newValue 新的值对象
* @return 被替换的旧值对象
*/
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/**
* 判断当前节点与另一个对象是否相等
* 相等条件：两个对象是同一个实例，或同为 Map.Entry 且键和值分别相等
* @param o 待比较的对象
* @return 若相等则返回 true，否则返回 false
*/
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}（3）红黑树（优化长链表性能）当链表长度超过阈值（默认 8），且数组长度不小于 64 时，链表会自动转为 红黑树。这是因为链表的查询时间复杂度为 O (n)，而红黑树可将查询复杂度优化至 O (log n)，避免长链表导致的性能下降。反之，当红黑树的节点数减少到 6 时，会重新转为链表（留出缓冲，避免频繁转换）。源码如下：
/**
* 树型桶的节点实体。继承自LinkedHashMap.Entry（该类本身继承自Node），
* 因此既可作为普通节点的扩展，也可作为链表节点的扩展使用
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 红黑树的父节点引用
TreeNode<K,V> left; // 红黑树的左子节点
TreeNode<K,V> right; // 红黑树的右子节点
TreeNode<K,V> prev; // 删除节点时用于解除下一个节点链接的前驱节点引用
boolean red; // 红黑树节点颜色标识（true为红色，false为黑色）
/**
* 构造树节点
* @param hash 键的哈希值
* @param key 键对象
* @param val 对应的值对象
* @param next 链表中的下一个节点（维持链表结构的引用）
*/
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 返回当前节点所在红黑树的根节点
* @return 红黑树的根节点
*/
final TreeNode<K,V> root() {
//...
}
/**
* 确保给定的根节点成为其所在桶的第一个节点
* @param tab 哈希表数组
* @param root 需要设为桶首的根节点
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
//...
}
/**
* 从根节点p开始查找具有指定哈希值和键的节点
* kc参数用于缓存首次比较键时通过comparableClassFor(key)获取的类信息
* @param h 要查找的键的哈希值
* @param k 要查找的键
* @param kc 键的比较类信息缓存
* @return 找到的节点，若不存在则返回null
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
//...
}
/**
* 调用根节点的find方法查找指定节点
* @param h 要查找的键的哈希值
* @param k 要查找的键
* @return 找到的节点，若不存在则返回null
*/
final TreeNode<K,V> getTreeNode(int h, Object k) {
//...
}
/**
* 当哈希值相等且键不可比较时，用于插入排序的打破平局工具
* 不需要完整的排序，仅需一致的插入规则以在重平衡时维持等价性
* 适当简化平局处理可略微简化测试
* @param a 比较对象a
* @param b 比较对象b
* @return 排序结果（-1、0或1）
*/
static int tieBreakOrder(Object a, Object b) {
//...
}
/**
* 将当前节点链接的所有节点转换为红黑树结构
* @param tab 哈希表数组
* @return 红黑树的根节点
*/
final void treeify(Node<K,V>[] tab) {
//...
}
/**
* 将当前节点链接的红黑树节点转换为普通链表节点
* @param map 当前HashMap实例
* @return 转换后的链表头节点
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
//...
}
/**
* 红黑树版本的putVal方法，用于在树中插入节点
* @param map 当前HashMap实例
* @param tab 哈希表数组
* @param h 键的哈希值
* @param k 键对象
* @param v 值对象
* @return 插入的节点或已存在的相同键节点
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
//...
}
/**
* 移除指定节点（调用前需确保节点存在）
* 比典型的红黑树删除代码更复杂，因为不能将内部节点的内容与
* 被"next"指针固定的叶子后继节点交换（这些指针在遍历中可独立访问）
* 因此改为交换树的链接。若当前树的节点数过少，会将桶转换回普通链表
* （测试表明当节点数在2到6之间时触发转换，具体取决于树结构）
* @param map 当前HashMap实例
* @param tab 哈希表数组
* @param movable 是否允许移动节点（影响并发处理）
*/
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
//...
}
/**
* 将树型桶中的节点分裂为低位和高位两个树桶，
* 若分裂后节点数过少则转换为普通链表。仅在扩容时调用；
* 参见上述关于分裂位和索引的讨论
* @param map 当前HashMap实例
* @param tab 用于记录桶头的哈希表数组
* @param index 正在分裂的桶的索引
* @param bit 用于分裂的哈希位
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//...
}
/* ------------------------------------------------------------ */
// 红黑树方法，均改编自《算法导论》(CLR)
/**
* 红黑树的左旋操作
* @param root 红黑树的根节点
* @param p 要进行左旋的节点
* @return 旋转后的根节点
*/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
//...
}
/**
* 红黑树的右旋操作
* @param root 红黑树的根节点
* @param p 要进行右旋的节点
* @return 旋转后的根节点
*/
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
//...
}
/**
* 插入节点后平衡红黑树（维持红黑树性质）
* @param root 红黑树的根节点
* @param x 新插入的节点
* @return 平衡后的根节点
*/
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
//...
}
/**
* 删除节点后平衡红黑树（维持红黑树性质）
* @param root 红黑树的根节点
* @param x 被删除的节点
* @return 平衡后的根节点
*/
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {
//...
}
/**
* 递归检查红黑树的不变性（用于验证树结构的正确性）
* @param t 要检查的树节点
* @return 若满足红黑树性质则返回true，否则返回false
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
//...
}
}在 HashMap 中，哈希值计算与索引确定的逻辑分散在 哈希值扰动 和 索引计算 两个核心步骤中，源代码如下：
HashMap 通过 hash(Object key) 方法对键的原始哈希值进行 扰动处理（高低位异或），目的是让哈希值的分布更均匀，减少哈希冲突。源代码如下：
/**
* 计算key的哈希值并将哈希值的高位与低位进行异或(XOR)运算，实现高位信息向低位的扩散
*
* 由于哈希表使用2的幂次大小的掩码来计算索引位置，那些只在当前掩码以上的位不同的哈希值集合
* 总会发生冲突。（已知的例子包括在小表中持有连续整数的Float键集合）
*
* 因此我们应用一种转换，将高位的影响扩散到低位。这在速度、实用性和位扩散质量之间需要权衡。
* 因为许多常见的哈希集合已经有合理的分布（因此从扩散中受益不大），并且我们使用树来处理桶中
* 大量的冲突，所以我们只是以最便宜的方式对一些移位的位进行异或运算，以减少系统性损失，
* 同时也纳入最高位的影响，否则由于表的边界限制，这些最高位永远不会在索引计算中被使用。
*/
static final int hash(Object key) {
int h; // 用于存储key的原始哈希值
// 如果 key 为 null，直接返回 0 作为哈希值
// 否则，先获取 key 的原始哈希值 h，再将 h 与 h 右移 16 位的结果进行异或运算
// 这步操作将高 16 位的信息混入低 16 位，减少哈希冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}上述源码，通过将原始哈希值的高 16 位与低 16 位进行异或运算，让高位信息也参与到后续的索引计算中，从而减少哈希冲突的概率，特别是在哈希表容量较小时效果更明显。
索引通过 “处理后的哈希值 & 数组长度 - 1” 计算，对应 putVal、get 等方法中定位桶（数组位置）的逻辑，下面以 putVal 方法源码为例：
/**
* 实现 Map.put 及相关方法的核心逻辑
* 负责将键值对存入哈希表，处理哈希冲突，并在需要时进行扩容或树化操作
*
* @param hash 键的哈希值（经过 hash() 方法处理过的）
* @param key 要存入的键
* @param value 要存入的值
* @param onlyIfAbsent 如果为true，当键已存在时不覆盖原有值
* @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; int n, i;
// 1. 检查哈希表是否未初始化或为空，如果是则进行扩容初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length; // 扩容后获取新的数组长度
// 2. 计算键在哈希表中的索引位置，并检查该位置是否为空
// 索引计算方式：(数组长度-1) & 哈希值（利用位运算高效计算）
if ((p = tab[i = (n - 1) & hash]) == null)
// 位置为空时，直接创建新节点存入该位置
tab[i] = newNode(hash, key, value, null);
else {
// 3. 哈希冲突：该位置已有节点，需要处理冲突
Node<K,V> e; K k; // e用于记录匹配到的节点，k用于临时存储节点的键
//...忽略...
}
//...忽略...
return null; // 新插入节点，返回null
}注意，上述源码中，“(n - 1) & hash”等价于“hash % n”，n 必须是 2 的幂，如 2^2、2^4、2^8 等等，你知道为什么吗？下面将娓娓道来：
首先，我们需要了解 2^n 的二进制特征，如果 n = 2^k，则 n 的二进制将表示为“1 后面跟 k 个 0”，例如：
n=2（2¹）→ 二进制 10
n=4（2²）→ 二进制 100
n=8（2³）→ 二进制 1000
n=16（2⁴）→ 二进制 10000
而 n - 1 的二进制将表示为“k 个连续的 1”（k 为 2 的多少次方，刚好与 n 的二进制互补），例如：
n=2（2¹）→ n-1=1 → 二进制 01
n=4（2²）→ n-1=3 → 二进制 011
n=8（2³）→ n-1=7 → 二进制 0111
n=16（2⁴）→ n-1=15 → 二进制 01111
明白了上面的二进制特征，那么“(n - 1) & hash”操作其实就是保留二进制最右边的 k 位。例如：
(n - 1) & hash => (8 - 1) & 25
其中，25 的二进制位 11001，8 等价 2^3，k 等于 3。因此，(8 - 1) & 25 就是保留最右边的 3 个二进制位 001，即十进制 1。
新的疑惑来了，为什么会与 hash % n（n 必须是 2 的幂）等价？
取模运算 hash % n 的数学含义是 “求 hash 除以 n 后的余数”，余数范围是 [0, n-1]。
取模运算从二进制视角看：若 n=2^k，意味着 n 是“能被 k 个二进制位表示的最大数 + 1”，例如：
n=4（2^2）= 3+1，3 是 2 个二进制位的最大数 11
n=8（2^3）= 7 + 1, 7 是 3 个二进制位的最大数 111
n=16（2^4）= 15 + 1, 15 是 4 个二进制位的最大数 1111
此时，hash 除以 n 的余数，本质是 hash 的二进制表示的“低 k 位”（可以这样理解，hash % n 取值范围为 0~n-1，而 n - 1 的二进制将表示为“k 个连续的 1”）。例如：
hash=13（二进制 1101），n=4（2²，k=2）： hash 除以 4 的商是 3（二进制 11），余数是 1（二进制 01）→ 余数恰好是 hash 的二进制表示的 “低 2 位”（01）；
hash=25（二进制 11001），n=8（2³，k=3）： hash 除以 8 的商是 3（二进制 11），余数是 1（二进制 001）→ 余数恰好是 hash 的二进制表示的“低 3 位”（001）。
注意，在编程语言中，hash & (n - 1) 的执行效率远高于 hash % n，原因是：
取模运算（%）属于 “算术运算”，需要经过除法、求余等复杂逻辑；
位运算（&）属于“硬件级运算”，直接操作二进制位，无需复杂计算，执行速度接近 CPU 时钟周期。
这也是 HashMap、ArrayList 等容器中，当需要“取模定位索引” 时（如 HashMap 数组索引计算），会强制将容量设为 2 的幂的核心原因 —— 用更高效的位运算替代取模运算，提升性能。
当两个不同的键（Key）通过哈希计算得到相同的数组索引时，会触发哈希冲突。
在 HashMap 中，主要通过链地址法解决哈希冲突问题。HashMap 的底层哈希表数组（table）每个索引对应一个 “桶（Bucket）”，当冲突发生时，HashMap 会将冲突的键值对以“链式结构” 存储在对应桶中 —— 即桶中存储的不是单个节点，而是链表（或红黑树）的头节点，新元素会被添加到该链表 / 红黑树中，从而实现冲突键值对的有序存储。
注意：当桶中链表的长度超过阈值（默认 8），且数组长度不小于 64 时，HashMap 会将链表自动转为红黑树。这是因为链表的查询时间复杂度为 O (n)，而红黑树的查询复杂度可降至 O (log n)，能有效解决长链表导致的性能退化问题，进一步优化哈希冲突场景下的操作效率。
当哈希表中键值对数量（size）超过阈值（threshold） 时，触发 resize() 方法进行扩容。
阈值计算公式：threshold = capacity × loadFactor（默认初始容量 16，负载因子 0.75，初始阈值为 12）。
若哈希表未初始化（table == null），调用 resize() 会直接初始化数组（按初始容量创建）。
下面以 putVal 方法源码为例：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果 table 为 null，或者没有元素
// 直接调用 resize() 进行扩容初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//...
else {
//...
}
//...
// 判断是否扩容
if (++size > threshold)
resize(); // 调用 resize 进行扩容
//...
return null;
}resize() 方法源码如下：
/**
* 初始化哈希表或哈希表容量扩容。
* 若表为 null，将根据 threshold 字段中保存的初始容量目标进行分配。
* 否则，由于使用 2 的幂次扩容，每个桶中的元素要么保持在原索引位置，
* 要么在新表中以 2 的幂次偏移量（原容量大小）移动到新索引位置。
*
* @return 新的哈希表数组
*/
final Node<K,V>[] resize() {
// 保存旧的哈希表数组
Node<K,V>[] oldTab = table;
// 计算旧表容量：若旧表为 null 则容量为 0，否则为旧表长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 保存旧的阈值（触发扩容的临界值）
int oldThr = threshold;
// 声明新容量和新阈值变量
int newCap, newThr = 0;
// 情况1：旧表已初始化（容量大于0）
if (oldCap > 0) {
// 若旧容量已达到最大容量（1 << 30），则不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
// 将阈值设为整数最大值，后续不再触发扩容
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 否则，新容量 = 旧容量 × 2（左移1位实现翻倍）
// 若翻倍后仍小于最大容量，且旧容量不小于默认初始容量（16），则新阈值 = 旧阈值 × 2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 阈值翻倍
}
// 情况2：旧表未初始化，但旧阈值大于0（构造函数中指定了初始容量时，threshold 暂存初始容量）
else if (oldThr > 0)
newCap = oldThr;
// 情况3：旧表未初始化且旧阈值为0（使用默认参数初始化）
else {
newCap = DEFAULT_INITIAL_CAPACITY; // 默认初始容量16
// 默认阈值12（16×0.75）
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 补充计算新阈值（针对情况 2 中未设置 newThr 的场景）
if (newThr == 0) {
float ft = (float)newCap * loadFactor; // 新容量 × 负载因子
// 若新容量小于最大容量且计算结果也小于最大容量，则新阈值为计算结果，否则为整数最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 更新全局阈值为新阈值
threshold = newThr;
// 创建新的哈希表数组（容量为newCap）
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 将哈希表引用指向新数组
table = newTab;
// 若旧表不为null，将旧表中的元素迁移到新表
if (oldTab != null) {
// 遍历旧表的每个桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 若当前桶不为空，保存桶的头节点
if ((e = oldTab[j]) != null) {
// 释放旧表中当前桶的引用（便于GC回收）
oldTab[j] = null;
// 子情况1：当前桶只有一个节点（无链表/红黑树）
if (e.next == null)
// 直接计算新索引并放入新表（新容量-1与哈希值按位与）
newTab[e.hash & (newCap - 1)] = e;
// 子情况2：当前桶是红黑树结构
else if (e instanceof TreeNode)
// 调用红黑树的split方法拆分树节点并迁移
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 子情况3：当前桶是链表结构（拆分链表并迁移）
else { // 保持链表顺序（尾插法迁移，避免环形链表）
// 定义两个子链表的头节点和尾节点：
// lo链表：新索引 = 旧索引（j）
// hi链表：新索引 = 旧索引 + 旧容量（j + oldCap）
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍历链表，拆分节点到两个子链表
do {
next = e.next; // 保存下一个节点引用
// 关键：通过哈希值与旧容量的按位与结果判断新索引
// 旧容量是2的幂，二进制为100...0，此操作等价于判断哈希值的第log2(oldCap)位是否为0
if ((e.hash & oldCap) == 0) {
// 若为0，放入lo链表（新索引不变）
if (loTail == null)
loHead = e; // 初始化头节点
else
loTail.next = e; // 尾插法链接节点
loTail = e; // 更新尾节点
}
else {
// 若为1，放入hi链表（新索引 = 旧索引 + 旧容量）
if (hiTail == null)
hiHead = e; // 初始化头节点
else
hiTail.next = e; // 尾插法链接节点
hiTail = e; // 更新尾节点
}
} while ((e = next) != null); // 遍历完所有节点
// 将lo链表放入新表的原索引位置（j）
if (loTail != null) {
loTail.next = null; // 切断链表尾部引用
newTab[j] = loHead;
}
// 将hi链表放入新表的偏移索引位置（j + oldCap）
if (hiTail != null) {
hiTail.next = null; // 切断链表尾部引用
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新的哈希表数组
return newTab;
}更多信息参考 https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html API 文档。
川公网安备51010802032098