哈希表

CIE A-Level 计算机科学· 第10单元：数据类型与结构· 15 分钟阅读

1. 哈希表与哈希函数★★☆☆☆⏱ 4 min

哈希表存储键值对，使用特殊的哈希函数将每个输入键映射到底层数组的一个索引。该索引直接指示我们存储对应值的位置，因此可以实现非常快速的访问。

📘 定义

哈希函数

$h (k)$

接收输入键（字符串或数字），将其转换为固定大小的数值哈希值，用作哈希表数组索引的函数。

例:

对于大小为10的哈希表， $h (k) = k mod 10$

📐 例题

使用 $h (k) = k mod 10$ ，计算大小为10的哈希表中，键 [12, 25, 31, 48, 52] 对应的哈希索引。

1
计算12的哈希值： $12 mod 10 = 2$
2
计算25的哈希值： $25 mod 10 = 5$
3
计算31的哈希值： $31 mod 10 = 1$
4
计算48的哈希值： $48 mod 10 = 8$
5
计算52的哈希值： $52 mod 10 = 2$
6
此时发生了冲突：两个键（12和52）哈希得到相同的索引2。我们会在后续章节讲解如何解决这个冲突。

2. 冲突解决：拉链法★★☆☆☆⏱ 3 min

当两个不同的键哈希得到同一个索引时就会发生冲突。拉链法是最简单的冲突解决方法，每个数组槽存储所有哈希到该索引的键的动态集合。

📘 定义

拉链法

一种冲突解决方法，哈希表数组的每个索引存储所有哈希到该索引的键的链表（或其他动态结构）。

📐 例题

使用拉链法解决上例中索引2处12和52的冲突，哈希表大小为10。

1
每个数组元素作为链表的头节点。插入12后，索引2处的链表为 [12]。
2
插入同样哈希到索引2的52时，将52添加到索引2处链表的末尾。
3
查找52时：先哈希得到索引2，然后遍历链表直到找到52。
4
索引2的最终状态：头节点 → 12 → 52 → 空

3. 冲突解决：开放定址法（线性探测）★★★☆☆⏱ 5 min

开放定址法是另一种冲突解决方法，所有键都直接存储在主哈希表数组中。如果发生冲突，你需要探测（查找）下一个可用的空槽来存储新键。CIE考试最常考查线性探测。

📘 定义

线性探测

一种开放定址法，如果哈希索引 $h$ 处发生冲突，你需要依次检查 $h + 1, h + 2, ...$ 槽（必要时绕回数组开头）直到找到空槽。

📐 例题

使用 $h (k) = k mod 10$ 和线性探测，将键 [12, 25, 31, 48, 52] 插入大小为10的哈希表。

1
插入12：h=2，槽2为空 → 将12存储在索引2
2
插入25：h=5，槽5为空 → 将25存储在索引5
3
插入31：h=1，槽1为空 → 将31存储在索引1
4
插入48：h=8，槽8为空 → 将48存储在索引8
5
插入52：h=2，槽2已满 → 检查下一个槽3，槽3为空 → 将52存储在索引3
6
哈希表最终状态：[空, 31, 12, 52, 空, 25, 空, 空, 48, 空]

4. 性能与负载因子★★★☆☆⏱ 3 min

哈希表的性能取决于它的负载因子，负载因子衡量哈希表的填充程度。当负载因子超过阈值时，哈希表会被调整大小（重哈希）以保持良好性能。

📘 定义

负载因子

$λ$

已存储条目数与哈希表数组总大小的比值： $λ = \frac{已存储条目数}{哈希表大小}$

典型阈值为：拉链法0.7，开放定址法0.5。查找、插入和删除的平均时间复杂度为O(1)，当所有键都哈希到同一个索引时，最坏时间复杂度为O(n)。

📐 例题

上述线性探测例子中，大小为10的数组中有5个条目，负载因子是多少？如果开放定址法的阈值是0.5，是否需要调整大小？

1
将数值代入负载因子公式：
2
$\lambda = \frac{5}{10} = 0.5$
3
如果阈值是0.5，当负载因子大于等于阈值时就会触发重调大小，因此需要执行重调大小。
4
重调大小为大小20的新数组后，新的负载因子是 $\frac{5}{20} = 0.25$

5. 常见陷阱

错误做法:

线性探测到达数组末尾后，忘记绕回数组开头继续查找

原因:

很多考生到达数组末尾后就停止查找空槽，即使数组开头还有空槽

正确做法:

到达数组末尾后，一定要从索引0开始继续查找，直到找到空槽或确认哈希表已满

错误做法:

混淆拉链法和开放定址法，认为拉链法中所有键都直接存储在主数组中

原因:

混淆了两种冲突解决方法的核心结构

正确做法:

拉链法在每个数组槽中使用链表，开放定址法将所有键直接存储在主数组中

错误做法:

将负载因子计算为（冲突数）/（表大小）

原因:

记错了负载因子的定义

正确做法:

负载因子始终是哈希表已填充的比例：（已存储条目数）/（总表大小）

错误做法:

认为哈希表操作的时间复杂度始终是O(1)

原因:

混淆了平均复杂度和最坏复杂度

正确做法:

哈希表操作的平均时间复杂度是O(1)，但如果所有键都哈希到同一个索引，最坏时间复杂度是O(n)

错误做法:

线性探测查找时遇到非目标键就停止

原因:

误解了开放定址法的查找原理

正确做法:

继续连续查找槽，直到找到目标键或遇到空槽（说明键不存在）

6. 速查表

概念	核心要点
哈希函数	将键映射为数组索引
冲突	两个键哈希得到同一个索引
拉链法	每个槽存储条目的链表
线性探测	检查下一个空槽，必要时绕回
负载因子	条目数 ÷ 表大小，阈值0.5-0.7
重哈希	负载因子超过阈值时调整表大小
平均时间复杂度	查找/插入/删除 = O(1)
最坏时间复杂度	查找/插入/删除 = O(n)

7. 常见问题

考试中我需要自己编写哈希函数吗？

不需要，考试几乎总会给出哈希函数让你应用。你只需要用它计算索引并解决冲突即可。

哈希表的平均性能和最坏性能有什么区别？

使用良好的哈希函数时，所有操作的平均时间复杂度为O(1)。当所有键都哈希到同一个索引时，最坏时间复杂度为O(n)。

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 12
拉链法冲突解决
2023 · 11
线性探测插入问题
2021 · 13
负载因子计算

深入阅读

syllabusCIE 9618 官方大纲查看第32页获取第10单元内容

下一步

哈希表是CIE A-Level计算机科学中经常考查的核心数据结构，会出现在试卷1的数据结构题和试卷2的解题任务中。它在实际应用中被广泛用于数据库索引、缓存，以及实现哈希集合和字典。掌握哈希和冲突解决的原理，为理解更复杂的数据结构打下坚实基础。学完本主题后，你可以继续学习其他基于数组和动态存储知识的常用数据结构。