散列表查找

真题练习：可在站内题库按“散列表”知识点筛选。

复习时重点掌握三点：1. 散列表的重要概念；2. 冲突处理方法；3. 平均查找长度的计算方法。

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

散列表

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

散列表的关键性能指标是其 装载因子，通常表示为 $\alpha$ （也有教材记作 $\lambda$ ）。若当前元素数为 $n$ 、表长为 $m$ ，则

\alpha=\frac{n}{m}.

随着装载因子的增加，散列冲突的可能性也会增加，这可能会降低散列表的性能。

散列函数

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

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

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

同义词

在哈希表中，同义词（synonym）指的是多个不同的键（key）通过哈希函数计算后，映射到 同一个初始哈希地址（即相同的哈希值或索引）。这就是冲突：开放定址法中一个物理槽位只能放一条记录，必须继续探测；拉链法中一个桶可以挂接多个结点，但仍需在该桶内继续比较键。

例如：
- 假设哈希函数是 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 是非同义词，因为它们被哈希函数分配到不同的位置。

查找方式

散列表的查找算法如下：

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

设表长为 $m$ 、当前记录数为 $n$ 。哈希表查找的最好情况时间复杂度为 $O(1)$ ；在哈希函数分布均匀且装填因子受控时，平均查找也可视为 $O(1)$ 。但在极端冲突下，开放定址法可能探测整张表，拉链法也可能退化为一条长链，最坏时间为 $O(m)$ 或 $O(n)$ （二者在同一量级约束下等价）。

冲突处理方法

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

概念对照

三种散列冲突处理方法

点击比较维度，对照线性探测、平方探测和拉链法的探测方式、聚集现象与删除策略。

比较维度线性探测平方探测拉链法

当前比较：冲突后的位置。

开放定址法可统一写成

H_i=(H(key)+d_i)\bmod m.

平方探测对应的偏移序列为

d_i=\pm1^2,\pm2^2,\ldots

开放定址法

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

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

线性探测法

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

平方探测法

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

注意：平方探测的偏移顺序必须由题设或实现明确，例如按 $+1^2,-1^2,+2^2,-2^2,\ldots$ 依次试探，或使用 $d_i=c_1i+c_2i^2$ 。它不像线性探测那样天然保证遍历每一个槽位；表长、系数和装填因子不合适时，可能尚有空槽却无法在该序列中访问到。

双散列法

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

计算公式为

H_i(key)=\bigl(H_1(key)+i\cdot H_2(key)\bigr)\bmod m, \qquad i=0,1,2,\ldots

其中 $i$ 为冲突次数，初始为 0； $m$ 为哈希表长度。为了使探测序列覆盖整张表，通常要求步长 $H_2(key)$ 与 $m$ 互素。

拉链法

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

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

平均查找长度

查找失败

在考题中常常需要计算散列表 查找失败 时的平均查找长度，这里举一个实例说明。

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

假如根据哈希函数计算出的初始查询位置为 0，查询失败时根据线性探测法一直向后探测，查找到位置 8 发现该位置为空得出查找失败，查询次数为 9，其他位置可以以此类推计算出来。

当查找一个新的 key 时，初始查询位置根据哈希函数计算可能在 0 到 6 之间，对于每个位置，查询失败时，需要查找的长度如下表所示：

查找失败的 平均查找长度 为

ASL_{\text{失败}}=\frac{9+8+7+6+5+4+3}{7}=6.

这里分母为 $7$ ，是因为题设的散列函数 key % 7 只会给出 $0$ 到 $6$ 这 7 个初始散列地址；它不是表长 $11$ 。计算失败 ASL 时应先确认题目要求对哪些初始地址等概率取平均。

查找成功

成功查找时的平均查找长度

只有存储在散列表中的元素才能被成功查找，对于这些元素，查找成功的长度分为两种情况：

使用散列函数 H(key) 查找到某个位置，该位置存储的元素就是 key，查找次数为 1
对于上述情况，该位置存储的元素不是 key，则向下一个位置探测，直到找到元素 key，探测次数为 N，则查找次数为 1 + N

将散列表中的所有元素的查找次数求和，然后除以 元素个数，即得到 查找成功时的平均查找长度。若表中有 $n$ 个元素，第 $i$ 个元素的成功查找次数为 $c_i$ ，则

ASL_{\text{成功}}=\frac{1}{n}\sum_{i=1}^{n}c_i.

装填因子

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

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

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

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

对于开放定址法， $\alpha<1$ 是基本约束，且 $\alpha$ 接近 1 时探测次数会明显增加；对于拉链法， $\alpha$ 可以大于 1，它表示每个桶的平均链长。因此常在装填因子达到实现设定的阈值时进行散列表扩容；0.7、0.75 只是常见工程取值，并非所有散列表的统一规定。

扩容

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

创建一个 更大容量 的新散列表，常按实现策略增长（如容量翻倍或选择合适的素数表长）；开放定址法还要保证新的表长与探测规则相容。
遍历旧散列表中的所有元素，按新的表长重新计算散列地址并插入新表；若实现同时调整散列函数，也要按新函数重新散列全部元素。
释放旧散列表的内存。

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

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

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

探测停止条件与删除标记

开放定址法中，查找不能把“被删除过的槽位”和“从未使用的空槽位”混为一谈。查找到 从未使用的空槽位 时，可以确定键不存在，因为若该键曾插入，它的探测路径不会跨过这个空槽；查到 删除标记 时却必须继续探测，因为后续槽位可能仍保存与该初始地址同义的键。插入时可复用删除标记的位置，但仍应确认探测序列中没有同键记录。

计算 ASL 时也应逐条记录“从初始散列地址开始检查了几次”，而不是只数发生了几次冲突。成功 ASL 的样本是表中已有记录，失败 ASL 的样本是题目规定的可能初始地址或待查关键字分布；分母不同会直接改变结果。