HashMap 是 Java 面试里出现频率最高的集合类，没有之一。

很多人能背出"数组加链表加红黑树"，但是再往下追一句"链表什么时候转红黑树？为什么是 8？红黑树的五个性质是什么？"，就开始含糊了。

这篇把 HashMap 涉及的数据结构从头到尾串一遍——二叉树、二叉搜索树、红黑树、散列表——然后讲 HashMap 是怎么把它们拼在一起的，以及 put 方法的完整流程。

二叉树：一切树结构的起点

二叉树就是每个节点最多有两个子节点的树结构。左子节点和右子节点。有些节点只有左，有些只有右，不是每个节点都必须有两个孩子。

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二叉树在内存中有两种存储方式：链式存储（上面的代码，左右指针）和数组存储（下标计算父子关系）。

二叉搜索树（BST）：加了排序规则

二叉搜索树在二叉树的基础上加一条规则：对任意节点，左子树的所有节点值都小于它，右子树的所有节点值都大于它。

在这个树上查 12：从根节点 10 开始，12 > 10，往右走；12 < 16，往左走；找到 12。每次比较都砍掉一半候选节点，所以理想情况下，查找、插入、删除都是 O(log n)。

但是 BST 有一个致命的缺陷：如果按顺序插入 1, 2, 3, 4, 5, 6，树会退化成一条线：

此时查找变成了 O(n)，跟链表一样。这就是为什么需要自平衡——不能让树长歪了。

红黑树：自平衡的二叉搜索树

红黑树就是为了解决 BST 退化问题而出现的自平衡二叉搜索树。它通过给每个节点标记颜色（红或黑），加上一套旋转和变色规则，保证树始终大致平衡。

五个性质，每条都不可或缺：

性质	内容
性质 1	节点要么是红色，要么是黑色
性质 2	根节点是黑色
性质 3	叶子节点（NIL）都是黑色的空节点
性质 4	红色节点的子节点都是黑色
性质 5	从任一节点到其叶子节点的所有路径都包含相同数目的黑色节点

性质 4 保证了不会出现连续的红色节点，性质 5 保证了从根到叶子的最长路径不会超过最短路径的两倍。

当添加或删除节点违反这些性质时，红黑树会通过旋转（左旋、右旋）和变色来恢复平衡。旋转和变色的成本是 O(1)，所以红黑树的增删改查整体都是 O(log n)。

HashMap 选择红黑树而不是 AVL 树（另一种自平衡树），原因是红黑树在插入和删除时需要的旋转次数更少。HashMap 是一个频繁读写的数据结构，写操作的成本比读操作更敏感，所以红黑树更适合。

散列表（哈希表）：数组的进化版

第一篇讲过，数组按下标随机访问是 O(1)。散列表就是利用这个特性——通过一个散列函数把任意 key 映射成数组下标，然后直接存取。

散列函数有三个基本要求：

1. 散列值必须是 ≥ 0 的正整数（作为数组下标）
2. 如果 key1 == key2，那么 hash(key1) == hash(key2)
3. 如果 key1 != key2，理想情况下 hash(key1) != hash(key2)

第三点是理想情况，现实中几乎做不到——不同的 key 算出相同的下标，这就叫哈希冲突。

哈希冲突：拉链法

处理哈希冲突最常用的方式就是拉链法：数组的每个位置（桶/bucket）不再只存一个元素，而是挂一条链表。散列值相同的元素都放进对应桶的链表中。

正常情况下（散列函数均匀、负载合理），每个桶的链表长度很短，查找还是接近 O(1)。但如果所有 key 都散列到了同一个桶里，就退化成了链表，查找 O(n)。

为什么引入红黑树

当某个桶的链表太长时，HashMap 会把它转成红黑树，让查找从 O(n) 回到 O(log n)。还有一个额外原因：防止 DDoS 攻击。

攻击者可以精心构造一批 key，让它们全部散列到同一个桶，导致 HashMap 退化成链表，服务器 CPU 飙升。引入红黑树之后，即使被恶意构造 key，查找复杂度也能维持在 O(log n)，不至于被拖垮。

两个条件缺一不可：链表长度 > 8 且 数组长度 ≥ 64。

为什么阈值是 8？

不是拍脑袋定的。HashMap 源码注释里有一段基于 Poisson 分布的概率计算。假设哈希函数足够理想，元素落入每个桶的概率服从 λ=0.5 的 Poisson 分布：

链表长度 = 0: 概率 0.60653066
链表长度 = 1: 概率 0.30326533
链表长度 = 2: 概率 0.07581633
链表长度 = 3: 概率 0.01263606
链表长度 = 4: 概率 0.00157952
链表长度 = 5: 概率 0.00015795
链表长度 = 6: 概率 0.00001316
链表长度 = 7: 概率 0.00000094
链表长度 = 8: 概率 0.00000006

链表长度达到 8 的概率只有 0.00000006（亿分之六）。换句话说，正常情况下几乎不可能出现长度 ≥ 8 的链表。如果真的出现了，大概率是两件事之一：要么哈希函数有问题，导致大量 key 集中冲突；要么有人在恶意构造哈希碰撞来攻击你的系统。

无论哪种情况，把 O(n) 的链表升级成 O(log n) 的红黑树都是合理防御。

为什么还要数组长度 ≥ 64？

假设数组长度只有 16，某个桶的链表到了 8 个元素，你把它树化了。但扩容一次（16→32）之后，链表被拆分到两个桶，每个桶可能就只剩 4 个元素——完全不需要树化。所以这种情况下，扩容比树化更划算。

只有数组长度已经 ≥ 64 时，扩容带来的拆分效果有限（每个桶分到的元素还是多），树化才有决定性意义。这个设计体现了 HashMap 的一个核心思路：优先用扩容分散元素，实在散不开才升级数据结构。

HashMap 的实现原理

好了，前面讲了那么多，现在可以拼起来了。HashMap 的数据结构就是：

数组 + 链表 + 红黑树

HashMap 的核心字段：

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

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

// 存数据的数组，长度总是 2 的幂
transient Node<K,V>[] table;

// 实际键值对数量
transient int size;

// 扩容阈值 = 数组容量 × 加载因子
int threshold;

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

加载因子 0.75 是一个时空权衡：如果设成 1.0，空间利用率高但冲突多、查询慢；如果设成 0.5，冲突少但空间浪费一半。0.75 是在大量实验后权衡出来的默认值。

至于默认初始容量选 16，同样是一个经验上的折中。太小（比如 4 或 8），存几十个元素就要反复扩容，扩容时数组拷贝是 O(n) 的，对小容量来说不划算；太大（比如 64 或 128），很多场景用不了几个元素，白白浪费内存。而且 16 是 2 的次幂，满足位运算的要求。实际使用时，如果你明确知道大概要存多少数据，应该在构造时就指定初始容量，比如 new HashMap(64)，这样可以减少扩容次数。

HashMap 是懒加载的——new HashMap() 的时候并没有初始化数组，只是把 loadFactor 设为 0.75。真正创建数组是在第一次 put 时。

put 方法完整流程

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

整个流程用 mermaid 图画出来非常清晰：

逐步骤拆解：

第一步：判断 table 是否为空。HashMap 是懒加载的，如果 table 为 null，先调用 resize() 初始化。默认容量 16，threshold = 16 × 0.75 = 12。

第二步：根据 key 的 hash 值计算数组索引 i = (n - 1) & hash。

第三步：如果 table[i] 为空，直接 new 一个 Node 放进去。

第四步：如果 table[i] 不为空，有三种情况：

• 第一个元素 key 相同 → 直接覆盖 value
• 如果该位置是 TreeNode → 走红黑树插入逻辑
• 否则是链表 → 遍历链表，找到相同 key 就覆盖，没找到就尾插

第五步：插入完成后，如果 ++size > threshold（12），触发扩容。

第六步：扩容时数组长度翻倍，原来 16 → 32，threshold 翻倍 12 → 24。老数据需要迁移到新数组。

JDK 1.7 vs JDK 1.8 的区别

对比项	JDK 1.7	JDK 1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树
链表插入方式	头插法	尾插法
扩容后元素位置	全部重新计算 hash	通过 e.hash & oldCap 判定
多线程扩容	可能形成环形链表，死循环	不会死循环，但仍不安全
hash 计算	更复杂的扰动	简化：高 16 位异或低 16 位

头插法和死循环的问题下一篇会细讲，这里先记住结论：JDK 1.8 把链表改成尾插法，解决了扩容时的死循环问题。

面试模板

问：“说一下 HashMap 的实现原理”

答：

HashMap 底层使用散列表，数据结构是数组加链表加红黑树。

JDK 1.8 之前只有数组加链表，1.8 开始当链表长度大于 8 且数组长度大于等于 64 时，链表会转成红黑树，提升查找效率从 O(n) 到 O(log n)。

HashMap 是懒加载的，new 的时候不会初始化数组，默认加载因子 0.75。第一次 put 时会调用 resize 创建容量为 16 的数组，扩容阈值是 12。

put 元素的流程是：先通过 hash 方法计算 key 的扰动哈希值，再用 (n-1) & hash 得到数组索引。如果该位置为空直接插入；如果有元素，先判断第一个是否 key 相同，相同就覆盖；判断是不是红黑树节点，是就走树插入；都不是就遍历链表，key 相同覆盖，不同就尾插。如果链表长度超过 8 且数组达到 64，转红黑树。插入完后如果 size 超过 threshold，触发扩容，容量翻倍。

JDK 1.7 和 1.8 的主要区别是：1.7 是数组加链表，头插法；1.8 加了红黑树，改尾插法，解决了多线程扩容时的死循环问题。