《牛小飞《数据结构》5散列表》由会员分享，可在线阅读，更多相关《牛小飞《数据结构》5散列表（47页珍藏版）》请在金锄头文库上搜索。
1、散列表散列表散列函数的构造方法处理冲突的方法散列表的查找算法散列表的查找分析小结和作业课堂练习散列的基本思想散列的基本思想散列的基本思想已讲查找表的共同特点：记录在表中的位置和它已讲查找表的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系；的关键字之间不存在一个确定的关系；查找的过程为查找的过程为给定值给定值依次和关键字集合中依次和关键字集合中各个关各个关键字键字进行比较；进行比较；查找的效率取决于和查找的效率取决于和给定值给定值进行进行比较比较的的关键字个关键字个数数。用这类方法表示的查找表，其平均查找长度都用这类方法表示的查找表，其平均查找长度都不为零不为零不同的表示方法，其
2、差别仅在于：不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。关键字和给定值进行比较的顺序不同。散列的基本思想散列的基本思想如果预先知道所查关键字在表中的位置，如果预先知道所查关键字在表中的位置，就可以实现。就可以实现。对于频繁使用的查找表，希望对于频繁使用的查找表，希望ASL = 0ASL = 0。只要记录在表中位置和其关键字之间存在只要记录在表中位置和其关键字之间存在一种确定的关系。一种确定的关系。散列的基本思想散列的基本思想若以下标为若以下标为000 999 000 999 的顺序表来表示。的顺序表来表示。例如：为每年招收的例如：为每年招收的10001000名新生建立一张查
3、找表，名新生建立一张查找表，其关键字为学号，其值的范围为其关键字为学号，其值的范围为xx000 xx999 (xx000 xx999 (前前两位为年份两位为年份) )。则查找过程可以简单进行：取给定值（学号）的则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找后三位，不需要经过比较便可直接从顺序表中找到待查关键字。到待查关键字。散列的基本思想散列的基本思想散列的基本思想散列的基本思想因此在一般情况下，需在关键字与记录在表中的因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，存储位置之间建立一个函数关系，以以 f(key) f(key) 作
4、作为关键字为为关键字为 key key 的记录在表中的位置，通常称的记录在表中的位置，通常称这个函数这个函数 f(key) f(key) 为哈希函数。为哈希函数。 Z Zhao, hao, Q Qian, ian, S Sun, un, L Li, i, W Wu, u, C Chen, hen, H Han, an, Y Ye, e, D Dei ei 例：对于如下例：对于如下9 9个关键字个关键字设设 散列函数散列函数 f(key) =f(key) = (Ord(Ord(第一个字母第一个字母)/2)/2 散列的基本思想散列的基本思想举例举例字母ABCDEFGHIJKLM序号12345678
5、910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526ChenZhaoQian SunLiWuHanYeDei序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13问题问题: : 若添加关键字若添加关键字Zhou , Zhou , 怎么办？怎么办？ Z Zhao, hao, Q Qian, ian, S Sun, un, L Li, i, W Wu, u, C Chen, hen, H Han, an, Y Ye, e, D Dei ei 由此可见，由此可见，1) 散列(Hash)函数是一个将关键字的集合映射到某个地址集合上，它的
6、设置很灵活，只要这个地址集合的大小不超出允许范围即可；2) 对不同的关键字可能得到同一散列地址，即： key1 key2，而 f(key1) = f(key2),因此，很容易产生“冲突”现象；散列的基本思想散列的基本思想结论结论3) 很难找到一个不产生冲突的散列函数。一般情况下，只能选择恰当的散列函数，使冲突尽可能少地产生。 因此，在构造这种特殊的因此，在构造这种特殊的“查找表查找表” 时，除时，除了需要选择一个了需要选择一个“好好”( (尽可能少产生冲突尽可能少产生冲突) )的散的散列函数之外；还需要找到一种列函数之外；还需要找到一种“处理冲突处理冲突” 的方的方法。法。散列的基本思想散列的
7、基本思想结论结论根据设定的散列函数根据设定的散列函数 H(key) H(key) 和所选中的处理冲突的和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的方法，将一组关键字映象到一个有限的、地址连续的地址集地址集 ( (区间区间) ) 上，并以关键字在地址集中的上，并以关键字在地址集中的“象象”作为相应记录在表中的存储位置，如此构造所得的查作为相应记录在表中的存储位置，如此构造所得的查找表称之为找表称之为“散列表散列表”。这一过程称为这一过程称为散列造表散列造表或者或者散列散列，所得的存储位置成，所得的存储位置成为为散列地址散列地址或者或者哈希地址哈希地址。散列的基本思想散列的基
8、本思想定义定义散列函数的构造方法散列函数的构造方法 对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法: :若是非数字关键字，则需先对其进行数字化处理。若是非数字关键字，则需先对其进行数字化处理。1. 1. 直接定址法直接定址法3. 3. 平方取中法平方取中法5. 5. 除留余数法除留余数法4. 4. 折叠法折叠法6. 6. 随机数法随机数法2. 2. 数字分析法数字分析法散列函数为关键字的线性函数散列函数为关键字的线性函数H(key) = key 或者或者 H(key) = a key + b1. 1. 直接定址法直接定址法散列函数的构造方法散列函数的构造方法散列函数的构造方法散列
9、函数的构造方法2. 2. 数字分析法数字分析法假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 s 位数字组位数字组成成 (u1, u2, , us)，分析关键字集中的全体，分析关键字集中的全体， 并从并从中提取分布均匀的若干位或它们的组合作为地址。中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：此方法仅适合于： 能预先估计出预先估计出全体关键字的每一位每一位上上各种数字数字出现的频度出现的频度。散列函数的构造方法散列函数的构造方法有有80个记录，关键字为个记录，关键字为8位十进制数，散列地址为位十进制数，散列地址为2位十进制数位十进制数8 1 3 4 6 5
10、3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作散列地址散列函数的构造方法散列函数的构造方法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3. 3. 平方取中法平方取中法此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高
11、的现象。散列函数的构造方法散列函数的构造方法4. 4. 折叠法折叠法将关键字分割成若干部分，然后取它们的叠加和为散列地址。有两种叠加处理的方法：移位叠加和间界叠加。此方法适合于: 关键字的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。散列函数的构造方法散列函数的构造方法例例 关键字为关键字为 ：0442205864，散列地址位数为，散列地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加4. 4. 折叠法折叠法散列函数的构造方法散列函数的构造
12、方法5. 5. 除留余数法除留余数法设定散列函数为设定散列函数为: : H(key) = key MOD pH(key) = key MOD p 其中其中， pm (pm (表长表长) ) 并且并且p p 应为不大于应为不大于 m m 的素数的素数 或是或是 不含不含 20 20 以下的质因子以下的质因子散列函数的构造方法散列函数的构造方法给定一组关键字为给定一组关键字为: 12, 39, 18, 24, 33, 21: 12, 39, 18, 24, 33, 21若取若取 p=9, p=9, 则它们对应的散列函数值将为则它们对应的散列函数值将为: : 3, 3, 0, 6, 6, 33, 3
13、, 0, 6, 6, 3为什么要对为什么要对p p加限制？加限制？可见，若可见，若p p中含中含质因子质因子3 3, , 则所有含质因子则所有含质因子3 3的关的关键字均映射到键字均映射到“3 3的倍数的倍数”的地址上，从而增加的地址上，从而增加了了“冲突冲突”的可能。的可能。散列函数的构造方法散列函数的构造方法6. 6. 随机数法随机数法设定散列函数为: H(key) = Random(key)其中Random 为随机函数此方法通常用于对长度不等的关键字构造散列函数。散列函数的构造方法散列函数的构造方法实际构造散列表时实际构造散列表时1.采用哪种构造散列函数的方法取决于建表的关键字集合的情况
14、(包括关键字的范围和形态)2.总的原则是使产生冲突的可能性尽可能的小。3.如果散列造表过程中产生冲突，应当如何处理这些冲突呢？处理冲突的方法处理冲突的方法冲突冲突：由关键字得到的散列地址为由关键字得到的散列地址为j j（0jn-10jn-1）的位置上）的位置上已存有记录已存有记录处理冲突：处理冲突：为产生冲突的地址寻找下一个空的散列地址为产生冲突的地址寻找下一个空的散列地址2. 不用链表的散列表不用链表的散列表开放定址法开放定址法5.45.43. 再散列法再散列法5.55.51. 分离链接法分离链接法5.34. 建立一个公共溢出区建立一个公共溢出区处理冲突的方法处理冲突的方法11. 分离链接法
15、分离链接法(separate chaining)将散列到同一个值的所有元素保留到同一线将散列到同一个值的所有元素保留到同一线性链表中。性链表中。处理冲突的方法处理冲突的方法1例如例如: : 关键字集合关键字集合 19, 01, 23, 19, 01, 23, 14, 55, 68, 11, 14, 55, 68, 11, 82, 36 82, 36 采用采用链地址链地址法来构造的法来构造的散列表：散列表：散列函数为散列函数为 H(key)=key MOD 7 11 198268 55 14 0136 23 1901231455681182360123456处理冲突的方法处理冲突的方法1执行一次
16、查找：执行一次查找：首首先使用散列函数来先使用散列函数来确定需要遍历的链确定需要遍历的链表；然后再在被确表；然后再在被确定的链表中执行一定的链表中执行一次查找。次查找。 11 198268 55 14 0136 23 0123456ASL=(61+22+31)/9=13/9处理冲突的方法处理冲突的方法1执行插入操作：执行插入操作：首首先检查相应的链表先检查相应的链表中该元素是否已处中该元素是否已处在适当的位置，否在适当的位置，否则被插入到链表的则被插入到链表的前端。前端。 11 198268 55 14 0136 23 0123456处理冲突的方法处理冲突的方法22. 2. 开放定址法开放定址
17、法为产生冲突的地址为产生冲突的地址 H(key) 求得一个地址序列：求得一个地址序列： H0, H1, H2, , Hs 1 sm-1其中：其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s m 为散列表表长为散列表表长处理冲突的方法处理冲突的方法21. 线性探测再散列法2. 平方探测再散列法3. 双散列法增量增量d di i的的三种三种取法取法处理冲突的方法处理冲突的方法21. 1. 开放定址法开放定址法对增量对增量 d di i 的三种取法的三种取法-：1) 线性探测再散列线性探测再散列 di = c i 最简单的情况最简单的情况 c
18、=1 , 即即di=f(i)=i; 即即 di= 1,2,3,m-1处理冲突的方法处理冲突的方法2例如例如: : 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 19, 01, 23, 14, 55, 68, 11, 82, 36 设定散列函数设定散列函数 H(key) = key MOD 11 ( H(key) = key MOD 11 ( 表长表长=11 )=11 )采用采用线性探测再散列线性探测再散列法来构造散列表。法来构造散列表。19 0 1 2 3 4 5 6 7 8 9 1019010123232314145555686868118211
19、361182361 1 2 1 3 6 2 5 1处理冲突的方法处理冲突的方法21. 1. 开放定址法开放定址法对增量对增量 d di i 有三种取法有三种取法-：2) 平方（二次）探测再散列平方（二次）探测再散列 di =f(i)= 12, -12, 22, -22, ,处理冲突的方法处理冲突的方法2例如例如: : 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 19, 01, 23, 14, 55, 68, 11, 82, 36 19 0 1 2 3 4 5 6 7 8 9 10190101232323 141455556868681182113
20、611823636设定散列函数设定散列函数 H(key) = key MOD 11 ( H(key) = key MOD 11 ( 表长表长=11 )=11 )采用采用二次探测再散列二次探测再散列法来构造散列表。法来构造散列表。1 1 2 1 2 1 4 1 3处理冲突的方法处理冲突的方法21. 1. 开放定址法开放定址法对增量对增量 d di i 有三种取法有三种取法-：3) 双散列法双散列法 di即即f(i)是一组随机数列是一组随机数列 或者或者 di=f(i)=iH2(key) (又称随机探测再散列又称随机探测再散列)处理冲突的方法处理冲突的方法2 H2(key) 是另设定的一个散列函数
21、，它的函数是另设定的一个散列函数，它的函数值应和值应和 TableSize 互为素数。互为素数。若若 TableSize 为素数，则为素数，则 H2(key) 可以是可以是 1 至至 TableSize-1 之间的任意数之间的任意数;若若 TableSize 为为 2 的幂次，则的幂次，则 H2(key) 应是应是 1 至至 TableSize-1 之间的任意奇数。之间的任意奇数。处理冲突的方法处理冲突的方法例如，当 m=11时， 可设 H2(key)=(3 key) MOD 10+11901231455681182362 1 1 1 2 1 2 1 3设定哈希函数设定哈希函数 H(key)
22、= key MOD 11 ( H(key) = key MOD 11 ( 表长表长=11 )=11 )例如例如: : 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 19, 01, 23, 14, 55, 68, 11, 82, 36 处理冲突的方法处理冲突的方法2即：产生的即：产生的 Hi 均不相同，且所产生的均不相同，且所产生的TableSize-1个个 Hi 值能覆盖散列表中所有地址。值能覆盖散列表中所有地址。则要求：则要求： 注意：注意：增量增量 d di i 应具有应具有“完备性完备性” 双散列时双散列时TableSize和和 di 没有公
23、因子。没有公因子。 平方探测时的表长平方探测时的表长 TableSize 必为形如必为形如 4j+3 的素数（如的素数（如: 7, 11, 19, 23, 等）；等）；处理冲突的方法处理冲突的方法33. 3. 再散列法再散列法Hi=RHi(key) i=1,2,3,，kRHi均是不同的散列函数，在同义词产生地址均是不同的散列函数，在同义词产生地址冲突时计算另一个散列函数地址，直到冲突冲突时计算另一个散列函数地址，直到冲突不再发生。不再发生。缺点：增加了计算时间。缺点：增加了计算时间。处理冲突的方法处理冲突的方法44. 4. 建立一个公共溢出区建立一个公共溢出区散列函数的值域散列函数的值域0,m
24、-1向量向量HashTable0.m-1为基本表，每个分量存为基本表，每个分量存放一个记录放一个记录向量向量OverTable0.v为溢出表为溢出表对于关键字和基本表对于关键字和基本表HashTable中关键字为同中关键字为同义词的记录，只要发生冲突，都填入溢出表。义词的记录，只要发生冲突，都填入溢出表。课堂练习课堂练习设有一组关键字设有一组关键字11，54，36，89，51，47，38，59，63，94，15，采用哈希函数：，采用哈希函数：H(key) = key % 13。采用开放地址法的线性探测再散列方法解决冲。采用开放地址法的线性探测再散列方法解决冲突，试在突，试在015的散列地址空间
25、中对该关键字序列构造的散列地址空间中对该关键字序列构造哈希表。哈希表。 散列表的查找算法散列表的查找算法查找过程和造表过程一致。假设采用查找过程和造表过程一致。假设采用开放定址开放定址处理冲突，则处理冲突，则查找过程查找过程为为: 1.对于给定值对于给定值 K, 计算散列地址计算散列地址 i = H(K)2.若若 ri = NULL 则查找不成功 3.若若 ri.key = K 则查找成功4.否则否则 “求下一地址 Hi” ，直至 rHi = NULL (查找不成功)或 rHi.key = K (查找成功) 为止。哈希表的查找分析哈希表的查找分析从查找过程得知：由于冲突的产生，哈希表的查找过程
26、仍然是一个给定值和关键字进行比较的过程。哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。哈希表的查找分析哈希表的查找分析1) 选用的哈希函数哈希函数;2) 选用的处理冲突的方法处理冲突的方法;3）哈希表饱和的程度，装载因子装载因子 =n/m 值的大小大小（n记录数，记录数，m表的长度，即表的长度，即TableSize）决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表的查找分析哈希表的查找分析一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈希表的因此，哈希表的ASL是是处理冲突方法处理冲突方法和和装载因子装载因子的函的函数。数。例
27、如：前述例子例如：前述例子线性探测处理冲突时，线性探测处理冲突时，ASL =链地址法处理冲突时，链地址法处理冲突时，ASL =22/913/9哈希表的查找分析哈希表的查找分析线性探测再散列线性探测再散列可以证明：查找成功查找成功时有下列结果：随机探测再散列随机探测再散列链地址法链地址法哈希表的查找分析哈希表的查找分析从以上结果可见，哈希表的平均查找长度是 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某平均查找长度限定在某个范围内个范围内。小结和作业小结和作业散列表散列表 1 1散列原理散列原理 2 2散列函数的构造方法散列函数的构造方法 3 3处理冲突的方法处理冲突的方法4 4散列表的查找及分析散列表的查找及分析 作业： P145, 5.1 a，b
