深入理解 Java HashMap：从源码到底层原理

前言

HashMap 是 Java 集合框架中使用频率最高的类之一，也是面试的高频考点。本文基于 JDK 8+ 源码，梳理它的底层结构、put 流程、扩容机制和常见踩坑点。

一、底层数据结构

JDK 8 之后，HashMap 采用 数组 + 链表 + 红黑树 的结构：

• 数组：Node<K,V>[] table，默认容量 16
• 链表：哈希冲突时以链表形式存储（尾插法）
• 红黑树：链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转为红黑树，查询从 O(n) 优化为 O(log n)

为什么树化阈值是 8？基于泊松分布，理想情况下链表长度达到 8 的概率约为千万分之一，树化更多是一种兜底保护。

二、hash 值如何计算

HashMap 并不是直接用 key.hashCode()，而是做了一次扰动处理：

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

将高 16 位与低 16 位异或，让高位也参与运算，减少哈希冲突。而在计算数组下标时用的是：

(n - 1) & hash   // n 为数组容量

这也是为什么容量必须是 2 的幂——只有 n 为 2 的幂时，(n-1) & hash 才等价于 hash % n，但位运算效率更高。

三、put 流程

put(key, value) 的核心逻辑如下：

1. 计算 key 的 hash，定位数组下标
2. 槽位为空 → 直接插入
3. 槽位首节点 key 相同 → 覆盖旧值
4. 首节点是树节点 → 按红黑树方式插入
5. 否则遍历链表插入尾部；插入后链表长度 ≥ 8 则尝试树化
6. ++size > threshold 时触发扩容

四、扩容机制

• 默认负载因子 loadFactor = 0.75，即容量 16 时，元素超过 12 就扩容
• 每次扩容为原来的 2 倍
• JDK 8 的扩容很巧妙：由于容量是 2 的幂，扩容后元素的新下标要么不变，要么等于原下标 + 旧容量，只需判断 hash & oldCap 是否为 0，无需重新计算每个元素的 hash

if ((e.hash & oldCap) == 0) {
    // 保持在原位置 low 链表
} else {
    // 移动到 原下标 + oldCap 的 high 链表
}

这也是 JDK 7 中著名的多线程扩容死循环（CPU 100%）问题在 JDK 8 中被修复的原因之一——但注意，HashMap 依然不是线程安全的，并发场景请使用 ConcurrentHashMap。

五、常见踩坑点

1. 用可变对象作为 key

List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value");
key.add("b");            // 修改了 key
System.out.println(map.get(key)); // null，找不到！

key 被修改后 hash 值变了，导致无法定位。key 推荐使用 String、Integer 等不可变类。

2. 遍历时删除元素

for (String key : map.keySet()) {
    if (key.startsWith("a")) {
        map.remove(key); // 抛出 ConcurrentModificationException
    }
}

正确做法是使用迭代器的 remove：

Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getKey().startsWith("a")) {
        it.remove();
    }
}
// 或者直接：
map.keySet().removeIf(key -> key.startsWith("a"));

3. 已知数据量却没有指定初始容量

频繁扩容 + rehash 是性能杀手。预估存 1000 个元素时，按 1000 / 0.75 ≈ 1334，初始化为：

Map<String, Object> map = new HashMap<>(2048); // 会自动对齐到 2 的幂

六、HashMap vs Hashtable vs ConcurrentHashMap

总结

• HashMap 底层是数组 + 链表 + 红黑树，容量始终为 2 的幂
• 扰动函数减少冲突，位运算代替取模提升效率
• 扩容时元素只可能留在原位或移动到「原下标 + 旧容量」
• 单线程用 HashMap 并指定初始容量，多线程用 ConcurrentHashMap