手写简单哈希表(设计哈希映射)
哪些公司问过
答案要点
- 拉链法:桶数组加链表,节点存 key、value、next
- put:哈希取模定位桶,key 存在则覆盖,否则插入新节点
- get、remove:定位桶后遍历链表按 key 查找,删除注意头节点
- 负载因子超过阈值时扩容并重新哈希,桶数为 2 的幂可用位与取模
- 平均 O(1),最坏冲突时 O(n);开放寻址删除需墓碑标记
易错点
- put 时没检查 key 已存在,导致重复插入
- 负数哈希值直接取模得到负下标
- 扩容后不重新哈希,旧数据查不到
面试官常见追问
- 开放寻址和拉链法各有什么优缺点?
- 扩容时为什么要重新哈希?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。