一、概述
根据设定的哈希函数H（key）和处理冲突的方法将一组关键字影像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
上面所提到的哈希函数是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像f（K）。
哈希函数也可叫哈希算法，它可以用于检验信息是否相同（文件校验），或者检验信息的拥有者是否真实（数字签名）。
下面分别就哈希函数和处理冲突的方法进行讨论;
二、哈希函数的构造方法
构造哈希函数的方法有很多。在介绍各种方法前，首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。
常用的构造哈希函数的方法有：
-
直接定址法
取关键字或关键字的某个线性函数值为哈希地址。即:
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项即可。
由于直接定址所得的地址集合和关键字集合的大小相同。因此，对于不同的关键字不会发生冲突，但是实际中能使用这种哈希函数的情况很少。 -
数字分析法
假设关键字是以r为基数的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。例如有80个记录，其关键字为8位十进制数。假设哈希表的表长为10010，则可取两位十进制数组成哈希地址。那么取哪两位呢？原则是使用得到的哈希地址尽量避免产生冲突，则需从分析这80个关键字着手。假设这80个关键字中的一部分如下所列：
对关键字的全体分析中我们发现：第①②位都是“8 1”，第③位只可能取1、2/3或4，第⑧位只可能取2、5或7，因此这4位都不可取。由于中间的4位都可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另两位的叠加求和后舍去进位作为哈希地址。 -
平方取中法
取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都有关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。例如：为BASIC原程序中的标识符建立一个哈希表。假设BASIC语言中允许的标识符为一个字母，或一个字母和一个数字。在计算机内可用两位八进制数表示字母和数字，如图（a）所示。取标识符在计算机中的八进制数为它的关键字。假设表长为512=29，则可取关键字平方后的中间 9 位二进制数作为哈希地址。例如图（b）列出了一些标识符及他们的哈希地址。
-
折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这种方法称为折叠法（folding）。关键字位数很多，而且关键字中每一位数字分布大致均匀时，可以采用折叠法得到哈希地址。例如：每一中西文图书都有一个国际标准图书编号（ISBN），它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到 10000 时，可采用折叠法构造一个四位数的哈希函数。在折叠法中数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。如国际标准图书编号
0-442-20586-4的哈希地址分别如图 （a）和（b）所示。
-
除留余数法
取关键字被某个不大于哈希表表长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=70 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90
理论研究表明，除留余数法的模p取不大于表长且最接近表长m的素数效果最好，且p最好取1.1n ~ 1.7n之间的一个素数（n为存在的数据元素个数）。
-
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H（key）= random（key），其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。
以上便是常用的6种构造哈希函数的方法，实际工作中需视不同的情况采用采用不同的哈希函数，通常考虑的因素有：
- 计算哈希函数所需时间（包括硬件指令的因素）。
- 关键字的长度。
- 哈希表的大小。
- 关键字的分布情况。
- 记录的查找频率。
三、处理冲突的方法
前面有提到过均匀的哈希函数可以减少冲突，但不能避免，因此，如何处理冲突是哈希造表不可缺少的另一方面。
通常用的处理冲突的方法有下列几种：
-
开放定址法
Hi = (H(key) + di) MOD m i = 1,2,...,k ( k ≤ m-1)
其中：H(key)为哈希函数；m 为哈希表表长；di为增量序列，可有下列3种取法：(1). di=1,2,3,...,m-1,称线性探测再散列。
(2). di=12, -12, 22, -22,..., ±k2 ( k ≤ m/2)称二次探测再散列。
(3). di=伪随机数序列,称伪随机探测再散列。例如，在长度为11的哈希表中已填有关键字分别为17,60,29的记录（哈希函数
H(key) = key MOD 11），现有第四个记录，其关键字为38，由哈希函数得到哈希地址为5，产生冲突。若用线性探测再散列方法处理，得到下一个地址为6，仍冲突，继续算7，仍冲突，知道最后算出8，填入哈希表。若用二次三册再散列，则应填入需要为4的位置。
再哈希法
Hi = RHi(key) i = 1,2,...,k
RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这个方法不易产生“聚集”，但增加了计算的时间。链地址法
将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间[0,m -1 ]上，则设立一个指针型向量
Chain ChainHash[m]
其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在链表中的插入位置可以在表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。建立一个公共溢出区
这也是处理冲突的一种方法、假设哈希函数的值域为[ 0, m - 1 ]，则设向量HashTable[ 0..m - 1 ]为基本表，每个分量存放一个记录，另设向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
四、哈希表的查找及其分析
在哈希表上进行查找的过程和哈希建表的过程基本一致。给定K值，根据建表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方案找“下一地址”，直到找到为止。
五、总结
- 哈希函数构造方法：直接定址法、数字分析法、折叠法、平方取中法、除留余数法、随机数法。
- 处理冲突方法：开放定址法、再哈希法、链地址法。
- 开放定址法中di的3种取法：线性探测再散列，二次探测再散列，伪随机探测再散列。
