← 课程目录 🚀 从零到一
📐 学习维度 阶段2 · 第6章 集合源码 🚀 从零到一 📚 课程目录 🏠 首页 🛤️ 学习路径

6.1 HashMap 源码深潜:数组、链表和那棵救场的红黑树

审校 2026-09-24 · 素材来源:L06-HashMap源码深潜(底稿改写)
📑 本篇章节导航 (共12节,点击直达)
长什么样:一排挂链的格子put 一次发生了什么扩容:不用重算 hash 的搬家JDK 7 死链 vs JDK 8 修复key 的两条军规搬家演算:一眼看懂高低位get 一次发生了什么null 键与扰动的手算附加一问:Hashtable 为什么连 null 值都禁踩坑清单面试怎么问一句话总结

面试官问「讲讲 HashMap」,五分钟讲不下来的人很多。这篇把它拆成五个问题:长什么样、放进去经历了什么、什么时候长树、扩容怎么搬、为什么不是线程安全的。

长什么样:一排挂链的格子

HashMap 底层是 Node[] table——一排格子(桶),每个格子可以挂一条链表,链表太长还会变成红黑树:


table[0] → null
table[1] → K1 → K2 → K5        (链表,短)
table[2] → TreeNode 树          (链长≥8 且 数组≥64 才树化)
table[3] → null

快递柜类比:柜子编号由地址决定(hash),塞同一个柜子的包裹在柜里排成串(链表),串太长翻起来慢,就改成立体货架(红黑树),按序摆放二分查找。

关键参数背下来:默认容量 16、负载因子 0.75(装到 75% 就扩容)、树化阈值 8、退树化阈值 6、树化最小数组 64。

put 一次发生了什么

1. 算 hash:hashCode 的高 16 位异或低 16 位(扰动,让高位也参与定位,减少扎堆)

2. 定位桶:(n - 1) & hash——n 是 2 的幂时等价于取模,但位运算快

3. 桶空 → 直接放

4. 桶不空 → 桶头 key 相同就更新;是树就按树插;是链表就尾插到尾,插完链长 ≥8 尝试树化

5. 元素总数超过 容量 × 0.75 → 扩容两倍

注意第 4 步的「尝试树化」有陷阱:链长到 8 但数组不足 64 时,只扩容、不树化——小数组扎堆,加格子比分枝更划算。这是「树化双条件」,面试高频陷阱。

扩容:不用重算 hash 的搬家

扩成两倍后,每个节点的新位置只有两种可能:原位置,或原位置 + 旧容量。判断只需看 hash & 旧容量 那一位是 0 还是 1——所以 JDK 8 把一条链拆成「低位链、高位链」两条,各自整体搬家,不用逐个重新散列。

为什么容量必须是 2 的幂?两个好处都来自位运算:(n-1) & hash 代替取模提速;扩容时新位置只由一个比特位决定。

JDK 7 死链 vs JDK 8 修复

JDK 7 扩容搬家用头插法(新节点插链头),搬到一半顺序会倒过来。两个线程同时扩容,一个刚取下 A 被挂起,另一个搬完了;恢复后继续插,A 指 B、B 又指 A——链表成环,之后 get 在环里转死循环,CPU 飙满。

JDK 8 两处修复:改尾插法(顺序不变,不会成环)+ 高低位拆分。但 HashMap 依然不是线程安全的:并发 put 仍会互相覆盖丢数据。多线程请用 ConcurrentHashMap(下一篇)。

key 的两条军规

1. 重写 equals 必须同时重写 hashCode。定位桶靠 hash,桶内比对靠 equals——两个「相等」的对象若 hash 不同,会进不同桶,get 永远找不到

2. key 要不可变。把可变对象当 key,放进去后再改它的字段,hash 变了,等于把包裹贴错了柜号,取不出来了

搬家演算:一眼看懂高低位

拿真实数字走一遍。旧容量 16,某节点 hash=21(二进制 10101):

第 5 位是 0 的节点呢?原地不动。所以一条链上的节点,按这一位分成「不动组」和「加 16 组」,整组搬迁。这就是「不用重算 hash」的全部含义——判断一个比特位,比重新散列便宜太多。

get 一次发生了什么

put 的镜像过程:

1. 同样的扰动 hash 定位桶

2. 先看桶头:hash 相等且(== 或 equals)→ 直接返回

3. 桶头是树 → 树查找,O(log n)

4. 是链表 → 顺着 next 逐个比对,比对条件依然是「hash 相等且 equals」

注意这个比对条件:先比 hash(int 比较,快),hash 相同才 equals(可能贵)。这也是「重写 equals 必须重写 hashCode」的性能理由——hash 不同的话,equals 根本不会被调用,两个「相等」对象各躺各的桶,查找直接落空。

null 键与扰动的手算

HashMap 允许一个 null 键:null 没法调 hashCode,干脆固定落在 table[0],get 和 put 对 null key 都直奔 0 号桶。value 要几个 null 都行,没人管。

扰动可以手算验证:把 hashCode 高 16 位异或到低 16 位。设 hashCode 为 0x00020001,高 16 位是 2、低 16 位是 1,异或后得 0x00020003。多这一步为哪般?定位桶只看低几位——两个 hashCode 仅高位不同,本该散开却全挤一个桶。把高位掺进来,等于让 32 位都参与定位,扰动就是防扎堆的搅拌动作。

桶下标口诀 (n - 1) & hash:n=16 时掩码是 15,等价于 hash 对 16 取模,但位运算免除了除法。注意等价只对 2 的幂成立——这是容量必须 2 的幂的第一个理由,第二个(扩容一步定位)见上文搬家演算。面试被问「hash 函数做了什么优化」,答「高 16 位异或低 16 位的扰动函数」,正是这一句。

附加一问:Hashtable 为什么连 null 值都禁

HashMap 的 null 键固定住 0 号桶,null 值随便放;Hashtable 两个都禁。差别在设计年代:Hashtable 出身早,取值靠「先 contains 判空再 get」的两步写法,并发下没法消歧,干脆一禁了之。这个取舍后来被 ConcurrentHashMap 继承(6.2 节讲过它的 null 禁令)。面试把这条因果链连起来答,是「懂得为什么」的信号。

踩坑清单

面试怎么问

一句话总结

HashMap 是「hash 定柜、链表串包、长了变树、满了翻倍搬家」的结构;2 的幂容量让定位和扩容都吃位运算红利,树化要过双条件,线程安全它从来不管。