GESP7级C++考试语法知识（四、哈希表（1、认识哈希表）-171主机测评

第一课：神奇邮箱管理员——哈希表是什么？

一、故事开始：国王遇到了大麻烦

1、很久很久以前，在程序王国里，有一座巨大的城市。

城市里住着：

100万名居民

2、国王每天都要处理各种事情：

给小明发奖状
给小红寄礼物
给小刚发通知

可是有一天，国王发现一个严重的问题。

3、国王的烦恼

（1）国王问卫兵：

“快帮我找到小明！”

（2）卫兵开始找：

第1个人？
不是

第2个人？
不是

第3个人？
不是

……

一直找到第500000个人……

终于找到了！

（3）国王气坏了：

“找个人怎么这么慢？”

卫兵无奈地说：

“全国有100万人呀，只能一个一个找。”

二、普通查找为什么慢？

1、假设有这样一个名单：

张三
李四
王五
赵六
小明
小红

（1）现在要找：

小明

（2）最笨的方法：

看看第1个
不是

看看第2个
不是

看看第3个
不是

……

（3）这种方法叫：

顺序查找

就像翻一本没有目录的书。

2、如果人数更多呢？

比如：

1000人
10000人
100万人

查找速度会越来越慢。

因为可能要看很多很多次。

三、智慧大臣发明了神奇邮箱

1、一天，程序王国最聪明的大臣来了。

他说：

“国王，我有办法！”

2、国王高兴极了：

“快说快说！”

3、大臣命令工匠建造：

1000个魔法邮箱

每个邮箱都有编号：

1号
2号
3号
……
1000号

然后规定：

小明住1号邮箱

小明 → 1号邮箱

小红住2号邮箱

小红 → 2号邮箱

小刚住3号邮箱

小刚 → 3号邮箱

4、于是整个系统变成：

名字邮箱

小明 → 1
小红 → 2
小刚 → 3

四、神奇的事情发生了

1、第二天。

国王又问：

“小明在哪里？”

以前：

一个一个找

2、现在：

管理员说：

小明在1号邮箱

直接打开：

1号邮箱

找到了！

3、整个过程：

1秒钟

完成！

4、国王惊呆了：

“这么快？”

智慧大臣笑着说：

“因为我们不再一个一个找了。”

五、这就是哈希表的思想

1、在计算机里。

我们也经常遇到：

名字 → 成绩

学号 → 学生

单词 → 次数

商品编号 → 商品信息

这种：

通过一个东西
快速找到另一个东西

的需求。

于是程序员发明了：

哈希表（Hash Table）

2、哈希表本质上就是：

钥匙(Key) → 宝箱(Value)

（1）例如：

Tom → 95

Jack → 88

Mike → 100

（2）这里：

Tom
Jack
Mike

叫做：

Key（键）

也叫钥匙。

（3）而：

95
88
100

叫做：

Value（值）

也叫宝藏。

六、什么是Key？

1、想象一下。

你有一个藏宝箱。

箱子上写着：

Tom

这个名字就是：

Key

它负责定位宝箱。

2、例如：

Tom → 95

这里：

Tom

是钥匙。

七、什么是Value？

1、宝箱里面装着：

这就是：

Value

2、例如：

Tom → 95

表示：

Tom的成绩是95

八、生活中的哈希表

其实你每天都在使用哈希表思想。

1、电话簿

张三 → 138xxxx

李四 → 139xxxx

2、新华字典

字 → 解释

3、学生管理系统

学号 → 学生

4、QQ好友

QQ号 → 用户

5、这些都是：

Key → Value

结构。

九、C++里的哈希表长什么样？

1、在C++里面。

最常见的哈希表叫：

unordered_map

虽然名字很长。

但其实就是：

神奇邮箱管理员

2、例如：

unordered_map<string,int> score;

表示：

名字 → 分数

存入数据：

score["Tom"] = 95;
score["Jack"] = 88;

查询：

cout << score["Tom"];

输出：

3、程序没有一个一个找。

而是直接找到对应邮箱。

这就是哈希表厉害的地方。

十、小游戏：你来当邮箱管理员

现在有下面的数据：

小明 → 98
小红 → 95
小刚 → 87

问题1

查询：

小红

结果是多少？

答案：

问题2

查询：

小刚

结果是多少？

答案：

问题3

查询：

小明

结果是多少？

答案：

是不是特别像：

打开对应邮箱
拿出里面的东西

？

这就是哈希表。

本课总结

1、今天我们认识了程序王国的新内容：

🏆 哈希表（Hash Table）

2、它的核心思想只有一句话：

通过钥匙(Key)
快速找到值(Value)

记住下面这张图：

Key Value

Tom → 95
Jack → 88
Mike → 100

其中：

Tom、Jack、Mike

是：

Key（键）

而：

95、88、100

是：

Value（值）

3、魔法口诀

同学们一定要背下来：

一个一个找，速度慢；

钥匙开箱，速度快。

名字就是钥匙(Key)；
数据就是宝藏(Value)。

Key找到Value，
这就是哈希表！

下一课，我们将进入：

《魔法编号机——哈希函数的秘密》

揭秘：

🤔 为什么输入“小明”，电脑就知道去哪个邮箱找？

真正的哈希魔法，即将开始！ 🚀

竞赛提高篇：

一、unordered_map与map有何不同

1、unordered_map

是：

哈希表（Hash Table）

内部使用：

哈希函数
+
哈希桶
+
冲突处理

来实现。

2、map

不是哈希表！

它内部使用的是：

红黑树（Red-Black Tree）

一种自平衡二叉搜索树。

我们前面学过：

二叉树
BST（二叉搜索树）
AVL树

那么红黑树也是树家族的一员。

3、所以：

unordered_map → 哈希表

map → 红黑树

二、故事理解

1、假设有一本通讯录：

Tom → 95
Jack → 88
Mike →100

2、map

像什么？

像一本：

📖 按字母顺序排列的字典

Jack
Mike
Tom

一定是有序的。

3、查找时：

利用树结构快速寻找。

类似：

先看中间

再决定往左

还是往右

查找速度：

O(log n)

4、unordered_map

像什么？

像邮局邮箱。

Tom → 123号邮箱
Jack → 456号邮箱
Mike → 789号邮箱

直接定位。

不需要排序。

5、查找速度：

平均

O(1)

几乎瞬间找到。

三、举个例子

1、代码：

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

int main()
{
map<string,int> mp;

mp["Tom"] = 95;
mp["Jack"] = 88;
mp["Mike"] = 100;

for(auto p : mp)
{
cout << p.first
<< " "
<< p.second
<< endl;
}
}

2、输出：

Jack 88
Mike 100
Tom 95

发现了吗？

自动排序了！

因为 map 是红黑树。

天然有序。

四、换成unordered_map

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

int main()
{
unordered_map<string,int> mp;

mp["Tom"] = 95;
mp["Jack"] = 88;
mp["Mike"] = 100;

for(auto p : mp)
{
cout << p.first
<< " "
<< p.second
<< endl;
}
}

1、输出可能是：

Mike 100
Tom 95
Jack 88

2、也可能：

Tom 95
Jack 88
Mike 100

甚至每台电脑都可能不同。

3、因为哈希表：

不保证顺序

五、性能比较

特点mapunordered_map

底层结构	红黑树	哈希表
是否有序	√ 有序	× 无序
插入	O(log n)	平均 O(1)
查找	O(log n)	平均 O(1)
删除	O(log n)	平均 O(1)
遍历	有序	无序

六、为什么unordered_map更快？

1、假设有100万个学生。

找：

小明

2、map

走树：

根节点

↓

左

↓

右

↓

左

↓

找到

3、大约需要：

log₂(1000000)
≈20次比较

4、unordered_map

直接：

小明

↓

哈希函数

↓

34567号桶

↓

找到

5、通常：

1~2次

就找到。

6、所以：

unordered_map 更快

七、什么时候用map？

1、如果题目要求：

按从小到大输出
按字典序输出
维护有序数据
找第一个大于x的元素
找区间元素

2、就必须用：

map

例如：

map<int,int> mp;

遍历时：

for(auto p : mp)

自动从小到大。

八、什么时候用unordered_map？

1、如果题目要求：

统计次数
快速查找
判断是否存在
哈希优化
Two Sum
查重

2、直接上：

unordered_map

3、例如：

统计数字出现次数：

unordered_map<int,int> cnt;

for(int x : a)
{
cnt[x]++;
}

这是竞赛最常见用法。

九、GESP和NOIP中怎么选？

1、汉克老师常说一句口诀：

需要排序找map

只求速度找unordered_map

2、例如：

统计字符数量：

unordered_map<char,int>

优先。

3、例如：

统计后要求：

按照字母顺序输出

就用：

map<char,int>

十、总结

1、把它们想象成两座仓库：

（1）🏢 第一座仓库：map

货物摆放整整齐齐

苹果
香蕉
橘子
葡萄

查找快。

而且有顺序。

（2）🏢 第二座仓库：unordered_map

货物直接扔进对应邮箱

苹果 → 15号桶
香蕉 → 88号桶
葡萄 → 31号桶

没有顺序。

但找得更快。

2、记住这张表：

容器本质

map	红黑树
multimap	红黑树
set	红黑树
multiset	红黑树
unordered_map	哈希表
unordered_set	哈希表

所以：

✅ unordered_map 是哈希表

❌ map 不是哈希表

✅ map 是红黑树实现的有序字典

3、这也是为什么很多算法竞赛题中，看到“统计出现次数”，高手第一反应往往是：

unordered_map<int,int> cnt;

因为它真正利用了哈希表“快速定位”的核心思想。

4、很多同学会觉得：

map

和

unordered_map

用法几乎一样：

mp[x]++;

都能统计次数。

于是就认为：

“那随便用哪个都行吧？”

实际上，在数据量大的时候，两者的速度可能差很多倍！