2023年7月27日发(作者：)

哈希表与哈希（Hash）算法⼀、概述根据设定的哈希函数H（key）和处理冲突的⽅法将⼀组关键字影像到⼀个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为哈希表，这⼀映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。上⾯所提到的哈希函数是指：有⼀个对应关系

f ，使得每个关键字和结构中⼀个唯⼀的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进⾏⽐较，⽽是根据这个对应关系

f 找到给定值K的像f（K）。哈希函数也可叫哈希算法，它可以⽤于检验信息是否相同（⽂件校验），或者检验信息的拥有者是否真实（数字签名）。下⾯分别就哈希函数和处理冲突的⽅法进⾏讨论;⼆、哈希函数的构造⽅法构造哈希函数的⽅法有很多。在介绍各种⽅法前，⾸先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任⼀个关键字，经哈希函数映像到地址集合中任何⼀个地址的概率是相等的，则称此类哈希函数是均匀的（Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到⼀个“随机的地址”，以便使⼀组关键字的哈希地址均匀分布在整个地址区间中，从⽽减少冲突。常⽤的构造哈希函数的⽅法有：1. 直接定址法取关键字或关键字的某个线性函数值为哈希地址。即:H（key）=key 或 H（key） = a * key + b其中a 和 b为常数（这种哈希函数叫做⾃⾝函数）。例如：有⼀个1岁到100岁的⼈⼝数字统计表，其中，年龄作为关键字，哈希函数取关键字⾃⾝。如下表所⽰：地址年龄⼈数....这样若要询问25岁的⼈有多少，则只要查表的第25项即可。由于直接定址所得的地址集合和关键字集合的⼤⼩相同。因此，对于不同的关键字不会发⽣冲突，但是实际中能使⽤这种哈希函数的情况很少。2. 数字分析法假设关键字是以r为基数的数（如：以10为基的⼗进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若⼲数位组成哈希地址。例如有80个记录，其关键字为8位⼗进制数。假设哈希表的表长为10010，则可取两位⼗进制数组成哈希地址。那么取哪两位呢？原则是使⽤得到的哈希地址尽量避免产⽣冲突，则需从分析这80个关键字着⼿。假设这80个关键字中的⼀部分如下所列：对关键字的全体分析中我们发现：第①②位都是“8 1”，第③位只可能取1、2/3或4，第⑧位只可能取2、5或7，因此这4位都不可取。由于中间的4位都可看成是近乎随机的，因此可取其中任意两位，或取其中两位与另两位的叠加求和后舍去进位作为哈希地址。3. 平⽅取中法取关键字平⽅后的中间⼏位为哈希地址。这是⼀种较常⽤的构造哈希函数的⽅法。通常在选定哈希函数时不⼀定能知道关键字的全部情况，取其中哪⼏位也不⼀定合适，⽽⼀个数平⽅后的中间⼏位数和数的每⼀位都有关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。例如：为BASIC原程序中的标识符建⽴⼀个哈希表。假设BASIC语⾔中允许的标识符为⼀个字母，或⼀个字母和⼀个数字。在计算机内可⽤两位⼋进制数表⽰字母和数字，如图（a）所⽰。取标识符在计算机中的⼋进制数为它的关键字。假设表长为512=29，则可取关键字平⽅后的中间 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=7674686理论研究表明，除留余数法的模p取不⼤于表长且最接近表长m的素数效果最好，且p最好取1.1n ~ 1.7n之间的⼀个素数（n为存在的数据元素个数）。6. 随机数法选择⼀个随机函数，取关键字的随机函数值为它的哈希地址，即H（key）= random（key），其中random为随机函数。通常，当关键字长度不等时采⽤此法构造哈希函数较恰当。以上便是常⽤的6种构造哈希函数的⽅法，实际⼯作中需视不同的情况采⽤采⽤不同的哈希函数，通常考虑的因素有：计算哈希函数所需时间（包括硬件指令的因素）。关键字的长度。哈希表的⼤⼩。关键字的分布情况。记录的查找频率。三、处理冲突的⽅法前⾯有提到过均匀的哈希函数可以减少冲突，但不能避免，因此，如何处理冲突是哈希造表不可缺少的另⼀⽅⾯。通常⽤的处理冲突的⽅法有下列⼏种：1. 开放定址法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的位置。2. 再哈希法Hi = RHi(key) i = 1,2,...,kRHi均是不同的哈希函数，即在同义词产⽣地址冲突时计算另⼀个哈希函数地址，直到冲突不再发⽣。这个⽅法不易产⽣“聚集”，但增加了计算的时间。3. 链地址法将所有关键字为同义词的记录存储在同⼀线性链表中。假设某哈希函数产⽣的哈希地址在区间[0,m -1 ]上，则设⽴⼀个指针型向量Chain ChainHash[m]其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插⼊到头指针为ChainHash[i]的链表中。在链表中的插⼊位置可以在表头或表尾；也可以在中间，以保持同义词在同⼀线性链表中按关键字有序。4. 建⽴⼀个公共溢出区这也是处理冲突的⼀种⽅法、假设哈希函数的值域为[ 0, m - 1 ]，则设向量HashTable[ 0..m - 1 ]为基本表，每个分量存放⼀个记录，另设向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，⼀旦发⽣冲突，都填⼊溢出表。四、哈希表的查找及其分析在哈希表上进⾏查找的过程和哈希建表的过程基本⼀致。给定K值，根据建表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则⽐较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的⽅案找“下⼀地址”，直到找到为⽌。五、总结哈希函数构造⽅法：直接定址法、数字分析法、折叠法、平⽅取中法、除留余数法、随机数法。处理冲突⽅法：开放定址法、再哈希法、链地址法。开放定址法中di的3种取法：线性探测再散列，⼆次探测再散列，伪随机探测再散列。