# 哈希表

> CIE A-Level 计算机科学 · 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-hash-tables/

哈希表是一种基于数组的高性能数据结构，支持键值数据的平均O(1)查找、插入和删除操作。本指南讲解哈希、冲突解决、性能以及常见考试要求。

**先修:** [数组](https://www.owlsprep.com/zh/study/cie-9618-u10-arrays/); [时间复杂度](https://www.owlsprep.com/zh/study/cie-9618-u08-time-complexity/)

## 学习目标

- 解释哈希表和哈希函数的结构与作用
- 描述并应用常用的冲突解决技术
- 计算负载因子，理解哈希表的性能
- 识别哈希表操作中的常见误区

## 哈希表与哈希函数

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

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

*记法:* $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处12和52的冲突，哈希表大小为10。

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

> **tip**
>
> 在CIE考试中，你可以将拉链法画为每个数组单元指向一个共享该索引的键的垂直列表。

## 冲突解决：开放定址法（线性探测）

开放定址法是另一种冲突解决方法，所有键都直接存储在主哈希表数组中。如果发生冲突，你需要探测（查找）下一个可用的空槽来存储新键。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, 空]

> **warning**
>
> 主聚集是线性探测的一个主要缺点：已填充的连续槽会吸引更多冲突，增加平均查找时间。

## 性能与负载因子

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

**负载因子** — 已存储条目数与哈希表数组总大小的比值：$\lambda = \frac{\text{已存储条目数}}{\text{哈希表大小}}$

*记法:* $\lambda$

典型阈值为：拉链法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$

## 常见错误

- **错误做法:** 线性探测到达数组末尾后，忘记绕回数组开头继续查找
  - 原因: 很多考生到达数组末尾后就停止查找空槽，即使数组开头还有空槽
  - 正确做法: 到达数组末尾后，一定要从索引0开始继续查找，直到找到空槽或确认哈希表已满
- **错误做法:** 混淆拉链法和开放定址法，认为拉链法中所有键都直接存储在主数组中
  - 原因: 混淆了两种冲突解决方法的核心结构
  - 正确做法: 拉链法在每个数组槽中使用链表，开放定址法将所有键直接存储在主数组中
- **错误做法:** 将负载因子计算为（冲突数）/（表大小）
  - 原因: 记错了负载因子的定义
  - 正确做法: 负载因子始终是哈希表已填充的比例：（已存储条目数）/（总表大小）
- **错误做法:** 认为哈希表操作的时间复杂度始终是O(1)
  - 原因: 混淆了平均复杂度和最坏复杂度
  - 正确做法: 哈希表操作的平均时间复杂度是O(1)，但如果所有键都哈希到同一个索引，最坏时间复杂度是O(n)
- **错误做法:** 线性探测查找时遇到非目标键就停止
  - 原因: 误解了开放定址法的查找原理
  - 正确做法: 继续连续查找槽，直到找到目标键或遇到空槽（说明键不存在）

## 速查表

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

## 下一步

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

- [编程](https://www.owlsprep.com/zh/study/cie-9618-u11-overview/)
- [编程基础](https://www.owlsprep.com/zh/study/cie-9618-u11-programming-fundamentals/)
- [控制流结构](https://www.owlsprep.com/zh/study/cie-9618-u11-control-flow-structures/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-hash-tables/