知识点深化 · 数据结构 · 哈希表
哈希表：哈希函数、冲突解决、负载因子
哈希表是以空间换时间的典型：给 key，通过哈希函数算出数组下标，理想情况下增删查改都是 O(1)。它是字典、缓存、索引的底层之王。但 key 会冲突、表会装太满，这一页把哈希函数、拉链法/开放寻址、负载因子与扩容讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：想象把 key 用哈希函数"粉碎"后撒进桶数组。
2记冲突与扩容（15 分钟）
读④：拉链法、开放寻址、负载因子 0.75。
3手算哈希（20 分钟）
精读⑤：手算取模、画拉链、算负载因子。
4刷题纠错（15 分钟）
做⑦⑩，错题回⑥。
本课小目标学完你要能：① 解释哈希表为什么平均 O(1)；② 说清拉链法与线性探测的区别；③ 理解负载因子为何到阈值要扩容。
② 一图看懂：哈希表全地图
读法：中心是哈希表，上半是哈希函数，右是冲突解决，下是负载因子扩容与易错。
③ 本质直觉：把 key 粉碎后均匀撒进桶数组
核心想法：有一个长度为 m 的桶数组。存 key→value 时，用 hash(key) 算出一个 0~m-1 的下标，直接把值塞进那个桶。取的时候再算一次下标，直接定位——不用挨个找，所以 O(1)。
冲突不可避免：抽屉只有 m 个，key 却可能有无数种，两个不同 key 算到同一个下标叫哈希冲突。解决办法：① 拉链法——每个桶挂一条链表（或红黑树），冲突的都挂在同一桶；② 开放寻址——冲突了就往后探测下一个空位。
为什么要扩容：桶装太满，冲突变多，链表变长，O(1) 退化成 O(n)。当元素数 n / 桶数 m = 负载因子 超过阈值（Java HashMap 是 0.75），就把桶扩到 2 倍，把旧元素重新哈希放进去。
好的哈希函数长什么样让 key 尽可能均匀散布到所有桶，避免扎堆。常用：把 key 转成整数后 hash = (h) % m，并用位运算扰动（Java HashMap 高地位异或）。取模用 2 的幂可优化成位与。
④ 完整体系与对比表
两种冲突解决对比
| 对比项 | 拉链法（链地址） | 开放寻址（线性探测） |
|---|
| 冲突后 | 同桶挂链表/树 | 往后找下一个空位 |
| 查找 | 遍历该桶链表 | 按探测序列找 |
| 删除 | 删链表节点即可 | 要打"墓碑"标记，不能直接清 |
| 空间 | 链表额外指针 | 全在数组里，缓存友好 |
| 典型实现 | Java HashMap、Python dict | ThreadLocalMap、Go map 部分 |
负载因子与扩容
负载因子load factor = 元素个数 n / 桶数组长度 m Java HashMap 阈值默认 0.75
超过阈值触发扩容：桶数组翻倍（m→2m），旧表每个元素重新 hash(key)%new_m 放入新桶。扩容是 O(n)，但均摊后插入仍 O(1)。
JDK8 优化：链表长度超过 8 且数组长度 ≥64 时，桶内链表转成红黑树，把最坏查找从 O(n) 降到 O(log n)。
经典用法
① 两数之和
遍历数组，用哈希表存"值→下标"，查 target−x 是否已存在。O(n)。
② 去重
把元素塞 HashSet，重复的自然被合并。
③ 计数
HashMap 存 key→出现次数，一遍扫描统计频率。
④ 缓存
LRU 缓存 = 哈希表 + 双向链表，哈希表定位 O(1)，链表维护顺序。
⑤ 用法场景与典型例题
例1（手算哈希）桶长 m=8，key=15，hash=key%m，落到几号桶？
取模算下标。
15 % 8 = 7。放入下标 7 的桶。若该桶已有元素就拉链挂后面。
例2（负载因子）HashMap 已存 12 个元素，默认阈值 0.75，初始桶长 16，是否需要扩容？
n/m 与 0.75 比。
load = 12/16 = 0.75。达到阈值，需要扩容到 32 并 rehash。（精确触发是 size > capacity×0.75，16×0.75=12，size=12 时下次插入即触发。）
例3（两数之和）数组 [2,7,11,15]，target=9，求两数下标
边查边存。
① 2：查 9−2=7 不在表，存 2→0；② 7：查 9−7=2 在表（下标 0）。答案：下标 [0,1]。一遍 O(n)。
做题心法看到"快速查存在性、计数、配对"第一反应就是哈希表。手算时先写 hash=key%m，冲突就画链。
⑥ 高频错误诊断（4 条）
错误1：以为哈希表一定 O(1)哈希均匀时平均 O(1)；哈希函数差导致全挤一个桶，链表退化成 O(n)。JDK8 转红黑树缓解。
错误2：用可变对象做 keykey 改了字段后 hash 变了，原位置找不到它。务必用不可变对象（String、Integer）做 key。
错误3：扩容时不 rehash桶扩长后旧的 hash%m 下标失效，必须把每个元素按新桶长重新哈希。
错误4：开放寻址删除直接清空会切断后续探测链，应打"墓碑"标记 lazy delete。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| O(1) 原因 | 问平均复杂度来源 | hash 直接定位下标 |
| 冲突解决 | 拉链 vs 开放寻址 | 链表挂桶 / 向后探测 |
| 负载因子 | 问何时扩容 | n/m > 0.75 翻倍 rehash |
| 应用 | 两数之和/去重/计数 | 哈希表 + 一次遍历 |
真题基础1. 哈希表平均时间复杂度最高效的操作是？
真题中档2. Java HashMap 默认负载因子阈值约为？
真题中档3. 哈希冲突用拉链法解决时，同一个桶里挂的是？
真题拔高4. 关于 HashMap 的 key，下列说法正确的是？
⑧ 必背知识点卡
哈希函数：hash(key)%m → 下标 越均匀越好
查找：平均 O(1) 最坏 O(n)/O(log n)
拉链法：同桶挂链表，过长转红黑树 JDK8 阈值 8
开放寻址：冲突向后探测，删除打墓碑
负载因子：n/m，Java 默认 0.75 超了翻倍扩容
扩容：m→2m，旧元素 rehash 均摊 O(1)
应用：两数之和/去重/计数/缓存 一次遍历
⑨ 应用输出：用哈希表统计词频
场景：给定一篇英文文章，统计每个单词出现次数并找出最高频词。
① 选型：单词→次数的映射，用 HashMap。
② 遍历：把文章按空格切分成单词，对每个单词 w：map[w] = map.getOrDefault(w,0)+1。
③ 输出：遍历 map 的 entrySet，打印每个单词和次数。
④ 找最高频：遍历时维护 maxWord 和 maxCount，遇到更大就更新。
⑤ 复杂度：n 个单词 O(n)，空间 O(不同单词数)。
口述思路合上书说："词频统计就是边读边往哈希表里加计数，最后扫一遍找最大。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础2两个不同 key 算到同一下标叫什么？
哈希冲突。
基础3拉链法每个桶里挂的是什么？
链表（过长转红黑树）。
基础4负载因子怎么算？
元素数 n ÷ 桶数 m。
基础5Java HashMap 默认负载因子？
0.75。
基础6扩容时旧元素要做什么？
按新桶长重新哈希 rehash。
▍中档 6 题
中档7桶长 16，key=35 落在几号桶？
35%16=3。
中档8为什么 key 要用不可变对象？
改字段后 hash 变化，原桶找不到该 entry。
中档9拉链法和开放寻址哪个删除更简单？
拉链法，直接摘链表节点；开放寻址要打墓碑。
中档10两数之和为什么 O(n)？
一次遍历，每次查哈希表 O(1)。
中档11JDK8 桶内链表多长才转树？
链表长度 ≥8 且数组长度 ≥64。
中档12哈希函数设计目标是什么？
让 key 均匀分布，减少冲突。
▍拔高 6 题
拔高13负载因子太大/太小各有什么问题？
太大冲突多变慢；太小时桶空太多浪费空间。0.75 是时间空间折衷。
拔高14为什么扩容要选 2 倍？
桶长为 2 的幂时 hash%m 可优化为位与，且 rehash 时节点位置要么不变要么偏移旧容量。
拔高15开放寻址线性探测的缺点？
容易形成"聚集"（primary clustering），探测变长。
拔高16LRU 缓存为什么是哈希表+双向链表？
哈希表 O(1) 定位节点，双向链表 O(1) 移动/删除节点维护最近最少顺序。
拔高17哈希碰撞攻击是什么？
恶意构造大量同 hash 的 key，让表退化成 O(n)，服务变慢。
拔高18为什么说哈希表空间换时间？
用额外桶数组和链表空间，换 O(1) 查找。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① key 哈希算下标，平均 O(1) 真快。② 冲突拉链挂桶上，负载过 .75 翻倍扩。③ 两数之和用哈希，不可变 key 记心间。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画拉链法示意图 | 能讲清 O(1) 来源 |
| 第 2 天 | 背负载因子 + 基础 1-6 | 阈值 0.75 记牢 |
| 第 3 天 | 做中档 7-12，手算 hash%m | 下标算对 |
| 第 4 天 | 做拔高 13-18，理解扩容 rehash | 能讲清 2 倍原因 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写两数之和思路 | 不看资料全默对 |
← 返回软件技术总览