信息技术大学
哈希表
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
信息技术大学
哈希表
数据结构与算法·面试高频 · 第 1 章 复杂度与线性结构
哈希函数与冲突解决
哈希把 key 映到桶：冲突不可怕，链地址挂链表或开放地址再找坑。
哈希函数
均匀散列是前提，好函数少冲突
链地址法
同桶挂链表，长了转红黑树兜底
开放地址
冲突后探测下一个空位，装填因子要控制
扩容
超负载因子就翻倍重建，均摊 O(1)
两数之和套路
一遍哈希：边遍历边查「补数来过没有」，查与存同步完成。
查存一体
先查 target−x 是否在表，再放 x 入表
一次遍历
O(n) 时间 O(n) 空间，替代双循环
变体
三数之和改排序加对撞，去重是难点
设计哈希集合
手写一遍底层：桶数组加链表，懂扩容与冲突就懂了 HashMap 的骨架。
骨架
桶数组加链表节点，index = hash % 容量
扩容再哈希
容量翻倍迁移，旧链逐节点重挂新桶
本节要点
- ✓冲突两条路：挂链或开放寻址
- ✓两数之和：查补数与存当前同步走
- ✓手写哈希：桶数组加链表加扩容
延伸主题：复述一次 HashMap 原理刷三数之和
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1负载因子为什么不能设成 1？
参考答案因子 1 意味着桶几乎全满，冲突链急剧变长，查找退化；留出空桶才能维持期望 O(1)。Java 默认 0.75，是空间与时间折中的工程值。
2两数之和为什么「先查后存」而不是「先存后查」？
参考答案先查后存保证查到的一定是之前的元素，不会与自己配对；先存后查还得额外排除同一下标。顺序里藏着正确性。
3Java 8 为什么把过长的链表转成红黑树？
参考答案哈希退化或恶意碰撞时链表查找 O(n)，转红黑树后 O(log n)，给最坏情形兜底；节点数回落再转回链表，平均与最坏两头兼顾。