HashMap 面试题，这一次彻底讲明白

集合是 Java 面试出现频率最高的板块，HashMap 又是集合里的"题眼"。我当年就是栽在"背了结论，说不清为什么"。这篇按我自己的理解重写一遍，尽量把"为什么"讲明白。

HashMap 底层长什么样

JDK 8 之后的 HashMap 是数组 + 链表 + 红黑树：

• 底层一张 Node[] 数组，每个位置叫一个桶（bucket）；
• key 算完哈希落到某个桶，撞上了就链成链表；
• 链表太长（长度 ≥ 8 且数组 ≥ 64）就树化成红黑树，查询从 O(n) 变 O(log n)；
• 反过来，树节点 ≤ 6 时退化成链表。

为什么是 8 和 6？ 8 是按泊松分布算出来的：正常情况下一个桶里链表长度超过 8 的概率只有千万分之几，基本不可能自然发生，说明是哈希坏得离谱，才值得树化。至于 6，是为了避免链表和树在临界值附近反复横跳，留出缓冲。

put 的完整流程（高频考点）：
1. 用 (n - 1) & hash 算出桶的位置；
2. 桶空，直接放；
3. 桶不空，先比 hash 再比 equals，相等就覆盖旧值；
4. 不相等，判断底下是链表还是树，链表尾插、树按树插；
5. 插入完链表超 8 且数组 ≥ 64，树化；
6. 元素数超过容量 × 负载因子（默认 0.75），扩容。

两个细节：hash 扰动和为什么容量是 2 的幂

hash 扰动：JDK 8 把 key 的 hashCode 高 16 位和低 16 位异或，让高位也参与定位，减少冲突。源码就这几行：

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

容量为什么必须是 2 的幂？ 因为定位用的是 (n - 1) & hash 而不是取模——只有 n 是 2 的幂时，n - 1 的二进制才全是 1，& 才能完整保留 hash 的低位信息。这也是为什么扩容永远是翻倍：翻倍后 n - 1 只多了一个最高位的 1，元素要么留在原桶，要么挪到"原位置 + 旧容量"，重定位代价极小。

扩容，和 JDK 7 那个著名的坑

• 触发条件：元素个数 > 容量 × 负载因子，默认就是 16 × 0.75 = 12；
• 扩容目标：容量翻倍；
• JDK 7 的坑：用的是头插法，并发扩容时可能形成循环链表，get 直接死循环；
• JDK 8 的改进：改尾插法，循环链表没了，但并发下还是会丢数据——两个线程同时 put 互相覆盖。

所以结论从来只有一个：HashMap 并发不安全，并发场景老老实实用 ConcurrentHashMap。

ConcurrentHashMap：从分段锁到 CAS + 锁

JDK 7 用 Segment 分段锁：默认 16 段，每段一把锁，段与段之间能并发写，理论上最多 16 个线程同时写。

JDK 8 放弃了分段锁，改成 CAS + synchronized 细化到桶：
- 桶是空的 → CAS 直接插，无锁；
- 桶不空 → 给桶头节点上 synchronized 锁，同一桶内串行、不同桶并发；
- 扩容时可以多个线程一起帮忙搬数据（拆任务并行迁移）；
- 树化条件跟 HashMap 一致。

为什么更快？锁粒度从"段"细到"桶"，加上空桶 CAS 根本不上锁，几乎只有真正撞桶才加锁。size() 也不加全局锁，用 baseCount + CounterCell[] 分段累计，近似准确。

ArrayList vs LinkedList：一道送分题，答案其实变了

• ArrayList：底层数组。随机访问 O(1)，尾部增删 O(1)，中间插入要挪元素 O(n)。扩容按 1.5 倍来（oldCapacity + (oldCapacity >> 1)）。
• LinkedList：底层双向链表。头尾增删 O(1)，但"中间插入快"是伪命题——找位置本身就要 O(n) 遍历，每个节点还多两个指针，内存更费。

实际开发里 ArrayList 几乎总是更优，LinkedList 更多是教学意义。面试答这个，能把"找位置也要遍历"说出来，就比只会背复杂度强。

几个高频追问

1. HashMap 为什么线程不安全？ JDK 7 循环链表，JDK 8 丢数据。
2. HashMap 允许 null key 吗？ 允许，put(null, v) 走第 0 个桶；但 ConcurrentHashMap 不允许 null key/value，避免并发语义上的歧义。
3. 为什么重写 equals 必须重写 hashCode？ 契约要求"equals 相等的 hashCode 一定相等"。否则两个相同的 key 算出不同 hash，落到不同桶，存进去就取不出来。
4. LinkedHashMap 和 TreeMap？ LinkedHashMap 保插入顺序（还能改成访问序做 LRU 缓存），TreeMap 底层红黑树、按 key 排序。

我的建议

集合题其实是一条链：hash 定位 → 冲突解决 → 扩容 → 并发安全。把这条链讲顺，比死记"8 和 6"值钱得多。另外 JDK 21 之后集合多了 SequencedCollection 这种新接口，提一嘴能显得你平时在跟版本。

一句话收尾：HashMap 用对场景是利器，用错并发场景是事故。理解底层，才知道什么时候该换工具。