Java HashMap 详解：从哈希定位到扩容与线程安全（JDK 25）

HashMap 的日常用法很简单：调用 put 保存键值对，调用 get 根据键查找。但要理解它为什么快、什么时候会变慢，就需要把哈希值、桶、冲突和扩容串起来。

这篇文章沿着一条具体的路径展开：一个键值对如何进入 HashMap，又如何在扩容之后被找到。 在这条路径上，我们也会回答几个常见问题：为什么容量是 2 的幂？为什么默认负载因子是 0.75？什么时候会转成红黑树？到了 JDK 25，HashMap 为什么仍然不能并发读写？

源码基线：OpenJDK 25 更新分支，本地检出标签 jdk-25.0.4.1+1，提交 7b65d74bcbd7c3a0b4c1f5c5bd85e64aa2e51b4a。文中的内部方法、常量和执行路径以这份源码为准；这些是实现细节，不是所有 Map 都必须遵守的接口约定。运行实验使用 Temurin 25.0.3+9。

一、先认识 HashMap 存储的东西

1. 键唯一，值可以重复

下面是一个可以直接运行的例子：

import java.util.HashMap;

public class HashMapBasics {
    public static void main(String[] args) {
        var ages = new HashMap<String, Integer>();

        ages.put("Hanserwei", 18);
        ages.put("Hanserwu", 25);

        Integer oldAge = ages.put("Hanserwei", 30);
        System.out.println(oldAge);             // 18
        System.out.println(ages.get("Hanserwei")); // 30
        System.out.println(ages.size());        // 2

        ages.remove("Hanserwu");
        System.out.println(ages.containsKey("Hanserwu")); // false

        ages.put("unknown", null);
        System.out.println(ages.get("unknown"));         // null
        System.out.println(ages.get("missing"));         // null
        System.out.println(ages.containsKey("unknown")); // true
        System.out.println(ages.containsKey("missing")); // false
    }
}

再次 put 一个相等的键，会替换这个键对应的值，不会额外增加一条映射。这里的“相等”遵循键的 equals 约定，而不是要求两次传入同一个对象。

HashMap 允许一个 null 键，也允许多个键对应 null 值。因此，get(key) == null 无法区分“键不存在”和“键存在但值为 null”，需要时应配合 containsKey。如果直接把可能为 null 的返回值赋给 int，自动拆箱会抛出 NullPointerException。

2. 数组负责定位，桶内结构负责处理冲突

JDK 25 的核心结构依旧是 数组 + 链表 / 红黑树。

数组 table 的每个位置称为一个桶。桶为空时保存 null；非空时保存一个节点引用，后面可能只有这一个节点，也可能连接多个节点。普通节点的核心字段如下，省略了构造器和其他方法：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

注意，节点保存了插入时计算出的 hash。后面解释扩容时，这个字段很关键。

graph LR
    T0["table[0]"] --> Z["null"]
    T1["table[1]"] --> A["Node：key A / value A"]
    T2["table[2]"] --> B["Node：key B / value B"]
    B -->|next| C["Node：key C / value C"]
    C -->|next| D["Node：key D / value D"]
    T3["table[3]"] --> R["TreeNode：树桶入口"]
    R --> L["左子树"]
    R --> H["右子树"]

上图是结构示意，只画出部分桶。树桶中的节点还保留 next 等链接，实际并不是把所有链式关系都丢弃了；这些链接也用于遍历和扩容拆分。

哈希冲突不等于键重复。 两个不相等的键可以落进同一个桶，它们都需要保存；只有命中相等的键时，put 才会覆盖原来的值。

二、从 key 到数组下标：两步各做什么

HashMap 定位桶的过程可以拆成两步：

key.hashCode() → hash 扰动 → 与容量掩码做位与 → 桶下标

1. hash 方法：把高位信息混入低位

JDK 25 的 hash 方法如下：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里涉及两个位运算：

• >>> 16：无符号右移 16 位，左侧补 0。
• ^：按位异或，相同为 0，不同为 1。

为什么需要这一步？因为容量较小时，下标计算只会使用哈希值的少量低位。如果两个键的 hashCode() 只在高位不同，这些差异就可能完全用不上。

例如，假设两个键的原始哈希码分别为 0x00000001 和 0x00010001，当前容量为 16：

原本都会落在桶 1，经过扰动后可以落到不同的桶。

它只能减少某些由位分布造成的冲突，不能保证均匀，更不能把相同的 hashCode() 变成不同的哈希值。如果所有键都返回同一个哈希码，扰动之后仍然全部相同。

null 键的扰动哈希值为 0，因此在数组已经分配时，它位于桶 0。其他键也可能落到桶 0。

2. (n - 1) & hash：保留用于定位的低位

当数组长度为 n 时，下标计算是：

int index = (n - 1) & hash;

HashMap 已分配的数组长度是 2 的幂。假设 n = 16，那么 n - 1 = 15，二进制低 4 位都是 1：

hash = 21     0001 0101
n - 1 = 15    0000 1111
按位与结果    0000 0101  → 下标 5

掩码把高位清零，保留低 4 位，所以结果一定在 0～15 之间。容量扩大到 32 时，掩码变成 31，便可以使用低 5 位。

这里需要把一个常见说法说准确：对正的、且为 2 的幂的 n，即使 hash 是负数，也有：

(hash & (n - 1)) == Math.floorMod(hash, n)

但它不总是等于 Java 的 % 结果，因为 % 对负被除数可能返回负数。例如：

System.out.println(-7 % 16);                // -7
System.out.println(Math.floorMod(-7, 16)); // 9
System.out.println(-7 & 15);                // 9

& 在这里是位与运算，用它实现桶定位有明确的容量前提。不能把“容量是偶数”或“容量是某个数的整数倍”当作相同条件，也不能因为使用位运算就保证哈希分布良好。

3. 下标相同，还需要比较键

找到桶，只完成了第一层筛选。桶内节点是否匹配，还要检查：

node.hash == hash
    && (node.key == key || (key != null && key.equals(node.key)))

这段是为便于阅读改写的匹配条件。可以分成三步理解：先比保存的扰动哈希值，再看是不是同一个对象，必要时调用 equals。

因此，自定义键必须遵守一个约定：如果两个对象 equals 为 true，它们的 hashCode 必须相同。 反过来不成立，哈希码相同的对象完全可以不相等。

还要避免在插入后修改参与 equals 或 hashCode 的字段。节点保存的是旧哈希值，而后续查询根据当前对象计算新哈希值；哪怕传入的还是同一个对象，也可能找不到原来的映射。

使用只包含不可变组件的 record 往往很合适：

record UserKey(long tenantId, long userId) {}

但 record 只是组件引用不能重新赋值，不会自动把组件引用的集合等对象变成不可变对象。

三、一次 put 是怎样完成的

公开的 put 方法很短：

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

真正的插入由 putVal 完成。先看流程，再看影响行为的源码片段，比一次性阅读整个方法更容易抓住重点。

graph TD
    A["put：计算扰动哈希"] --> B{"table 已分配？"}
    B -->|否| C["resize：初始化数组"]
    B -->|是| D["计算桶下标"]
    C --> D
    D --> E{"桶为空？"}
    E -->|是| F["创建普通节点"]
    E -->|否| G["检查桶首节点，再按链表或树查找"]
    G --> H{"找到相等的键？"}
    H -->|是| I["替换 value，返回旧值"]
    H -->|否| J["插入新节点；链表路径按条件尝试树化"]
    F --> K["modCount 和 size 增加"]
    J --> K
    K --> L{"size 大于 threshold？"}
    L -->|是| M["resize：扩容"]
    L -->|否| N["返回 null"]
    M --> N

这张图描述的是普通 HashMap.put 主路径，省略了供子类使用的钩子。

1. 数组延迟分配

执行下面这行时，并不会立刻创建一个长度为 16 的数组：

var map = new HashMap<String, Integer>();

无参构造器只设置默认负载因子，table 仍然为 null。第一次 put 才会通过 resize() 分配数组。

所以“默认容量 16”的准确含义是：无参构造的 HashMap 沿这条路径首次初始化时，数组长度为 16。它既不是所有 HashMap 的起始容量，也不是构造时已经分配的空间。

2. 更新已有键，不增加 size

putVal 找到已有映射后，会替换值并返回旧值，不会执行后面的 ++size。因此，默认容量为 16、已经存了 12 个键时，反复更新这些键并不会因为数量阈值而扩容。

3. 新增映射后，检查的是“大于阈值”

普通 put 路径末尾的源码是：

++modCount;
if (++size > threshold)
    resize();

默认容量 16、负载因子 0.75 时，数量阈值为 12。在没有桶冲突提前触发扩容的前提下：

• 插入第 12 个不同的键后，size == 12，不因数量阈值扩容。
• 插入第 13 个不同的键后，size == 13，扩容到 32。

这也说明，阈值计算的是映射总数，不是“已经使用的桶数”。12 个键即使集中在少数桶里，size 仍然是 12。

4. get 沿相同的定位规则查找

JDK 25 的入口调用关系是 get(key) → getNode(key)；当前源码的内部签名是 getNode(Object key)。

getNode 先判断数组和桶是否存在，再检查桶首节点。如果没有命中，就根据桶内结构进入树查找，或者沿 next 遍历链表。命中后返回节点，get 取出其中的值；没有命中则返回 null。

只要键的相等性和哈希码保持稳定，插入和查询就能沿相同规则找到同一条映射。

四、扩容：为什么只会留在原位，或移动到原位加旧容量

1. 先分清容量、数量、负载因子和阈值

在常规容量和负载因子下，可以把阈值理解为：

实现中存在阈值翻倍、最大容量和饱和处理，不能把这条公式机械套到全部边界情况。

还有一个读源码时容易混淆的细节：数组分配前，带容量的构造器会借用 threshold 保存首次分配的目标容量。 例如 new HashMap<>(20) 会先把这个字段设为 32；首次 put 分配 32 个桶后，它才变成通常意义上的阈值 24。

2. 容量按 2 的幂归整，正常扩容时翻倍

JDK 25 用下面的方法计算不小于目标容量的 2 的幂，并处理上下界：

static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

例如 20 会归整为 32，100 会归整为 128。正常的非首次扩容会把容量翻倍，默认负载因子下通常也把数量阈值翻倍：

容量：  16 → 32 → 64 → 128
阈值：  12 → 24 → 48 → 96

源码中的最大桶数组容量是 1 << 30。达到上限后，resize 不再继续扩大数组，并把阈值设为 Integer.MAX_VALUE；这只是实现上限，不代表机器有足够内存分配它，也不代表 HashMap 最多只能保存 1 << 30 条映射。

3. 容量翻倍，相当于多检查一位

假设旧容量是 16，新容量是 32：

旧掩码：15 = 0000 1111
新掩码：31 = 0001 1111
新增的位：16 = 0001 0000

新下标只比旧下标多受一个二进制位影响，因此只需检查：

(node.hash & oldCap) == 0

结果为 0，节点留在旧下标 j；结果不为 0，节点移动到 j + oldCap。

例如，以下四个已扰动哈希值在旧容量 16 时都落在桶 5：

graph TD
    O["旧容量 16：桶 5"] --> A["A：hash 5"]
    A --> B["B：hash 21"]
    B --> C["C：hash 37"]
    C --> D["D：hash 53"]
    D --> S["沿旧链表遍历，检查 hash 与 16 的位与结果"]
    S -->|等于 0| L["新容量 32：桶 5"]
    S -->|不等于 0| H["新容量 32：桶 21"]
    L --> LA["A：hash 5"]
    LA --> LC["C：hash 37"]
    H --> HB["B：hash 21"]
    HB --> HD["D：hash 53"]

图中的拆分保持了两个子链表各自的相对顺序：A 仍在 C 前面，B 仍在 D 前面。但这不保证整个 Map 的遍历顺序不变，也不意味着原来的四个节点还处在同一条链上。

这条“原位或原位加旧容量”的规律来自 2 的幂容量、翻倍扩容和位掩码定位，不依赖 h ^ (h >>> 16) 这个特定的扰动公式。

4. resize 不会重新调用每个键的 hashCode

迁移时使用的是节点已保存的 hash，然后按新容量定位。

JDK 25 的 resize 针对三种情况处理：

1. 桶内只有一个节点：用 e.hash & (newCap - 1) 放入新数组。
2. 普通链表：按 e.hash & oldCap 拆成低位、高位两组，分别接到两个目标桶。这里的“高位组”仅表示被检查的那一位为 1。
3. 树桶：调用 TreeNode.split，按相同的位分组，再决定每一组保留为树还是退化为链表。

迁移需要分配新的桶数组并遍历旧数组、处理节点；树桶还可能重建树或转换节点形式。因此扩容有真实成本，只是这个成本不能解释成“重新调用所有键的 hashCode()”。

普通链表迁移时还会把两个子链表的尾部 next 设为 null，用于断开旧链中的跨组连接，使两个新链表各自正确结束。

五、链表什么时候变成红黑树

树化是 HashMap 对长桶的一种处理手段。数组已经比较大、某个桶却仍聚集大量节点时，只扩大数组未必能有效改善查找，于是引入树结构。

1. 8、6、64 要放回具体路径里看

三个相关常量是：

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

常见的“链表长度到 8 就树化”容易遗漏两个细节。

首先，treeifyBin 会先检查数组容量：

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

容量小于 64 时，它优先尝试扩容。这是第二种扩容触发来源：即使总映射数尚未超过数量阈值，严重的桶冲突也可能让数组扩容。

其次，常量的值不等于所有插入路径里“插入后节点数”的边界。普通 putVal 链表路径先追加节点，再执行：

if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

这里的 binCount 从 0 开始计数。沿普通 put 连续向同一个普通链表桶插入不相等的键时，原来有 8 个节点，再插入第 9 个节点，才会调用 treeifyBin；数组容量至少为 64 时，才真正树化。

例如，对 new HashMap<>(64) 连续 put 9 个哈希码相同但互不相等的键，前 8 个还是普通节点，第 9 个插入后桶变成树。

computeIfAbsent 有自己的计数和插入逻辑。在这份源码中，同样从空 Map 开始、初始容量设为 64、连续用它插入同哈希的不同键且回调返回非 null，插入第 8 个节点时就会尝试树化。不能把 put 的边界直接套给所有 API。

2. “节点剩 6 个就退化”也不是通用规则

UNTREEIFY_THRESHOLD = 6 直接用于扩容时的树桶拆分：拆分后，某一组节点数小于等于 6，就转换成普通链表。

普通删除走的是另一条路径。removeTreeNode 根据树的形状等条件判断是否太小，并不是每次统计节点数，再统一用 <= 6 判断。通过迭代器删除时，还会受到 movable 参数的影响。

可以把这三个数字记成：8 与树化尝试相关，64 是树化时的最小数组容量，6 是扩容拆分时的退化阈值。要回答精确边界，必须同时说明调用路径。

3. 树化不等于所有查找都保证 O(log n)

红黑树的高度受到约束，但 HashMap 的树查找还需要决定往哪一边走。

它优先比较保存的哈希值；哈希值相同时，先判断键是否相等，再尝试借助源码能够识别的 Comparable 顺序。如果大量不相等的键拥有相同哈希值，又无法用比较结果区分方向，查找可能搜索多个分支。

因此，更准确的描述是：在哈希值或可用的键比较顺序能够有效区分节点时，树桶能把桶内操作控制在对数级；极端同哈希、无法有效比较的键，查找仍可能退化到线性级。 树化并不能替代正确的 hashCode 设计。

六、为什么默认负载因子是 0.75

1. 它是时间和空间的折中

先区分两个容易混用的概念：

• loadFactor 是创建 Map 时设置的参数，默认值为 0.75。
• 当前实际负载是 size / capacity，会随着插入和扩容变化。

实际负载也不是“非空桶的百分比”。同一个桶可以保存多个节点，所以实际负载可以大于 1；HashMap 的构造器也允许设置大于 1 的负载因子。

在键分布比较均匀、其他条件相同时：

源码和 API 文档把默认的 0.75 描述为时间与空间成本之间的良好折中，并没有给出“由某个概率公式唯一推导出 0.75”的结论。JDK 25 HashMap API

它是实用的默认值，不能保证对所有键分布、内存布局和访问模式都最优。没有实际测量需求时，通常保留默认值，把注意力放在键设计和容量预估上更有价值。

2. 泊松分布能解释长桶为何少见，不能证明 0.75 唯一最优

在哈希值独立、均匀分布的理想模型下，把 m 个键放入 n 个桶。对某一个固定桶，节点数 X 服从二项分布；当桶数较大时，可以用泊松分布近似：

JDK 25 源码的实现说明使用约 0.5 的参数，粗略说明在默认扩容策略下，节点分布良好时长桶很少出现，并明确提醒扩容粒度会带来较大的变化。它不是说每个时刻的实际负载都是 0.5。

以源码中的近似参数 lambda = 0.5 计算，某个桶恰有 8 个节点的概率约为 5.88 × 10^-8。这个数字描述理想随机模型中的桶长度，不能直接当作所有真实业务里的树化概率，也不能由此倒推出负载因子必须取 0.75。

另一个容易混淆的表达式是：

它表示某个指定桶在 m 次放入后仍为空的概率，不是“所有放入操作都没有发生碰撞”的概率。在相同理想模型中，后者在 m <= n 时应为：

因此，把前一个概率设为大于 0.5，推得 ln 2，再取整或折中成 0.75，并不能构成 HashMap 默认负载因子的正确推导。

七、JDK 25 中怎样设置初始容量

1. 构造器参数是容量目标，不是预计映射数量

假设预计要保存 100 条映射：

var map = new HashMap<String, Integer>(100);

这个 100 会归整为 128 个桶；默认负载因子下，数量阈值是 96。因此，普通 put 插入第 97 个不同键时，仍会因为超过数量阈值扩容。

2. 已知映射数量时，使用 newHashMap

在 JDK 25 中，可以直接写：

HashMap<String, Integer> map = HashMap.newHashMap(100);

这个工厂方法接收的是预计映射数量。它从 JDK 19 就已经提供，并不是 JDK 25 才新增的方法。

在这份源码中，它先按默认负载因子计算所需容量，再调用构造器归整：

预计 100 条映射
→ ceil(100 / 0.75) = 134
→ 归整为 256 个桶
→ 首次分配后，数量阈值为 192

数组仍然延迟分配。这种写法可以避免手工混淆容量和预计条目数。JDK 25 newHashMap API

这里避免的是通常由数量阈值引起的中途扩容；不能把它理解成对任意冲突分布都绝对不扩容。例如，为很少的条目预估容量时，如果它们全挤在同一桶，前面讲的树化尝试仍可能触发扩容。

也不应无限放大初始容量。HashMap 遍历需要扫描桶数组，再访问其中的映射，成本与 capacity + size 成正比。桶太多会浪费空间，也可能拖慢遍历。

3. 删除元素不会自动缩小桶数组

在这份 JDK 25 实现中，普通 remove 不会缩容，clear 清空映射也会保留已经分配的桶数组。

如果一个长期存活的 Map 曾经很大，后来只剩少量数据，可以在合适的时机创建新 Map 来重建容量。原 Map 的引用、并发访问方式和业务中的共享关系也要随之处理，不能只在某个局部变量上重新赋值，就假设所有使用者都切换了容器。

八、JDK 25 的 HashMap 为什么仍然线程不安全

问题的根源是：HashMap 的插入、更新、删除和扩容没有提供并发访问所需的原子性与可见性保证。

解释当前版本时，没有必要再把旧版本的扩容头插成环过程搬过来。只看当前 putVal 的空桶插入，就能看到真实的数据竞争。

1. 两个线程可能覆盖彼此插入的节点

相关源码可以简化为：

if (tab[index] == null) {
    tab[index] = newNode(hash, key, value, null);
}

“判断为空”和“写入节点”不是一个不可分割的操作。假设数组已初始化，两个不相等的键恰好落入同一空桶，可能出现下面的交错：

sequenceDiagram
    participant A as 线程 A
    participant T as 同一个桶
    participant B as 线程 B
    A->>T: 读取桶，看到 null
    B->>T: 读取桶，也看到 null
    A->>T: 写入节点 A
    B->>T: 写入节点 B，覆盖桶中的引用
    Note over A,B: 一种可能的交错：节点 A 不再从该桶可达

不需要发生扩容，也不需要两个键相等，就可能丢失映射。++size 等更新同样不是原子操作，计数也可能出错。

2. 并发 get 也不能保证读到正确状态

一个线程写入、另一个线程读取，如果没有建立必要的 happens-before 关系，就不能保证读者看到最新状态。

扩容又包含一系列更新：分配新数组、修改 table、迁移各个桶、调整节点链接。在 JDK 25 的 resize 中，table = newTab 位于迁移循环之前。未同步的读者可能观察到尚未迁移完的数据，也可能观察到旧状态。

这里说的是可能出现的并发后果，不能写成“另一个线程必然立即看到新数组，所以 get 必然返回 null”。Java 内存模型没有为这种未同步的访问提供这样的保证。

即使只是覆盖已有键的值、不改变 size，也不能据此认定并发安全。“不是结构性修改”只是在解释结构变化和迭代器检测，不能替代线程间的同步。

3. fail-fast 用来发现错误，不负责保证线程安全

HashMap 的迭代器保存创建时的 modCount，遍历时检查它与当前计数是否一致。发生不符合预期的结构性修改时，可能抛出 ConcurrentModificationException。

这也是单线程代码里边遍历、边直接调用 map.remove 容易报错的原因。需要在迭代时删除当前元素，可以使用迭代器自身的 remove，或在合适的场景下使用 entrySet().removeIf(...)。

但 fail-fast 是尽力检测；没有抛异常不代表不存在并发问题，不能靠捕获这个异常实现同步。JDK 25 HashMap 的并发与迭代说明

4. 根据共享方式选择容器

例如，多线程计数应把一次计数更新表达为单次原子操作：

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
counts.merge("java", 1, Integer::sum);

如果换成“先 get、自行加一、再 put”，即使容器本身是 ConcurrentHashMap，整个读改写过程也不是原子的。JDK 25 ConcurrentHashMap API

当前 ConcurrentHashMap 的实现使用 CAS、桶级同步以及扩容协作等机制，不能再解释成“把整个 Map 分成多个 Segment 小 Map，各自加锁”。源码保留的 Segment 类型主要服务于序列化兼容，也不代表当前并发更新走的是旧分段锁架构。

九、把源码结论用回日常代码

1. 按键聚合时，不必反复手写查找和插入

在单线程场景下，可以用 computeIfAbsent 为分组创建列表：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

HashMap<String, List<String>> postsByTag = new HashMap<>();
postsByTag.computeIfAbsent("java", key -> new ArrayList<>())
          .add("HashMap 详解");

键不存在，或者对应值为 null 时，才需要计算；回调返回 null 时，不会新增一条非空值映射。回调中不要修改正在计算的这个 Map，源码会尽力检测结构性修改，但这不是事务回滚机制。

换成 ConcurrentHashMap 也不意味着内部的 ArrayList 就能被多个线程安全地调用 add：容器对映射的并发保证，不会自动延伸到值对象内部。

另外，computeIfAbsent、compute 和 merge 各有自己的实现路径。前文关于普通 put 在插入后检查数量阈值、链表末尾追加节点等细节，不应当推广成所有写入 API 的统一规则。

2. 不要依赖偶然出现的遍历顺序

HashMap 不承诺插入顺序、排序顺序，也不承诺随着扩容和修改顺序保持不变。某次测试中整数键恰好按大小输出，只是当时的数据和内部布局产生的结果。

需要按插入顺序遍历时使用 LinkedHashMap；需要按照键的自然顺序或比较器排序时使用 TreeMap。HashMap 的桶内红黑树用于处理冲突，不会让整个 Map 按键排序。

3. 正确理解复杂度

下面用 b 表示某个桶内的节点数，并假定键的 hashCode、equals 和比较操作本身成本为常数：

因此，“HashMap 的增删改查都是 O(1)”省略了关键前提。某一次插入可能触发扩容，糟糕的键设计也可能使大量查找落进同一个长桶。

读完源码，真正值得带回业务代码的是几件事：让键的相等性和哈希值保持稳定；已知条目数量时正确预估容量；不依赖遍历顺序；共享可变数据时明确同步方式。桶定位、树化和扩容，则为这些选择提供了具体理由。

参考源码与文档

• 本文使用的 HashMap 固定提交源码：重点阅读 hash、tableSizeFor、putVal、resize、treeifyBin、TreeNode.find、TreeNode.split 和 newHashMap。
• 相同提交的 ConcurrentHashMap 源码：重点阅读类内实现说明，以及 putVal、transfer。
• Java SE 25 HashMap API。
• Java SE 25 ConcurrentHashMap API。

阅读顺序建议：先看普通链表桶的 putVal → resize → getNode，再进入树桶。这样可以先把哈希定位和容量变化理解完整，再处理红黑树带来的额外分支。