散列表查找

散列表

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

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

散列函数

散列函数（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 是非同义词，因为它们被哈希函数分配到不同的位置。

查找方式

散列表的查找算法如下：

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

假设数组长度为 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$ ）个位置，以此类推，直到找到一个空槽位。
  • 查找：与插入操作类似，也按照平方的序列移动。
  • 删除：和线性探测法类似，可以使用特殊标记表示槽位已被删除。

双散列法

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

计算公式为

$$H_i = (\text{Hash}_1{(key)} + i \times \text{Hash}_2{(key)}) \mod n$$

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

拉链法

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

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

平均查找长度

查找失败

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

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

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

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

查找失败的平均查找长度为 (9 + 8 + 7 + 6 + 5 + 4 + 3) / 7 = 6。

查找成功

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

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

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

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

装填因子

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

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

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

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

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

扩容

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

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

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

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

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