I IT 面试题库
什么是哈希表?如何解决哈希冲突?
中级简答题硬件工程师芯片设计工程师(IC设计)数据结构哈希表
参考答案
内容深度:基础 · 无代码示例 · 来源:外部链接 · 已复核 · 28 天前更新
原理
- 哈希函数把 key 映射到桶下标,理想 O(1) 查找/插入/删除;实际受哈希质量、负载因子和冲突影响。
冲突
- 链地址法:每个桶挂链表/红黑树(Java HashMap 链表长度≥8 且容量≥64 转红黑树);实现简单、删除方便。
- 开放地址:线性/二次探测、双重哈希;缓存友好但删除要墓碑、易聚集。
- 再哈希/公共溢出区用于特定场景。
扩容
- 负载因子(元素/桶数)超阈值(如 0.75)扩容并 rehash;扩容有一次性/渐进式,注意停顿。
- 哈希攻击:构造大量冲突退化为 O(n),用随机种子/限流/红黑树缓解;一致性哈希用于分布式缓存。
题目与答案就在本页;收藏、批注和错题重练在应用内