数据结构哈希表（课堂PPT）

1、1哈希表哈希表什么是哈希表哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的查找分析小结和作业课堂练习2A0A1A2A3A4A5A6A7A8A9A10A0A1A2A3A4A5A6A7A8A9A10例例1:1:有一批考试成绩，统计各分数段的人数。有一批考试成绩，统计各分数段的人数。对成绩对成绩GradeGrade，执行：，执行：Agrade/10+Agrade/10+什么是哈希表什么是哈希表3例例2: 2: Ord(Char)=asc(char) asc(a) + 1什么是哈希表什么是哈希表0 1(A) 3 4 5(E) 9(I) 268(H)4(D) 19(S) 22(V) 0 18(R)

2、7(G) 190 5(E)HADHAS HAV HEHERHEREHIGHIS4将将10001000个学生的信息存放在数组个学生的信息存放在数组A0A999A0A999中中例例3:3:为每年招收的为每年招收的10001000名新生建立一张查找表，其名新生建立一张查找表，其关键字为学号，其值的范围为关键字为学号，其值的范围为xx000 xx999 (xx000 xx999 (前前两位为年份两位为年份) )。什么是哈希表什么是哈希表 number(substring( number(substring(学号学号, 3,3), 3,3)5建立查找表：建立查找表： 给定关键字给定关键字keykey计算

3、计算f(key)f(key)数组下标数组下标查找表：查找表： 使用数组存放使用数组存放n n个关键字，数组的下标个关键字，数组的下标0 0n-1n-1什么是哈希表什么是哈希表查找时：查找时： 给定关键字给定关键字keykey计算计算f(key)f(key)数组下标数组下标6建立查找表：建立查找表： 给定给定gradegrade计算计算f(grade)f(grade)数组下标数组下标例例4 4：统计学生成绩各分数段的人数：统计学生成绩各分数段的人数 什么是哈希表什么是哈希表查找时：查找时： 给定给定gradegrade计算计算f(grade)f(grade)数组下标数组下标HashHash函数：

4、函数：f(grade) = grade/10 f(grade) = grade/10 7什么是哈希表什么是哈希表 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 例例5 5：对于如下：对于如下9 9个关键字个关键字设设 哈希函数哈希函数 f(key) =f(key) = (Ord(Ord(第一个字母第一个字母) - Ord(A) + 1)/2) - Ord(A) + 1)/2 8什么是哈希表什么是哈希表字母ABCDEFGHIJKLM序号1234567

5、8910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526ChenZhaoQian SunLiWuHanYeDei序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13问题问题: : 若添加关键字若添加关键字Zhou , Zhou , 怎么办？怎么办？9什么是哈希表什么是哈希表由此可见，由此可见，1) 哈希(Hash)函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；2) 对不同的关键字可能得到同一哈希地址，即： key1 key2，而 f(key1) = f(key2

6、),因此，很容易产生“冲突”现象；10什么是哈希表什么是哈希表3) 很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的因此，在构造这种特殊的“查找表查找表” 时，除时，除了需要选择一个了需要选择一个“好好”( (尽可能少产生冲突尽可能少产生冲突) )的哈的哈希函数之外；还需要找到一种希函数之外；还需要找到一种“处理冲突处理冲突” 的方的方法。法。11哈希表的定义哈希表的定义根据设定的哈希函数根据设定的哈希函数 H(key) H(key) 和所选中的处理冲突的和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的方法，

7、将一组关键字映象到一个有限的、地址连续的地址集地址集 ( (区间区间) ) 上，并以关键字在地址集中的上，并以关键字在地址集中的“象象”作为相应记录在表中的存储位置，如此构造所得的查作为相应记录在表中的存储位置，如此构造所得的查找表称之为找表称之为“哈希表哈希表”。这一过程称为这一过程称为哈希造表哈希造表或者或者散列散列，所得的存储位置成，所得的存储位置成为为哈希地址哈希地址或者或者散列地址散列地址。12哈希函数的构造方法哈希函数的构造方法 对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法: :若是非数字关键字，则需先对其进行数字若是非数字关键字，则需先对其进行数字化处理。化处理。

8、1. 1. 直接定址法直接定址法3. 3. 平方取中法平方取中法5. 5. 除留余数法除留余数法4. 4. 折叠法折叠法6. 6. 随机数法随机数法2. 2. 数字分析法数字分析法13哈希函数为关键字的线性函数哈希函数为关键字的线性函数H(key) = key 或者或者 H(key) = a key + b1. 1. 直接定址法直接定址法哈希函数的构造方法哈希函数的构造方法14哈希函数的构造方法哈希函数的构造方法2. 2. 数字分析法数字分析法假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 s 位数字组位数字组成成 (u1, u2, , us)，分析关键字集中的全体，分析

9、关键字集中的全体， 并从并从中提取分布均匀的若干位或它们的组合作为地址。中提取分布均匀的若干位或它们的组合作为地址。此方法仅适合于：此方法仅适合于： 能预先估计出预先估计出全体关键字的每一位每一位上上各种数字数字出现的频度出现的频度。15哈希函数的构造方法哈希函数的构造方法有有80个记录，关键字为个记录，关键字为8位十进制数，哈希地址为位十进制数，哈希地址为2位十进制数位十进制数8 1 3 4 6 5 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

10、 4 1 9 3 5 5. 分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址16哈希函数的构造方法哈希函数的构造方法以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3. 3. 平方取中法平方取中法此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。17哈希函数的构造方法哈希函数的构造方法4. 4. 折叠法折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。此方法适合于: 关键字

11、的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。18哈希函数的构造方法哈希函数的构造方法例例 关键字为关键字为 ：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. 折叠法折叠法19哈希函数的构造方法哈希函数的构造方法5. 5. 除留余数法除留余数法设定哈希函数为设定哈希函数为: : H(key) = key MOD pH(key) = key MOD p 其中其中， pm (pm (表长

12、表长) ) 并且并且p p 应为不大于应为不大于 m m 的素数的素数 或是或是 不含不含 20 20 以下的质因子以下的质因子20哈希函数的构造方法哈希函数的构造方法给定一组关键字为: 12, 39, 18, 24, 33, 21若取 p=9, 则它们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3为什么要对p加限制？可见，若p中含质因子3, 则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。21哈希函数的构造方法哈希函数的构造方法6. 6. 随机数法随机数法设定哈希函数为: H(key) = Random(key)其中Random 为随机函数此方法通常

13、用于对长度不等的关键字构造哈希函数。22哈希函数的构造方法哈希函数的构造方法实际构造哈希表时实际构造哈希表时1.采用哪种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)2.总的原则是使产生冲突的可能性尽可能的小。3.如果哈希造表过程中产生冲突，应当如何处理这些冲突呢？23处理冲突的方法处理冲突的方法冲突冲突：由关键字得到的哈希地址为由关键字得到的哈希地址为j j（0jn-10jn-1）的位置上已存有记录的位置上已存有记录处理冲突：处理冲突：为产生冲突的地址寻找下一个空的哈为产生冲突的地址寻找下一个空的哈希地址希地址1. 开放定址法开放定址法2. 再哈希法再哈希法3. 链

14、地址法链地址法处理处理冲突冲突方法方法4. 建立一个公共溢出区建立一个公共溢出区24处理冲突的方法处理冲突的方法1. 1. 开放定址法开放定址法为产生冲突的地址为产生冲突的地址 H(key) 求得一个地址序求得一个地址序列：列： H0, H1, H2, , Hs 1 sm-1其中：其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s m 为哈希表表长为哈希表表长25处理冲突的方法处理冲突的方法1. 线性探测再散列法2. 二次探测再散列法3. 随机探测再散列法增量增量d di i的的三种三种取法取法26处理冲突的方法处理冲突的方法1. 1.

15、开放定址法开放定址法对增量对增量 d di i 的三种取法的三种取法-：1) 线性探测再散列线性探测再散列 di = c i 最简单的情况最简单的情况 c=1 即即 di= 1,2,3,m-127处理冲突的方法处理冲突的方法例如例如: : 关键字集合关键字集合 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 )采用采用线性探测再散列线性探测再散列法来构造哈希表。法来

16、构造哈希表。19 0 1 2 3 4 5 6 7 8 9 1019010123232314145555686868118211361182361 1 2 1 3 6 2 5 128处理冲突的方法处理冲突的方法1. 1. 开放定址法开放定址法对增量对增量 d di i 有三种取法有三种取法-：2) 平方（二次）探测再散列平方（二次）探测再散列 di = 12, -12, 22, -22, ,29处理冲突的方法处理冲突的方法例如例如: : 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 19, 01, 23, 14, 55, 68, 11, 82, 36

17、 19 0 1 2 3 4 5 6 7 8 9 10190101232323 141455556868681182113611823636设定哈希函数设定哈希函数 H(key) = key MOD 11 ( H(key) = key MOD 11 ( 表长表长=11 )=11 )采用采用二次探测再散列二次探测再散列法来构造哈希表。法来构造哈希表。1 1 2 1 2 1 4 1 330处理冲突的方法处理冲突的方法1. 1. 开放定址法开放定址法对增量对增量 d di i 有三种取法有三种取法-：3) 随机探测再散列随机探测再散列 di是一组随机数列是一组随机数列 或者或者 di=iH2(key)

18、 (又称双散列函数探又称双散列函数探测测)31处理冲突的方法处理冲突的方法即：产生的即：产生的 H Hi i 均不相同，且所产生的均不相同，且所产生的m-1m-1个个 H Hi i 值能覆盖哈希表中所有地址。值能覆盖哈希表中所有地址。则要求：则要求： 注意：注意：增量增量 d di i 应具有应具有“完备性完备性” 随机探测时的随机探测时的 m 和和 di 没有公因子。没有公因子。 平方探测时的表长平方探测时的表长 m 必为形如必为形如 4j+3 的素数的素数（如（如: 7, 11, 19, 23, 等）；等）；32处理冲突的方法处理冲突的方法 H2(key) 是另设定的一个哈希函数，它的函数

19、值应是另设定的一个哈希函数，它的函数值应和和 m 互为素数。互为素数。若若 m 为素数，则为素数，则 H2(key) 可以是可以是 1 至至 m-1 之间的之间的任意数任意数;若若 m 为为 2 的幂次，则的幂次，则 H2(key) 应是应是 1 至至 m-1 之间的之间的任意奇数。任意奇数。33处理冲突的方法处理冲突的方法例如，当 m=11时， 可设 H2(key)=(3 key) MOD 10+11901231455681182361 1 1 1 2 1 1 2 234处理冲突的方法处理冲突的方法2. 2. 再哈希法再哈希法H Hi i=RH=RHi i( (keykey) i=1,2,3

20、,) i=1,2,3,，k kRHRHi i均是不同的哈希函数，在同义词产生地址均是不同的哈希函数，在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突冲突时计算另一个哈希函数地址，直到冲突不再发生。不再发生。缺点：增加了计算时间。缺点：增加了计算时间。35处理冲突的方法处理冲突的方法3. 3. 链地址法链地址法所有关键字为同义词的记录存储在同一线性所有关键字为同义词的记录存储在同一线性链表中。链表中。定义指针型向量定义指针型向量Chain ChainHashm;Chain ChainHashm;凡是哈希地址为凡是哈希地址为i i的记录都插入到头指针为的记录都插入到头指针为ChainHash

21、i的链表中。的链表中。36处理冲突的方法处理冲突的方法例如例如: : 关键字集合关键字集合 19, 01, 23, 14, 19, 01, 23, 14, 55, 68, 11, 82, 55, 68, 11, 82, 36 36 采用采用链地址链地址法来构造哈法来构造哈希表。希表。哈希函数为 H(key)=key MOD 7 11 198268 55 14 0136 23 1901231455681182360123456ASL=(61+22+31)/9=13/937处理冲突的方法处理冲突的方法4. 4. 建立一个公共溢出区建立一个公共溢出区哈希函数的值域哈希函数的值域0,m-10,m-1向

22、量向量HashTable0.m-1HashTable0.m-1为基本表，每个分量为基本表，每个分量存放一个记录存放一个记录向量向量OverTable0.vOverTable0.v为溢出表为溢出表对于关键字和基本表对于关键字和基本表HashTable中关键字为同中关键字为同义词的记录，只要发生冲突，都填入溢出表。义词的记录，只要发生冲突，都填入溢出表。38哈希表的查找算法哈希表的查找算法查找过程和造表过程一致。假设采用查找过程和造表过程一致。假设采用开放定址开放定址处理冲突，则处理冲突，则查找过程查找过程为为: 1.对于给定值对于给定值 K, 计算哈希地址计算哈希地址 i = H(K)2.若若

23、ri = NULL 则查找不成功 3.若若 ri.key = K 则查找成功4.否则否则 “求下一地址 Hi” ，直至 rHi = NULL (查找不成功)或 rHi.key = K (查找成功) 为止。39哈希表的查找算法哈希表的查找算法int hashsize = 997, . ; typedef struct ElemType *elem; int count; / 当前数据元素个数 int sizeindex; / 为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/- 开放定址哈希表开放定址

24、哈希表的存储结构 -/40哈希表的查找算法哈希表的查找算法Status SearchHash (HashTable H, KeyType K, int &p, int &c) / 在开放定址哈希表H中查找关键码为K的记录 / SearchHashp = Hash(K); / 求得哈希地址while ( H.elemp.key != NULLKEY & !EQ(K, H.elemp.key)） collision(p, +c); / 求得下一探查地址 pif (EQ(K, H.elemp.key) return SUCCESS; / 查找成功，返回待查数据元素位置 pel

25、se return UNSUCCESS; / 查找不成功41哈希表的维护算法哈希表的维护算法Status InsertHash (HashTable &H, Elemtype e) / InsertHashc = 0;if ( SearchHash ( H, e.key, p, c ) = = SUCCESS ) return DUPLICATE; / 表中已有与 e 有相同关键字的元素 else if ( c hashsizeH.sizeindex/2 ) / 冲突次数 c 未达到上限，（阀值 c 可调）H.elemp=e; +H.count; return OK; else RecreateHashTable(H); return UNSUCCESS; / 重建哈希表42哈希表的查找分析哈希表的查找分析从查找过程得知：1、由于冲突的产生，哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。2、哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。43哈希表的查找分析哈希表的查找分析1) 选用的哈