2026春招大厂面试真题补充 - 七、HashMap深度追问(几乎所有公司必问)
本文是 2026春招大厂面试真题补充 的分章阅读版。
七、HashMap深度追问(几乎所有公司必问)
// 面试官: "HashMap底层原理?为什么用红黑树?"
回答框架:
1) 数据结构: 数组 + 链表 + 红黑树(JDK8+)
Node<K,V>[] table → 每个桶是链表或红黑树
2) put流程:
① hash(key) → 扰动函数(h ^ h>>>16)减少碰撞
② (n-1) & hash → 计算桶下标(等价于取模但更快)
③ 桶为空 → 直接插入
④ 桶非空 → key相同则覆盖 → 否则尾插法插入链表
⑤ 链表长度>=8 且 桶数量>=64 → 转红黑树(查找O(logn))
⑥ 元素数量 > capacity * loadFactor → resize扩容(2倍)
3) 为什么链表转红黑树阈值是8?
泊松分布计算:链表长度达到8的概率仅0.00000006
→ 正常情况下几乎不会转红黑树
→ 转树是极端hash冲突的保底措施
→ 低于6退化为链表(避免频繁转换)
4) JDK7 vs JDK8区别:
| 维度 | JDK7 | JDK8 |
|------|------|------|
| 插入方式 | 头插法(多线程死链) | 尾插法 |
| 数据结构 | 数组+链表 | 数组+链表+红黑树 |
| hash计算 | 9次扰动 | 1次扰动(h^h>>>16) |
| 扩容 | 重新hash | 原位置or原位置+旧容量 |
5) 为什么HashMap线程不安全?
① JDK7头插法+并发扩容 → 死循环链表
② JDK8并发put → 数据丢失(两个线程同时CAS到同一个桶)
③ size计算不准确(没有CAS保护++)
→ 线程安全替代: ConcurrentHashMap(分段锁/CAS+synchronized)
相关页面