HashMap 底层结构：桶里挤到一定程度，就该换个查法了（018）

覆盖考点：018｜HashMap 数据结构：数组、链表、红黑树、扩容和哈希扰动

适合读者：高级 Java 工程师、技术专家、架构师候选人

预计阅读时长：38 分钟（文末问答不计入）

前两篇讲的 ArrayList、LinkedList 都只用了一种底层结构组织数据——一个是连续内存的数组，一个是散落堆中的双向链表。HashMap 不一样，它是数组、链表、红黑树三种结构在同一个类里协同工作的复合结构，还外加一个"哈希扰动"这道并不直观的工序。很多人能背出"数组+链表"这个结论，但说不清链表什么时候会变成红黑树、扩容时数据怎么重新分布、hash() 方法里那行位运算到底在解决什么问题——这些正是这道题真正考验"读过源码"还是"背过结论"的分水岭。

面试官在这一考点上通常按这条链追问：为什么要用哈希表，而不是直接用数组或链表 → 底层的数组、链表、红黑树具体怎么组织 → hash() 方法里的位运算（哈希扰动）在解决什么问题 → 索引是怎么算出来的，为什么要求容量是 2 的幂 → 链表什么时候变成红黑树、什么时候又退化回链表 → 扩容具体做了什么、JDK 7 和 JDK 8 的扩容有什么本质区别 → 生产代码里容易踩的坑有哪些。本文按这个顺序展开。

一、为什么需要哈希表：直接寻址和顺序查找都不够用

1. 数组和链表各自的短板

上两篇反复讲过：数组按下标访问是 O(1)，但如果你要按"值"去查找一个元素在哪，只能从头到尾遍历，是 O(n)；链表更糟，连按下标访问都要遍历，插入删除虽然快，查找依然是 O(n)。业务场景里大量存在"给一个 key，尽快找到对应的 value"这种需求（缓存、索引、去重、计数），如果每次都要 O(n) 遍历，规模一大就完全无法接受。

2. 哈希表的核心想法：把"值"直接映射成"下标"

哈希表的思路是：既然数组按下标访问是 O(1)，那就想办法把 key 算成一个下标，直接跳到那个位置，而不是一个个比较。这个"算"的工具就是哈希函数——输入任意的 key，输出一个固定范围内的整数（下标）。理想情况下，不同的 key 算出不同的下标，查找、插入、删除都能做到接近 O(1)。但现实中不同的 key 完全可能算出同一个下标（哈希碰撞），HashMap 的大部分设计复杂度，都是在解决"碰撞发生之后怎么办"这一个问题。

二、三层结构：数组、链表、红黑树

1. table 数组：每个位置叫一个"桶"

HashMap 内部核心字段是 Node<K,V> 数组类型的 table，这是一个普通数组，数组的每一个位置习惯上叫一个桶（bucket）。

Node 是一个简单的类，包含 hash（缓存下来的哈希值）、key、value、next（指向同一个桶里的下一个节点）：

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

如果两个 key 被算到了同一个桶，HashMap 不会覆盖或者报错，而是把新节点接到这个桶已有节点的 next 上，形成一条链表——这就是"数组+链表"这句话里"链表"的来源，它本质上是"同一个桶内所有哈希碰撞的 key"串成的冲突链。

2. JDK 8 新增的第三层：红黑树

如果某个桶因为运气不好（或者被恶意构造）挂了特别长的链表，查找这个桶里的元素会退化成 O(n) 的链表遍历，失去了哈希表原本追求的近似 O(1)。JDK 8 引入了一个优化：当某个桶内链表长度达到一定阈值时，把这条链表转换成红黑树，用 TreeNode（继承自 Node）组织，查找复杂度从 O(n) 降到 O(log n)。这也是为什么严谨的说法是"数组 + 链表/红黑树"，而不是简单地说"数组+链表"——链表和红黑树是同一个桶内组织数据的两种可能形态，会根据情况互相转换，具体转换条件在后文第七节展开。

三、哈希扰动：hash() 方法到底在算什么

1. 直接用 hashCode() 当索引的问题

Object.hashCode() 返回一个 32 位的 int，理论上有 2^32 种取值，但 HashMap 的数组长度通常远小于这个范围（默认 16，很少有场景会用到几十亿长度的数组）。如果直接拿 hashCode() 的低若干位去对应数组下标，会导致一个问题：高位的信息完全被浪费掉。如果很多 key 的 hashCode() 恰好只在高位上有差异（低位模式相似，这在很多自定义 hashCode() 实现或者某些数值型 key 上并不罕见），直接截取低位会让这些原本不同的 key 全部落到同一个桶，人为造成大量哈希碰撞。

2. 扰动函数：把高位信息"搬"下来参与运算

HashMap.hash() 方法的实现只有一行核心逻辑：

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

h >>> 16 是无符号右移 16 位，把原来的高 16 位挪到了低 16 位的位置（高位补 0），再和原始的 h 做异或（^）。这一步操作的效果是：最终参与索引计算的低 16 位，同时融合了原始哈希值的高 16 位和低 16 位的信息。这样即使两个 key 的低 16 位完全相同，只要高 16 位有差异，异或之后低位也会产生差异，从而分散到不同的桶里，显著降低了"低位模式相似导致大量碰撞"这类场景的发生概率。这个操作在源码注释里被称为 perturb（扰动），中文社区通常译作"哈希扰动"或"扰动函数"。

3. 为什么不用更复杂的扰动算法

一次右移加一次异或，代价极低（两条 CPU 指令级别的操作），却能覆盖绝大多数真实场景下的哈希分布问题。HashMap 的设计目标是"性价比最高的扰动"，不是"理论上最均匀的扰动"——如果用类似 MurmurHash 那种更复杂的多轮混合算法，均匀性会更好，但每次 put/get 都要多付出数倍的计算开销，这对一个被调用频率极高的基础容器类来说并不值得。这也是工程设计里常见的权衡：够用的方案，往往比理论最优的方案更适合放进标准库。

四、索引计算：(n - 1) & hash 与"容量必须是 2 的幂"

1. 位运算代替取模

拿到扰动后的哈希值，HashMap 用下面这行代码算出最终的桶下标：

int index = (n - 1) & hash;   // n 是数组长度

这里的 &（按位与）在效果上等价于 hash % n，但只有当 n 是 2 的幂时才等价。原因在于：如果 n 是 2 的幂（比如 16，二进制 10000），那么 n - 1（15，二进制 01111）的二进制表示是低位全 1。任何数和一个"低位全 1"的数做按位与，效果就是只保留这个数的低若干位，这正好等价于对 2 的幂取模的结果。而位运算 & 是单条 CPU 指令，比涉及除法的取模运算 % 快得多——这是 HashMap 强制要求容量必须是 2 的幂的直接原因。

2. tableSizeFor()：即使你传错了，也会被纠正回 2 的幂

如果构造 HashMap 时传入的初始容量不是 2 的幂（比如 new HashMap<>(100)），HashMap 不会直接使用 100，而是通过 tableSizeFor() 方法向上取整到最近的一个 2 的幂（100 会被纠正为 128）：

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

这个方法的具体位运算技巧不需要逐行死记，但结论要记住：不管你传入的数字是多少，HashMap 的实际容量永远是 2 的幂，这是为了保证上面 (n-1)&hash 这条索引计算公式始终成立。

五、put() 的完整流程

1. 定位桶，处理三种情况

put(key, value) 的核心逻辑（putVal 方法）大致分三步：先用 (n-1)&hash 算出桶下标；如果这个桶是空的，直接放一个新节点进去；如果桶不为空，则需要区分当前桶内是链表还是红黑树，分别遍历查找是否已经存在相同的 key（hash 相等且 equals 判定相等），存在则覆盖 value 并返回旧值，不存在则把新节点接到链表末尾（或者按红黑树规则插入）。

2. 插入后检查是否需要树化

如果新节点插入后，当前桶内链表长度达到 TREEIFY_THRESHOLD（默认 8），会触发树化检查——但树化并不是无条件发生的，还要看数组长度是否已经达到 MIN_TREEIFY_CAPACITY（默认 64）。如果数组长度还不够 64，HashMap 会优先选择扩容而不是树化，因为链表变长很可能只是"数组太小、桶太少"造成的假性拥挤，扩容后重新分布数据，链表往往会自然变短，不需要动用红黑树这种更重的结构。

六、扩容 resize()：不只是搬家，还要重新分桶

1. 触发条件：负载因子 0.75

HashMap 维护一个 threshold（阈值）字段，等于 容量 × 负载因子（负载因子默认 0.75）。当元素个数超过这个阈值，就会触发扩容，新容量是旧容量的2 倍（保证扩容后依然是 2 的幂）。0.75 这个负载因子本身也是权衡结果：调得越低，桶越空、冲突越少，但空间浪费越多；调得越高，空间利用率越高，但冲突概率上升、链表变长的风险增加。0.75 是 JDK 作者综合空间利用率和查找性能给出的经验值。

2. JDK 8 的关键优化：不需要重新计算 hash，只需要判断一个位

扩容意味着数组从旧容量 oldCap 变成新容量 newCap = 2 × oldCap。旧数组里某个桶上的所有节点，扩容后要重新分配到新数组的某个位置——如果每个节点都重新执行一次 (newCap-1)&hash 显然可行，但 JDK 8 用了一个更巧妙的观察：因为新容量正好是旧容量的 2 倍，一个节点在新数组里的位置，只有两种可能——原来的下标，或者原来的下标 + oldCap。判断走哪一条，只需要看这个节点的 hash 值在 oldCap 对应的那一个二进制位上是 0 还是 1（(hash & oldCap) == 0 就留在原下标，否则去 "原下标 + oldCap" 的新位置），完全不需要重新做一次完整的 (newCap-1)&hash 计算。

3. 链表拆分成两条，保持原有顺序

具体实现上，JDK 8 会把旧桶里的链表一次遍历拆分成两条新链表（loHead/loTail 和 hiHead/hiTail），分别挂到新数组对应的两个新桶上，并且保持了原链表内的相对顺序。这一点特意强调是因为 JDK 7 的扩容实现在重新插入时会导致链表顺序反转，这个"顺序反转"叠加"多线程并发扩容"，正是 JDK 7 里那个经典的"扩容死循环"故障的根源之一（详见第八节）。JDK 8 这次"不重排顺序、只做一次遍历分裂"的重写，同时优化了性能和消除了这个特定故障模式。

七、树化与退化：8 上 6 下的两个阈值

1. TREEIFY_THRESHOLD = 8：什么时候链表变成树

一个桶内链表长度达到 8，且数组长度已经不小于 64（否则优先扩容，见第五节），才会触发树化，把这条链表转换成红黑树。为什么选 8 这个数字：源码注释里给出了依据——在哈希值分布足够随机均匀的理想情况下，单个桶里链表长度符合泊松分布，链表长度达到 8 的概率大约是千万分之几这个量级，属于极端罕见事件。如果真的观察到某个桶的链表长度达到了 8，几乎可以确定是不正常的哈希碰撞（可能是 hashCode() 实现质量差，也可能是攻击者故意构造了大量哈希碰撞的 key 发起"哈希碰撞攻击"）——这种情况下用红黑树把最坏情况下的查找复杂度从 O(n) 兜底到 O(log n)，是一种针对小概率极端情况的保护机制，不是常规路径下会频繁触发的逻辑。

2. UNTREEIFY_THRESHOLD = 6：为什么退化阈值不是 8

红黑树在删除元素、桶内元素变少之后，如果元素个数降到 6 以下，会退化回普通链表。退化阈值特意选得比树化阈值（8）更低，而不是同样用 8，是一个经典的"滞后区间"（hysteresis）设计：如果树化和退化都用同一个阈值 8，元素个数在 8 附近轻微波动（一次插入超过 8 触发树化，紧接着一次删除又降到 8 以下触发退化）就会导致链表和树反复来回转换，每次转换本身都有不小的开销。用两个不同阈值（8 和 6）中间留出一段"缓冲区"，避免了这种在临界值附近反复抖动的情况。

3. 红黑树节点怎么比较大小

红黑树需要维护节点间的大小关系才能保持平衡，TreeNode 的比较规则是：先比较两个节点的 hash 值；如果 hash 相同，且 key 的类实现了 Comparable 接口，就调用 compareTo()；如果两者都不满足（hash 相同、且不可比较或者比较结果也是 0），会用一种称为 tieBreakOrder 的方式（基于类名字符串比较，最终兜底用 System.identityHashCode 或者插入顺序）强制打破平局，保证树结构始终有一个确定的顺序，不会因为比较结果模糊而破坏红黑树的结构约束。

八、常见误区与工程实践

1. 初始容量该怎么估：不是"要装多少"，是"数组要多长"

new HashMap<>(16) 里的 16 是数组的初始长度，不是"能装 16 个元素而不扩容"——因为负载因子是 0.75，实际到 12 个元素就会触发扩容。如果已知业务预计要放入 N 个元素，又不想中途扩容，正确的估算公式是 初始容量 = (int)(N / 0.75) + 1，再交给 tableSizeFor() 纠正到最近的 2 的幂。

2. key 的可变性陷阱

如果作为 key 的对象在放入 HashMap 之后被修改了，并且这次修改影响了 hashCode() 的计算结果，会导致这个 key 再也找不到了——因为 get() 时会用当前的 hashCode() 重新定位桶，而这个对象实际存放的位置是插入那一刻的旧 hashCode() 算出来的桶，两者对不上。正确实践是：作为 HashMap（以及 HashSet）key 的对象应该是不可变的，或者至少保证放入之后不会再修改会影响 hashCode()/equals() 结果的字段。

3. 并发问题：JDK 7 死循环 vs JDK 8 死链

HashMap 从头到尾都没有任何同步保护，多线程并发操作是未定义行为，但具体故障模式在 JDK 7 和 JDK 8 之间发生了变化。JDK 7 扩容时是"从旧链表头部开始，逐个取出节点插入新链表头部"，这个过程会导致链表顺序反转，如果多个线程同时在做这件事，可能因为指针操作交错，导致某个节点的 next 反过来指向了它自己的前驱，形成一个环——之后只要有线程遍历到这个环，就会陷入死循环，CPU 占用飙升到 100% 且永不结束，这是生产环境里非常经典的一类故障。JDK 8 改成"一次遍历、保持原顺序地拆分成两条链表"的实现方式后，理论上不会再形成环，但多线程并发写仍然可能导致其他形式的数据丢失或者链表结构被破坏（称为"死链"，指某些元素在并发写后事实上从链上丢失，而不是真的死循环）。结论不变：任何多线程共享的场景都应该用 ConcurrentHashMap，HashMap 从设计上就不是为并发场景准备的。

4. null key 的特殊处理

HashMap 允许存放一个 null 作为 key（hash(null) 被定义为固定返回 0，对应桶下标也固定），这是它和 Hashtable（不允许 null key/value，会直接抛 NullPointerException）的一个明显区别。虽然语言层面支持，但生产代码里如果显式依赖"用 null 作为一个有意义的 key"这个特性，通常会让代码的可读性和意图变得模糊，多数团队规范会建议避免这种写法。

九、面试追问链

延伸阅读

• JDK 源码：java.util.HashMap（hash()、putVal()、resize()、treeifyBin()）
• 泊松分布与哈希碰撞概率：TREEIFY_THRESHOLD 取值 8 的统计学依据
• 红黑树基础：五条性质与旋转操作（作为背景知识，不要求手写实现）
• java.util.concurrent.ConcurrentHashMap：并发场景下的哈希表替代方案
• 哈希碰撞攻击（Hash Flooding）：为什么框架层要防御恶意构造的哈希碰撞输入

问答（不计入阅读时长）

Q1：扰动函数为什么右移 16 位，而不是移动其他位数？这个数字是怎么定的？

A：int 在 Java 里是 32 位，右移 16 位正好把高 16 位和低 16 位对半分开，让"上半段"和"下半段"各自完整地参与一次异或。这不是唯一可行的移位量，但它是一个直觉上很自然的折中：移得太少（比如只移 4 位），高位大部分信息还是没有机会跟低位混合；移得太多（比如移 24 位），只有很小一部分高位信息参与混合，效果和不移位差别不大。32 位对半分（16+16）是让"两段信息量尽量对等地互相影响"的一个朴素且计算成本相同（都是一次移位）的选择，源码作者在注释里也承认这只是权衡后的经验值，不是通过严格数学证明得出的最优解。

Q2：HashMap 默认初始容量为什么是 16，不是 10 或者 32？

A：这和"必须是 2 的幂"这条硬约束直接相关——10 不是 2 的幂，不能作为默认值（会被 tableSizeFor 纠正掉）。在满足 2 的幂的前提下，16 是一个经验性的起点：太小（比如 4）意味着几乎任何有实际数据量的场景都会立刻触发多次扩容，创建成本被搬迁成本抵消；太大（比如 64、128）又会让大量只存少量元素的小 HashMap（这在实际业务代码里非常常见，很多 HashMap 只是临时用来存三五个键值对）白白浪费内存。16 只是在"绝大多数场景下够用、又不过度浪费"之间选的一个折中数字，本身没有更深的数学依据，如果能提前预估规模，更好的做法始终是显式指定初始容量，而不是依赖这个默认值。

Q3：JDK 8 虽然消除了扩容死循环，但"死链"具体是怎么发生的？

A：JDK 8 的 resize() 在单线程视角下是"一次遍历、无锁地把旧链表拆成两条挂到新数组"，但如果两个线程同时进入这段逻辑，它们各自都会读取同一个旧链表、各自计算拆分结果、各自往（各自持有引用的）新数组里挂节点——这个过程里没有任何同步保护，可能出现的具体故障是：线程 A 刚把某个节点接到新链表尾部，线程 B 几乎同时也在处理同一个旧节点，并把它接到另一条链表或者覆盖了 A 刚写的 next 指针，最终导致某些元素在"新数组"里彻底丢失引用——不是形成环，而是有些元素从此再也访问不到（但也没有被当作垂悬对象回收，因为可能还有别的路径能间接引用到它，具体取决于交错时序）。这类问题的表现是"数据莫名其妙少了"而不是 CPU 飙升，比死循环更隐蔽，往往要等到业务上发现某个 key 查不到才会被注意到，排查难度反而更高。

Q4：为什么树化要同时满足"链表长度 8"和"数组长度不小于 64"两个条件？只看链表长度会有什么问题？

A：如果只看链表长度、不管数组大小，会误判一种常见但完全正常的情况——数组本身太小。举例：数组长度只有 4 或 8 的小 HashMap，即便哈希分布完全均匀，只要塞进去二三十个元素，单个桶的平均链表长度也很容易达到 6-8，这时候"链表变长"根本不是哈希碰撞异常，只是"桶的数量本来就不够分"。这种情况下正确的应对是扩容（增加桶的数量，让元素重新分散），而不是花代价去建一棵红黑树——树化和后续维护红黑树平衡的开销远高于简单扩容。只有当数组已经达到 64 这个"不算小"的规模、链表还能长到 8，才说明问题不在桶的数量上，而是真的出现了统计意义上的异常聚集，这时候用红黑树兜底最坏查找性能才是划算的。

Q5：TreeNode 比较大小时的 tieBreakOrder，具体在什么场景才会真正用到？

A：只有当两个节点的 hash 值相同、且 key 所属的类没有实现 Comparable（或者实现了但 compareTo() 恰好返回 0，说明这个类的比较逻辑认为两者"相等"但 equals() 却判断不相等，这本身已经是一种不常见但允许存在的类设计）时，才会走到 tieBreakOrder 这条兜底逻辑。它的实现是先比较两个对象运行时类的类名字符串（getClass().getName()），如果类名还相同（说明是同一个类的两个不同实例），最后用 System.identityHashCode() 做最终裁决。这条逻辑在实践中触发频率极低——大多数作为 key 的类型（String、Integer、自定义的业务对象）hash 相同的概率已经很低，再叠加"不可比较或比较结果为 0"的条件，属于双重小概率事件。它存在的意义是保证红黑树在任何输入下都有一个确定的、全序的比较结果，不会因为比较逻辑返回"无法比较"而破坏树结构的正确性，这是一种防御性的兜底设计，不是常规路径。

Q6：HashMap 和 Hashtable 除了 null key/value 的区别，还有哪些容易被忽略的差异？

A：至少还有三点：扩容策略不同——Hashtable 默认扩容是"旧容量 × 2 + 1"（不要求是 2 的幂，索引计算用取模 % 而不是位运算 &），HashMap 则严格要求容量是 2 的幂；同步机制不同——Hashtable 几乎所有公开方法都用 synchronized 修饰，是一个方法级别全表加锁的容器，HashMap 完全没有同步；迭代器行为不同——Hashtable 的 Enumeration（它比 Iterator 出现得更早，是遗留 API）不支持 fail-fast 检测，HashMap 的迭代器有 modCount 校验会抛 ConcurrentModificationException。现代代码几乎不再使用 Hashtable，它更多作为历史遗留 API 出现在老代码库里，新代码需要哈希表用 HashMap，需要并发安全用 ConcurrentHashMap，两者分别覆盖了 Hashtable 曾经想同时兼顾的两个目标。

Q7：为什么覆写 equals() 必须同时覆写 hashCode()？如果只覆写 equals() 会发生什么具体故障？

A：HashMap 判断两个 key 是否"是同一个 key"，走的是"先比较 hash 是否相等，hash 相等再调用 equals() 精确比较"这个两步流程——这是一个性能优化，hash 不相等就直接跳过，不需要付出 equals() 的比较代价。如果只覆写了 equals()（认为两个属性相同的对象应该"相等"）却没有覆写 hashCode()（继承了 Object 默认的、基于对象内存地址的哈希实现），会出现"两个 equals() 返回 true 的对象，hashCode() 却大概率不同"的情况——这直接违反了 Java 规范里"相等的对象必须有相等的 hashCode"这条契约。具体故障表现是：用一个逻辑上"相等"的新对象去 get()，因为它的 hashCode() 和插入时那个对象不同，会被路由到完全不同的桶，遍历那个桶的链表根本找不到目标节点，get() 返回 null，即便逻辑上这个 key"应该"能查到。

Q8：生产环境怎么发现某个 HashMap 已经出现了异常的哈希碰撞（某个桶挂了很长的链表甚至已经树化）？

A：几种可行的排查思路：从现象反推——如果监控发现某个使用了 HashMap 作为缓存或索引的服务，get/put 的耗时出现了不成比例的抖动（大多数请求很快，少数请求明显变慢），且这个变慢和某些特定 key 相关，很可能是这些 key 落在了同一个链表很长的桶里；堆内存分析——用 jmap/MAT（Eclipse Memory Analyzer）之类的工具 dump 堆内存，直接检查目标 HashMap 实例的 table 数组，统计每个桶挂的节点数分布，能直接看到是否存在异常聚集的桶，甚至能看到某些桶已经是 TreeNode 类型（说明已经树化）；代码层面的主动防御——如果 key 来自不可信的外部输入（比如 HTTP 请求参数直接作为 key），要意识到这是"哈希碰撞攻击"的经典入口，攻击者可以精心构造大量 hashCode() 相同的字符串批量提交，故意把某个桶的链表撑到很长，让服务端处理这批请求的耗时暴涨（一种应用层的拒绝服务手法），生产系统对这类不可信输入通常会限制单次请求携带的 key 数量，或者改用带随机盐值的哈希算法（Java 字符串的 hashCode() 在某些版本上是可以被预先计算碰撞的）。