哈希表与哈希（Hash）算法

一、概述

根据设定的哈希函数H（key）和处理冲突的方法将一组关键字影像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

上面所提到的哈希函数是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像f（K）。

哈希函数也可叫哈希算法，它可以用于检验信息是否相同（文件校验），或者检验信息的拥有者是否真实（数字签名）。

下面分别就哈希函数和处理冲突的方法进行讨论;

二、哈希函数的构造方法

构造哈希函数的方法有很多。在介绍各种方法前，首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。
常用的构造哈希函数的方法有：

1. 直接定址法
   取关键字或关键字的某个线性函数值为哈希地址。即:
   H（key）=key 或 H（key） = a * key + b
   其中a 和 b为常数（这种哈希函数叫做自身函数）。

   例如：有一个1岁到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。如下表所示：

   地址	01	02	03	...	25	26	27	...	100
   年龄	1	2	3	...	25	26	27	...	100
   人数	3000	2000	5000	...	1050	...	...	...	...
   ...

   这样若要询问25岁的人有多少，则只要查表的第25项即可。
   由于直接定址所得的地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突，但是实际中能使用这种哈希函数的情况很少。

2. 数字分析法
   假设关键字是以r为基数的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

   例如有80个记录，其关键字为8位十进制数。假设哈希表的表长为100₁₀，则可取两位十进制数组成哈希地址。那么取哪两位呢？原则是使用得到的哈希地址尽量避免产生冲突，则需从分析这80个关键字着手。假设这80个关键字中的一部分如下所列：
   

   
   对关键字的全体分析中我们发现：第①②位都是“8 1”，第③位只可能取1、2/3或4，第⑧位只可能取2、5或7，因此这4位都不可取。由于中间的4位都可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另两位的叠加求和后舍去进位作为哈希地址。

3. 平方取中法
   取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都有关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

   例如：为BASIC原程序中的标识符建立一个哈希表。假设BASIC语言中允许的标识符为一个字母，或一个字母和一个数字。在计算机内可用两位八进制数表示字母和数字，如图（a）所示。取标识符在计算机中的八进制数为它的关键字。假设表长为512=2⁹，则可取关键字平方后的中间 9 位二进制数作为哈希地址。例如图（b）列出了一些标识符及他们的哈希地址。
   

   

4. 折叠法
   将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这种方法称为折叠法（folding）。关键字位数很多，而且关键字中每一位数字分布大致均匀时，可以采用折叠法得到哈希地址。

   例如：每一中西文图书都有一个国际标准图书编号（ISBN），它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到 10000 时，可采用折叠法构造一个四位数的哈希函数。在折叠法中数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。如国际标准图书编号0-442-20586-4的哈希地址分别如图 （a）和（b）所示。
   

   

5. 除留余数法
   取关键字被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即
   H（key） = key MOD p ， p ≤ m
   这是一种最简单，也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模（MOD），也可以在折叠、平方取中等运算之后取模。
   值得注意的是，在使用除留余数法时，对p的选择很重要。若p选的不好，容易产生同义词。

   例如，已知散列元素为（18、75、60、43、54、90、46），表长m= 10，p = 7，则有
   h(18)=18 % 7=4 ， h(75)=75 % 7=5 ， h(60)=60 % 7=4 ，
   h(43)=43 % 7=1 ， h(54)=54 % 7=5 ， h(90)=90 % 7=6 ，
   h(46)=46 % 7=4
   由于冲突较多，为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：
   h(18)=18 % 13=5 ， h(75)=75 % 13=10， h(60)=60 % 13=8 ，
   h(43)=43 % 13=4 ， h(54)=54 % 13=2 ， h(90)=90 % 13=12 ，
   h(46)=46 % 13=7

   0	1	2	3	4	5	6	7	8	9	10	11	12
   		54		43	18		46	60		75		90

理论研究表明，除留余数法的模p取不大于表长且最接近表长m的素数效果最好，且p最好取1.1ⁿ ~ 1.7ⁿ之间的一个素数（n为存在的数据元素个数）。

6. 随机数法
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H（key）= random（key），其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。

以上便是常用的6种构造哈希函数的方法，实际工作中需视不同的情况采用采用不同的哈希函数，通常考虑的因素有：

• 计算哈希函数所需时间（包括硬件指令的因素）。
• 关键字的长度。
• 哈希表的大小。
• 关键字的分布情况。
• 记录的查找频率。

三、处理冲突的方法

前面有提到过均匀的哈希函数可以减少冲突，但不能避免，因此，如何处理冲突是哈希造表不可缺少的另一方面。

通常用的处理冲突的方法有下列几种：

1. 开放定址法
   H_i = (H(key) + d_i) MOD m i = 1,2,...,k ( k ≤ m-1)
   其中：H(key)为哈希函数；m 为哈希表表长；d_i为增量序列，可有下列3种取法：

   (1). d_i=1,2,3,...,m-1,称线性探测再散列。
   (2). d_i=1², -1², 2², -2²,..., ±k² ( k ≤ m/2)称二次探测再散列。
   (3). d_i=伪随机数序列,称伪随机探测再散列。

   例如，在长度为11的哈希表中已填有关键字分别为17,60,29的记录（哈希函数 H(key) = key MOD 11），现有第四个记录，其关键字为38，由哈希函数得到哈希地址为5，产生冲突。若用线性探测再散列方法处理，得到下一个地址为6，仍冲突，继续算7，仍冲突，知道最后算出8，填入哈希表。若用二次三册再散列，则应填入需要为4的位置。
   

   

2. 再哈希法
   H_i = RH_i(key) i = 1,2,...,k
   RH_i均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这个方法不易产生“聚集”，但增加了计算的时间。

3. 链地址法
   将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间[0,m -1 ]上，则设立一个指针型向量
   Chain ChainHash[m]
   其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在链表中的插入位置可以在表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。

4. 建立一个公共溢出区
   这也是处理冲突的一种方法、假设哈希函数的值域为[ 0, m - 1 ]，则设向量HashTable[ 0..m - 1 ]为基本表，每个分量存放一个记录，另设向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。

四、哈希表的查找及其分析

在哈希表上进行查找的过程和哈希建表的过程基本一致。给定K值，根据建表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方案找“下一地址”，直到找到为止。

五、总结

• 哈希函数构造方法：直接定址法、数字分析法、折叠法、平方取中法、除留余数法、随机数法。
• 处理冲突方法：开放定址法、再哈希法、链地址法。
• 开放定址法中d_i的3种取法：线性探测再散列，二次探测再散列，伪随机探测再散列。