常用的哈希数据结构及原理
哪些公司问过
深信服1某游戏厂1
答案要点
- 常用结构:C++ 的 unordered_map、unordered_set,Java 的 HashMap、ConcurrentHashMap,Python 的 dict
- 哈希函数把 key 映射到桶下标,平均 O(1) 查找插入,最坏退化为 O(n)
- 冲突处理有链地址法和开放寻址法,Java 8 HashMap 链表过长会转红黑树
- 负载因子超过阈值时扩容并 rehash
- 自定义 key 要同时提供一致的哈希函数和相等判断
易错点
- 说哈希表查找一定是 O(1),忽略最坏情况和 rehash 开销
- 重写 equals 却不重写 hashCode,导致相等对象落在不同桶
- 把 Hashtable 的整表加锁和 ConcurrentHashMap 的细粒度并发混为一谈
面试官常见追问
- 负载因子默认是多少,为什么?
- 开放寻址法删除元素要注意什么?
- unordered_map 和 map 怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。