Java 基础体系 · 第 57/100 篇。示例统一以 Java 25 LTS 为语言和 JVM 基线；框架示例使用与其兼容的现代稳定版本。

Java HashMap 深入：哈希、桶、树化、扩容、迭代和键约束

HashMap<K, V> 是基于哈希表的键值映射。它解决的问题不是“保存一组键值对”这么简单，而是：

1. 如何从键快速定位候选位置；
2. 多个键定位到同一位置时如何共存；
3. 元素增多后如何维持可接受的查找成本；
4. 迭代时哪些行为有保证，哪些只是当前实现的结果；
5. 键发生什么变化后，映射关系会失效。

理解这些问题，需要同时区分三层内容：

• Map/HashMap API 规范保证：例如键相等的判断、允许 null、不保证迭代顺序；
• 哈希表的一般算法：哈希、桶、冲突、负载因子和扩容；
• OpenJDK 25 中的常见实现细节：数组桶、链表、红黑树、树化阈值和拆分扩容。

后两类内容不能反过来当作 HashMap 的 API 契约。应用代码可以利用规范保证，不能依赖未承诺的内部布局或遍历顺序。

---

1. 从 Map 抽象开始：键和值分别承担什么角色

Map<K, V> 表示从键 K 到值 V 的映射。一个键至多对应一个值：

Map<String, Integer> ages = new HashMap<>();

ages.put("Alice", 20);
ages.put("Alice", 21);

System.out.println(ages.size());   // 1
System.out.println(ages.get("Alice")); // 21

第二次 put 没有增加一个新的键，而是替换了已有键对应的值。

判断两个键是否代表同一个映射项，使用的是键的 equals 语义，而不是对象身份 ==。但是，HashMap 为了快速查找，会先使用哈希值缩小候选范围，再使用 equals 做最终确认。

因此，一次典型的 get 逻辑可以抽象为：

key
  │
  ├─ 计算 hashCode
  │
  ├─ 对 hash 做扰动
  │
  ├─ 根据桶数量计算桶下标
  │
  ├─ 检查该桶中的候选节点
  │
  └─ 使用 equals 确认具体键

哈希值相同，并不表示键相等；哈希值不同，则按照 equals/hashCode 契约，键不应当相等。

---

2. equals 与 hashCode：查找正确性的形式化条件

对作为 HashMap 键的类型，最重要的约束是：

如果两个对象相等，则它们的哈希值必须相等。

形式化表示为：

$$a.equals(b) = true \Rightarrow a.hashCode() = b.hashCode()$$

但反方向不成立：

$$a.hashCode() = b.hashCode() \not\Rightarrow a.equals(b) = true$$

后一个情况就是哈希冲突，它是正常现象，哈希表必须能够处理。

2.1 为什么相等键必须拥有相同哈希值

假设两个逻辑相等的键：

Key a = new Key("id-1");
Key b = new Key("id-1");

如果 a.equals(b) 为 true，但两者哈希值不同，那么：

map.put(a, value);
map.get(b);

put 可能把 a 放入桶 3，get 却根据 b 的哈希值去桶 7。即使桶 3 中已经存在逻辑相等的键，查找也不会到达那里。

所以，hashCode 不是为了证明对象相等，而是为了保证相等对象进入同一个候选区域。

2.2 一个合法但冲突严重的键

下面的键满足 equals/hashCode 契约，但所有实例都返回相同哈希值：

final class PoorKey {
    private final int id;

    PoorKey(int id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof PoorKey other && id == other.id;
    }

    @Override
    public int hashCode() {
        return 1; // 合法，但会制造大量冲突
    }
}

它不会破坏逻辑正确性，因为 equals 仍然能区分不同的 id；但性能会恶化。哈希表的性能依赖于哈希值能够把键较均匀地分散到各个桶中。

2.3 反例：重写 equals，却没有重写 hashCode

final class BrokenKey {
    private final String value;

    BrokenKey(String value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof BrokenKey other
                && value.equals(other.value);
    }

    // 错误：没有根据 value 重写 hashCode
}

两个 BrokenKey("x") 很可能使用不同的默认对象哈希值。此时：

Map<BrokenKey, String> map = new HashMap<>();
map.put(new BrokenKey("x"), "value");

System.out.println(map.get(new BrokenKey("x")));

结果可能是 null，因为两个逻辑相等的键被分配到了不同的候选桶。

2.4 equals 还需要满足的性质

作为一般对象契约，equals 应当满足：

• 自反性：x.equals(x) 为 true；
• 对称性：x.equals(y) 与 y.equals(x) 结果一致；
• 传递性：x.equals(y) 且 y.equals(z) 时，x.equals(z)；
• 一致性：对象相关状态不变时，重复调用结果一致；
• 非空性：x.equals(null) 为 false。

如果这些条件被破坏，HashMap 的行为也会变得不可预测。尤其是对称性和可变状态问题，通常会造成“有时能查到、有时查不到”的故障。

---

3. 哈希、扰动与桶下标

3.1 hashCode 不是桶下标

键的 hashCode() 返回一个 int，范围是：

$$-2^{31} \leq hashCode \leq 2^{31}-1$$

哈希表不能直接把它当作数组下标，因为它可能为负数，也可能远大于数组长度。需要经过处理得到桶下标。

在 OpenJDK 的 HashMap 实现中，常见的扰动函数是：

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

这里：

• h 是键原始的 hashCode()；
• h >>> 16 是无符号右移 16 位；
• ^ 是按位异或；
• 结果把高位的一部分信息混入低位。

这个函数是 OpenJDK 实现细节，不是 HashMap API 要求所有实现都必须使用的公式。

3.2 为什么需要把高位混入低位

当前实现使用长度为 $n$ 的数组，并且桶下标通常通过：

$$index = (n - 1) \mathbin{\&} hash$$

计算。为了让这个公式成立，数组长度通常取 2 的幂，例如 16、32、64。

当 $n=16$ 时：

n - 1 = 15 = 0000...1111

按位与只会保留哈希值的低 4 位。若某个键类型的哈希值低位分布很差，即使高位分布良好，也可能集中到少数桶中。

扰动操作：

$$h' = h \oplus (h \mathbin{\ggg} 16)$$

不能创造新的信息，但可以把高位的差异折叠到低位，降低某些哈希函数低位分布不佳的影响。

3.3 一个完整的桶下标算例

假设桶数组长度为 16，某个键的原始哈希值为：

h = 0x12340005

右移 16 位：

h >>> 16 = 0x00001234

异或后：

h' = 0x12340005 ^ 0x00001234
   = 0x12341231

桶下标为：

index = (16 - 1) & 0x12341231
      = 0x0000000f & 0x12341231
      = 0x00000001

所以该键进入下标为 1 的桶。

如果两个键的扰动后哈希值都落在同一个下标，它们就发生了冲突。冲突不代表数据丢失，代表同一个桶中需要继续比较键。

---

4. 桶、节点与冲突处理

可以把哈希表想象成一个数组：

table
┌────┬────┬────┬────┬────┬────┐
│ 0  │ 1  │ 2  │ 3  │ 4  │ ...│
└────┴────┴────┴────┴────┴────┘
          │
          └── 桶 1 中保存多个候选节点

在 OpenJDK HashMap 中，数组元素称为桶的头节点。一个桶最初可以保存：

• 空值；
• 一个节点；
• 多个通过链表连接的节点；
• 达到条件后转换为红黑树结构的节点。

每个节点概念上至少包含：

hash
key
value
next

查找时，先比较节点保存的哈希值，再比较键：

节点哈希值相同
    │
    └─ 键是同一个对象，或 key.equals(node.key) 为 true
           │
           └─ 找到目标

先比较哈希值是为了避免对大量明显不相等的键调用 equals。但哈希值相同仍然只能说明“可能相等”，最终判断仍然需要 equals。

4.1 冲突链表

在未树化的桶中，冲突节点以链表形式连接：

桶 5
  │
  ▼
[keyA, valueA] -> [keyB, valueB] -> [keyC, valueC] -> null

查找复杂度取决于链表长度。理想情况下，链表很短；极端情况下，所有键都进入同一个桶，查找会退化为线性扫描。

对于容量为 $n$、元素数量为 $m$ 的表，平均负载可以粗略表示为：

$$\alpha = \frac{m}{n}$$

其中 $\alpha$ 是平均每个桶中的元素数量。负载因子越高，空间浪费越少，但平均冲突程度越高；负载因子越低，冲突通常较少，但需要更大的数组。

---

5. 树化：为什么链表会转换为红黑树

5.1 树化解决什么问题

如果一个桶中的节点持续增加，链表查找的最坏情况是：

$$O(k)$$

其中 $k$ 是该桶中的节点数。

OpenJDK 的 HashMap 会在满足条件时把该桶转换为红黑树，使查找在树结构下通常为：

$$O(\log k)$$

树化是对严重碰撞的一种防御和性能优化，但它不意味着所有 HashMap 操作都变成了 $O(\log n)$。不同桶仍然独立，整体性能仍取决于哈希分布。

5.2 OpenJDK 中的关键阈值

在 OpenJDK 25 的常见 HashMap 实现中，可以看到以下实现常量：

TREEIFY_THRESHOLD     = 8
UNTREEIFY_THRESHOLD   = 6
MIN_TREEIFY_CAPACITY  = 64

这些数值是实现细节，不应作为 HashMap API 的跨实现契约。

它们的含义是：

• 桶中节点数量达到树化阈值附近时，可能尝试树化；
• 但如果整个表容量小于 64，通常优先扩容，而不是树化；
• 树中的节点数量减少到较低阈值时，在某些操作中可能退回链表。

“达到 8 个节点就一定树化”是常见误解。实际逻辑还要看当前表容量，以及触发的是插入、扩容还是删除路径。

5.3 为什么容量不足时先扩容

假设表容量只有 16，而某个桶中出现了很多节点。这可能只是因为整体表太小，多个普通键暂时集中到了同一个桶。

扩容会增加桶数量，重新计算节点位置，使冲突分散：

容量 16：某桶有 8 个节点
        │
        └─ 先扩容到 32 或更大，重新分布节点

只有在容量已经达到一定规模后，仍然存在很长的单桶冲突，树化才更有意义。

这体现了两种成本之间的取舍：

• 扩容：增加数组空间，并重新分布节点；
• 树化：增加节点结构和维护成本。

5.4 树化不等于排序

树桶使用红黑树结构，是为了维护查找结构，不是为了让 HashMap 按键排序。

因此，以下结论都不成立：

树化后会按 key 排序
树化后迭代顺序稳定
树化后 HashMap 变成 TreeMap

TreeMap 的排序来自其有序映射契约；HashMap 没有这个契约。

树中的节点需要某种比较关系来组织。对于可比较键，当前实现可以利用自然顺序；对于无法直接比较的键，还会使用类名、身份哈希等实现级规则辅助确定树结构。这个内部排序不应被应用程序当作迭代顺序或业务排序依据。

---

6. 扩容：阈值、容量和重新分布

6.1 什么时候扩容

在常见实现中，表有两个关键参数：

• capacity：桶数组长度；
• loadFactor：负载因子；
• threshold：触发扩容的元素数量阈值。

通常有：

$$threshold = capacity \times loadFactor$$

默认负载因子是 0.75f。例如：

capacity   = 16
loadFactor = 0.75
threshold  = 12

当元素数量超过阈值时，表通常扩容到原容量的两倍。

这是实现机制的概括，具体构造参数还会受到容量上限、整数溢出和延迟初始化等因素影响。API 保证的是映射行为，不是这些内部字段的可见语义。

6.2 扩容前后的下标关系

假设旧容量为：

$$oldCap = 16$$

新容量为：

$$newCap = 32$$

旧桶下标使用低 4 位：

$$(oldCap - 1) \mathbin{\&} hash$$

新桶下标使用低 5 位：

$$(newCap - 1) \mathbin{\&} hash$$

相比旧容量，新下标只多看一位：oldCap 对应的那一位。因此，旧桶中的节点扩容后只有两种去向：

旧桶 i
 ├─ 低位链（lo）：新下标仍为 i
 └─ 高位链（hi）：新下标变为 i + oldCap

判断条件可以写成：

$$(hash \mathbin{\&} oldCap) = 0 \Rightarrow newIndex = oldIndex$$

$$(hash \mathbin{\&} oldCap) \ne 0 \Rightarrow newIndex = oldIndex + oldCap$$

6.3 扩容算例

旧容量为 16，某个节点扩容前位于桶 3。因为：

oldIndex = hash & 15 = 3

扩容到 32 后：

newIndex = hash & 31

若 hash & 16 == 0：

newIndex = 3

若 hash & 16 != 0：

newIndex = 3 + 16 = 19

所以扩容并不需要对每个节点重新执行完整的“取模任意整数”逻辑；当前实现可以利用容量翻倍的性质，将每个旧桶拆成两个部分。

6.4 扩容的成本

扩容需要遍历已有节点并重新放置，因此一次扩容的成本与当前元素数量近似成正比：

$$O(m)$$

其中 $m$ 是扩容时已有节点数量。

但如果容量按倍数增长，单次插入的均摊成本仍然通常接近常数。这就是动态数组式扩容常见的摊销分析：不是每次插入都支付搬迁成本，而是把搬迁成本分摊到后续多次操作中。

如果能够合理估计元素数量，可以通过初始容量减少扩容次数：

Map<String, Long> counts = new HashMap<>(100_000);

这里的参数是初始容量意图，不一定等于实际立刻分配的桶数组长度。现代 OpenJDK 中，HashMap 的桶数组通常在首次插入时才初始化；而且构造器参数还会经过负载因子和容量上限处理。应用代码应关注“减少不必要扩容”的意图，不应依赖具体初始化时机。

---

7. null 键、null 值和重复键

HashMap 允许：

• 一个 null 键；
• 任意数量的 null 值；
• 每个非 null 键至多一个映射。

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

map.put(null, 100);
map.put("a", null);
map.put("b", null);

System.out.println(map.get(null)); // 100
System.out.println(map.size());    // 3

在常见实现中，null 键使用哈希值 0，因此会进入由 0 计算出的桶。这是实现层面的处理方式；“允许一个 null 键”是 API 层面的行为保证。

7.1 get 返回 null 的歧义

下面两个状态都可能使 get 返回 null：

Map<String, String> map = new HashMap<>();

map.put("present-null", null);
// "absent" 根本不存在

因此不能只通过 get 判断键是否存在：

if (map.get("present-null") == null) {
    // 这里无法区分：键不存在，还是键存在但值为 null
}

应该使用：

if (map.containsKey("present-null")) {
    System.out.println("键存在，值可能为 null");
}

这两个操作的语义不同：

• get(key)：取得映射值，找不到或映射到 null 都可能返回 null；
• containsKey(key)：判断映射项是否存在。

7.2 不要用 containsValue 代替键查找

containsValue 需要检查值，而值没有哈希桶定位结构，通常需要遍历整个表。它的用途是值存在性判断，不是高效查找键。

---

8. 键约束：为什么键必须稳定、不可变或至少不参与变化

HashMap 依赖两个事实：

1. 插入时，键的哈希值决定它进入哪个桶；
2. 查找时，使用当前键的哈希值重新计算桶位置，并通过 equals 确认。

如果键放入映射后，参与 equals 或 hashCode 的状态发生变化，插入位置不会自动迁移，但后续查找会使用新的结果。

8.1 可变键导致“键还在，但查不到”

import java.util.HashMap;
import java.util.Map;

final class MutableKey {
    private String value;

    MutableKey(String value) {
        this.value = value;
    }

    void setValue(String value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof MutableKey other
                && value.equals(other.value);
    }

    @Override
    public int hashCode() {
        return value.hashCode();
    }

    @Override
    public String toString() {
        return value;
    }
}

public class MutableKeyDemo {
    public static void main(String[] args) {
        MutableKey key = new MutableKey("before");

        Map<MutableKey, String> map = new HashMap<>();
        map.put(key, "stored");

        System.out.println(map.get(key)); // stored

        key.setValue("after");

        System.out.println(map.get(key));       // 通常为 null
        System.out.println(map.containsKey(key)); // 通常为 false
        System.out.println(map.size());         // 1

        for (Map.Entry<MutableKey, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

程序的关键状态变化是：

插入时：
key.hashCode() == hash("before")
桶位置 == bucket(hash("before"))

修改后：
key.hashCode() == hash("after")
查找位置 == bucket(hash("after"))

节点仍然留在原来的桶中，但查找沿着新的桶位置进行，所以可能找不到它。size() 仍为 1，因为修改键并不会自动删除节点。

这不是 HashMap 的 bug，而是键违反了哈希映射所要求的稳定性前提。

8.2 更稳妥的键类型

常见安全选择包括：

• String；
• 包装类型，如 Integer、Long；
• UUID；
• 不可变的 record；
• 自定义不可变类。

例如：

record UserKey(long tenantId, long userId) {}

Map<UserKey, String> users = new HashMap<>();
users.put(new UserKey(10, 42), "Alice");

System.out.println(users.get(new UserKey(10, 42))); // Alice

record 自动生成基于组件的 equals 和 hashCode，并且组件引用本身不能被重新赋值。不过，如果 record 的组件引用指向可变对象，例如 List，则“record 外壳不可重新赋值”不等于所有内部状态都不可变。键的整体逻辑状态仍必须保持稳定。

8.3 键的字段不是全部都必须不可变

并非对象的任何字段变化都会破坏 HashMap。真正受约束的是：

参与 equals 或 hashCode 结果的状态，在对象作为键期间必须保持稳定。

例如，一个只修改日志计数、不参与相等性和哈希计算的字段，不会改变映射定位。但将这种约束隐藏在复杂对象中容易出错，实际设计中通常优先使用简单、不可变的键。

---

9. 迭代：没有顺序保证，也不是快照

HashMap 不保证键、值或条目的迭代顺序：

Map<Integer, String> map = new HashMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");

for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

输出可能看起来像某种稳定顺序，但这不代表该顺序受保证。顺序可能因以下因素改变：

• 初始容量；
• 元素数量；
• 扩容时机；
• 键的哈希值；
• JDK 实现变化；
• 删除和重新插入；
• 桶从链表转换为树。

如果业务需要排序，应明确使用：

Map<Integer, String> sorted = new TreeMap<>();

如果只需要稳定的插入顺序，应考虑：

Map<Integer, String> insertionOrdered = new LinkedHashMap<>();

这不是“把 HashMap 调整成有序”，而是选择具有相应契约的数据结构。

9.1 迭代复杂度

HashMap 的集合视图迭代成本通常与容量和元素数量之和相关：

$$O(capacity + size)$$

即使实际元素很少，过大的空桶数组也需要被扫描。因此，盲目设置极大的初始容量可能减少扩容，却可能增加迭代成本和内存占用。

这是初始容量选择中的真实取舍：

容量过小：扩容次数增加，搬迁成本增加
容量过大：空桶增多，内存和迭代扫描成本增加

9.2 迭代器的 fail-fast 行为

通过 keySet()、values() 或 entrySet() 得到的迭代器，在检测到迭代期间发生结构性修改时，通常会抛出 ConcurrentModificationException：

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);

for (String key : map.keySet()) {
    if (key.equals("a")) {
        map.remove(key); // 可能触发 ConcurrentModificationException
    }
}

正确的删除方式是使用迭代器自身的 remove：

Iterator<String> iterator = map.keySet().iterator();

while (iterator.hasNext()) {
    String key = iterator.next();
    if (key.equals("a")) {
        iterator.remove();
    }
}

也可以使用 removeIf：

map.keySet().removeIf(key -> key.equals("a"));

fail-fast 的含义是“尽早发现明显的错误”，不是并发安全机制。规范明确不保证在所有情况下都能检测到并发修改，尤其不能依赖 ConcurrentModificationException 来保证业务正确性。

9.3 什么是结构性修改

对 HashMap 而言，增加或删除映射项通常属于结构性修改，例如：

map.put("new-key", 1);
map.remove("old-key");
map.clear();

替换已有键的值通常不改变表结构：

map.put(existingKey, newValue);

因此，不能简单地把所有 put 都理解为结构性修改。当前实现通过内部修改计数辅助 fail-fast 检测，但这个检测细节也不应被当作并发同步手段。

9.4 集合视图是受支持的动态视图

以下方法返回的是与原映射关联的视图，而不是独立副本：

map.keySet();
map.values();
map.entrySet();

例如：

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);

map.keySet().remove("a");

System.out.println(map.containsKey("a")); // false

通过 keySet 删除键，会删除映射中的对应条目。values 和 entrySet 也以受支持的方式反映原映射变化。

如果需要快照，应显式复制：

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

快照之后，两个映射彼此独立；但值对象本身是否被复制，取决于值的类型和复制方式，普通构造器只复制键值引用。

---

10. 并发：HashMap 不是线程安全容器

HashMap 没有为多个线程同时读写提供线程安全保证。下面的场景存在风险：

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

// 线程 A
map.put("a", 1);

// 线程 B
map.get("a");

即使某些简单场景“看起来能工作”，也不能据此认为代码正确。缺少适当的同步时，问题包括：

• 一个线程看不到另一个线程的更新；
• 读操作与写操作之间出现竞态；
• 迭代期间发生结构变化；
• 复合操作不是原子的。

Collections.synchronizedMap 可以提供基于同步包装的访问，但迭代仍需要在外部持有同一个映射的监视器：

Map<String, Integer> map =
        Collections.synchronizedMap(new HashMap<>());

synchronized (map) {
    for (var entry : map.entrySet()) {
        System.out.println(entry);
    }
}

如果需要并发访问，通常应直接评估 ConcurrentHashMap。它具有不同的并发设计和语义，例如不允许 null 键和值；不能因为两者都实现了 Map 就把它们的边界混为一谈。

HashMap 的单线程可变使用与并发使用是两个不同问题：

单线程：
操作顺序由当前线程控制，普通 HashMap 可以使用

多线程读写：
需要同步、并发容器或不可变发布策略

将一个已经完成构建、之后只读的 HashMap 安全发布给其他线程，仍然需要满足 Java 内存模型中的安全发布条件；“之后不再修改”本身不能替代安全发布。

---

11. 常用操作的语义和边界

11.1 put、putIfAbsent 与 computeIfAbsent

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

map.put("count", 1);
map.put("count", 2); // 替换为 2

map.putIfAbsent("count", 3); // 已有非 null 值时不替换

对于允许 null 值的 HashMap，putIfAbsent 的行为需要结合“键是否存在”和“当前值是否为 null”理解。若业务需要区分“缺少键”和“键存在但值为 null”，应显式使用 containsKey，不要只看 get。

computeIfAbsent 适合构建分组或索引：

Map<String, List<Integer>> groups = new HashMap<>();

groups.computeIfAbsent("even", ignored -> new ArrayList<>())
      .add(2);

groups.computeIfAbsent("even", ignored -> new ArrayList<>())
      .add(4);

System.out.println(groups); // {even=[2, 4]}，显示顺序不作保证

映射函数返回 null 时，通常不会建立映射；映射函数也不应在计算过程中对同一个映射进行不受支持的递归修改，否则可能抛出异常或产生不可预期行为。

11.2 getOrDefault 仍然存在 null 语义

Map<String, String> map = new HashMap<>();
map.put("x", null);

System.out.println(map.getOrDefault("x", "default")); // null
System.out.println(map.getOrDefault("y", "default")); // default

getOrDefault 只在没有映射时使用默认值；如果键存在且映射值就是 null，结果仍然是 null。

11.3 replaceAll 和 forEach 的修改边界

这些方法适合更新值或执行只读处理：

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 10);
scores.put("Bob", 20);

scores.replaceAll((name, score) -> score + 5);
scores.forEach((name, score) ->
        System.out.println(name + ": " + score));

在 forEach 回调中结构性修改同一个 HashMap，可能触发并发修改异常或造成不应依赖的结果。需要增删元素时，应选择专门的删除 API、迭代器，或先收集待修改项。

---

12. HashMap 的复杂度：平均、最坏和现实条件

在哈希分布良好、扩容策略正常的前提下，get、put、remove 的平均时间复杂度通常接近：

$$O(1)$$

这里的“平均”包含两个重要前提：

1. 哈希值能较均匀地分布；
2. 键的 equals 和 hashCode 本身不是昂贵操作。

如果大量键集中到同一桶：

• 链表结构下，查找可能接近 $O(k)$；
• 树化后，当前实现通常可改善为接近 $O(\log k)$；
• 如果键的比较逻辑、哈希函数或对象状态存在问题，实际成本和正确性都可能进一步恶化。

此外，复杂度分析不包括键方法本身的成本。例如，一个键的 hashCode() 每次都遍历一个很长的数组，那么哈希表的定位虽然是常数次调用，单次调用仍可能是线性成本。

扩容操作本身是 $O(m)$，但按容量倍增通常具有摊销效率。生产问题中，“HashMap 很慢”不能只看 HashMap 类名，还需要检查：

• 键的哈希分布；
• equals/hashCode 是否重复计算大量数据；
• 是否频繁扩容；
• 是否设置了过大的容量；
• 是否在单线程容器上进行了并发访问；
• 是否错误地依赖了遍历顺序。

---

13. 规范保证与 OpenJDK 实现细节的边界

下面几组结论需要明确区分。

API 层面的可靠保证

可以依赖：

• 一个键最多对应一个值；
• equals 相等的键代表同一映射关系；
• HashMap 允许 null 键和 null 值；
• 不保证迭代顺序；
• 非同步；
• 集合视图与原映射关联；
• 迭代器的 fail-fast 行为用于发现错误，但不是并发正确性保证。

OpenJDK 常见实现

可以用于理解当前 Java 25 运行时的内部行为，但不应作为通用 API 契约：

• 使用节点数组作为桶表；
• 哈希扰动常见为 h ^ (h >>> 16)；
• 容量通常是 2 的幂；
• 下标常见为 (n - 1) & hash；
• 冲突桶先使用链表，满足条件后树化；
• 树化阈值常见为 8，最小树化容量常见为 64；
• 容量通常按约两倍增长；
• 扩容时根据旧容量对应位拆分桶。

如果代码需要某种顺序、并发语义、排序语义或持久化布局，应使用具有相应契约的类型，而不是观察一次 OpenJDK 的内部结果。

---

14. 一个可运行的综合示例

下面的程序同时演示：

• 相等键替换值；
• null 键；
• 哈希冲突不等于键相等；
• 可变键导致查找失效；
• entrySet 视图删除；
• 不应依赖迭代顺序。

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class HashMapDemo {
    static final class CollisionKey {
        private final int id;

        CollisionKey(int id) {
            this.id = id;
        }

        @Override
        public int hashCode() {
            return 7; // 所有实例冲突
        }

        @Override
        public boolean equals(Object obj) {
            return obj instanceof CollisionKey other
                    && id == other.id;
        }

        @Override
        public String toString() {
            return "CollisionKey(" + id + ")";
        }
    }

    static final class MutableKey {
        private String value;

        MutableKey(String value) {
            this.value = value;
        }

        void changeTo(String value) {
            this.value = value;
        }

        @Override
        public int hashCode() {
            return value.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return obj instanceof MutableKey other
                    && value.equals(other.value);
        }

        @Override
        public String toString() {
            return "MutableKey(" + value + ")";
        }
    }

    public static void main(String[] args) {
        Map<Object, String> map = new HashMap<>();

        // 1. 相等键会替换原值
        map.put("language", "Java");
        map.put(new String("language"), "Java 25");
        System.out.println(map.get("language")); // Java 25
        System.out.println(map.size());          // 1

        // 2. null 键和值
        map.put(null, "null-key");
        map.put("nullable-value", null);
        System.out.println(map.get(null)); // null-key
        System.out.println(map.containsKey("nullable-value")); // true

        // 3. 哈希冲突仍可通过 equals 区分
        CollisionKey key1 = new CollisionKey(1);
        CollisionKey key2 = new CollisionKey(2);

        map.put(key1, "one");
        map.put(key2, "two");

        System.out.println(map.get(new CollisionKey(1))); // one
        System.out.println(map.get(new CollisionKey(2))); // two

        // 4. 修改键的哈希相关状态后，节点仍在但可能无法定位
        MutableKey mutableKey = new MutableKey("before");
        map.put(mutableKey, "mutable");

        mutableKey.changeTo("after");

        System.out.println(map.get(mutableKey)); // 通常为 null
        System.out.println(map.size());          // 仍包含该节点

        // 5. 使用迭代器安全删除
        Iterator<Map.Entry<Object, String>> iterator =
                map.entrySet().iterator();

        while (iterator.hasNext()) {
            Map.Entry<Object, String> entry = iterator.next();
            if (entry.getValue() == null) {
                iterator.remove();
            }
        }

        System.out.println(map.containsKey("nullable-value")); // false

        // 6. 只观察映射，不对迭代顺序作断言
        map.forEach((key, value) ->
                System.out.println(key + " -> " + value));
    }
}

运行前提是 JDK 25 或兼容的较新 JDK。程序中标记为“通常”的输出，说明它描述的是由可变键破坏前提后的常见结果，而不是应当依赖的业务契约；最后的遍历输出顺序也不应写入测试断言。

---

15. 诊断典型故障

“明明放进去，却取不出来”

优先检查：

1. equals 相等的对象是否具有相同 hashCode；
2. put 和 get 使用的键类型是否真的一致；
3. 键放入后是否被修改；
4. 是否错误地用 get(key) == null 判断键不存在；
5. 是否在多个线程间无同步地读写。

可以打印以下诊断信息：

System.out.println(key);
System.out.println(key.hashCode());
System.out.println(map.containsKey(key));
System.out.println(map.get(key));

如果键是可变对象，还应在插入前后分别记录参与 equals 和 hashCode 的字段，而不是只打印对象地址。

“HashMap 为什么没有按插入顺序遍历”

因为 HashMap 没有顺序契约。当前观察到的顺序通常来自桶数组下标和节点结构，而不是插入顺序。扩容可能改变元素所在桶，树化也可能改变内部组织，所以依赖输出顺序的测试本身就是错误测试。

“大量键后性能突然变差”

应区分三条路径：

元素增加
  ├─ 超过阈值：扩容，短期出现搬迁成本
  ├─ 哈希分布差：单桶冲突增加
  └─ 键方法昂贵：hashCode/equals 本身耗时

如果键全部返回相同哈希值，树化可能缓解查找退化，但不能替代正确的哈希设计。若键的 equals 还不满足契约，树结构也无法修复逻辑错误。

---

16. 选择 HashMap 时真正需要确认的条件

HashMap 适合以下需求：

• 通过键快速查找值；
• 不要求排序；
• 不要求插入顺序；
• 访问模型已经由外部同步或单线程保证；
• 键的相等性和哈希值稳定；
• null 键和值的语义不会造成业务歧义。

如果需求是：

• 按键排序：使用 TreeMap；
• 保留插入顺序：使用 LinkedHashMap；
• 多线程并发映射：评估 ConcurrentHashMap；
• 不允许 null：选择有对应约束的实现，或在边界处主动校验；
• 不希望键被修改：使用不可变键和必要的防御性复制。

HashMap 的核心不是“数组加链表”这一句结构描述，而是一条必须同时成立的因果链：

稳定的键状态
  → 一致的 equals/hashCode 契约
  → 合理的哈希分布
  → 桶内冲突可控
  → 扩容维持负载
  → 树化处理极端冲突
  → 无序迭代与明确的并发边界

其中任意一环被误解，都会表现为不同类型的问题：键查找失败、顺序断言失败、性能退化、迭代异常或并发数据错误。

---

系列导航与关联阅读

• 系列入口：Java 完整学习路线：从 Java 25 语言与 JVM 到 Spring、微服务和生产交付
• 上一篇：Java List 深入：ArrayList、LinkedList、迭代器、复杂度和选型
• 下一篇：Java 有序集合：TreeMap、TreeSet、Comparator 和一致性

官方资料

• Java SE 25 Documentation
• Java Language Specification

本文依据 Java、Spring 与相关项目官方文档重新梳理；正文、示例与生产清单由 WR BLOG 编写。