第6章哈希表

🎯 本章学习目标

通过本章的学习，你将能够：

理解哈希表基本概念：掌握哈希表的核心思想和 O(1) 查找的原理
掌握哈希函数：理解哈希函数的作用和常见设计方法
理解哈希冲突：知道冲突不可避免，理解鸽巢原理
掌握冲突解决方案：熟练掌握链地址法、开放寻址法、再哈希法
理解装填因子：知道装填因子对性能的影响
熟练使用unordered_map：掌握 C++ STL 中的哈希表容器
熟练使用unordered_set：掌握哈希集合的用法和应用场景
区分map和unordered_map：清楚两者底层实现和性能区别
解决经典问题：能解决两数之和、统计次数、去重等经典哈希表应用
应对真题题型：能解决选择、判断、编程等各类哈希表题目

🗺️ 本章知识图谱

哈希表
├── 基本概念
│   ├── 键值对存储
│   ├── 哈希函数：键 → 数组下标
│   ├── 理想查找/插入/删除：O(1)
│   └── 数组 + 哈希函数 = 哈希表
├── 哈希函数
│   ├── 要求
│   │   ├── 计算快
│   │   ├── 分布均匀
│   │   └── 相同键得到相同下标
│   └── 常见方法
│       ├── 直接定址法
│       ├── 除留余数法（最常用）
│       ├── 数字分析法
│       └── 平方取中法
├── 哈希冲突
│   ├── 定义：不同键映射到同一位置
│   ├── 原因：鸽巢原理（键多位置少）
│   └── 不可避免，只能减少和解决
├── 冲突解决方案
│   ├── 链地址法（拉链法）
│   │   ├── 同一位置用链表串联
│   │   ├── 优点：空间灵活
│   │   └── 缺点：缓存不友好
│   ├── 开放寻址法
│   │   ├── 线性探测
│   │   ├── 二次探测
│   │   └── 双重哈希
│   └── 再哈希法
│       ├── 多个哈希函数
│       └── 第一个冲突用第二个
├── 装填因子
│   ├── α = 元素数 / 表长
│   ├── α 越大，冲突越多
│   └── 超过阈值要扩容（rehash）
├── C++ STL
│   ├── unordered_map
│   │   ├── 键值对
│   │   ├── 底层：哈希表
│   │   └── 平均 O(1)
│   └── unordered_set
│       ├── 只有键（去重）
│       ├── 底层：哈希表
│       └── 平均 O(1)
├── vs map/set
│   ├── map/set 底层是红黑树
│   ├── map/set 有序
│   ├── map/set O(log n)
│   └── unordered 无序但更快
└── 经典应用
    ├── Two Sum 两数之和
    ├── 统计次数（计数）
    ├── 去重
    └── 查找/存在性判断

一、📖 哈希表基本概念

1.1 什么是哈希表？

哈希表（Hash Table），也叫散列表，是一种根据键（Key）直接访问内存存储位置的数据结构。

核心思想只有一句话：

通过哈希函数，把 Key 映射成数组下标，从而实现 O(1) 级别的查找。

打个比方：查字典时，你可以一页页翻（O(n)），也可以按拼音直接翻到对应页码（接近 O(1)）。哈希表做的就是后者。

1.2 为什么需要哈希表？

假设要存 100 个学生的成绩，学号是 1~100，直接开数组 score[101] 就行。但如果学号是 20240101、20240999 这种大数字呢？直接开数组会爆内存。

哈希函数的作用就是把大范围的 Key 压缩到小范围的数组下标：

Index = Hash(Key)

这样无论学号多大，都映射到一个固定大小的数组里，既省空间又快。

二、🔧 哈希函数设计方法

哈希函数是把 Key 转换成数组下标的函数。好的哈希函数要满足：计算简单、分布均匀。

方法	公式	特点	适用场景
直接定址法	H(key) = a×key + b	简单，不产生冲突	Key 分布连续
除留余数法	H(key) = key % p	最常用，p 取质数	通用场景
数字分析法	取 Key 中分布均匀的若干位	需已知 Key 分布规律	已知数据特征
平方取中法	取 key² 的中间几位	分布较均匀	Key 位数较少
折叠法	Key 分段后叠加	处理长 Key	Key 位数很多

⚠️ 高频考点：除留余数法中，p 通常取不大于表长 m 的最大质数，这样能减少冲突。

代码示例：除留余数法

cpp

int hashFunc(int key, int p) {
    return key % p;  // p 为质数，通常 p <= 表长 m
}

// 示例：表长 11，p = 11
// H(22) = 22 % 11 = 0
// H(33) = 33 % 11 = 0  ← 与 22 冲突！
// H(4)  = 4 % 11  = 4

三、💥 哈希冲突：不可避免的"宿命"

3.1 什么是冲突？

当两个不同的 Key 经过哈希函数计算后得到相同的地址，就叫哈希冲突：

Key1 ≠ Key2，但 H(Key1) = H(Key2)

这两个 Key 互称为同义词。

3.2 为什么会产生冲突？

根本原因：数组空间有限，而 Key 的取值范围可能无限大。

根据鸽巢原理（抽屉原理）：如果哈希表有 m 个槽位，插入超过 m 个元素时，必然会有冲突。任何哈希函数都无法完全消除冲突，只能尽量减少。

📌 真题考法（2025年6月判断题）："哈希表的槽位有限，元素足够多时必然冲突（鸽巢原理），任何解决方法仅能缓解。" —— 正确 ✅

四、🛡️ 冲突解决方案详解

冲突不可消除，但必须处理。需要掌握以下四大类冲突解决方案，其中开放寻址法又细分为三种探测策略：

4.1 开放寻址法（Open Addressing）

冲突时，在哈希表内按某种规则寻找下一个空位。

通用公式：H_i = (H(key) + d_i) % m

① 线性探测法

d_i = 1, 2, 3, ...（依次往后找）

cpp

// 线性探测插入
int insert(int key) {
    int h = key % M;       // 初始哈希地址
    int i = 0;
    while (table[(h + i) % M] != EMPTY && i < M) {
        i++;                // 冲突就往后走一步
    }
    if (i < M) {
        table[(h + i) % M] = key;
        return (h + i) % M;
    }
    return -1;  // 表满
}

模拟示例（真题高频题型）：

哈希函数 h(x) = x % 11，表长 11，依次插入 {22, 33, 4, 15, 26}：

步骤	插入元素	h(x)	冲突？	最终位置
1	22	22%11=0	无	0
2	33	33%11=0	是→探测1	1
3	4	4%11=4	无	4
4	15	15%11=4	是→探测5	5
5	26	26%11=4	是→4,5均占→探测6	6

⚠️ 缺点：容易产生**聚集（Clustering）**现象——冲突的元素挤成一团，后续插入的元素更易冲突。

② 二次探测法

d_i = 1², -1², 2², -2², 3², -3², ...（跳着找）（注意：正负顺序不影响正确性）

cpp

// 二次探测
int probe(int h, int i, int m) {
    int offset = (i + 1) / 2;  // 1,1,2,2,3,3...
    int sign = (i % 2 == 0) ? 1 : -1;
    return ((h + sign * offset * offset) % m + m) % m;
}

优点：跳跃式探测，有效缓解聚集。缺点：不一定能探测到所有位置（最多探测 m/2 个）。

③ 双重哈希法

使用第二个哈希函数计算步长：

H_i = (H₁(key) + i × H₂(key)) % m

cpp

int h1 = key % M;
int h2 = 1 + (key % (M - 1));  // 第二个哈希函数，注意不能为0

int probe(int i) {
    return (h1 + i * h2) % M;
}

优点：三种开放寻址法中分布最均匀、最不易聚集。

📌 考法提醒：三种探测法对比是选择题常考点——线性探测能找遍全表但有聚集；二次探测和双重哈希无聚集但不一定能遍历全表。

4.2 链地址法（拉链法 / Chaining）

每个槽位挂一个链表，冲突元素直接挂到链表尾部。

cpp

#include <vector>
using namespace std;

const int M = 11;
vector<int> table[M];  // 每个槽位是一个 vector（当链表用）

void insert(int key) {
    int h = key % M;
    table[h].push_back(key);
}

bool find(int key) {
    int h = key % M;
    for (int x : table[h]) {
        if (x == key) return true;
    }
    return false;
}

结构示意：

槽位 0 → [22] → [33] → NULL
槽位 1 → NULL
槽位 4 → [4] → [15] → [26] → NULL
槽位 5 → NULL
...

⚠️ 真题考法（2026年6月第12题）："使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 O(n)。" —— 正确 ✅

4.3 再哈希法（Rehashing）

准备多个哈希函数，第一个冲突就用第二个，再冲突就用第三个……

H₁(key) → 冲突 → H₂(key) → 冲突 → H₃(key) → ...

cpp

int hash1(int key) { return key % M; }
int hash2(int key) { return 1 + key % (M - 1); }
int hash3(int key) { return (key * 31 + 7) % M; }

int insert(int key) {
    if (table[hash1(key)] == EMPTY) return hash1(key);
    if (table[hash2(key)] == EMPTY) return hash2(key);
    if (table[hash3(key)] == EMPTY) return hash3(key);
    // ...
}

优点：不易产生聚集。缺点：增加了计算开销，且多个哈希函数设计困难。

4.4 建立公共溢出区

另设一个溢出表，冲突的元素统一存入溢出区。

主表:  [0]=22  [1]=___  [2]=___  [3]=___  [4]=4  ...
溢出表: [0]=33  [1]=15  [2]=26  ...

查找时先查主表，没找到再去溢出区线性查找。

优点：实现简单。缺点：溢出区可能变长，查找效率下降。

五、📊 四种冲突解决方案优缺点对比

方案	优点	缺点	装填因子限制	适用场景
线性探测	实现简单，能遍历全表	产生聚集（Clustering）	α < 1	数据量小、冲突少
二次探测	缓解聚集	不一定能探测所有位置	α < 1	中等装填因子
双重哈希	分布最均匀，几乎无聚集	计算稍复杂	α < 1	对性能要求高
链地址法	无聚集，删除简单，α 可 ≥1	需额外指针空间	无限制	最通用，C++ STL 采用
再哈希法	不易聚集	多哈希函数设计困难	α < 1	关键字分布已知
公共溢出区	实现最简单	溢出区可能很长	无限制	冲突极少的情况

🚨 最高频易错点（2025年6月真题第9题）：
"用新元素覆盖旧元素"不是合法的冲突解决方法！ 这会导致数据丢失，破坏数据完整性。
合法的方案包括：链地址法（子哈希表/二叉排序树）、再哈希法等，但不能覆盖。

六、⚖️ 装填因子（负载因子）

定义

α = n / m（n 为表中记录数，m 为哈希表长度）

核心影响

α 值	含义	冲突概率	查找效率
小（如 0.3）	表很空	低	快
大（如 0.9）	表很满	高	慢
= 1	表满	极高	开放寻址法无法插入

关键结论：

α 越大，冲突概率越高——这是最常考的判断点
开放寻址法要求 α < 1（表不能满）
链地址法 α 可以 ≥ 1（链表可以无限长）

📌 真题考法（2026年3月第5题）："装载因子越大，发生冲突的概率通常越高" —— 正确 ✅

📌 真题考法："开放定址法在删除元素时实现相对复杂" —— 正确 ✅（需要特殊标记"已删除"，不能直接清空，否则会断开探测链）

七、💻 C++ 中的哈希表：unordered_map / unordered_set

C++11 引入了基于哈希表实现的容器，考试中可以直接使用。

7.1 unordered_map 基本用法

💻 编译器提示：下文遍历 map 时用的 for (auto& [k, v] : mp) 是 C++17 结构化绑定。旧版 Dev-C++（TDM-GCC 4.9.2）报错时，改写为 C++11 形式即可： for (auto& p : mp) cout << p.first << ":" << p.second;

cpp

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, int> score;
    
    // 插入 / 修改
    score["Alice"] = 95;
    score["Bob"] = 87;
    score["Alice"] = 98;  // 覆盖
    
    // 查找
    if (score.count("Bob")) {
        cout << "Bob: " << score["Bob"] << endl;  // 输出 87
    }
    
    // 遍历
    for (auto& [name, s] : score) {
        cout << name << " -> " << s << endl;
    }
    
    // 删除
    score.erase("Bob");
    
    // 统计元素个数
    cout << "共 " << score.size() << " 人" << endl;
    
    return 0;
}

7.2 unordered_set 基本用法

cpp

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<int> s;
    
    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(1);  // 重复插入无效，set 中仍只有一个 1
    
    // 判断是否存在
    cout << s.count(1) << endl;  // 输出 1（存在）
    cout << s.count(2) << endl;  // 输出 0（不存在）
    
    // 不同元素个数
    cout << "不同元素个数: " << s.size() << endl;  // 输出 3
    
    return 0;
}

7.3 何时用哪个？

题目特征	选择
统计次数、键值映射	`unordered_map`
判断是否存在、查重	`unordered_set`
统计不同元素个数	`unordered_set`
学号 → 姓名	`unordered_map`

八、⚔️ unordered_map vs map：核心区别

这是判断题和选择题的高频考点：

特性	`std::map` / `std::set`	`std::unordered_map` / `std::unordered_set`
底层实现	红黑树（平衡二叉搜索树）	哈希表
查找/插入/删除（平均）	O(log n)	O(1)
查找/插入/删除（最坏）	O(log n)	O(n)
元素是否有序	✅ 按 Key 排序	❌ 无序
是否需要比较函数	需要 `<` 运算符	需要哈希函数 `hash<Key>`
内存占用	较少	较多（需要额外桶空间）

记忆口诀 🧠

map 有序 log n，unordered 无序但 O(1)
要排序选 map，要速度选 unordered

cpp

#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;

int main() {
    // map：按 key 排序
    map<int, string> m;
    m[3] = "C";
    m[1] = "A";
    m[2] = "B";
    for (auto& [k, v] : m) cout << k << ":" << v << " ";  // 1:A 2:B 3:C
    
    cout << endl;
    
    // unordered_map：无序
    unordered_map<int, string> um;
    um[3] = "C";
    um[1] = "A";
    um[2] = "B";
    for (auto& [k, v] : um) cout << k << ":" << v << " ";  // 顺序不确定
    
    return 0;
}

九、🧩 哈希表经典应用：Two Sum

cpp

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

// 给定数组和目标值，找两个数使和等于目标值
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;  // 值 → 下标
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (mp.count(complement)) {
            return {mp[complement], i};
        }
        mp[nums[i]] = i;
    }
    return {};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    auto res = twoSum(nums, target);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl;  // [0, 1]
    return 0;
}

十、📝 高频易错点汇总

#	易错点	正确理解
1	"覆盖旧元素"能解决冲突	❌ 不合法！会导致数据丢失
2	好的哈希函数能完全避免冲突	❌ 只能减少，不能消除（鸽巢原理）
3	unordered_map 最坏也是 O(1)	❌ 最坏 O(n)，平均才是 O(1)
4	链地址法装填因子必须 <1	❌ 可以 ≥1，链表可无限增长
5	开放寻址法删除直接清空即可	❌ 需标记"已删除"，否则断开探测链
6	map 和 unordered_map 底层一样	❌ map 是红黑树，unordered_map 是哈希表
7	二次探测能找遍全表	❌ 最多探测 m/2 个位置
8	线性探测没有缺点	❌ 产生聚集（Primary Clustering）

哈希表考试口诀：

除留余数取质数，冲突难免别发愁
线性探测易聚集，二次跳跃不遍求
双重哈希最均匀，链地址法 α 自由
覆盖旧元是陷阱，鸽巢原理记心头
map 有序 log n，unordered 无序 O(1) 均

十一、📝 实战练习

练习题 1（单选题）

题目： 有一个长度为 11 的哈希表，哈希函数为 h(x) = x % 11，采用线性探测法解决冲突。依次插入关键字 {22, 33, 4, 15, 26}，则关键字 26 最终存储在哪个地址？

A. 4
B. 5
C. 6
D. 7

🔑 点击查看答案与解析

答案： C

逐步模拟：

插入	h(x)	过程	最终位置
22	0	无冲突	0
33	0	冲突→探测1（空）	1
4	4	无冲突	4
15	4	冲突→探测5（空）	5
26	4	冲突→4占→5占→探测6（空）	6

练习题 2（单选题）

题目： 关于哈希表的冲突解决方法，下列说法中错误的是：

A. 链地址法可以在每个槽位维护一个链表来处理冲突
B. 发生冲突后，该槽位就不能再插入新的元素了
C. 无论哈希函数设计得多好，冲突仍有可能发生
D. 开放定址法中，查找时必须沿着探测序列继续查找，直到找到目标或遇到空位

🔑 点击查看答案与解析

答案： B

A 正确：链地址法的核心就是在每个槽位挂链表
B 错误：发生冲突后当然可以继续插入——链地址法把新元素挂到链表尾部；开放寻址法找下一个空位。冲突不代表不能再插入
C 正确：鸽巢原理，冲突不可避免
D 正确：开放定址法查找必须沿探测序列走完，遇到空位才确定查找失败

练习题 3（判断题）

题目： 使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 O(1)。

🔑 点击查看答案与解析

答案： 错误 ❌

当所有元素都映射到同一个槽位时，链表退化为长度为 n 的单链表，查找需要遍历整个链表，最坏时间复杂度为 O(n)，而非 O(1)。

哈希表的 O(1) 是平均情况下的时间复杂度，前提是哈希函数分布均匀。最坏情况下，所有元素挤在一个槽位，性能退化到 O(n)。

练习题 4（单选题）

题目： 哈希表的装填因子 α 是指？（）

A. 哈希函数的个数
B. 表中元素数 / 表的长度
C. 冲突的次数 / 总插入次数
D. 表的长度 / 表中元素数

🔑 点击查看答案与解析

答案： B

解析： 装填因子（负载因子）α = 表中元素个数 / 哈希表的长度

α 越小，冲突越少，查找越快，但空间浪费越多
α 越大，冲突越多，查找越慢，空间利用率越高

通常当 α 超过某个阈值（如 0.75）时，哈希表会扩容（rehash），把表长扩大，重新计算所有元素的位置。

选 B。

🍎 生活比喻：装填因子就像教室的上座率。人太少（α小）浪费空间，人太多（α大）又太挤影响效率。

---

练习题 5（判断题）

题目： 链地址法（拉链法）解决哈希冲突的方式是：把哈希到同一个位置的元素用链表串联起来。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 链地址法（也叫拉链法）的基本思想：

哈希表的每个位置都是一个链表的头节点
当发生冲突时，把新元素插入到对应位置的链表中
查找时，先算哈希值找到位置，再遍历链表查找

优点：

空间灵活，不会因为元素多而装不下
删除操作简单（直接删链表节点）

缺点：

链表节点分散存储，缓存命中率低
需要额外的指针空间

🔥 高频考点：链地址法是最常用的冲突解决方案，也是考试重点。

---

练习题 6（单选题）

题目： 关于 C++ 中 unordered_map 和 map 的区别，下列说法错误的是？（）

A. unordered_map 底层是哈希表，map 底层是红黑树
B. unordered_map 平均时间复杂度 O(1)，map 是 O(log n)
C. unordered_map 的元素是有序的，map 的元素是无序的
D. unordered_map 和 map 都是键值对存储

🔑 点击查看答案与解析

答案： C

解析：

特性	unordered_map	map
底层实现	哈希表	红黑树
元素顺序	无序	有序（按key排序）
平均查找	O(1)	O(log n)
最坏查找	O(n)	O(log n)
空间	略大	略小

选项 C 说反了：unordered_map 是无序的，map 是有序的。

选 C。

💡 记忆：名字里有 "ordered" 的反而是无序的（un-ordered = 不排序），map 虽然没说但默认是有序的（红黑树保证）。

---

练习题 7（单选题）

题目： 采用线性探测法解决冲突时，可能会出现"二次聚集"问题，这是指？（）

A. 哈希函数计算太慢
B. 冲突的元素越来越多地聚集在一起
C. 表的长度不够用
D. 链表太长

🔑 点击查看答案与解析

答案： B

解析： 线性探测：冲突时，依次找下一个空位（+1, +2, +3...）。

二次聚集（也叫堆积）：因为大家都线性往下找，冲突的元素会越来越多地"挤在一起"，形成一片连续的占用区域，导致后续的插入和查找越来越慢。

比如：位置 5 冲突了，去占 6；后面一个哈希到 6 的元素，又得去占 7……这样冲突越来越多，像滚雪球一样。

二次探测（+1², -1², +2², -2²...）可以缓解这个问题。

选 B。

🍎 生活比喻：就像排队买奶茶，第一个人队伍变长了，后面来的人只能排在更后面，队伍越来越长。

---

练习题 8（编程题）

题目： 给定一个整数数组和一个目标值 target，找出数组中和为 target 的两个数的下标。

输入：第一行 n 和 target，第二行 n 个整数
输出：两个下标（空格分隔，按出现顺序），保证有且仅有一组解

样例输入：

4 9
2 7 11 15

样例输出：

0 1

🔑 点击查看答案与解析

答案： 参考代码（哈希表 O(n) 解法）：

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    unordered_map<int, int> mp;  // 值 → 下标
    for (int i = 0; i < n; i++) {
        int complement = target - nums[i];
        if (mp.count(complement)) {  // 找到了
            cout << mp[complement] << " " << i << endl;
            return 0;
        }
        mp[nums[i]] = i;  // 没找到，把当前数存入哈希表
    }
    
    return 0;
}

解析： 经典的 Two Sum 问题，哈希表解法时间复杂度 O(n)：

遍历数组，对每个数 nums[i]
计算 complement = target - nums[i]（需要找的"另一半"）
如果 complement 在哈希表里 → 找到了，输出下标
否则把 nums[i] 和它的下标存入哈希表

暴力解法是 O(n²) 双重循环，哈希表优化到 O(n)，这就是哈希表的威力！

💡 关键思想：用空间换时间。把已经看过的数存起来，后面的数直接查表找"另一半"。

---

十二、📊 考点总结表

考点	重要程度	出题形式	易错点
哈希表基本概念	⭐⭐⭐⭐	选择/判断	理想O(1)，最坏O(n)
哈希函数	⭐⭐⭐⭐	选择/判断	除留余数法最常用
哈希冲突必然性	⭐⭐⭐⭐⭐	选择/判断	鸽巢原理，不可避免
链地址法	⭐⭐⭐⭐⭐	选择/判断/编程	同一位置链表串联
开放寻址法（线性探测）	⭐⭐⭐⭐⭐	选择/计算	二次聚集问题
再哈希法	⭐⭐⭐	选择/判断	多个哈希函数
装填因子	⭐⭐⭐⭐	选择/判断	α=元素数/表长
unordered_map/set	⭐⭐⭐⭐⭐	编程题/选择	底层哈希表，无序
map vs unordered_map	⭐⭐⭐⭐⭐	选择/判断	红黑树vs哈希表，有序vs无序
Two Sum 经典应用	⭐⭐⭐⭐⭐	编程题	哈希表存已遍历元素
统计次数/去重	⭐⭐⭐⭐	编程题	unordered_map计数/set去重
开放寻址删除	⭐⭐⭐	选择/判断	不能直接删，要标记墓碑

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│         哈希表 · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. 哈希表 = 数组 + 哈希函数                │
│  2. 理想时间复杂度：查找/插入/删除都是O(1)   │
│  3. 哈希冲突不可避免（鸽巢原理）             │
│  4. 链地址法：同一位置用链表串联             │
│  5. 开放寻址法：冲突时找下一个空位           │
│  6. 线性探测会产生二次聚集（堆积）           │
│  7. 二次探测可以缓解聚集问题                 │
│  8. 再哈希法：多个哈希函数换着用             │
│  9. 装填因子α = 元素数 / 表长               │
│ 10. α越大冲突越多，超过阈值要扩容            │
│ 11. unordered_map底层是哈希表，无序         │
│ 12. map底层是红黑树，有序，O(log n)         │
│ 13. unordered_set用于去重和存在性判断       │
│ 14. Two Sum：遍历+哈希表存已遍历元素        │
│ 15. 哈希表思想：空间换时间                   │
└─────────────────────────────────────────────┘

十三、🎯 备考策略总结

选择题重点：冲突解决方案辨析（哪种合法/不合法）、线性探测模拟、装填因子概念
判断题重点：冲突必然性（鸽巢原理）、时间复杂度（平均 O(1) vs 最坏 O(n)）、删除操作复杂度
编程题准备：熟练使用 unordered_map 和 unordered_set，掌握统计次数、查重、Two Sum 等经典模板
易错提醒：覆盖旧元素 ≠ 解决冲突；二次探测不能遍历全表；开放寻址法删除需标记

第6章 哈希表 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📖 哈希表基本概念 ​

1.1 什么是哈希表？ ​

1.2 为什么需要哈希表？ ​

二、🔧 哈希函数设计方法 ​

代码示例：除留余数法 ​

三、💥 哈希冲突：不可避免的"宿命" ​

3.1 什么是冲突？ ​

3.2 为什么会产生冲突？ ​

四、🛡️ 冲突解决方案详解 ​

4.1 开放寻址法（Open Addressing） ​

① 线性探测法 ​

② 二次探测法 ​

③ 双重哈希法 ​

4.2 链地址法（拉链法 / Chaining） ​

4.3 再哈希法（Rehashing） ​

4.4 建立公共溢出区 ​

五、📊 四种冲突解决方案优缺点对比 ​

六、⚖️ 装填因子（负载因子） ​

定义 ​

核心影响 ​

七、💻 C++ 中的哈希表：unordered_map / unordered_set ​

7.1 unordered_map 基本用法 ​

7.2 unordered_set 基本用法 ​

7.3 何时用哪个？ ​

八、⚔️ unordered_map vs map：核心区别 ​

记忆口诀 🧠 ​

九、🧩 哈希表经典应用：Two Sum ​

十、📝 高频易错点汇总 ​

十一、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（判断题） ​

练习题 4（单选题） ​

练习题 5（判断题） ​

练习题 6（单选题） ​

练习题 7（单选题） ​

练习题 8（编程题） ​

十二、📊 考点总结表 ​

⭐ 必背速记卡 ​

十三、🎯 备考策略总结 ​

第6章哈希表

🎯 本章学习目标

🗺️ 本章知识图谱

一、📖 哈希表基本概念

1.1 什么是哈希表？

1.2 为什么需要哈希表？

二、🔧 哈希函数设计方法

代码示例：除留余数法

三、💥 哈希冲突：不可避免的"宿命"

3.1 什么是冲突？

3.2 为什么会产生冲突？

四、🛡️ 冲突解决方案详解

4.1 开放寻址法（Open Addressing）

① 线性探测法

② 二次探测法

③ 双重哈希法

4.2 链地址法（拉链法 / Chaining）

4.3 再哈希法（Rehashing）

4.4 建立公共溢出区

五、📊 四种冲突解决方案优缺点对比

六、⚖️ 装填因子（负载因子）

定义

核心影响

七、💻 C++ 中的哈希表：unordered_map / unordered_set

7.1 unordered_map 基本用法

7.2 unordered_set 基本用法

7.3 何时用哪个？

八、⚔️ unordered_map vs map：核心区别

记忆口诀 🧠

九、🧩 哈希表经典应用：Two Sum

十、📝 高频易错点汇总

十一、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（判断题）

练习题 4（单选题）

练习题 5（判断题）

练习题 6（单选题）

练习题 7（单选题）

练习题 8（编程题）

十二、📊 考点总结表

⭐ 必背速记卡

十三、🎯 备考策略总结