第六章哈希表

6.5哈希表6.5哈希表(Hashtable)哈希又称散列，是一种重要的存储方法。如何体现记录在表中的位置与关键字之间的关系？应用搜索引擎中的查找编译器中的符号表图论中顶点的非数值表示与查找在线拼写检查

…

为今年招收的<=1000名新生建立查找表，关键字为学号，值的范围为j2005000~j2005999。

若以下标为000~999的顺序表表示。则查找过程可以简单进行：取给定值（学号）的后三位，便可直接从顺序表中找到待查关键字。基本思想以结点的关键字k为自变量，通过一个确定的哈希函数H，计算出对应的函数值H(k)，作为结点的存储位置并将结点存入。顺序查找、折半查找、树的查找是建立在比较基础上的查找，而哈希查找是直接查找。6.5哈希表(Hashtable)冲突和同义词若某个哈希函数H对于不同的关键字得到相同的哈希地址，称为冲突。发生冲突的这两个关键字则称为该哈希函数的同义词。6.5哈希表(Hashtable)已知关键字序列为（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=k

mod7通过哈希函数对6个元素建立哈希表：253923914冲突举例：H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4冲突！0123456在哈希查找方法中，冲突无法完全避免。构造好的哈希函数所选函数尽可能简单，以便提高转换速度；所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。制定好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询相关单元。6.5.1哈希函数的构造方法(1)直接定址法(2)除留余数法(3)数字分析法(4)平方取中法(5)折叠法(6)随机数法Hash(k)=a·k+b(a、b为常数)优点：以关键字的某个线性函数值为哈希地址，不会产生冲突；缺点：要占用连续地址空间，空间效率低。例：关键码集合为{100，300，500，700，800，900}，选取哈希函数为Hash(k)=k/100，则存储结构（哈希表）如下：0123456789900800700500300100（1）直接定址法Hash(k)=kmodp

(p是整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取p≤m且为质数。（2）除留余数法用某关键字的某几位组合成哈希地址。34705243491487348269634852703486305349805834796713473919例：80个关键字。（3）数字分析法①

第1、2位均是“3和4”，第3位只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。位号：①②③④⑤⑥⑦②若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址；也可取其中两位与其它两位叠加求和后，取低两位作哈希地址。特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。

例：2589的平方值为6702921，可以取中间的029为地址。（4）平方取中法（5）折叠法特点：将关键码自左到右分成位数相等的几部分，然后叠加求和，并按哈希表表长，取后几位作为哈希地址。例：元素42751896。用法1：427＋518＋96=1041

用法2：42751896→724+518+69=1311（6）随机数法Hash(k)=random(k)(random为伪随机函数)适用于：关键字长度不等的情况。优点：造表和查找都很方便。6.5.2冲突处理方法（1）开放定址法（开地址法）（2）链地址法（拉链法）（3）再哈希法（双哈希函数法）（4）建立一个公共溢出区（1）开放定址法（开地址法）线性探测法二次探测法伪随机探测法Hi=(Hash(k)+di)mod

m(1≤i<m)其中：

Hash(k)为哈希函数

m为哈希表长度

di

为增量序列1，2，…，m-1，且di

=i线性探测法例题已知哈希表的空间为0-14，将关键字序列（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数H(k)=k%13和线性探测法处理冲突构造哈希表。（19,14,23,01,68,20,84,27,55,11,10,79）01234567891011121314H(19)=19%13=619H(14)=14%13=114H(23)=23%13=1023H(01)=01%13=1H1=(1+1)%15=21H(68)=68%13=368H(20)=20%13=720H(84)=84%13=6H1=(6+1)%15=7H2=(6+2)%15=884H(27)=27%13=1H1=(1+1)%15=2H2=(1+2)%15=3H3=(1+3)%15=427H(55)=55%13=3H1=(3+1)%15=4H2=(3+2)%15=555H(11)=11%13=1111H1=(10+1)%15=11H2=(10+2)%15=12H(10)=10%13=1010H3=(1+3)%15=4H1=(1+1)%15=2H2=(1+2)%15=3H(79)=79%13=1H4=(1+4)%15=5H5=(1+5)%15=6H6=(1+6)%15=7H7=(1+7)%15=8H8=(1+8)%15=979练习

已知一组关键字为（39,23,41,38,44,15,68,12,06,51,25），求按哈希函数H(k)=k%13和线性探测法处理冲突构造所得的哈希表HT[0..14]。

012345678910111213143925411568440623381251优点：只要哈希表未被填满，一定能找到一个空地址单元存放冲突元素；缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词。因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，降低查找效率。解决方案：采用二次探测法或伪随机探测法。线性探测法优缺点二次探测法Hi=(Hash(k)±di)mod

m其中：di为增量序列：12，-12，22，-22，…，q2。伪随机探测法Hi=(Hash(k)±di)mod

m其中：di为伪随机序列。

已知哈希表的空间为0-14，将关键字序列（19,14,23,01,68,20,84,27,55,11,10）按哈希函数H(k)=k%13和二次探测法处理冲突构造哈希表。例题（19,14,23,01,68,20,84,27,55,11,10）01234567891011121314H(19)=19%13=619H(14)=14%13=114H(23)=23%13=1023H(01)=01%13=1H1=(1+1)%15=201H(68)=68%13=368H(20)=20%13=720H1=(6+1)%15=7H(84)=84%13=6H2=(6-1)%15=584H1=(1+1)%15=2H(27)=27%13=1H2=(1-1)%15=027H1=(3+1)%15=4H(55)=27%13=355H(11)=11%13=1111H2=(10-1)%15=9H1=(10+1)%15=11H(10)=10%13=1010

将所有同义词结点链接在同一个单链表中。若哈希函数的值域为0到m-1，将散列表定义为一个由m个头指针组成的指针数组HT[m]，凡是散列地址为i的结点，均插入到以HT[i]为头指针的单链表中。（2）链地址法已知哈希表的空间为0-14，将关键字序列（19,14,23,01,68,20,84,27,55,11,10）按哈希函数H(key)=key%13和链地址法处理冲突构造所得的哈希表。例题（19,14,23,01,68,20,84,27,55,11,10）0123456789101112H(19)=19%13=6H(14)=14%13=1H(23)=23%13=10H(01)=01%13=1H(68)=68%13=3H(20)=20%13=7H(84)=84%13=6H(27)=27%13=1H(55)=55%13=3H(11)=11%13=11H(10)=10%13=101914230168208427551110^^^^^^^^^^^^^Hi=RHi(k)i=1,2,…,kRHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。优点：不易产生聚集；缺点：增加了计算时间。（3）再哈希法（双哈希函数法）

除设立哈希基本表外，另设立一个溢出向量表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。（4）建立一个公共溢出区6.5.3哈希表的查找及分析

（1）散列函数没有“万能”公式，要根据元素集合的特性而分别构造。

（2）哈希查找的速度是否为真正的O(1)?

不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，用平均查找长度ASL和装填因子α来衡量。6.5.3哈希表的查找及分析

（1）散列函数没有“万能”公式，要根据元素集合的特性而分别构造。

（2）哈希查找的速度是否为真正的O(1)?

不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，用平均查找长度ASL和装填因子α来衡量。

已知哈希表的空间为0-14，将关键字序列（19,14,23,01,68,20,84,27,55,11,10,79）按哈希函数H(key)=key%13和线性探测法处理冲突构造哈希表，并求出在等概率情况下的查找成功和查找不成功的平均查找长度。练习：（19,14,23,01,68,20,84,27,55,11,10,79）1234567891011121314比较次数H(19)=19%13=619H(14)=14%13=114H(23)=23%13=1023H(01)=01%13=1H1=(1+1)%15=21H(68)=68%13=368H(20)=20%13=720H(84)=84%13=6H1=(6+1)%15=7H2=(6+2)%15=884H(27)=27%13=1H3=(1+3)%15=427H(55)=55%13=3H1=(3+1)%15=4H2=(3+2)%15=555H(11)=11%13=1111H1=(10+1)%15=11H2=(10+2)%15=12H(10)=10%13=1010H2=(1+2)%15=3H(79)=79%13=1H4=(1+4)%15=5H5=(1+5)%15=6H6=(1+6)%15=7H7=(1+7)%15=8H8=(1+8)%15=9791112113431390查找成功时的平均查找长度：查找不成功时的平均查找长度：1234567