哈希表的原理与冲突解决
哪些公司问过
答案要点
- 哈希函数把 key 映射为数组下标,平均查找、插入、删除 O(1)
- 链地址法:冲突元素挂在同一桶的链表(Java HashMap;JDK8 链表过长转红黑树)
- 开放地址法:冲突后按探测序列找下一个空槽(线性探测、二次探测、双重哈希)
- 装载因子超过阈值触发扩容,并对所有元素 rehash
- 好的哈希函数分布均匀、计算快;最坏情况(大量冲突)退化为 O(n)
易错点
- 说哈希表查找“一定是 O(1)”:只是平均,最坏会退化
- 把链地址法和开放地址法的特点说反
- 忽略哈希函数质量:分布不均会让冲突剧增
- 忘记 rehash 的开销:扩容时一次性重新分配,可能造成延迟尖刺
面试官常见追问
- 负载因子是什么,为什么默认是 0.75?
- 开放地址法的缺点是什么?
- 哈希表扩容为什么要重新计算位置?
- JDK8 的 HashMap 冲突链表过长为什么转红黑树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。