终面通常不会问'怎么用',而是盯着'为什么这么设计'和'出问题怎么办'问。下面还原这场面试里被追问最多的几个问题,整理成回答思路和关键细节。
数据结构:从二叉树到红黑树,要的是取舍
面试官: 说说二叉树、平衡二叉树、红黑树。
我从使用场景切入:
- 普通二叉搜索树(BST)在有序插入时会退化成链表,查找从 O(log n) 掉到 O(n)。
- 平衡二叉树(AVL)通过严格平衡(任意节点左右子树高度差 ≤1)保证 O(log n),但插入删除时旋转开销大,适合读多写少,比如数据库索引。
- 红黑树是近似平衡,靠五条规则保证最长路径不超过最短路径的 2 倍:节点红黑着色,根和叶子(NIL)是黑色,红色节点的子节点必须黑色,任一节点到其后代叶子的路径包含相同数目的黑节点。它牺牲了一点严格平衡,换来了更少的旋转,读写混合场景更均衡。
这里面试官如果追问'HashMap 1.8 为什么用红黑树而不用 AVL',可以指出:树化是链表过长时的兜底策略,写入频率通常不高;红黑树实现比 AVL 简单,旋转次数少,综合成本更低。
HashMap 底层:数组 + 链表/红黑树
面试官: HashMap 的底层原理?
JDK 1.8 是'数组(Node<K,V>[] table)+ 链表/红黑树'的混合结构:
- 通过
(n - 1) & hash计算桶下标(n 是 2 的幂,保证分布均匀)。 - 哈希冲突时,先用链表串起来,1.7 是头插法,1.8 改成尾插法(避免并发 resize 的死循环)。
- 当链表长度 ≥ 8 且数组长度 ≥ 64 时,链表会被转为红黑树,查询从 O(n) 降到 O(log n)。扩容时,1.8 会根据高位 bit 将链表拆成两条,避免重新哈希,效率比 1.7 高。
核心插入逻辑简化后是这样:
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 遍历链表或树
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; // 找到相同 key,更新 value
if (binCount >= TREEIFY_THRESHOLD - 1) // >=7
treeifyBin(tab, hash); // 链表转红黑树
}
ConcurrentHashMap 如何解决线程安全问题
面试官: HashMap 线程安全吗?ConcurrentHashMap 的底层结构?
HashMap 不是线程安全的。并发下可能出现数据覆盖、size 计数错误,1.7 还因为头插法形成环形链表导致死循环。
ConcurrentHashMap(CHM)的演进是从分段锁到 CAS + synchronized:
- 1.7 用 Segment 分段锁,默认 16 个段,每段独立加锁。
- 1.8 放弃了 Segment,直接锁住具体的桶:桶为空时 CAS 插入,桶为链表/树时 synchronized 锁住头节点。其他线程仍可以操作不同桶,锁粒度更细。
1.8 的 putVal 关键片段:
if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
{
(f) {
(tabAt(tab, i) == f) {
}
}
}

