7.6 散列表

散列函数的构造方法，开放定址法与拉链法处理冲突，装填因子与 ASL 的计算。

基本概念

在前面介绍的线性表和树表的查找中，记录在表中的位置与记录的关键字之间不存在确定关系，因此在这些表中查找记录时需进行一系列的关键字比较，查找的效率取决于比较的次数。

• 散列函数（哈希函数）：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为 $\mathrm{Hash}(key) = Addr$（这里的地址可以是数组下标、索引或内存地址等）。
• 冲突：散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。
• 散列表（哈希表）：根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下，对散列表进行查找的时间复杂度为 $O(1)$，即与表中元素的个数无关。

散列函数的构造方法

在构造散列函数时，必须注意以下几点：

1. 散列函数的定义域必须包含全部关键字，而值域的范围则依赖于散列表的大小；
2. 散列函数计算出的地址应尽可能均匀分布在整个地址空间，尽可能地减少冲突；
3. 散列函数应尽量简单，能在较短的时间内计算出任意一个关键字对应的散列地址。

处理冲突的方法

开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为

式中，$H(key)$ 为散列函数；$i = 0, 1, 2, \ldots, k$（$k \le m - 1$）；$m$ 表示散列表表长；$d_i$ 为增量序列。取定某一增量序列后，对应的处理方法就是确定的：

1. 线性探测法：$d_i = 0, 1, 2, \ldots, m - 1$。冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元或查遍全表。线性探测法可能使第 $i$ 个散列地址的同义词存入第 $i + 1$ 个散列地址，这样本应存入第 $i + 1$ 个散列地址的元素就争夺第 $i + 2$ 个散列地址……从而造成大量元素在相邻的散列地址上”聚集”（或堆积）起来，大大降低了查找效率。
2. 平方探测法：$d_i = 0^2, 1^2, -1^2, 2^2, -2^2, \ldots, k^2, -k^2$（$k \le m/2$）。散列表长度 $m$ 必须是一个可以表示成 $4k + 3$ 的素数。平方探测法是一种处理冲突的较好方法，可以避免出现”堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
3. 双散列法：$d_i = i \times \mathrm{Hash}_2(key)$。需要使用两个散列函数，当通过第一个散列函数 $H(key)$ 得到的地址发生冲突时，则利用第二个散列函数 $\mathrm{Hash}_2(key)$ 计算该关键字的地址增量。
4. 伪随机序列法：$d_i$ = 伪随机数序列。

拉链法（链接法）

显然，对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为 $i$ 的同义词链表的头指针存放在散列表的第 $i$ 个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

动画演示与 ASL 计算

默认数据是 408 的一道经典题：将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 $H(key) = (key \times 3) \bmod 7$，处理冲突采用线性探测再散列法，要求装填（载）因子为 0.7。

散列查找的性能分析

虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于冲突的产生，使得散列表的查找过程仍然是一个和关键字比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。

即时练习