数据结构之散列表

散列表概念

散列表（Hash Table）是一种根据关键字直接进行访问的数据结构，它通过散列函数将关键字映射到存储地址，达到快速查找的目的。理想情况下，散列表查找的时间复杂度为 $ O(1) $，与表中元素个数无关。

散列函数与冲突处理

散列函数（Hash Function）: 将关键字映射为对应的地址，表示为 $ (key) = Addr $。
- 地址可以是数组下标、索引或内存地址。
冲突（Collision）: 两个或多个不同关键字被映射到相同地址。
- 这些不同关键字称为同义词。
目标: 设计良好的散列函数尽量减少冲突，同时设计有效的冲突处理方法。

散列函数的构造方法

构造散列函数时需要注意：

定义域包含所有关键字，值域依赖于散列表的大小。
散列地址应等概率、均匀分布，减少冲突。
计算简单高效，能快速得到散列地址。

常用的散列函数构造方法

1. 直接定址法

概念: 直接定址法是最简单的一种散列函数构造方法，直接将关键字通过一个线性函数映射为散列地址。通常，散列函数为线性形式，例如：

$ H(key) = key $
$ H(key) = axkey + b $，其中 $ a $ 和 $ b $ 是常数。

这种方法将关键字直接映射为存储地址，无需复杂的运算，计算时间非常短。

特点:

简单无冲突：由于直接取关键字值或其线性变换，理论上不会产生冲突。
适用性：适合关键字的分布基本连续的情况，例如当关键字为自然数并且没有过多的间隔时。
缺点：如果关键字分布不连续，会造成大量空闲地址，导致存储空间浪费。例如，当关键字是离散的非连续数值时，许多地址可能无法被使用。

适用场景:

用于场景中，关键字数量有限且连续，比如小型数据库或某些固定数值范围内的标识符。

2. 除留余数法

概念: 除留余数法是散列表中最常用的散列函数构造方法之一。它通过对关键字取模操作，将其映射到散列表的地址空间中：

$ H(key) = key % p $

其中，$ p $ 是小于或等于散列表大小 $ m $ 的质数。质数的选择非常重要，能够确保散列地址的均匀分布，减少冲突的可能性。

特点:

常用且有效：取模运算简单，易于实现，并且通过选用合适的质数 $ p $，可以均匀分配地址，降低冲突的几率。
灵活性：可以适应不同规模的散列表，只需根据散列表大小调整 $ p $ 值。
冲突的减少：质数 $ p $ 的选择非常关键，选得好会使关键字更均匀地分布在散列表的每个槽中，减少碰撞。

适用场景:

通常用于大多数通用的散列算法，适合关键字范围较大的应用场景，如数据库索引和缓存系统。

3. 数字分析法

概念: 数字分析法通过对关键字的数字位进行分析，选取出现频率均匀的位数作为散列地址。这种方法通常适用于关键字已知且呈现某种模式的情况下。

例如，假设关键字是由多个位（例如十进制数）组成的数值，其中某些位的取值较为均匀，而某些位则取值集中。这种情况下，可以选择关键字中分布较为均匀的位来构造散列地址。

特点:

适用于特定场景：特别适合关键字集合已知且关键字的某些位分布均匀的情况。
灵活但有限：对于未知或变化的关键字集合，可能需要频繁重新构造散列函数，不够灵活。
减少冲突：通过选择分布较均匀的位，可以有效减少冲突的发生。

缺点:

如果关键字集合发生变化，原有的散列函数可能不再适用，需要重新分析并设计新的散列函数。

适用场景:

适用于关键字集合已经确定且变化不大的场景，如某些统计或分类数据。

4. 平方取中法

概念: 平方取中法通过将关键字平方后，取其平方值的中间几位作为散列地址。由于平方值包含关键字所有位的信息，因此能均匀地分布散列地址。

步骤：
1. 计算关键字的平方值 $ key^2 $。
2. 从平方值中间选取若干位作为散列地址。

特点:

均匀分布：平方运算能够使得关键字的各位数值更加分散，使得散列地址的分布更均匀。
适用于不均匀的关键字：当关键字的各位数值分布不均时，这种方法可以使得散列地址较为均匀。
灵活性：取多少位作为散列地址可以根据实际需要灵活调整。

缺点:

计算复杂度稍高：相对于除留余数法等简单的算法，平方取中法涉及平方运算，可能会增加计算时间。

适用场景:

适用于关键字的各个位数值分布不均匀或关键字范围较大的场景。此方法可以确保散列地址的均匀性，减少冲突的发生。

散列函数	计算简单性	冲突可能性	适用场景
直接定址法	极简	无冲突（若连续）	关键字连续且范围较小
除留余数法	较简单	低（合适质数）	通用，关键字范围较大
数字分析法	较复杂	低	已知的关键字集合
平方取中法	较复杂	低	关键字不均匀时

在不同的场景下，选择合适的散列函数能够大大提升散列表的查找效率，并减少冲突的发生。

处理冲突的方法

在散列过程中，冲突是不可避免的。任何设计的散列函数都无法保证100%避免冲突，因此我们必须考虑在冲突发生时，如何为冲突的关键字寻找新的散列地址。处理冲突的常用方法是开放定址法。

1. 开放定址法

定义:
开放定址法是指散列表中的每个空闲单元都可以用于存放发生冲突的元素。无论是与现有元素同义的关键字（即散列到同一地址的不同关键字）还是非同义的关键字，只要是空闲地址，都可以作为冲突后的存储位置。

数学递推公式: $ H_i = (H(key) + d) % m $

$ H(key) $ 为散列函数计算出的地址；
$ i = 0, 1, 2, , k $ 表示探测次数；
$ d $ 为增量序列；
$ m $ 为散列表的大小。

通过改变增量 $ d $ 的取值，产生不同的探测方法。下面详细介绍常见的4种探测法：

线性探测法

增量序列: $ d = 0, 1, 2, , m-1 $

原理:
发生冲突时，从冲突发生位置开始，逐个检查下一个散列表单元，直到找到一个空闲单元。如果探测到散列表的最后一个位置（$ m-1 $），下一个探测位置则从表的开头（0）继续。这种方法总能在表未填满时找到一个空闲单元。

特点:

简单易实现：线性探测法的增量序列是等差数列，计算非常简单。
产生聚集效应: 当某个位置发生冲突后，同义词将会连续地存储在相邻位置。这会导致其他关键字也需要向后查找，形成所谓的“堆积”现象，严重降低查找效率。

示例:

假设 $ m = 11 $，散列函数为 $ H(key) = key % 11 $，插入关键字序列 $ { 12, 44, 13, 88 } $，当插入 88 时，若 88 产生了冲突，那么依次探测 $ H(88) + 1 $、$ H(88) + 2 $，直到找到空位。

平方探测法

增量序列: $ d = 0, 1^2, -1^2, 2^2, -2^2, $

原理:
平方探测法使用正负平方数作为增量序列来探测下一个空闲位置。假设散列表的大小为 $ m $，要求 $ m $ 是形如 $ 4k+3 $ 的质数，平方探测法通过不规则的增量可以避免产生聚集效应。

特点:

减少聚集: 平方探测法避免了线性探测法中的堆积现象，因为它通过非连续的增量来探测下一个位置。
探测范围有限: 平方探测法并不能遍历散列表中的所有位置，它只能探测散列表的一半左右单元。通常，$ k m / 2 $。

示例:

假设 $ m = 7 $，关键字 $ key = 18 $，散列函数 $ H(18) = 18 % 7 = 4 $。当 4 号地址发生冲突时，依次探测 $ 4 + 1^2 $、$ 4 - 1^2 $、$ 4 + 2^2 $、$ 4 - 2^2 $，直到找到空闲单元。

双散列法

增量序列:
使用两个散列函数 $ H_1(key) $ 和 $ H_2(key) $。当第一个散列函数 $ H_1(key) $ 产生冲突时，利用第二个散列函数 $ H_2(key) $ 来确定增量。

散列公式:
$ H_i = (H_1(key) + i H_2(key)) % m $

原理:
双散列法通过两个散列函数减少了冲突的概率。当第一次计算出的地址发生冲突时，使用第二个散列函数的值作为增量进行探测。

特点:

避免聚集现象: 双散列法通过两个独立的散列函数生成不同的增量序列，从而减少了聚集效应。
探测范围广: 使用两个散列函数可以确保遍历所有位置，探测过程能够遍历散列表中的所有单元，避免某些位置无法探测到的情况。

示例:

假设 $ H_1(key) = key % 11 $ 和 $ H_2(key) = 7 - (key % 7) $，当 $ key = 22 $ 时，$ H_1(22) = 22 % 11 = 0 $，若 0 号地址冲突，增量为 $ H_2(22) = 7 - (22 % 7) = 5 $，则下一个地址为 $ (0 + 1 ) % 11 = 5 $。

伪随机序列法

增量序列:
使用伪随机数生成器产生增量序列。

原理:
伪随机序列法通过伪随机数生成器生成一系列随机数作为增量序列，避免了固定的增量序列可能产生的聚集现象。伪随机数生成器通过一定的种子值和算法，确保每次生成的增量是可预测的。

特点:

灵活性强：伪随机序列的生成可以根据不同需求灵活调整。
删除问题: 在开放定址法中，不能简单地物理删除散列表中的某个元素，因为可能会中断其他具有相同散列地址的元素的查找路径。因此，采用伪随机序列法时，删除操作通常只进行“逻辑删除”，即为被删除的元素打上标记，而不实际删除它。随着时间推移，逻辑删除会使得散列表看起来变满，因此需要定期进行维护和整理，物理删除那些已被逻辑删除的元素。

处理方法	增量序列	优点	缺点	适用场景
线性探测法	$ d = 0, 1, 2, $	实现简单	容易产生堆积现象	适合简单场景，散列表较小时
平方探测法	$ d = 0, 1^2, -1^2, 2^2, $	减少堆积	不能遍历所有单元	适用于较大散列表
双散列法	$ H_i = H_1(key) + i H_2(key) $	冲突概率小，探测范围广	实现复杂	适用于冲突概率较大的场景
伪随机序列法	伪随机数生成器	灵活	删除操作复杂	适用于需要随机化的场景

拉链法（Chaining）

拉链法（或称链接法）是一种处理散列表冲突的经典方法。通过散列函数，多个关键字可能会映射到相同的散列地址，这就是所谓的“冲突”。为了应对这种冲突，拉链法将所有映射到同一散列地址的关键字存储在一个线性链表中，该链表的头指针存放在对应散列地址的表单元中。这个结构确保每个散列地址可以容纳多个关键字。

拉链法的特点

线性链表存储同义词：对于散列地址相同的关键字（称为同义词），它们通过链表链接起来。表中的每个单元存放一个链表的头指针，链表中的每个节点存储一个关键字。
适用于动态操作：由于拉链法的查找、插入和删除操作都主要在链表中进行，它非常适合需要频繁进行插入和删除的场景。例如，当需要删除某个关键字时，只需在链表中操作，无需大规模调整散列表结构。
空间利用率高：即使发生冲突，拉链法只会扩展链表的长度，不会影响其他表单元的存储空间，因此空间利用率较高。

拉链法的查找、插入、删除操作

查找操作：通过散列函数计算关键字对应的散列地址 $ H(key) $，然后顺着该散列地址对应的链表依次查找关键字。
插入操作：新插入的关键字首先计算其散列地址，然后插入到对应散列地址的链表中。可以选择将新关键字插入到链表的头部或尾部。
删除操作：在查找到链表中的关键字后，将其从链表中删除。拉链法支持较高效的删除操作，不会影响其他单元的元素。

例如，关键字序列为{19,14,23,01,68,20,84,27,55,11,10,79}，散列函数H(key)=key%13，用

平均查找长度（ASL）

在拉链法中，平均查找长度（ASL） 反映了散列表查找一个元素的效率。ASL 是链表中查找到元素的平均步数，它由链表的长度和链表中元素的分布情况决定。当链表较短且元素均匀分布时，ASL 较低，查找效率较高。

散列查找及性能分析

散列表查找的过程与构造散列表的过程基本一致。通过散列函数，计算关键字的散列地址，进行查找的步骤如下：

查找过程

初始化：根据给定关键字 $ $，通过散列函数计算散列地址：$ = H() $
步骤①：检测散列表中地址为 $ $ 的位置是否有记录：
- 若无记录，则查找失败。
- 若有记录，比较其值与关键字 $ $，若相等，则查找成功。
- 若不相等，继续执行步骤②。
步骤②：用处理冲突的方法计算下一个散列地址，将 $ $ 置为此地址，转回步骤①，直到找到匹配的记录或空位置。

示例

给定关键字序列 $ {19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79} $，散列函数 $ H() = % 13 $，使用线性探测法处理冲突，构造的散列表如下：

查找 84 的过程：
1. 计算散列地址 $ H(84) = 84 % 13 = 6 $。
2. 地址 $ [6] $ 存放的是 19，不等于 84，发生冲突。
3. 使用线性探测，计算下一个地址 $ H' = (6 + 1) % 13 = 7 $。
4. 地址 $ [7] $ 存放的是 20，查找失败，之后再加1，查找成功，返回地址 8。
查找 38 的过程：
1. 计算散列地址 $ H(38) = 38 % 13 = 12 $。
2. 地址 $ [12] $ 存放的是 23，不等于 38，发生冲突。
3. 使用线性探测，计算下一个地址 $ H' = (12 + 1) % 13 = 13 $。
4. 地址 $ [13] $ 是空的，查找失败。

查找效率与平均查找长度（ASL）

平均查找长度（ASL）：用于衡量查找成功或失败时的效率，表示为查找操作中比较次数的平均值。

对应本例中的关键字序列，查找成功时的平均查找长度为： $ = = 2.5 $

散列表查找效率的影响因素

散列函数：好的散列函数可以均匀分布关键字，减少冲突的发生。
处理冲突的方法：不同的冲突处理方法，如线性探测法、平方探测法、双散列法等，对查找效率有不同的影响。
装填因子 $ $：定义为表中的记录数与散列表长度之比：$ = $ 其中 $ n $ 是表中记录数，$ m $ 是散列表的长度。装填因子越大，表中越满，发生冲突的可能性越高，查找效率降低。