日期：2026-07-11
标签：#面试 #八股 #后端 #Java集合 #系统设计 #场景题
一句话答案
使用数组保存桶，通过哈希扰动和索引定位桶，冲突采用链表或树处理，并在负载因子超过阈值时扩容；设计重点是哈希质量、冲突、扩容和并发语义。
面试口语版
我会先定义 put/get/remove、是否允许 null、是否要求有序和线程安全。底层用长度为 2 的幂的桶数组，索引用 (n - 1) & spread(hash) 计算。桶为空直接插入，发生冲突时比较 hash 和 equals，已存在则替换，否则追加链表；链表过长且数组达到一定容量时转红黑树。元素数量超过 capacity * loadFactor 时扩容为两倍，并重新分配节点。JDK 8 中节点迁移时根据旧容量对应的 hash 位判断留在原索引还是移动到 oldIndex + oldCapacity。
核心结构
class Node<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
}
Node<K, V>[] table;
int size;
int threshold;
float loadFactor;关键细节
- 容量取 2 的幂，使取模可用位运算，并让扩容迁移更高效。
equals相等的对象必须有相同hashCode；可变 Key 会导致元素“丢失”。- 默认负载因子 0.75 是空间和冲突概率的折中，并非所有场景的唯一答案。
- 树化需要最小容量限制，否则小表优先扩容比维护红黑树更合适。
- 线程安全版本需额外考虑安全发布、桶级并发、CAS 和协助扩容。
面试官追问
- 为什么容量必须是 2 的幂？
- JDK 7 与 JDK 8 扩容有什么区别？
- 为什么链表要树化？
- hashCode 相同但 equals 不同怎么办？
- 如何设计线程安全版本？
面试官追问参考答案
1. 为什么容量必须是 2 的幂？
严格说不是“必须”，但 2 的幂让索引可用 (n-1)&hash 代替取模，并使低位掩码均匀覆盖桶。扩容翻倍时只需检查 hash 中旧容量对应的一位，节点要么留在原桶，要么移动到 oldIndex + oldCapacity。
2. JDK 7 与 JDK 8 扩容有什么区别？
JDK 7 采用头插法迁移链表，多线程错误使用时可能形成环；JDK 8 保持相对顺序，并按 hash 位拆成 low/high 两条链，同时在冲突严重时引入红黑树。HashMap 在两者中都不是线程安全容器。
3. 为什么链表要树化？
恶劣哈希或攻击可让大量 Key 落入同一桶，链表查找退化为 O(n)。红黑树将该桶查找降到 O(log n)；但树节点更耗空间，所以只在链长超过阈值且表容量足够大时树化，小表优先扩容。
4. hashCode 相同但 equals 不同怎么办？
它们是哈希冲突，会存放在同一桶的链表或树中。查找先比较 hash，再比较 key 引用或 equals；只有 equals 为 true 才视为同一个键并替换值，否则作为不同节点共存。
5. 如何设计线程安全版本？
简单方案是整表互斥锁；提升并发可采用分段/桶级锁，空桶插入用 CAS，冲突桶锁定桶头，扩容由多个线程按区间协助。无锁读取还需 volatile 和安全发布，并提供 putIfAbsent/compute 等原子复合操作。
学习清单
- 手写
put/get伪代码。 - 理解哈希扰动、树化阈值和扩容迁移。