04.1.1.4 Map:HashMap 与并发 Map
所属:全栈开发面试题库 / 04 后端语言与运行时 / 04.1 Java / 04.1.1 语言基础与现代特性
04.1.1.4-001 HashMap 的底层数据结构是什么?
一句话结论
JDK 8 是“数组 + 链表 + 红黑树”:Node[] table,每个桶挂链表;链表长度 ≥ 8 且表容量 ≥ 64 时转红黑树,退化阈值 6。
概念解释
- 节点保存
hash、key、value、next。 - 默认容量 16,负载因子 0.75。
- 红黑树保证最坏 O(log n),避免哈希攻击退化为 O(n)。
原理流程
哈希表数组作为桶目录,每个桶先以链表组织冲突节点;冲突节点过多且表足够大时把链表升级为红黑树,降低最坏查询复杂度。
代码或图示
table[0] → Node → Node → ...
table[1] → TreeNode(红黑树)
table[2] → null
常见误区
- 以为冲突多时仍用纯链表:答:满足树化条件后会转红黑树,避免查询退化为 O(n)。
- 以为树化只看链表长度:答:还要求表容量 ≥ 64,容量不足优先扩容。
追问
- 为什么不用纯链表?答:冲突多时查询退化。
- 为什么树化阈值是 8?答:泊松分布下冲突概率极低,兼顾转换成本。
04.1.1.4-002 HashMap 的 hash 扰动是怎么做的?
一句话结论
hash = (h = key.hashCode()) ^ (h >>> 16),把高 16 位异或到低 16 位,让高位也参与桶定位。
概念解释
- 数组长度是 2 的幂,定位用
(n-1) & hash,只用到低位。 - 扰动让高位信息影响低位,减少规律性冲突。
- JDK 7 扰动更复杂(多次移位/异或),JDK 8 简化为一次。
原理流程
先取 key.hashCode(),右移 16 位后与原值异或,使高位哈希信息混入低位;桶定位时低位分布更均匀,降低低位相同导致的集中冲突。
代码或图示
本题无代码,扰动公式见一句话结论。
常见误区
- 以为 hashCode 直接用于取模定位:答:先经过扰动混合高低位再定位桶。
- 自定义 key 随意写 hashCode:答:应保证相等对象 hash 相等且分布均匀,可用
Objects.hash或质数组合。
追问
- 为什么需要扰动?答:否则高位不同、低位相同的 key 会挤在同一桶。
- 自定义 key 的 hashCode 怎么写?答:用
Objects.hash或质数组合,保证分布均匀。
04.1.1.4-003 HashMap 如何定位桶?
一句话结论
index = (table.length - 1) & hash,等价于 hash % length,但要求 length 是 2 的幂,位运算更快。
概念解释
容量为 2 的幂时,n-1 是低位全 1 的掩码;位与运算按掩码截取哈希低位作为下标。
原理流程
用掩码 (n-1) & hash 得到 0 到 n-1 的桶下标;传入的初始容量若不是 2 的幂,由 tableSizeFor 向上补到最近的 2 的幂。
代码或图示
int n = table.length; // 16
int index = (n - 1) & hash; // 0~15
常见误区
- 以为任意容量都能用位与定位:答:只有 2 的幂容量下
n-1才是全 1 掩码,分布才均匀。 - 以为传入容量就是实际容量:答:非 2 的幂会被向上取整到最近的 2 的幂。
追问
- 为什么容量必须是 2 的幂?答:
n-1的二进制全 1,位与等价取模且分布均匀。 - 传入非 2 的幂会怎样?答:
tableSizeFor向上取最近的 2 的幂。
04.1.1.4-004 HashMap 的 put 流程是怎样的?
一句话结论
计算 hash → 定位桶 → 空桶直接放 → 非空则比较 key(== 或 equals)→ 链表/红黑树插入 → 超过阈值扩容。
概念解释
key 相同的判定:hash 相同且 == 或 equals 为 true;相同则覆盖 value,不同则追加节点。
原理流程
空表先初始化;定位桶后空桶直接新建节点;非空桶先比首节点 key,命中则覆盖,否则按链表或红黑树结构查找插入;插入后 size 超过阈值触发扩容。
代码或图示
put(k,v)
hash(k)
if table empty: resize()
i = (n-1)&hash
if table[i] == null: new Node
else if 首节点 key 相同: 覆盖
else if TreeNode: 红黑树插入
else: 遍历链表,相同覆盖,否则尾插
++size > threshold: resize()
常见误区
- 以为 put 只在空桶写入:答:非空桶需先比较 key,重复则覆盖而非新增。
- 以为 JDK 8 链表是头插:答:JDK 8 改为尾插,顺序稳定且不易在并发扩容中成环。
追问
- key 相同怎么判断?答:hash 相同且
==或equals为 true。 - 为什么 JDK 8 改尾插?答:避免并发扩容形成环,且顺序稳定。
04.1.1.4-005 HashMap 的扩容过程是怎样的?
一句话结论
容量翻倍,阈值 = 容量 × 0.75;旧数组元素重新分配到新数组,JDK 8 利用 hash 高位判断,元素要么留在原索引,要么移到“原索引 + 旧容量”。
概念解释
- 扩容成本 O(n),需要 rehash。
- JDK 8 不需要重新计算 hash,只看
hash & oldCap。 - 扩容时链表可能拆成两条,保持相对顺序。
原理流程
新建两倍容量数组;遍历旧桶元素,用 hash & oldCap 判断新增的那一位是 0 还是 1:为 0 留在原索引,为 1 移到原索引加旧容量;链表按高低位拆成两条并保持顺序。
代码或图示
本题无代码,高低位拆分见原理流程。
常见误区
- 以为扩容只需复制引用不重排:答:元素需按新容量重新分配桶位置。
- 以为 JDK 8 扩容要重算 hashCode:答:只看 hash 与旧容量的位与结果,不重新计算 hash。
追问
- 为什么扩容后位置只可能变到 +oldCap?答:容量是 2 的幂,新增一位决定高低。
- 如何减少扩容?答:预设初始容量。
04.1.1.4-006 链表什么时候转红黑树?为什么?
一句话结论
链表长度 ≥ 8 且 table 容量 ≥ 64 时树化;容量不足 64 优先扩容,因为小表扩容比树化更划算。
概念解释
- 树化阈值
TREEIFY_THRESHOLD=8。 - 退化阈值
UNTREEIFY_THRESHOLD=6。 - 红黑树节点是普通节点的两倍大小,过多会浪费内存。
原理流程
桶内链表达到 8 个节点时检查表容量:≥64 则把链表转为红黑树;不足 64 先扩容数组。节点删除导致树大小降到 6 以下时退化为链表。
代码或图示
本题无代码,阈值与退化条件见概念解释。
常见误区
- 以为链表到 8 个节点立刻树化:答:还要求表容量 ≥ 64,否则先扩容。
- 以为树化后不会退化:答:节点减少到退化阈值 6 以下会退回链表。
追问
- 为什么阈值是 8?答:哈希分布下链表长度到 8 的概率约千万分之一。
- 为什么退化是 6 不是 8?答:留缓冲,避免频繁转换。
04.1.1.4-007 为什么负载因子是 0.75?
一句话结论
在空间利用率与冲突概率之间折中:太低浪费空间,太高冲突多、查询变慢;0.75 对应泊松分布下较优的冲突率。
概念解释
- 阈值 = 容量 × 0.75,超过就扩容。
- 0.75 让表在装满 3/4 时扩容,保持桶内冲突可控。
- 可通过构造器调整,但一般不推荐。
原理流程
负载因子决定何时触发扩容:元素数达到容量与负载因子的乘积即扩容;0.75 在桶填充率与冲突概率之间取得平衡,避免表过空浪费或过挤退化。
代码或图示
本题无代码,折中依据见概念解释。
常见误区
- 以为负载因子调大更省内存:答:冲突增加、查询变慢、树化概率上升。
- 以为调小负载因子无代价:答:频繁扩容、内存浪费。
追问
- 负载因子调大有什么后果?答:冲突增加、查询变慢、树化概率上升。
- 调小呢?答:频繁扩容、内存浪费。
04.1.1.4-008 为什么 HashMap 容量必须是 2 的幂?
一句话结论
为了用 (n-1) & hash 代替取模,且 n-1 二进制全 1 能让哈希值各低位均匀参与,减少冲突。
概念解释
- 位运算比
%快。 - 容量为 2 的幂时,
n-1是掩码,结果分布均匀。 tableSizeFor会把传入容量向上补到 2 的幂。
原理流程
2 的幂容量减 1 后低位全为 1,掩码与哈希位与得到均匀下标;若容量非 2 的幂,掩码存在 0 位,部分桶永远无法被命中。
代码或图示
本题无代码,掩码分布见原理流程。
常见误区
- 以为容量 15 也能均匀取模:答:
n-1=14(1110)最低位永远为 0,部分桶永远用不到。 - 以为传入 1000 初始容量就是 1000:答:实际向上取整为 1024。
追问
- 如果容量是 15 会怎样?答:
n-1=14(1110),最低位永远为 0,部分桶永远用不到。 - 初始容量 1000 实际是多少?答:1024。
04.1.1.4-009 JDK 7 和 JDK 8 的 HashMap 有什么区别?
一句话结论
JDK 7 是数组+链表、头插、扩容时重新计算 hash;JDK 8 加红黑树、改尾插、利用高位优化扩容、hash 扰动简化。
概念解释
两版在数据结构、插入方向、扩容迁移与扰动实现上均有差异。
原理流程
JDK 7 冲突节点以头插挂链表,扩容时重新 rehash;JDK 8 引入红黑树解决长链查询,尾插保持顺序,扩容按高低位拆分,扰动合并为一次移位异或。
代码或图示
| 维度 | JDK 7 | JDK 8 |
|---|---|---|
| 结构 | 数组+链表 | 数组+链表+红黑树 |
| 插入 | 头插 | 尾插 |
| 扩容 | rehash | 高低位拆分 |
| 并发 | 扩容成环 | 仍不安全但不易成环 |
常见误区
- 以为 JDK 8 HashMap 线程安全:答:并发 put 仍可能丢数据或覆盖,只是不易成环。
- 以为两版插入方向相同:答:JDK 7 头插、JDK 8 尾插。
追问
- 头插为什么要改尾插?答:并发扩容时头插可能形成环形链表,导致死循环。
- JDK 8 就线程安全了吗?答:不是,并发 put 仍可能丢数据。
04.1.1.4-010 HashMap 并发扩容为什么会死循环?
一句话结论
JDK 7 头插 + 并发扩容时,两个线程同时迁移同一链表,可能把 A→B 改成 B→A 并形成环,后续 get 遍历永远不结束。
概念解释
- 扩容时线程 A、B 同时操作同一桶。
- 头插反复修改 next 指针。
- 形成
A.next=B, B.next=A。 - CPU 100%,get 卡死。
原理流程
并发线程各自把链表节点头插到新数组,next 指针被交叉改写;链表头尾反向链接成环后,遍历遇到环不会终止,CPU 被打满。
代码或图示
本题无代码,成环机理见原理流程。
常见误区
- 以为这是 JDK 8 的问题:答:成环问题出现在 JDK 7 头插实现;JDK 8 尾插不易成环,但仍非线程安全。
- 以为并发用 HashMap 只是慢:答:会丢数据、覆盖,甚至死循环打满 CPU。
追问
- JDK 8 为什么不容易成环?答:尾插保持顺序,但仍会丢数据/覆盖。
- 并发场景用什么?答:ConcurrentHashMap。
04.1.1.4-011 ConcurrentHashMap 1.8 的实现原理?
一句话结论
数组 + 链表 + 红黑树;用 CAS + synchronized 锁单个桶(首节点),扩容支持多线程协助迁移。
概念解释
- 空桶用 CAS 插入,失败自旋。
- 非空桶锁首节点,锁粒度是桶。
sizeCtl控制初始化/扩容状态。- 多线程可协助
transfer,迁移 stride 分段。
原理流程
插入时空桶先 CAS 占位,冲突则自旋重试;桶非空时对首节点加 synchronized,同桶互斥、不同桶并行;扩容时多线程按 stride 分段迁移节点。
代码或图示
本题无代码,桶锁与协助迁移见原理流程。
常见误区
- 以为锁的是整张表:答:锁粒度是单个桶首节点,不同桶可并行写入。
- 以为 CHM 允许存 null:答:并发下无法区分“无值”和“值为 null”,不允许 null key/value。
追问
- 为什么锁首节点?答:同一桶的操作互斥,不同桶可并行。
- CHM 为什么不允许 null key/value?答:并发下无法区分“无值”和“值为 null”。
04.1.1.4-012 ConcurrentHashMap 1.7 的分段锁是什么?
一句话结论
Segment[] 分段,每个 Segment 继承 ReentrantLock 并含一个 HashMap;默认 16 段,锁粒度是段。
概念解释
- 不同段可并发写,同段串行。
- 段数决定并发度,初始化后不可变。
- JDK 8 改为桶级锁 + CAS,并发度更高。
原理流程
数据按 key 哈希分到多个 Segment,每个 Segment 自带锁与内部哈希表;写操作只锁住所属段,其他段并行;跨段遍历与统计需遍历所有段。
代码或图示
本题无代码,分段结构见原理流程。
常见误区
- 以为段数可运行时调整:答:段数初始化后固定,决定初始并发度。
- 以为分段锁粒度比桶级更细:答:段是粗粒度,JDK 8 桶级锁并发度更高。
追问
- 分段锁有什么缺点?答:段数固定、内存开销、跨段操作复杂。
- 为什么 1.8 放弃分段锁?答:桶级锁粒度更细,且红黑树优化冲突。
04.1.1.4-013 ConcurrentHashMap 的弱一致性是什么意思?
一句话结论
迭代器不保证反映迭代开始后的修改,可能看到旧值、也可能看到新值,但不会抛 ConcurrentModificationException。
概念解释
get无锁,可能读到正在迁移的数据。size是估算值,并发下不精确。- 复合操作要用
computeIfAbsent/merge保证原子性。
原理流程
CHM 迭代基于当前分段结构遍历,不快照也不记录修改计数;并发写入可能落在尚未遍历或已遍历的桶中,因此视图不强一致,读操作不加锁。
代码或图示
本题无代码,弱一致表现见概念解释。
常见误区
- 以为 CHM 迭代是强一致快照:答:弱一致,迭代期间修改不一定可见。
- 先 get 判断再 put:答:非原子复合操作,并发下应使用
computeIfAbsent/merge等原子方法。
追问
size()为什么不准?答:并发插入/删除持续变化。- 如何做原子复合操作?答:用 CHM 的原子方法,不要 get 后 put。
04.1.1.4-014 LinkedHashMap 如何实现 LRU?
一句话结论
构造器 accessOrder=true 按访问顺序排序,重写 removeEldestEntry 在超过容量时删除最旧条目。
概念解释
accessOrder=false 为插入顺序;true 时每次访问把条目移到链表尾部;最旧条目位于链表头部。
原理流程
开启访问顺序后,get/put 命中会重排双向链表;插入新条目后调用 removeEldestEntry,返回 true 即删除链表头部最旧条目。
代码或图示
LinkedHashMap<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
return size() > 3;
}
};
常见误区
- 以为 LinkedHashMap 天然线程安全:答:不安全,多线程需加锁或换并发缓存。
- 以为默认就是访问顺序:答:默认 accessOrder=false,按插入顺序。
追问
- accessOrder=false 是什么顺序?答:插入顺序。
- 生产环境直接用吗?答:需要线程安全,可加锁或使用 Caffeine。
04.1.1.4-015 TreeMap 的底层和适用场景?
一句话结论
TreeMap 基于红黑树,按 key 的 Comparable 或 Comparator 排序,支持范围查询、有序遍历,操作 O(log n)。
概念解释
- key 不能为 null(自然排序)。
firstKey/lastKey/headMap/tailMap/subMap支持范围操作。- 不允许 key 重复,重复会覆盖 value。
原理流程
key 按比较规则插入红黑树,树中保持有序;查找、插入、删除沿树路径比较,复杂度 O(log n);范围视图基于树区间返回子映射。
代码或图示
本题无代码,红黑树结构见原理流程。
常见误区
- 需要排序却选 HashMap:答:HashMap 无序,范围查询与有序遍历应用 TreeMap。
- 以为 TreeMap 用链表排序:答:底层是红黑树,不是链表。
追问
- TreeMap 和 HashMap 怎么选?答:需要排序/范围查询用 TreeMap。
- 红黑树为什么比 AVL 更适合?答:插入/删除旋转少,综合性能好。
本节高频题
- HashMap put/扩容(004-004/005)
- 为什么 2 的幂、0.75(004-007/008)
- JDK7 死循环(004-010)
- CHM 1.8 桶锁(004-011)
- LinkedHashMap LRU(004-014)