散列表查找

需熟练掌握散列表的冲突处理方法，对于其他知识点了解即可，可能在选择题中考察。

散列表

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

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

散列函数

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

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

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

冲突处理方法

1. 开放定址法

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

keysJohn SmithLisa SmithSam DoeSandra DeeTed Bakerbuckets000001Lisa Smith521-8976002:::151152John Smith521-1234153Sandra Dee521-9655154Ted Baker418-4165155:::253254Sam Doe521-5030255

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

线性探测法

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

平方探测法

  • 原理：与线性探测法相似，但它不是每次冲突后移动到下一个连续的槽位，而是移动到 $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{(key)} + i \times Hash_2{(key)}) \mod m$$

其中 $i$ 为冲突次数，初始为0。

2. 拉链法

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

keysJohn SmithLisa SmithSam DoeSandra DeeTed Bakerbuckets000001002::151152153154::253254255entriesLisa Smith521-8976John Smith521-1234Sandra Dee521-9655Ted Baker418-4165Sam Doe521-5030
  • 操作：
    • 查找：通过散列函数找到对应的索引位置，在该索引的链表中顺序查找键。
    • 插入：通过散列函数找到对应的索引位置。若该键在链表中已存在，更新其值；否则，在链表中添加新的键值对。
    • 删除：通过散列函数找到对应的索引位置。在链表中查找并删除对应的键值对，若未找到则无操作。

平均查找长度

查找失败

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

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

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

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

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

位置
0
1
2
3
4
5
6
查找次数
9
8
7
6
5
4
3

查找失败的平均查找长度为 (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。

扩容

扩容（Rehasing）是增加散列表的容量以容纳更多的项并降低装填因子的过程。扩容的主要步骤包括：

  1. 创建一个新的、更大的散列表。
  2. 遍历旧散列表中的每一项，并使用新的散列函数将它们插入到新的散列表中。
  3. 释放旧散列表的内存。

扩容会消耗时间，特别是当散列表中的项数很多时。但是，由于扩容不是经常发生，所以它的平均开销被分摊到了每一次的插入操作上，使得插入操作的平摊时间复杂度仍然为O(1)。