「哈希表hash table」，又称「散列表」，其通过建立键key 与值value 之间的映射，实现高效的元素查询。具
体而言，我们向哈希表输入一个键key ，则可以在𝑂(1) 时间内获取对应的值value 。
如图6‑1 所示，给定𝑛 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个
学号，返回对应的姓名”的查询功能，则可以采用图6‑1 所示的哈希表来实现。

除哈希表外，数组和链表也可以实现查询功能，它们的效率对比如表6‑1 所示。
‧ 添加元素：仅需将元素添加至数组（链表）的尾部即可，使用𝑂(1) 时间。
‧ 查询元素：由于数组（链表）是乱序的，因此需要遍历其中的所有元素，使用𝑂(𝑛) 时间。
‧ 删除元素：需要先查询到元素，再从数组（链表）中删除，使用𝑂(𝑛) 时间。
表6‑1 元素查询效率对比
数组链表哈希表
查找元素𝑂(𝑛) 𝑂(𝑛) 𝑂(1)
添加元素𝑂(1) 𝑂(1) 𝑂(1)
删除元素𝑂(𝑛) 𝑂(𝑛) 𝑂(1)
观察发现，在哈希表中进行增删查改的时间复杂度都是𝑂(1) ，非常高效。

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为「桶
bucket」，每个桶可存储一个键值对。因此，查询操作就是找到key 对应的桶，并在桶中获取value 。
那么，如何基于key 来定位对应的桶呢？这是通过「哈希函数hash function」实现的。哈希函数的作用是将
一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有key ，输出空间是所有桶（数
组索引）。换句话说，输入一个key ，我们可以通过哈希函数得到该key 对应的键值对在数组中的存储位置。
输入一个key ，哈希函数的计算过程分为以下两步。
1. 通过某种哈希算法hash() 计算得到哈希值。
2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该key 对应的数组索引index 。
index = hash(key) % capacity
随后，我们就可以利用index 在哈希表中访问对应的桶，从而获取value 。
设数组长度capacity = 100、哈希算法hash(key) = key ，易得哈希函数为key % 100 。图6‑2 以key 学号
和value 姓名为例，展示了哈希函数的工作原理。

本质上看，哈希函数的作用是将所有key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间
往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。
对于上述示例中的哈希函数，当输入的key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为
12836 和20336 的两个学生时，我们得到：

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时。并且由于哈希表容量
capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步提高了扩容过程的计算
开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。
「负载因子load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希
冲突的严重程度，也常被作为哈希表扩容的触发条件。例如在Java 中，当负载因子超过0.75 时，系统会将
哈希表容量扩展为原先的2 倍。

通常情况下哈希函数的输入空间远大于输出空间，因此理论上哈希冲突是不可避免的。比如，输
入空间为全体整数，输出空间为数组容量大小，则必然有多个整数映射至同一桶索引。
哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为解决该问题，我们可以每当遇到哈希冲突时就
进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量
的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。
1. 改良哈希表数据结构，使得哈希表可以在存在哈希冲突时正常工作。
2. 仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。
哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。