从 0 学习 Java HashMap 源码解析——6 大核心精讲

为什么 HashMap 是面试必问？为什么扩容因子是 0.75？链表什么时候变成红黑树？

---

一、什么是 HashMap

1.1 一句话定义

HashMap = 数组 + 链表 + 红黑树的复合结构，根据 key 的 hash 值定位存储位置，平均 O(1) 时间复杂度完成增删改查。

1.2 为什么 HashMap 这么重要？

• ✅ Java 后端使用频率最高的集合之一
• ✅ 面试 100% 必问（数据结构 + 源码）
• ✅ 搞懂 HashMap = 搞懂 Java 集合框架
• ✅ 底层数据结构 + 算法 浓缩在 2000 行代码里

1.3 JDK 版本演进

JDK 版本	关键变化
JDK 7	数组 + 链表，头插法（并发死循环）
JDK 8	数组 + 链表 + 红黑树，尾插法

⚠️ 本文基于 JDK 8（主流版本，也是面试主要考点）

1.4 6 大核心地图

---

二、底层结构

2.1 一句话定义

HashMap 底层是一个 Node<K,V>[] 数组，每个数组元素是一个链表头（或红黑树根）。

2.2 3 大数据结构

2.3 核心字段（jdk 8）

public class HashMap<K,V> extends AbstractMap<K,V> {

    // 默认初始容量（必须是 2 的幂）
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;  // = 16

    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;  // = 2^30

    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 链表转红黑树阈值
    static final int TREEIFY_THRESHOLD = 8;

    // 红黑树退化为链表阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    // 桶数组
    transient Node<K,V>[] table;

    // 实际元素个数
    transient int size;

    // 扩容阈值 = capacity * loadFactor
    int threshold;
}

2.4 Node 节点

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;       // hash 值
    final K key;          // key
    V value;              // value
    Node<K,V> next;       // 下一个节点（链表）

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

2.5 关键点

• ✅ 数组 + 链表 + 红黑树 复合结构
• ✅ Node 是 HashMap 的最小存储单元
• ✅ table 数组长度永远是 2 的幂（扩容时左移一位）
• ✅ size 不等于 table.length，前者是元素个数，后者是桶数

---

三、hash 函数

3.1 一句话定义

HashMap 的 hash 函数 = key.hashCode() 异或上 hashCode() 高 16 位，让高位也参与下标计算，减少哈希冲突。

3.2 源码（JDK 8）

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

3.3 为什么异或高 16 位？

原因：

• 数组长度通常比较小（默认 16，最大也就 2^30）
• 取模运算 (length - 1) & hash 实际只用到了 hash 的低 N 位
• 如果 hash 的高位变化大、低位变化小，容易冲突
• 把高位异或到低位：让高位也参与定位，分布更均匀

3.4 下标计算

// 数组长度是 2 的幂时，n % length 等价于 n & (length - 1)
int index = (length - 1) & hash;

为什么要用 & 代替 %？

运算	性能
n % length	慢（除法）
n & (length - 1)	快（位运算，差一个数量级）

3.5 关键点

• ✅ hash = key.hashCode() ^ (h >>> 16)（JDK 8 改进）
• ✅ 数组长度是 2 的幂时，可以用 & 代替 %
• ✅ 目的是减少哈希冲突，让 key 均匀分布
• ❌ 不要自己重写 hashCode 后不重写 equals（HashMap 依赖两者）
• ❌ key 最好是 String / Integer 等不可变对象（hashCode 要稳定）

---

四、put 流程

4.1 一句话定义

put 流程：算 hash → 算下标 → 找桶 → 桶为空直接放 → 桶不为空遍历链表/红黑树找相同 key → 找到就覆盖 / 找不到就追加 → 检查 size 是否需要扩容。

4.2 完整流程图

4.3 源码（JDK 8 简化版）

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

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 为空 → 初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // ② 桶为空 → 直接放
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

    // ③ 桶不为空 → 遍历
    else {
        Node<K,V> e;
        K k;
        // ③.1 key 已存在（hash 相等 + equals 相等）→ 覆盖
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;

        // ③.2 红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

        // ③.3 链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 链表长度 ≥ 8 → 转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // ④ key 已存在 → 覆盖 value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    // ⑤ size 超阈值 → 扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4.4 关键点

• ✅ 4 大分支：桶为空 / key 已存在 / 红黑树 / 链表
• ✅ 链表长度 ≥ 8 且数组 ≥ 64 才转红黑树（不是 ≥ 8 就转）
• ✅ key 已存在就覆盖 value，返回旧 value
• ✅ size 超阈值才扩容（不是每次都扩）
• ❌ key 必须正确实现 hashCode 和 equals，否则 HashMap 行为异常

---

五、扩容机制

5.1 一句话定义

扩容 = 创建 2 倍大小的新数组，把旧数组的所有节点重新 hash 到新数组。

5.2 扩容触发条件

5.3 扩容流程

5.4 为什么 2 倍扩容？

• 位运算高效：newCap = oldCap << 1
• 节点重 hash 简单：(e.hash & oldCap) == 0 决定节点去低位还是高位
• 链表拆分不需要重新算 hash：因为是 2 的幂，节点在新数组的下标要么是旧下标，要么是旧下标 + 旧容量

// 神奇的拆分：不需要重新算 hash
if ((e.hash & oldCap) == 0) {
    // 节点去低位（j 下标）
    loTail.next = e;
} else {
    // 节点去高位（j + oldCap 下标）
    hiTail.next = e;
}

5.5 为什么加载因子是 0.75？

加载因子	优点	缺点
0.5	冲突少	空间浪费 50%
0.75	时间和空间平衡	默认值
1.0	空间利用率高	冲突多，链表长

0.75 是统计学权衡：

• 太小 → 频繁扩容 → 浪费空间
• 太大 → 哈希冲突多 → 链表长 → 查询慢
• 0.75 ≈ 泊松分布的临界点

5.6 关键点

• ✅ 扩容是 2 倍（位运算 + 重 hash 简单）
• ✅ 扩容时机：size > threshold = capacity × loadFactor
• ✅ 0.75 是时间和空间的平衡点
• ✅ 节点重 hash 不需要重新计算：用 (e.hash & oldCap) 判断去低位还是高位
• ❌ 扩容是性能瓶颈（要遍历所有节点）→ 预设初始容量 可以减少扩容

// ✅ 最佳实践：预设初始容量
// 如果预期存 1000 个元素，设置 capacity = 1000 / 0.75 ≈ 1334，再向上取 2 的幂 = 2048
Map<String, Integer> map = new HashMap<>(2048);

---

六、树化与退化

6.1 一句话定义

当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树；当红黑树节点数 ≤ 6 时，退化为链表。

6.2 树化条件

6.3 为什么是 8？

泊松分布计算：

在 hash 均匀分布下，单个桶内链表长度达到 8 的概率是 千万分之六（0.0000006）。所以一旦真的出现，说明 hash 函数有问题。

6.4 为什么退化阈值是 6？

阈值	原因
8（树化）	链表足够长，O(n) → O(log n) 收益大
6（退化）	略小于 8，避免频繁转换（“抖动”）

// 阈值差 2，避免在边界值附近反复转换
static final int TREEIFY_THRESHOLD = 8;   // 树化
static final int UNTREEIFY_THRESHOLD = 6;  // 退化

6.5 为什么数组 ≥ 64 才树化？

• 数组太小时，优先扩容数组分散节点
• 数组长度 ≥ 64 时，扩容代价已经比较大，树化收益更高

6.6 关键点

• ✅ 链表 ≥ 8 且数组 ≥ 64 才树化
• ✅ 红黑树节点 ≤ 6 退化为链表
• ✅ 8 / 6 差 2 是为了避免抖动
• ✅ 8 是泊松分布的数学保证
• ❌ 不要手写阈值覆盖（会破坏 HashMap 的内部设计）

---

七、红黑树（HashMap 为何引入）

7.1 一句话定义

红黑树 = 自平衡二叉查找树，HashMap 在链表过长时引入，保证最坏情况 O(log n)。

7.2 链表 vs 红黑树

7.3 红黑树的 5 大性质

#	性质
1	每个节点要么红、要么黑
2	根节点是黑色
3	叶子节点（NIL）是黑色
4	红色节点的子节点必须是黑色（不能有连续红节点）
5	从任一节点到其叶子的所有路径，包含相同数目的黑色节点（黑高一致）

7.4 为什么选红黑树而不是 AVL？

树	平衡度	插入/删除	查询
AVL	严格平衡	慢（旋转多）	快
红黑树	大致平衡	快（旋转少）	略慢但仍是 O(log n)

HashMap 选红黑树：插入删除场景多，红黑树更合适。

7.5 TreeNode 节点

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;            // 颜色
}

7.6 关键点

• ✅ 红黑树 = 自平衡二叉查找树
• ✅ HashMap 链表 → 红黑树是为了应对最坏情况
• ✅ 红黑树查询 O(log n)，比链表 O(n) 强
• ✅ 选红黑树不选 AVL：插入删除场景多
• ❌ 不要把 TreeMap 和 HashMap 的红黑树搞混（TreeMap 整棵树都是红黑树）

---

八、并发问题

8.1 一句话定义

HashMap 不是线程安全的：JDK 7 并发扩容会导致死循环 + 数据丢失，JDK 8 不会死循环但仍可能数据丢失。

8.2 JDK 7 的死循环（头插法）

原因：JDK 7 用头插法重排链表，并发扩容时两个线程同时操作同一桶，链表会形成环 → 后续 get 死循环。

8.3 JDK 8 的改进（尾插法）

JDK 8 改成尾插法后，不会形成环，但仍可能：

• ✅ 数据丢失（并发 put 被覆盖）
• ✅ size 不准（modCount 并发修改）
• ✅ get 到 null（并发扩容期间）

8.4 4 种解决方案

方案	适用场景	性能
Collections.synchronizedMap	简单包装	慢（全局锁）
ConcurrentHashMap ⭐	生产首选	快（分段锁 / CAS）
Hashtable	老项目	慢
Map.computeIfAbsent 等原子方法	简单场景	局部安全

8.5 ConcurrentHashMap 演进

8.6 关键点

• ✅ HashMap 不是线程安全的（JDK 7 死循环 / JDK 8 数据丢失）
• ✅ JDK 8 改用尾插法，避免链表成环
• ✅ 生产环境用 ConcurrentHashMap，不用 HashMap
• ✅ ConcurrentHashMap 用 CAS + 桶锁，性能远好于 synchronizedMap
• ❌ 不要在多线程环境下用 HashMap（即使单 put 也是不安全的）

---

九、6 大核心的关系图

---

十、5 个常见踩坑

#	踩坑	现象	解法
1	多线程用 HashMap	JDK 7 死循环 / JDK 8 数据丢失	用 ConcurrentHashMap
2	不预设初始容量	频繁扩容，性能差	new HashMap<>(预期 / 0.75f + 1)
3	key 是可变对象	put 后改 key 字段，get 不到	key 用 String/Integer 等不可变
4	重写 equals 不重写 hashCode	HashMap 行为异常	equals/hashCode 一起重写
5	遍历时修改 map	ConcurrentModificationException	用 Iterator.remove() 或 ConcurrentHashMap

1 行代码预设容量

// 预期存 1000 元素
int initialCapacity = (int) (1000 / 0.75f) + 1;
// 然后向上取最近的 2 的幂（HashMap 内部会做，但显式更清晰）
Map<String, Integer> map = new HashMap<>(2048);

---

十一、6 步学习路径

1. 第 1 步：理解结构（数组 + 链表 + 红黑树）
2. 第 2 步：掌握 hash 函数（高 16 位异或）
3. 第 3 步：跑通 put 流程（4 大分支）
4. 第 4 步：搞懂扩容机制（2 倍 + 0.75）
5. 第 5 步：理解树化（8 / 6 阈值）
6. 第 6 步：重视并发（用 ConcurrentHashMap）

---

十二、推荐阅读

如果你想深入学 HashMap 源码，这几本 / 这些资料值得读：

• 📚 《Java 核心技术 卷 I》（Cay S. Horstmann）—— 集合框架基础
• 📚 《Java 编程的逻辑》（马俊昌）—— 讲透 Java 集合设计
• 📖 JDK 8 源码 java.util.HashMap—— 直接读官方实现
• 📖 美团技术团队《Java 8 系列之重新认识 HashMap》—— 中文最佳解析
• 🔗 Visualgo（visualgo.net）—— 数据结构可视化
• 🔗 极客时间《数据结构与算法之美》（王争）—— 算法基础

---

十三、附录：一句话总结各核心

核心	一句话
底层结构	数组 + 链表 + 红黑树的复合结构
hash 函数	hashCode 异或高 16 位，让高位参与定位
put 流程	算 hash → 找桶 → 链表/红黑树 → 覆盖或追加
扩容机制	2 倍大小 + 阈值 = capacity × 0.75
树化与退化	链表 ≥ 8 转红黑树，节点 ≤ 6 退化链表
红黑树	自平衡二叉查找树，最坏情况 O(log n)
并发问题	HashMap 不是线程安全，生产用 ConcurrentHashMap

---

十四、面试常问的 6 个问题

Q1：HashMap 为什么用 2 的幂作为数组长度？

取模运算 hash % length 中，当 length = 2^n 时，可以用 hash & (length - 1) 代替除法，性能更好。

Q2：HashMap 为什么线程不安全？

JDK 7 头插法 + 并发扩容会导致链表成环（死循环）；JDK 8 改成尾插法后不会死循环，但仍有数据丢失、size 不准、get 到 null 等问题。

Q3：HashMap 的扩容因子为什么是 0.75？

0.75 是时间和空间的平衡点：太小浪费空间，太大哈希冲突多。0.75 ≈ 泊松分布的临界点。

Q4：为什么链表长度 ≥ 8 才转红黑树？

泊松分布计算下，单个桶链表长度达到 8 的概率是千万分之六。一旦出现说明 hash 函数有问题，需要用红黑树保证最坏 O(log n)。

Q5：HashMap 和 Hashtable 有什么区别？

• HashMap：线程不安全，允许 null key/value
• Hashtable：线程安全（synchronized），不允许 null

Q6：ConcurrentHashMap 怎么保证线程安全？

JDK 7 用分段锁 Segment，JDK 8 改成 CAS + synchronized 锁单个桶，性能远好于 Hashtable。