高性能哈希表设计:探测、扩容与并发
哪些公司问过
答案要点
- 链地址法指针跳转导致缓存不友好、节点分配开销大,高性能实现多用开放寻址
- 开放寻址要素:2 的幂容量加位运算、线性探测或 Robin Hood、合理负载因子、墓碑或移位删除
- SwissTable 用元数据字节和 SIMD 批量比较槽位,进一步提升探测效率
- 扩容可一次翻倍重哈希,延迟敏感场景用渐进式 rehash 分摊搬迁成本
- 并发用分片锁、CAS 或版本号乐观读;使用随机种子哈希防御哈希洪水
易错点
- 开放寻址直接把删除位置置空,会截断后续元素的探测链导致查找失败
- 负载因子设得过高,线性探测下聚集严重,性能急剧下降
- 说工业界都不用链地址法,Java HashMap 等主流实现仍然是链式
面试官常见追问
- Robin Hood Hashing 是什么?
- Redis 的渐进式 rehash 怎么做?
- Java ConcurrentHashMap 如何做并发?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。