GESP7级C++考试语法知识（四、哈希表（2、哈希函数）

第二课：魔法编号机——哈希函数的秘密

一、上节课的未解之谜

1、上一课里，我们认识了哈希表。

还记得神奇邮箱管理员吗？

小明 → 1号邮箱
小红 → 2号邮箱
小刚 → 3号邮箱

国王只要说：

找小明

管理员立刻打开：

1号邮箱

就找到了。

2、可是聪明的小朋友一定会想到一个问题：

🤔

“小明为什么住1号邮箱？”

“小红为什么住2号邮箱？”

“电脑怎么知道该放哪个邮箱？”

这个问题问得太好了！

今天我们就来揭开：

哈希函数（Hash Function）的秘密

二、魔法编号机登场

1、一天。

程序王国来了100万居民。

管理员慌了。

因为邮箱只有：

1000个

可是居民却有：

100万个

如果人工安排：

小明住1号
小红住2号
小刚住3号
……

那得安排到什么时候？

2、这时智慧大臣搬来一台机器。

机器闪闪发光。

上面写着：

魔法编号机

3、大臣说：

“只要把名字放进去，它就会自动产生邮箱号码！”

国王惊呆了：

“真的吗？”

大臣点点头：

“试试看。”

输入：

Tom

输出：

123

输入：

Jack

输出：

456

输入：

Mike

输出：

789

于是：

Tom → 123号邮箱

Jack → 456号邮箱

Mike → 789号邮箱

全部自动完成！

三、什么是哈希函数？

1、刚才那台魔法编号机。

其实就是：

哈希函数（Hash Function）

2、它的工作只有一件事：

输入一个东西

↓

计算

↓

输出一个编号

3、例如：

名字

↓

哈希函数

↓

邮箱编号

4、可以画成：

Tom
↓
哈希函数
↓
123

5、或者：

Jack
↓
哈希函数
↓
456

6、所以：

哈希函数就是一个“编号生成器”

四、现实中的哈希函数

生活里其实也有类似东西。

1、身份证

每个人都有：

姓名

但是查询时经常使用：

身份证号

2、图书馆

一本书：

《西游记》

对应：

A-102

编号。

3、学校

学生：

张三

对应：

20250101

学号。

这些编号都方便查找。

哈希函数也是同样思想。

五、电脑如何给名字编号？

1、假设：

Tom

电脑不认识字母。

它只认识数字。

怎么办？

2、其实每个字符都有编号。

例如：

'A' = 65

'B' = 66

'C' = 67

小写字母：

'a' = 97

'b' = 98

'c' = 99

例如：

Tom

变成：

T = 84
o = 111
m = 109

于是：

Tom

就能转换成：

84 + 111 + 109

结果：

304

于是：

Tom
↓
304

这就是最简单的哈希思想。

六、为什么还需要取模？

1、现在问题来了。

假设：

Tom → 304

还不错。

但是：

SuperMagicStudent

可能得到：

1947

又来一个：

WonderfulBoy

得到：

3218

邮箱只有：

1000个

怎么办？

难道建：

3218号邮箱？

太浪费了！

于是智慧大臣想出一个办法：

取模

七、什么是取模？

1、还记得：

%

吗？

2、例如：

17 % 5

表示：

17 ÷ 5 的余数

3、计算：

17 = 5×3 + 2

余数：

2

所以：

17 % 5 = 2

八、魔法缩小术

1、智慧大臣说：

“无论数字多大，都压缩到1000以内！”

方法：

hash = x % 1000;

2、例如：

304

变成：

304 % 1000 = 304

3、例如：

1947

变成：

1947 % 1000

结果：

947

4、例如：

3218

变成：

3218 % 1000

结果：

218

5、于是：

Tom → 304号邮箱

SuperMagicStudent → 947号邮箱

WonderfulBoy → 218号邮箱

全部成功放进邮箱。

九、最简单的哈希函数

1、假设有数字：

18
25
39
42
57

2、邮箱数量：

10

3、使用：

hash = x % 10;

4、计算：

18 % 10 = 8

放入：

8号邮箱

25 % 10 = 5

放入：

5号邮箱

39 % 10 = 9

放入：

9号邮箱

42 % 10 = 2

放入：

2号邮箱

5、得到：

数字 邮箱

18 → 8
25 → 5
39 → 9
42 → 2
57 → 7

十、小游戏：你来当哈希管理员

邮箱数量：

10

规则：

hash = x % 10;

第一题

数字：

36

邮箱号是多少？

计算：

36 % 10 = 6

答案：

6号邮箱

第二题

数字：

74

计算：

74 % 10 = 4

答案：

4号邮箱

第三题

数字：

123

计算：

123 % 10 = 3

答案：

3号邮箱

十一、C++中的简单模拟

我们来写一个小程序。

#include <iostream>
using namespace std;

int main()
{
int x;

cin >> x;

int hashValue = x % 10;

cout << "邮箱编号是："
<< hashValue;

return 0;
}

输入：

36

输出：

邮箱编号是：6

输入：

123

输出：

邮箱编号是：3

十二、本课总结

今天我们认识了哈希表背后的魔法机器：

🏆 哈希函数（Hash Function）

它的作用：

输入数据

↓

计算编号

↓

找到邮箱

最简单的哈希函数：

hash = x % m;

其中：

x

表示数据

m

表示邮箱数量

最终得到：

邮箱编号

本课魔法口诀

名字太长不好找，
魔法机器来帮忙。

输入数据算编号，
快速定位效率高。

哈希函数会计算，
邮箱号码马上到。

最简单的一种法：

hash = x % m

下一课我们将进入最精彩的一课：

《撞车事故现场——哈希冲突》

因为同学们马上会发现：

😱

18 % 10 = 8
28 % 10 = 8
38 % 10 = 8

怎么都跑到同一个邮箱去了？

多个居民抢一个邮箱怎么办？

哈希表最大的难题——冲突问题，即将揭晓！🚀