散列表 | Frank's Blog

一、基本概念

散列表（Hash Table） 也叫哈希表，是根据关键码值（Key Value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数。散列表建立了关键字和存储地址之间的一种直接映射关系。

当关键字全域 U 较小时，我们可以使用一个称为直接寻址表（direct-address table）的数组表示一个取自关键字全域的动态集合，其中每个位置称之为槽（slot），对应全域 U 中的一个关键字，槽 k 指向集合中一个关键字为 k 的元素。

但当关键字全域 U 比较大时，这样做显然是不合适的，因为这样的话直接寻址表的空间开销会很大，而且很大概率会浪费很多空间（取决于实际关键字的数量，如果数量相对于关键字全域很少，那么就会造成大量空间的浪费）。

因此，我们需要用散列函数根据关键字来计算出槽的位置。这样，散列函数 h 就将关键字的全域 U 映射到散列表$T[0..m-1]$的槽位上。散列表的大小 m 一般比关键字全域 U 小得多，这样就解决了当使用直接寻址表时造成的大量空间浪费的问题。但是这样做又会出现一个新的问题，假如不同的关键字的散列函数值相同，即不同的关键字被映射到同一个槽中，那么又该怎么办呢？我们称这种情形为冲突（collision），在下文中会介绍几种处理冲突的方法。

二、构造散列函数

上文中提到散列函数通过把关键码值映射到表中一个位置来访问记录，那么该如何构造散列函数呢？下面介绍几种常见的构造方法。

1、直接定址法

直接取关键字的某个线性函数值为散列函数，散列函数为：
$$
h(key) = a \times key + b
$$
式中 a 和 b 为常数。这种方法计算最简单，且不会产生冲突。它适合关键字分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

2、除留余数法

假定散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p，利用模运算将关键字转换为散列地址，散列函数如下：
$$
h(key) = key % p
$$
该方法的关键是选择一个好的 p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，尽可能减少冲突的可能性。

3、乘法散列法

该方法分为两个步骤。第一步，用关键字 key 乘上常数$A(0 < A < 1)$，并提取$key \times A$的小数部分。第二步，用 m 乘以这个值。散列函数如下：
$$
h(key) = \lfloor m \times (key \times A - \lfloor key \times A \rfloor) \rfloor
$$
乘法散列法的一个优点就是对 m 的选择不是特别关键，一般令$m = 2^p$（p 为某个整数）。常数 A 建议选择为$(\sqrt5 - 1) / 2$。

三、处理冲突

1、链接法

在链接法（chaining）中，把散列到同一槽中的所有元素都放在一个链表中，如下图所示。槽 j 中有一个指针，它指向存储所有散列到 j 的元素的链表的表头；如果不存在这样的元素，则槽 j中为空指针。

存放元素的链表可以是单链表，也可以是双向链表。图中链表画为双链，因为这样删除操作比较快。链接法适用于经常进行插入和删除的情况。

2、开放寻址法

在开放寻址法（open addressing）中，所有的元素都存放在散列表里。也就是说，每个表项或包含动态集合的一个元素，或包含空指针。当查找某个元素时，要系统地检查所有的表项，直到找到所需的元素，或者最终查明该元素不在表中。不像链接法，这里既没有链表，也没有元素存放在散列表外。因此在开放寻址法中，散列表可能会被填满，以至于不能插入任何新的元素。

开放寻址法的数学递推公式为：
$$
h_i = (h(key)+d_i) % m
$$
其中，$h(key)$为散列函数，$i \in [1, m-1]$且为整数，m 为散列表表长，$d_i$为增量序列。

接下来就要确定增量序列的取法，通常有以下三种取法：

（1）线性探查

当$d_i = 0, 1, 2, …, m-1$时，称之为线性探查（linear probing）。该方法的思想是：冲突发生时，顺序查看表中下一个单元（探测到表尾时下一个探测地址是表首地址），直到找出一个空闲单元。

线性探查方法比较容易实现，但它存在着一个问题，称为一次群集（primary clustering）。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。群集现象很容易出现，这是因为当一个空槽前有 i 个满的槽时，该空槽为下一个将被占用的概率是$(i+ 1)/m$。连续被占用的槽就会变得越来越长，因而平均查找时间也会越来越大。

（2）二次探查

当$d_i = 0^2, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2$，其中$k\le m/2$且 m 为可表示成$4k+3$的素数时，称为二次探查（quadratic probing）。

这是一种处理冲突的较好方法，但会导致一种轻度的群集，称为二次群集（secondary clustering），此外这种方法不能探测到散列表上的所有单元。

（3）双重散列

双重散列（double hashing）是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择排列的许多特性。双重散列采用如下形式的散列函数：
$$
h(k, i) = (h_1(k) + ih_2(k)) % m
$$
其中$h_1$和$h_2$均为辅助散列函数，i 为冲突的次数，初始值为 0。初始探查位置为$T[h_1(k)]$，后续的探查位置是前一个位置加上偏移量$h_2(k)$模 m。因此，不像线性探查或二次探查，这里的探查序列以两种不同方式依赖于关键字k，因为初始探查位置、偏移量或者二者都可能发生变化。