哈希表有哪些常见实现方式
哪些公司问过
微软1富途1
答案要点
- 拉链法:桶内链表存冲突元素,实现简单、负载因子可大于 1,缓存局部性差
- Java HashMap:数组+链表+红黑树,桶内达到 8 个且容量≥64 时树化
- 开放寻址:线性探测、二次探测、双重哈希,缓存友好但需低负载因子,删除用墓碑
- Robin Hood 哈希均衡探测距离,Cuckoo 哈希查找最多访问两个位置
- 负载因子超过阈值时扩容并重新哈希,影响性能的关键是哈希函数质量
易错点
- 说 HashMap 链表长度到 8 就一定树化,忽略容量需≥64,否则先扩容
- 开放寻址删除直接置空,导致后续查找失败
- 认为哈希表操作一定是 O(1),忽略最坏情况和扩容开销
面试官常见追问
- 开放寻址法删除元素为什么不能直接置空?
- HashMap 为什么容量取 2 的幂?
- 线性探测有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。