哈希表查找课件

知识回顾：上堂课我们学习了三种查找方法：新课引入：理想的情况是依据关键码直接得到其对应的数据元素存储位置，本堂课要讲的哈希表查找方法就属于此情况。顺序查找：折半查找：上述三种查找方法都是建立在比较基础之上的，查找效率由比较一次后缩小的查找范围决定。分块查找：什么是哈希表9.3.19.3哈希表

主要内容

哈希函数的构造方法9.3.2处理冲突的方法9.3.3哈希表的查找及其分析9.3.49.3.1什么是哈希表【例】关键码序列为{18，27，1，20，22，6，10，13，41，15，25}。设关键码与元素存储位置的函数为f(key)=keymod11。

选取某个函数f(key)

，依该函数关键码计算元素的存储位置，并按此存放；查找时，用同一个函数对给定值kx计算地址，将kx与地址单元中元素关键字进行比较，确定查找是否成功，这就是哈希方法，哈希方法中使用的转换函数f(key)称为哈希函数，按这个思想构造的表称为哈希表。则这11个元素通过f(key)函数映射可建立如下的查找表：22113251527618412010012345678910“冲突”现象：即key1≠key2，而f(key1)=f(key2)。同义词：产生“冲突”现象的词。由于改进哈希函数只能减少冲突，不能避免冲突，因此，哈希方法需解决以下二个问题：2）选择一种好的处理冲突方法1）构造“好”的哈希函数所选函数尽可能简单，以便提高转换效率。所选函数对关键码计算出的地址，应在哈希地址中大致均匀分布，以减少空间浪费。9.3.2哈希函数的构造方法常用的哈希函数有：1.直接定址法5.除留余数法2.数字分析法(略)

3.平方取中法

(略)4.折叠法

(略)

6.随机数法(略)

1.直接定址法哈希函数为关键码的线性函数，即：H(key)=a×key+b(a，b为常数)。【例9-6】若key={100,300,500,700,800,900}H(key)=key/100，1003005007008009000123456789则关键码存储格式如下：5.除留余数法H(key)=keyMODp(p是一个整数)关键问题是：如何选取p?一般情况。可以选p为不大于表长m

的质数，或者是不包含小于20的质因子的合数。例如：关键码key=12,39,18,24,33,21时，若取p=9。则关键码的地址如下所示：出现的问题：使所有含质因子3的关键字均映射到地址3,6上，从而增加了“冲突”现象。1812,39,2124,3301234567899.3.3处理冲突的方法处理冲突：是指为产生冲突的地址寻找下一个空的哈希地址。方法有：开放定址法、再哈希法、拉链法、建立一个公共溢出区。开放定址法：为产生冲突的地址H(key)求得一个探测地址序列：

H0,H1,H2,…,Hs（1≤s≤m-1）。其中：

H0=H(key)，Hi=(H(key)+di)MODmi=1,2,…,s。增量di有四种取法：（1）线性探测法（2）二次（平方）探测法（3）哈希函数探测法（略）（4）随机函数探测法（略）（1）线性探测法：di=c*i最简单的情况c=1【例9-7】

key={47,7,29,11,16,92,22,8,3}，哈希表长度为11，H(key)=keymod11，用线性探测法处理冲突，建表如下：012345678910112247921637298（2）二次（平方）探测法：di=12,-12,22,-22,…,【例9-8】仍以上述例子用二次探测法处理冲突，建表如下：01234567891011223479216

72983.链地址法

将所有哈希地址相同的关键码都链接在同一链表中。假设某哈希函数产生的哈希地址在区间[0，m-1]上，则设立一个指针型向量DataType*Hash[m]其每一个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为Hash[i]的链表中。插入位置可以在表尾、表头、或表中，以保持同义词在同一线性链表中按关键码有序。2.再哈希法Hi=RHi(key)i=1,2,…,kRHi为不同的哈希函数，即在同义词发生地址冲突时计算另一个哈希函数地址，直至冲突不再发生。总结：线性探测容易产生二次聚集，链地址肯定不会产生二次聚集。一次聚集的产生主要取决于哈希函数，在哈希函数均匀的前提下，可以认为没有一次聚集。【例9-3】设

key={19,14,23,01,68,20,84,27,55,11,10,79}按哈希函数为：H(key)=keymod13和链地址法处理冲突构造所得的哈希表如下：解：由已知条件可得每个关键码的哈希地址为：6,1,10,1,3,7,6,1,3,11,10,1。0∧01142779556819111023∧∧∧∧∧∧∧∧∧∧∧∧12345679810111284209.3.4哈希表的查找及其分析

查找过程和造表过程一致。由于“冲突”的产生，使得哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需以ASL作为衡量哈希表查找效率的量度。决定哈希表查找的ASL的因素：1.选用的哈希函数;2.选用的处理冲突的方法;3.哈希表饱和的程度，装载因子α=n/m值的大小

一般情况，可认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。哈希表的ASL是处理冲突方法和装载因子的函数。

可以证明查找成功时有下列结果（见P261）

线性探测再散列平均查找长度为Snl=

随机探测再散列