散列表是支持 INSERT 、DELETE 和 SEARCH 的字典操作，其是对普通数组概念的推广，因为可以对数组元素进行直接寻址，故可在 O(1) 时间内访问数组的任意元素。

当实际存储的关键字数比可能的关键字总数较小时，这时采用散列表比直接的数组寻址更为有效，因为散列表通常采用的数组尺寸与索要存储的关键字数是成比例的。在散列表中，根据关键字计算出数组下标。

直接寻址表

当关键字的全域 U 比较小并且任意两个关键字都不相同时，其中每个关键字元素取自全域 U={0,1,...,m-1}，此处 m 是一个不大的数，我们用一个数组（寻址表）T[0...m-1]，其中每个位置对应全域 U 中的一个关键字。在这个表中进行字典操作的执行是很快的，只需 O(1) 的时间。

直接寻址技术一个明显的问题是，如果域U很大，在一台典型计算机的可用内存容量限制下，为其设计一个对应的直接寻址表T是不太现实的。

散列表

当实际存储在字典中的关键字集合 K 比所有可能的关键字域U小得多时，我们使用散列表。

在直接寻址方式下，具有关键字 k 的元素被存放到槽 k 中。在散列方式下，该元素处于 h(k) 中，也就是利用散列函数 h，根据关键字 k 计算出槽的位置，函数 h 将关键字映射到散列表 T[0...m-1] 的槽位上。

h:U→{0...m-1}

采用散列函数的目的就在于缩小需要处理的小标范围,即要处理的值从 |U| 降到了 m，从而降低了空间开销。

这样做存在一个问题，就是两个关键字很可能映射到同一个槽上，我们将这种情形成为发生了碰撞。

我们可以通过如下两种方式解决碰撞：

1）链表法

在链表法中，把散列到同一个槽中的所有元素都放在一个链表中。如槽j中有一个指针，它指向由所有散列到j的元素构成的链表的投，如果不存在这样的元素，则 j 中为 NIL。

用链表法散列的最坏情况是所有的关键字 n 都散列到同一个槽中，从而产生出一个长度为 n 的链表，这时最坏情况下查找的时间为 O(n)。散列方法的平均态依赖于所选取的散列函数 h 在一般情况下，将所有关键字分不在 m 个槽位上的均匀程度。假定任何元素散列到 m 个槽中的每一个的可能性相同，且与其他元素已被散列到什么位置上是独立无关的，这个假定称为简单一致散列。

一个好的散列函数应或近似地满足简单一致散列的假设。

将关键字解释为自然数：多数散列函数都假定关键字域为自然数集 N={0,1,2,...}，如果给定的关键字不为自然数，则必须有一种方法来将他们解释为自然数。

a.除法散列法

通过取 k 除以 m 的余数，将关键字 k 映射到 m 个槽的某一个中去，即散列函数：

h(k)=k mod m

对于 m 的选择常常为与2的整数幂不太接近的质数。

b.乘法散列法

构造散列函数的乘法方法包含两个步骤，首先用关键字k乘上常数 A(0

h(k)=floor(m(kA mod 1))

其中 kA mod 1 为 kA 的小数部分，对于 A 的选择一般为：A 约等于(√5-1)/2，而 m 一般选择为2的某个幂次。

c.全域散列

任何一个特定的散列函数都有可能出现最坏的情况，使得平均检索时间为O(n)，唯一有效的改进方法是随机地选择散列函数，使之独立于要存储的关键字，这种方法成为全域散列。

全域散列的基本思想是在执行开始时，从一族仔细设计的函数中，随机选择一个作为散列函数，随机化保住了没有哪一种输入会始终导致最坏情况形态，同时，随机化使得即使对同一个输入，算法在每一次执行的形态也都不一样，这样就可以确保对于任何输入，算法都具有较好的平均情况形态。

2）开放寻址法

在开放寻址法中，所有的元素都存放在散列表理，亦即每个表项或包含动态集合的一个元素或为NIL。当查找一个元素时，要检查所有的表项，直到找到所需的元素或发现元素不在表中。开放寻址法中的装在因子不能超过1。

在开放寻址法中，当插入一个元素时，可以连续检查散列表的各项，直到找到一个空槽来放置待插入的关键字为止。检查的顺序不一定为0,1,2...，而是要依赖待插入的关键字，为了确定要探查哪些槽，我们将散列函数加以扩充，使之包含探查号（从0开始）以作为其第二个输入参数，如下面伪代码：

查找关键字 k 的算法的探查序列与将 k 插入时的插入算法一样，当查找到关键字或查找过程中碰到一个空槽时，查找算法就停止。

在开放寻址法中，当我们从槽 i 中删除关键字时，不能仅将 NIL 置于其中来标志它为空，如果这样的话，就会有个问题：在插入某关键字 k 的探查过程中，发现i被占用了，则 k 就被插入到后面的位置上，在将槽i中的关键字删除后，就无法检索关键字 k 了。

有一个办法就是在槽 i 中置一个特定的值 DELETED，而不是 NIL。这样 HASH-INSERT 做相应调整，使得 DELETED 标志的槽位仍可放入新的元素。

有三种技术常用来计算开放寻址法中的探查序列：线性探查、二次探查以及双重探查。

a.线性探查

首先给定一个普通的散列函数 h1(k)，则线性探查的散列函数为：

h(k,i)=(h1(k)+i) mod m,i=0,1,...,m-1

线性探查容易实现，但存在一个问题称作一次群集，随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。群集现象很容易出现，因为一个空槽前有i个满的槽时，该空槽为下一个将被占用槽的概率为 (i+1)/m。

b.二次探查

二次探查采用如下形式的散列函数：

h(k,i)=(h1(k)+c1*i+c2*i2) mod m

其中h1是一个普通散列函数，c1、c2 为常数，i=0,1,...,m-1。如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的，这一性质可导致一种程度较轻的群集现象，称为二次群集。

c.双重散列

双重散列所产生的排列具有随机选择的排列的许多特性，它采用如下形式的散列函数：

h(k,i)=(h1(k)+ih2(k)) mod m

其中 h1 和 h2 为普通散列函数，初始探查位置为 T[h1(k)]，后续探查位置在此基础上加上偏移量 h2(k)，这里的探查序列以两种方式依赖于关键字k，因为初始探查位置、偏移量都可能发生变化。

d.完全散列

当关键字集合是静态的时（指各关键字存入表中后，关键字集合就不再变化了）。如果某一种散列技术在进行查找时，其最坏情况内存访问次数为 O(1) 的话，则称其为完全散列。

设计一种完全散列：我们利用一种两级的散列方案，每一级都采用全域散列。

第一级与带链接的散列基本上是一样的：利用从某一全域散列函数族中仔细选出一个散列函数 h，将 n 个关键字映射到 m 个槽中。

对于第二级，我们不是对散列到槽j中的所有关键字建立一个链表，而是采用了一个较小的二次散列表 S，与其相关的散列函数 h1，可以确保在第二级上不出现碰撞。

本文作者：陈文龙（点融黑帮），现就职于点融网成都架构组担任研发工程师，平时喜欢听歌及户外运动。