前言

部分内容摘自程杰的《大话数据结构》

1. 散列表查找（哈希表）概述

在前面的顺序表查找中，我们曾经说过，如果你要查找某个关键字的记录，就是从表头开始，挨个的比较记录a[i]与key的值是 “ $=$ ” 还是 “ $\neq$ ”，直到有相等才算是查找成功，返回i。到了有序表查找时，我们可以利用a[i]与key的 “ $<$ ” 或 “ $>$ ” 来折半查找，直到相等时查找成功返回i。最终我们的目的都是为了找到那个i，其实也就是相对的下标，再通过顺序存储的存储位置计算方法， $LOC(a_i)=LOC(a_i)+(i-1)\times c$ ，也就是通过第一个元素内存存储位置加上i-1个单元位置，得到最后的内存地址。
此时我们发现，为了查找到结果，之前的方法 “比较” 都是不可避免的，但这是否真的有必要？能否直接通过关键字key得到要查找的记录内存存储位置呢？

1.1 散列表查找定义

试想这样的场景，你很想学太极拳，听说学校有个叫张三丰的人打得特别好，于是你到学校学生处找人，学生处的工作人员可能会拿出学生名单，一个一个的查找，最终告诉你，学校没这个人，并说张三丰几百年前就已经在武当山作古了。可如果你找对了人，比如在操场上找那些爱运动的同学，人家会告诉你，“哦，你找张三丰呀，有有有，我带你去。” 于是他把你带到了体育馆内，并告诉你，那个教大家打太极的小伙子就是 “张三丰”，原来 “张三丰” 是因为他太极拳打得好而得到的外号。
学生处的老师找张三丰，那就是顺序表查找，依赖的是姓名关键字的比较。而通过爱好运动的同学询问时，没有遍历，没有比较，就凭他们 “欲找太极‘张三丰’，必在体育馆当中” 的经验，直接告诉你位置。
也就是说，我们只需要通过某个函数 $f$ ，使得

$存储位置=f（关键字）$

那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。这就是一种新的存储技术——散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 $f$ ，使得每个关键字key对应一个存储位置 $f$ （key）。查找时，根据这个确定的对应关系找到给定值key的映射 $f$ （key），若查找集合中存在这个记录，则必定在 $f$ （key）的位置上。
这里我们把这种对应关系 $f$ 称为散列函数，又称为哈希（Hash）函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。那么关键字对应的记录存储位置我们称为散列地址。

1.2 散列表查找步骤

整个散列过程其实就是两步。

在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。就像张三丰我们就让他在体育馆，那如果是 ‘爱因斯坦’ 我们让他在图书馆，如果是 ‘居里夫人’，那就让她在化学实验室，如果是 ‘巴顿将军’，这个打仗的将军——我们可以让他到网吧。总之，不管什么记录，我们都需要用同一个散列函数计算出地址再存储。
当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。说起来很简单，在哪存的，上哪去找，由于存取用的是同一个散列函数，因此结果当然也是相同的。

所以说，散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。
散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率就会大大提高。但万事有利就有弊，散列技术不具备很多常规数据结构的能力。
比如那种同样的关键字，它能对应很多记录的情况，却不适合用散列技术。一个班级几十个学生，他们的性别有男有女，你用关键字 “男” 去查找，对应的有许多学生的记录，这显然是不合适的。只有如用班级学生的学号或者身份证号来散列存储，此时一个号码唯一对应一个学生才比较合适。
同样散列表也不适合范围查找，比如查找一个班级 18~22 岁的同学，在散列表中没法进行。想获得表中记录的排序也不可能，像最大值、最小值等结果也都无法从散列表中计算出来。
说了这么多，散列函数应该如何设计？这个需要重点来讲解，总之设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。
另一个问题是冲突。在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字 key $_1\neq$ key $_2$ ，但是却有 $f$ （key $_1$ ） $=$ $f$ （key $_2$ ），这种现象我们称为冲突（collision），并把 key $_1$ 和 key $_2$ 称为这个散列函数的同义词（synonym）。出现了冲突当然非常糟糕，那将造成数据查找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少，但是不能完全避免。于是如何处理冲突就成了一个很重要的问题，这在我们后面也需要详细讲解。

2. 散列函数的构造方法

不管做什么事要达到最优都不容易，既要付出尽可能的少，又要得到最大化的多。那么什么才算是好的散列函数呢？这里我们有两个原则可以参考。

计算简单
你说设计一个算法可以保证所有的关键字都不会产生冲突，但是这个算法需要很复杂的计算，会耗费很多时间，这对于需要频繁地查找来说，就会大大降低查找的效率了。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
散列地址分布均匀
我们刚才也提到冲突带来的问题，最好的办法就是尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。

接下来我们就要介绍几种常用的散列函数构造方法。估计设计这些方法的前辈们当年可能是从事间谍工作，因为这些方法都是将原来数字按某种规律变成另一个数字而已。

2.1 直接定址法

如果我们现在要对 0~100 岁的人口数字统计表，如下表所示，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时 $f$ （key） $=$ key。

如果我们现在要统计的是 80 后出生年份的人口数，如下表所示，那么我们对出生年份这个关键字可以用年份减去 1980 来作为地址。此时 $f$ （key） $=$ key $-$ 1980。

也就是说，我们可以取关键字的某个线性函数值为散列地址，即

$f（key）=a\times key+b（a、b为常数）$

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

2.2 数字分析法

如果我们的关键字是位数较多的数字，比如我们的 11 位手机号 “130××××1234”，其中前三位是接入号，一般对应不同运营商公司的子品牌，如 130 是联通如意通、136 是移动神州行、153 是电信等；中间四位是HLR识别号，表示用户号的归属地；后四位才是真正的用户号，如下表所示。

若我们现在要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前 7 位都是相同的。那么我们选择后面的四位成为散列地址就是不错的选择。如果这样的抽取工作还是容易出现冲突问题，还可以对抽取出来的数字再进行反转（如 1234 改成 4321）、右环位移（如 1234 改成 4123）、左环位移、甚至前两数与后两数叠加（如 1234 改成 12+34=46）等方法。总的目的就是为了提供一个散列函数，能够合理地将关键字分配到散列表的各位置。
这里我们提到了一个关键词——抽取。抽取方法是使用关键字的一部分来计算散列存储位置的方法，这在散列函数中是常常用到的手段。
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

2.3 平方取中法

这个方法计算很简单，假设关键字是 1234，那么它的平方就是 1522756，再抽取中间的 3 位就是 227，用做散列地址。再比如关键字是 4321，那么它的平方就是18671041，抽取中间的 3 位就可以是 671，也可以是 710，用做散列地址。平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

2.4 折叠法

折叠法是将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是 9876543210，散列表表长为三位，我们将它分为四组，987|654|321|0，然后将它们叠加求和 987+654+321+0=1962，再求后 3 位得到散列地址为 962。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如我们将 987 和 321 反转，再与 654 和 0 相加，变成 789+654+123+0=1566，此时散列地址为 566。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

2.5 除留余数法

此方法为最常用的构造散列函数方法。对于散列表长为 $m$ 的散列函数公式为：

$f(key)=$ key mod $p$ $(p\leq m)$

mod是取模（求余数）的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
很显然，本方法的关键就在于选择合适的 $p$ ， $p$ 如果选得不好，就可能会容易产生同义词。
例如下表，我们对于有 12 个记录的关键字构造散列表时，就用了 $f(key)$ = key mod 12 的方法。比如29 mod 12=5，所以它存储在下标为 5 的位置。

不过这也是存在冲突的可能的，因为 12=2×6=3×4。如果关键字中有像 18（3×6）、30（5×6）、42（7×6）等数字，它们的余数都为 6，这就和 78 所对应的下标位置冲突了。
甚至极端一些，对于下表的关键字，如果我们让 $p$ 为 12 的话，就可能出现下面的情况，所有的关键字都得到了 0 这个地址数，这未免也太糟糕了点。

此就只有 12 和 144 有冲突，相对来说，就要好很多。
因此根据前辈们的经验，若散列表表长为 $m$ ，通常 $p$ 为小于或等于表长（最好接近 $m$ ）的最小质数或不包含小于 20 质因子的合数。

2.6 随机数法

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是 $f$ (key)=random(key)。这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
有同学问，那如果关键字是字符串如何处理？其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来对待，比如ASCII码或者Unicode码等，因此也就可以使用上面的这些方法。
总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考：

计算散列地址所需的时间。
关键字的长度。
散列表的大小。
关键字的分布情况。
记录查找的频率。

综合这些因素，才能决策选择哪种散列函数更合适。

3. 处理散列冲突的方法

从刚才除留余数法的例子也可以看出，我们设计得再好的散列函数也不可能完全避免冲突，这就像我们再健康也只能尽量预防疾病，但却无法保证永远不得病一样，既然冲突不能避免，就要考虑如何处理它。
那么当我们在使用散列函数后发现两个关键字 key $_1$ $\neq$ key $_2$ ，但是却有 $f$ (key $_1$ ) = $f$ (key $_2$ )，即有冲突时，怎么办呢？我们可以从生活中找寻思路。
试想一下，当你观望很久很久，终于看上一套房打算要买了，正准备下订金，人家告诉你，这房子已经被人买走了，你怎么办？
对呀，再找别的房子呗！这其实就是一种处理冲突的方法——开放定址法。

3.1 开放定址法

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
它的公式是：

$f_i$ (key) = ( $f$ (key)+d $_i$ ) MOD m (d $_i$ =1, 2, 3, ···, m-1 )

比如说，我们的关键字集合为 {12,67,56,16,25,37,22,29,15,47,48,34}，表长为 12。我们用散列函数 $f$ (key) =key mod 12。
当计算前 5 个数 {12,67,56,16,25} 时，都是没有冲突的散列地址，直接存入，如下表所示。

计算key=37时，发现 $f$ (37) =1，此时就与 25 所在的位置冲突。于是我们应用上面的公式 $f$ (37) = ( $f$ (37)+1) mod 12=2。于是将 37 存入下标为 2 的位置。这其实就是房子被人买了于是买下一间的作法，如下表所示。

接下来 22,29,15,47 都没有冲突，正常的存入，如下表所示。

到了key=48，我们计算得到 $f$ (48) =0，与 12 所在的 0 位置冲突了，不要紧，我们 $f$ (48) = ( $f$ (48)+1) mod 12=1，此时又与 25 所在的位置冲突。于是 $f$ (48) = ( $f$ (48) +2) mod 12=2，还是冲突······一直到 $f$ (48) = ( $f$ (48)+6) mod12=6 时，才有空位，机不可失，赶快存入，如下表所示。

我们把这种解决冲突的开放定址法称为线性探测法。
从这个例子我们也看到，我们在解决冲突的时候，还会碰到如 48 和 37 这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。
考虑深一步，如果发生这样的情况，当最后一个 key=34， $f$ (key)=10，与 22 所在的位置冲突，可是 22 后面没有空位置了，反而它的前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差。因此我们可以改进 d $_i$ =1 $^2$ , -1 $^2$ , 2 $^2$ , -2 $^2$ , ···, $q^2$ , $-q^2$ , $(q≤m/2)$ ，这样就等于是可以双向寻找到可能的空位置。对于 34 来说，我们取 d $_i$ =-1 即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。

$f_i$ (key) = ( $f$ (key) + $d_i$ ) MOD $m$ ( $d_i$ =1^2^, -1^2^, 2^2^, -2^2^, ···, $q^2$ , $-q^2$ , $q≤m/2$ )

还有一种方法是，在冲突时，对于位移量 $d_i$ 采用随机函数计算得到，我们称之为随机探测法。
此时一定有人问，既然是随机，那么查找的时候不也随机生成 $d_i$ 吗？如何可以获得相同的地址呢？这是个问题。这里的随机其实是伪随机数。伪随机数是说，如果我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在查找时，用同样的随机种子，它每次得到的数列是相同的，相同的 $d_i$ 当然可以得到相同的散列地址。

$f_i$ (key) = ( $f$ (key) + $d_i$ ) MOD $m$ ( $d_i$ 是一个随机数列)

总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。

3.2 再散列函数法

我们继续用买房子来举例，如果你看房时的选择标准总是以市中心、交通便利、价格适中为指标，这样的房子凤毛麟角，基本上当你看到时，都已经被人买去了。
我们不妨换一种思维，选择市郊的房子，交通尽管要差一些，但价格便宜很多，也许房子还可以买得大一些、质量好一些，并且由于更换了选房的想法，很快就找到了你需要的房子了。
对于我们的散列表来说，我们事先准备多个散列函数。

$f_i(key)=RH (key) (i=1,2,···,k)$

这里 RH $_i$ 就是不同的散列函数，你可以把我们前面说的什么除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。

3.3 链地址法

思路还可以再换一换，为什么有冲突就要换地方呢，我们直接就在原地想办法不可以吗？于是我们就有了链地址法。
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于关键字集合 {12,67,56,16,25,37,22,29,15,47,48,34}，我们用前面同样的 12 为除数，进行除留余数法，可得到如下图结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。

链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。

3.4 公共溢出区法

这个方法其实就更加好理解，你不是冲突吗？好吧，凡是冲突的都跟我走，我给你们这些冲突找个地儿待着。这就如同孤儿院收留所有无家可归的孩子一样，我们为所有冲突的关键字建立了一个公共的溢出区来存放。
就前面的例子而言，我们共有三个关键字 {37,48,34} 与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如下图所示。

在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

4. 散列表查找的实现

4.1 散列表查找的算法实现

首先是需要定义一个散列表的结构以及一些相关的常数。其中HashTable就是散列表结构。结构当中的elem为一个动态数组。

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12	/* 定义散列表长为数组的长度 */
#define NULLKEY -32768

typedef struct
{
	int elem;	/* 数据元素存储基址，动态分配数组 */
	int count;	/* 当前数据元素个数 */
}HashTable;

int m=0;	/* 散列表表长，全局变量 */

有了结构的定义，我们可以对散列表进行初始化。

/* 初始化散列表 */
Status InitHashTable ( HashTable *H)
{
	int i;
	m=HASHSIZE;
	H->count=m;
	H->elem=(int *)malloc(m*sizeof(int));
	for (i=0;i<m;i++)
		H->elem[i]=NULLKEY;
	return OK;
}

为了插入时计算地址，我们需要定义散列函数，散列函数可以根据不同情况更改算法。

/* 散列函数 */
int Hash(int key)
{
	return key %m;/*c除留余数法c*/
}

初始化完成后，我们可以对散列表进行插入操作。假设我们插入的关键字集合就是前面的 {12,67,56,16,25,37,22,29,15,47,48,34}。

/* 插入关键字进散列表 */
void InsertHash(HashTable *H,int key)
{
	int addr = Hash(key);	/* 求散列地址 */
	while (H->e1em[addr] != NULLKEY)	/* 如果不为空，则冲突 */
	{
		addr = (addr+1) % m;	/* 开放定址法的线性探测 */
	}
	H->elem[addr] = key;	/* 直到有空位后插入关键字 */
}

代码中插入关键字时，首先算出散列地址，如果当前地址不为空关键字，则说明有冲突。此时我们应用开放定址法的线性探测进行重新寻址，此处也可更改为链地址法等其他解决冲突的办法。
散列表存在后，我们在需要时就可以通过散列表查找要的记录。

/* 散列表查找关键字 */
Status SearchHash ( HashTable H,int key, int *addr )
addr = Hash (key) :
/*求散列地址*/
while (H.elem[*addr] !- key) /* 如果不为空，则冲突*/
*addr = ( *addr+1)号m;
/*开放定址法的线性探测*/
if (H.elem[*addr] NULLKEY 11 *addr -- Hash (key) )
{/*如果循环回到原点*/
return UNSUCCESS:
/*则说明关键宇不存在*/ 
return SUCCESS:

查找的代码与插入的代码非常类似，只需做一个不存在关键字的判断而已。

4.2 散列表查找性能分析

最后，我们对散列表查找的性能作一个简单分析。如果没有冲突，散列查找是我们本章介绍的所有查找中效率最高的，因为它的时间复杂度为 $O(1)$ 。可惜，我说的只是 “如果”，没有冲突的散列只是一种理想，在实际的应用中，冲突是不可避免的。那么散列查找的平均查找长度取决于哪些因素呢？

散列函数是否均匀
散列函数的好坏直接影响着出现冲突的频繁程度，不过，由于不同的散列函数对同一组随机的关键字，产生冲突的可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。
处理冲突的方法
相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。
散列表的装填因子
所谓的装填因子 $\alpha$ = 填入表中的记录个数/散列表长度。 $\alpha$ 标志着散列表的装满的程度。当填入表中的记录越多， $\alpha$ 就越大，产生冲突的可能性就越大。比如我们前面的例子，如前面链地址法的图所示，如果你的散列表长度是 12，而填入表中的记录个数为 11，那么此时的装填因子 $\alpha$ =11/12=0.9167，再填入最后一个关键字产生冲突的可能性就非常之大。也就是说，散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。