散列表查找

🔥 高优先级

经常考查，重点掌握三点：1. 哈希表的重要概念。2. 冲突处理方法。 3. 平均查找长度计算方法。

其中平均查找长度（成功或失败的）也常在大题考查，需熟练掌握计算方法和易错点。

散列表

散列表（hash table），也叫 哈希表，是一种常用的数据结构，提供了快速的数据存储和检索操作。它使用一个数组（通常称为桶或槽）来存储数据。为了将数据存储到散列表中，数据项首先与一个键关联，然后使用一个 散列函数 将该键转换为数组的索引。这样，通过该键可以快速找到相应的数据项。

散列表的关键性能指标是其 装载因子，通常表示为 λ。装载因子是散列表中当前存储的元素数量与散列表的容量之比。随着装载因子的增加，散列冲突的可能性也会增加，这可能会降低散列表的性能。

注意

散列表（哈希表）是一种根据 关键字（Key） 快速查找记录的数据结构。实际存储的通常是 <Key, Value> 形式的记录，其中哈希函数仅根据 Key 计算存储位置。

在考研中，一般谈论散列表都是用于查找 key，而不是检索 value，所以哈希函数仅根据 Key 计算存储位置。为了简化讨论，后文若无特殊说明，将直接把关键字视为散列表中的元素。

散列函数

散列函数（Hash Function）是一种函数，它接受一个输入（或“键”）并返回一个输出（或“值”），通常用作数组的索引。其主要目的是均匀地分布键到数组中，以便在可能的范围内平均分配值，从而最大限度地减少冲突。

一个好的散列函数应具有以下特性：

均匀分布：无论输入数据的分布如何，散列函数都应该确保输出均匀分布在其范围内，以减少冲突。
计算速度：散列函数应该快速计算，这样就不会成为整个哈希过程的瓶颈。
确定性：对于同一输入，散列函数应始终产生相同的输出。
最小冲突：尽管冲突是不可避免的，但好的散列函数应该使它们降到最低。

同义词

在哈希表中，同义词（synonym）指的是多个不同的键（key）通过哈希函数计算后，映射到 同一个哈希表位置（即相同的哈希值或索引）。这通常会导致冲突，因为哈希表的一个槽位（bucket）只能存储一个键值对。

例如：
- 假设哈希函数是 h(key) = key % 10，键 15 和 25 都会映射到索引 5（因为 15 % 10 = 5 和 25 % 10 = 5）。
- 在这种情况下，15 和 25 就是同义词，因为它们在哈希表中竞争同一个位置。

同理，非同义词（non-synonym）指的是通过哈希函数计算后，映射到不同哈希表位置（即不同哈希值或索引）的键（key）。这些键不会竞争同一个槽位，因此不会引发冲突。

非同义词

例如：

假设哈希函数是 h(key) = key % 10：
- 键 15 映射到索引 5（因为 15 % 10 = 5）。
- 键 17 映射到索引 7（因为 17 % 10 = 7）。
在这种情况下，15 和 17 是非同义词，因为它们被哈希函数分配到不同的位置。

操作

散列表提供多种操作：

Insert(key)：插入一个 key
Search(key)：查找 key 是否存在
Delete(key)：删除一个 key

删除和插入操作思路类似（都是以查找操作作为基础），这里重点理解查找和插入操作。

查找

散列表的查找算法如下：

哈希函数映射：通过 哈希函数 h(key) 将键映射到哈希表的索引位置。
访问槽位：根据索引访问哈希表中的对应槽位。
冲突处理：如果发生冲突，通过 探测方法 计算下一个可能位置，直到找到匹配的键、遇到空槽或遍历完全部位置。
返回结果：找到匹配键则返回对应值，未找到则返回空。

假设数组长度为 n，哈希表查找的最好情况下时间复杂度为 O(1)，但随着冲突次数的增多最坏会恶化到 O(n)。

插入

散列表插入的基本思想是：先利用哈希函数计算关键字的存储位置，若该位置为空，则直接插入；若已被占用，则先判断是否为相同关键字，若不是，则按照冲突处理方法继续探测，直到找到空槽完成插入，或遍历完所有可能位置后判定插入失败。

冲突处理方法

散列表的冲突处理策略总结为以下几种：

开放定址法

开放定址法（Open Addressing）使用单个数组来存储所有的键值对。当发生冲突时，根据 开放定址策略 在散列表中寻找另一个空槽，将键值对存储在那里。

常用的 开放定址策略 有：线性探测、平方探测和 双散列，具体如下：

线性探测法

原理：当发生冲突时，线性探测法会不断查找下一个可用的槽位（通常是 下一个连续的位置），直到找到一个空槽位为止。
操作：
- 插入：当要插入一个新元素并遇到冲突时，它会向前移动到下一个槽位，直到找到一个空槽位。
- 查找：查找时也是一样的，如果在预期的槽位中没有找到元素，它会继续向前移动，直到找到该元素或遇到一个空槽位为止。
- 删除：删除稍微复杂一些，因为直接删除一个元素可能会中断查找其他元素的连续性。通常的做法是用一个特殊的标记替换被删除的元素，表明该槽位已被删除但仍可能在查找时被访问。

平方探测法

原理：与线性探测法相似，但它不是每次冲突后移动到下一个连续的槽位，而是移动到 $1^{2}$ 、 $- 1^{1}$ 、 $2^{2}$ 、 $- 2^{2}$ 、 $3^{2}$ 、 $- 3^{2} ...$ 位置直到找到一个空槽位。
操作：
- 插入：遇到冲突时，首先尝试移动正负 $1$ 的平方（ $1^{2} = 1$ ）个位置，然后正负 $2$ 的平方（ $2^{2} = 4$ ）个位置，接着正负 $3$ 的平方（ $3^{2} = 9$ ）个位置，以此类推，直到找到一个空槽位。
- 查找：与插入操作类似，也按照平方的序列移动。
- 删除：和线性探测法类似，可以使用特殊标记表示槽位已被删除。

双散列法

原理：双散列法使用 两个独立的散列函数：一个是常规的散列函数 $Hash_{1}$ ，另一个是用于冲突解决的散列函数 $Hash_{2}$ 。
操作：
- 插入：当发生冲突时，首先使用第一个散列函数得到基本的索引位置，如果该位置已被占用，则使用第二个散列函数得到一个步长，按这个步长查找下一个槽位，直到找到一个空槽位。
- 查找：与插入相似，首先使用第一个散列函数，如果没找到，则使用第二个散列函数得到的步长继续查找。
- 删除：和上述方法类似，使用特殊标记表示槽位已被删除。

计算公式为

H_{i} = (Hash_{1} (k ey) + i \times Hash_{2} (k ey)) mod n

其中 $i$ 为冲突次数，初始为 0； $n$ 为哈希表的长度。

拉链法

拉链法（Seperate Chaining）使用数组与链表相结合的方式。散列表的每个槽位都包含一个链表（或其他数据结构，如平衡树）。当发生冲突时，键值对被添加到相应槽位的链表中。

操作：
- 查找：通过散列函数找到对应的索引位置，在该索引的链表中顺序查找键。
- 插入：通过散列函数找到对应的索引位置。若该键在链表中已存在，更新其值；否则，在链表中添加新的键值对。
- 删除：通过散列函数找到对应的索引位置。在链表中查找并删除对应的键值对，若未找到则无操作。

平均查找长度

平均查找长度（Average Search Length，ASL）用于衡量查找算法的平均效率，其定义为：

在所有可能的查找请求中，查找所需比较（或探测）次数的数学期望。

由于不同查找请求出现的概率可能不同，因此平均查找长度本质上是一个 加权平均值：

A S L = i = 1 \sum n P_{i} L_{i}

其中：

$P_{i}$ ：第 $i$ 种查找请求发生的概率；
$L_{i}$ ：对应查找请求所需的查找长度（比较次数或探测次数）。

在散列表中，通常采用以下两种默认假设：

查找失败：假设哈希函数均匀，每个初始哈希地址出现的概率相同，因此对 所有可能的初始哈希地址 求平均。
查找成功：假设散列表中每个元素被查找的概率相同，因此对 所有已存储元素 的查找长度求平均。

下面分别介绍这两种情况的计算方法。

查找失败

计算查找失败的平均查找长度时，需要抓住一个核心思想：

对于一个待查找的新 key，我们事先并不知道它的值，因此只能知道它经过哈希函数后可能映射到哪些初始位置。通常假设哈希函数是均匀的，即每个初始位置出现的概率相同，因此平均查找长度就是这些初始位置查找长度的平均值。

在考题中，常常需要计算散列表 查找失败 时的平均查找长度（ASL）。下面通过一个实例进行说明。

假设哈希表如下图所示，哈希表长度为 12，哈希函数为 H(key)=key%7，采用线性探测法解决冲突。

散列地址	0	1	2	3	4	5	6	7	8	9	10	11
关键字	98	22	30	87	11	40	6	20

由于哈希函数为 H(key)=key % 7，因此任意关键字的初始散列地址只能是 0～6，并且通常认为这 7 个初始地址出现的概率相同，因此查找失败的平均查找长度也是在这 7 个初始地址 上求平均，而不是对整个哈希表的 12 个存储单元求平均。

0 1 2 3 4 5 6 7 8
● ● ● ● ● ● ● ● ○

从各个初始地址开始：

初始地址	探测序列	长度
0	0→1→2→3→4→5→6→7→8	9
1	1→2→3→4→5→6→7→8	8
2	2→3→4→5→6→7→8	7
3	3→4→5→6→7→8	6
4	4→5→6→7→8	5
5	5→6→7→8	4
6	6→7→8	3

因此，查找失败的平均查找长度为：

A S L_{失败} = \frac{9 + 8 + 7 + 6 + 5 + 4 + 3}{7} = 6

需要注意的是，这里分母为 7 而不是 12。这是因为 ASL 是对所有可能的初始散列地址求平均，而不是对哈希表中的所有存储单元求平均。本例中哈希函数只能产生 0～6 这 7 个初始散列地址，因此平均查找长度应除以 7。

查找成功

查找成功时的平均查找长度如何计算呢？

与查找失败不同，查找成功时，不是对所有可能的哈希地址取平均，而是对散列表中已经存储的所有元素取平均。 通常假设每个元素被查找的概率相同，因此每个元素的查找长度具有相同权重。

对于散列表中的每个元素，其查找长度分为两种情况：

使用散列函数 H(key) 定位到某个位置，该位置存储的元素就是 key，则查找长度为 1；
若该位置存储的不是 key，则按照冲突处理方法继续探测，直到找到元素 key。若共探测了 N 次，则查找长度为 1+N。

将散列表中 所有元素 的查找长度求和，再除以 元素个数，即可得到 查找成功时的平均查找长度。

装填因子

装填因子（load factor）是一个衡量散列表“满”的程度的指标，其中 装填因子 = 散列表中已存储的项数 / 散列表的总大小。

例如，如果一个容量为 100 的散列表中已经有 70 项，那么装填因子为 0.7。

装填因子的值影响散列表的性能：

当装填因子太小，意味着散列表中有很多空位，这可能导致内存浪费。
当装填因子太大，冲突的概率会增加，从而降低查找、插入和删除的速度。

因此，常常在装填因子达到某个阈值时进行散列表扩容，例如当装填因子大于 0.7 或 0.75。

扩容

扩容（Rehashing）是增加散列表容量以容纳更多元素并降低装载因子的过程。以下是扩容的主要步骤：

创建一个 更大容量 的新散列表，通常采用指数倍增长策略（如容量翻倍）。
遍历旧散列表中的所有元素，使用 新的哈希函数（或调整后的哈希函数）将它们重新插入到新散列表中。
释放旧散列表的内存。

扩容会消耗一定时间，尤其当散列表元素较多时开销较大。然而，由于扩容操作不频繁，其时间成本被分摊到每次插入操作中，使得插入的平摊时间复杂度仍为 O(1)。

对于使用开放定址法的哈希表，扩容的过程如下图所示：

对于使用拉链法的哈希表，扩容前后的哈希表如下图所示：