第09章-查找-数据结构-(第二版)-教学课件.ppt

《第09章-查找-数据结构-(第二版)-教学课件.ppt》由会员分享，可在线阅读，更多相关《第09章-查找-数据结构-(第二版)-教学课件.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章第九章 查找查找 静态查找表静态查找表 动态查找表动态查找表 哈希查找表哈希查找表 9.1 9.1 静态查找表静态查找表查找表查找表查找表查找表(table):(table):由同类型的由同类型的由同类型的由同类型的DE(DE(或记录或记录或记录或记录)构成的集构成的集构成的集构成的集合合合合.查找表上的基本运算查找表上的基本运算:建立查找表建立查找表create(ST,n)查找查找search(ST,k)遍历查找表遍历查找表traverse(ST)9.1 9.1 静态查找表静态查找表查找查找查找查找 :在查找表中确定与给定值相等的在查找表中确定与给定值相等的在查找表中确定与给定值相等的

2、在查找表中确定与给定值相等的DEDE的过程的过程的过程的过程.查找结果查找结果:查找成功查找成功查找成功查找成功(table table 中存在给定值的记录中存在给定值的记录中存在给定值的记录中存在给定值的记录)查找不成功查找不成功查找不成功查找不成功(table table 中不存在给定值的记录中不存在给定值的记录中不存在给定值的记录中不存在给定值的记录)查找表分为查找表分为查找表分为查找表分为:静态查找表静态查找表 (对查找表中的数据元素对查找表中的数据元素对查找表中的数据元素对查找表中的数据元素不不不不进行插入和删进行插入和删进行插入和删进行插入和删除操作除操作除操作除操作)动态查找表动

3、态查找表 (对查找表中的数据元素对查找表中的数据元素对查找表中的数据元素对查找表中的数据元素可可可可进行插入和删进行插入和删进行插入和删进行插入和删除操作除操作除操作除操作)9.1 9.1 静态查找表静态查找表一一.顺序表的查找顺序表的查找 FUNC seqsrch(r:sqlisttp;k:keytype):integer;r0.key:=k;i:=n;WHILE ri.key k DO i:=i-1;RETURN(i)ENDF;seqsrch9.1 9.1 静态查找表静态查找表(2)(2)循环结束有两种可能：循环结束有两种可能：循环结束有两种可能：循环结束有两种可能：查找成功查找成功查找成

4、功查找成功 ri.key=kri.key=k 条件控制式条件控制式 查找不成功查找不成功查找不成功查找不成功 i=0i=0 计数控制式计数控制式这两种可能形成两种不同类型的循环控制：这两种可能形成两种不同类型的循环控制：这两种可能形成两种不同类型的循环控制：这两种可能形成两种不同类型的循环控制：条件条件条件条件循环循环循环循环 WHILE WHILE 条件条件条件条件 DO DO 循环体循环体循环体循环体 REPEAT REPEAT 循环体循环体循环体循环体 UNTIL UNTIL 条件条件条件条件 计数循环计数循环计数循环计数循环 FOR i:=n DOWNTO 0FOR i:=n DOWN

5、TO 09.1 9.1 静态查找表静态查找表常规解决办法常规解决办法常规解决办法常规解决办法:(1)(1)条件循环为主条件循环为主条件循环为主条件循环为主 WHILE ri.key k DO WHILE ri.key k DO IF i=1 THEN RETURN(0)IF i=1 THEN RETURN(0)ELSE i:=i-1;ELSE i:=i-1;(2)(2)复合条件复合条件复合条件复合条件 WHILE ri.key k AND i=1 DO i:=i-1;WHILE ri.key k AND i=1 DO i:=i-1;(3)(3)计数循环为主计数循环为主计数循环为主计数循环为主

6、FOR i:=n DOWNTO 1 DO FOR i:=n DOWNTO 1 DO IF ri.key=k THEN RETURN(i)IF ri.key=k THEN RETURN(i)9.1 9.1 静态查找表静态查找表 FUNC seqsrch(r:sqlisttp;k:keytype):integer;r0.key:=k;i:=n;WHILE ri.key k DO i:=i-1;RETURN(i)ENDF;seqsrch3.r03.r0起监视哨作用起监视哨作用起监视哨作用起监视哨作用9.1 9.1 静态查找表静态查找表平均查找长度平均查找长度平均查找长度平均查找长度(ASL):(AS

7、L):查找过程中查找过程中查找过程中查找过程中,给定值需与关键字比较的次数的期望值给定值需与关键字比较的次数的期望值给定值需与关键字比较的次数的期望值给定值需与关键字比较的次数的期望值.n nASL=PASL=Pi iC Ci i i=1i=1其中其中其中其中:P:Pi i 为查找第为查找第为查找第为查找第i i 个记录的概率个记录的概率个记录的概率个记录的概率;C Ci i 为找到第为找到第为找到第为找到第i i 个记录时个记录时个记录时个记录时,已比较的次数已比较的次数已比较的次数已比较的次数.顺序查找的平均查找长度顺序查找的平均查找长度顺序查找的平均查找长度顺序查找的平均查找长度ASLs

8、s=npASLss=np1 1+(n-1)p+(n-1)p2 2+p+pn n n n当当当当p pi i=1/n=1/n时时时时,ASLss=P,ASLss=Pi iC Ci i=(n+1)/2 =(n+1)/2 i=1i=19.1 9.1 静态查找表静态查找表二二.有序表的查找有序表的查找有序表有序表有序表有序表 :查找表中记录按关键字有序排列的表查找表中记录按关键字有序排列的表.即即:ri.keyrmid.key:low:=mid+1;k=rmid.key:found:=true;krmid.key:high:=mid-1;ENDC;IF found THEN RETURN(mid)EL

9、SE RETURN(i)ENDF;binsrch例例例例:k=21,k=21,有序表为有序表为有序表为有序表为:(5,13,(5,13,1919,2121,37,37,5656,64,75,80,88,64,75,80,88,92)92)1.Low=1,high=11,mid=1.Low=1,high=11,mid=6 62.2.21212119 19 low=4 mid=low=4 mid=4 44.21=21 found=true return(4)4.21=21 found=true return(4)折半查找的平均查找长度折半查找的平均查找长度折半查找的平均查找长度折半查找的平均查找长

10、度ASLbs=(n+1)/nlogASLbs=(n+1)/nlog2 2(n+1)-1(n+1)-1 loglog2 2(n+1)-1(n+1)-19.1 9.1 静态查找表静态查找表例例例例.查找表为查找表为查找表为查找表为:22,12,13,8,9,2022,12,13,8,9,20,33,42,44,38,24,48,33,42,44,38,24,48,60,58,74,49,86,5360,58,74,49,86,53索引表为索引表为索引表为索引表为:关键字项关键字项关键字项关键字项指针项指针项指针项指针项2222484886861 17 713139.1 9.1 静态查找表静态查找表

11、查找分为两步查找分为两步查找分为两步查找分为两步:1.1.确定待查记录所在块确定待查记录所在块确定待查记录所在块确定待查记录所在块;(;(可以用顺序或折半查找可以用顺序或折半查找可以用顺序或折半查找可以用顺序或折半查找)2.2.在块内顺序查找在块内顺序查找在块内顺序查找在块内顺序查找.(.(只能用顺序查找只能用顺序查找只能用顺序查找只能用顺序查找)关键字项关键字项关键字项关键字项指针项指针项指针项指针项2222484886861 17 7131322,12,13,8,9,2022,12,13,8,9,20,33,42,44,38,24,4833,42,44,38,24,48,60,58,74,

12、49,86,5360,58,74,49,86,53例如例如例如例如:k=38:k=38第第第第1 1步步步步:k=38:k=38 的记录只可能在块的记录只可能在块的记录只可能在块的记录只可能在块2 2中中中中;第第第第2 2步步步步:从从从从r7r7开始开始开始开始,直到直到直到直到k=ri.key k=ri.key 或或或或i12i12为止为止为止为止.9.2 9.2 动态查找表动态查找表动态查找表的特点是动态查找表的特点是动态查找表的特点是动态查找表的特点是:表结构本身是在查找过程中动态生成的。表结构本身是在查找过程中动态生成的。表结构本身是在查找过程中动态生成的。表结构本身是在查找过程中

13、动态生成的。即查找不成功时，将该记录插入在动态查找表中。即查找不成功时，将该记录插入在动态查找表中。即查找不成功时，将该记录插入在动态查找表中。即查找不成功时，将该记录插入在动态查找表中。一、二叉排序树（一、二叉排序树（一、二叉排序树（一、二叉排序树（Binary Sort Tree)Binary Sort Tree)（又称为二叉查找树）（又称为二叉查找树）（又称为二叉查找树）（又称为二叉查找树）1 1、BSTBST定义：定义：定义：定义：BST BST或者是一棵空树；或者是具有如下性质的或者是一棵空树；或者是具有如下性质的或者是一棵空树；或者是具有如下性质的或者是一棵空树；或者是具有如下性质

14、的BT:BT:若左子树非空，则左子树上所有结点的值均小于根结点的值；若左子树非空，则左子树上所有结点的值均小于根结点的值；若左子树非空，则左子树上所有结点的值均小于根结点的值；若左子树非空，则左子树上所有结点的值均小于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树也为左、右子树也为左、右子树也为左、右子树也为BSTBST9.2 9.2 动态查找表动态查找表78100619012372484553例如：例如

15、：例如：例如：9.2 9.2 动态查找表动态查找表2 2、查找过程为、查找过程为、查找过程为、查找过程为:(1)(1)当前当前当前当前BSTBST非空时，将给定值非空时，将给定值非空时，将给定值非空时，将给定值k k与当前根结点的关键字比较与当前根结点的关键字比较与当前根结点的关键字比较与当前根结点的关键字比较:(2)(2)若相等，查找成功，结束若相等，查找成功，结束若相等，查找成功，结束若相等，查找成功，结束;若若若若k k小于当前根结点的关键字，则将左子树作为当前小于当前根结点的关键字，则将左子树作为当前小于当前根结点的关键字，则将左子树作为当前小于当前根结点的关键字，则将左子树作为当前B

16、ST;BST;若若若若k k大于当前根结点的关键字，则将右子树作为当前大于当前根结点的关键字，则将右子树作为当前大于当前根结点的关键字，则将右子树作为当前大于当前根结点的关键字，则将右子树作为当前BST;BST;(3)(3)重复重复重复重复(1)(1)。9.2 9.2 动态查找表动态查找表算法描述为：算法描述为：FUNC bstsrch(t:bitreptr;k:keytype):bitreptr;查找不成功时返回查找不成功时返回NIL IF (t=NIL)COR(t.key=k)THEN RETURN(t)ELSE IF t.keyk THEN RETURN(bstsrch(t.rchild

17、,k)ELSE RETURN(bstsrch(t.lchild,k)ENDF bstsrch 9.2 9.2 动态查找表动态查找表1.3.BST的插入的插入插入原则插入原则：记下查找不成功时比较的最后一个结点的位：记下查找不成功时比较的最后一个结点的位置，将插入结点作为该结点的左或右孩子。置，将插入结点作为该结点的左或右孩子。PROC insbst(VAR bst:bitreptr;k:keytype);f:=NIL;found:=false;f:=srch_bstree (f,bst,k,found)IF NOT found THEN ins_bstree(f,bst,k)ENDP;insb

18、st9.2 9.2 动态查找表动态查找表PROC ins_bstree(VAR f,bst:bitreptr;k:keytype);new(s);s.key:=k;s.lchild:=NIL;s.rchild:=NIL;IF bst=NIL THEN bst:=s ELSE IF k00 插入后平衡因子的绝对值插入后平衡因子的绝对值插入后平衡因子的绝对值插入后平衡因子的绝对值11 离插入结点最近的失去平衡的祖先结点离插入结点最近的失去平衡的祖先结点离插入结点最近的失去平衡的祖先结点离插入结点最近的失去平衡的祖先结点判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡，判别插入结点后可能失去

19、平衡的最小子树的根结点是否失去平衡，判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡，判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡，（该结点的平衡因子的绝对值（该结点的平衡因子的绝对值（该结点的平衡因子的绝对值（该结点的平衡因子的绝对值11）;判别旋转类型作相应处理。判别旋转类型作相应处理。判别旋转类型作相应处理。判别旋转类型作相应处理。9.2 9.2 动态查找表动态查找表1.1.4 4、AVLAVL树上插入结点算法树上插入结点算法树上插入结点算法树上插入结点算法2.2.(1)(1)算法描述算法描述算法描述算法描述 查找查找查找查找 s s 结点的插入位置过程中，记下离结点

20、的插入位置过程中，记下离结点的插入位置过程中，记下离结点的插入位置过程中，记下离s s 最近的，且平衡因子最近的，且平衡因子最近的，且平衡因子最近的，且平衡因子不等于不等于不等于不等于0 0的结点，令的结点，令的结点，令的结点，令 a a 指向该结点；（即可能失去平衡的最小指向该结点；（即可能失去平衡的最小指向该结点；（即可能失去平衡的最小指向该结点；（即可能失去平衡的最小子树的根结点）。子树的根结点）。子树的根结点）。子树的根结点）。修改修改修改修改 a a 至至至至 s s 路径上所有结点的平衡因子值；路径上所有结点的平衡因子值；路径上所有结点的平衡因子值；路径上所有结点的平衡因子值；判别

21、判别判别判别a a 结点的平衡因子绝对值是否大于结点的平衡因子绝对值是否大于结点的平衡因子绝对值是否大于结点的平衡因子绝对值是否大于1 1，若是，作旋转处理，若是，作旋转处理，若是，作旋转处理，若是，作旋转处理（2 2）过程描述过程描述过程描述过程描述 PROC ins_AVLtree(VAR tPROC ins_AVLtree(VAR t：AVLinktpAVLinktp；：；：；：；：keytypekeytype）；）；）；）；在在t为根结点的为根结点的AVL上插入关键字为上插入关键字为K的新结点的新结点 new(s)new(s)；sskeykey：=K=K，s slchildlchild

22、：=s=srchildrchild：=NIL=NIL；s sbfbf：=0=0；IF t=NIL THEN t IF t=NIL THEN t：=s =s 插入根结点插入根结点 ELSE ELSE (1)(1)查找查找查找查找s s 的插入位置的插入位置的插入位置的插入位置q,q,同时记下：同时记下：同时记下：同时记下：a a及及及及a a的双亲的双亲的双亲的双亲f f 从根到叶结点搜索从根到叶结点搜索从根到叶结点搜索从根到叶结点搜索 f f：=NIL=NIL；a a：=t=t；p p：=t=t；q q：=NIL=NIL；WHILE pNIL DO WHILE pNIL DO IF p IF

23、p bf 0 THEN abf 0 THEN a：=p=p；f f：=q=q；qq是是是是p p的双亲的双亲的双亲的双亲,p,p、q q是沿路径移动是沿路径移动是沿路径移动是沿路径移动,a,a、f f是跳跃移动是跳跃移动是跳跃移动是跳跃移动 q q：=p=p；IF s IF skeyp key THEN pkeyp key THEN p：=p=p lchildlchild ELSE p ELSE p：=p=p rchild rchild；插入插入插入插入ss IF s IF skeyq key THEN q keyq key THEN q lchild lchild：=s=s ELSE q E

24、LSE q rchildrchild：=s;=s;9.2 9.2 动态查找表动态查找表 （2 2）修改修改修改修改aa至至至至s s 路径上的平衡因子路径上的平衡因子路径上的平衡因子路径上的平衡因子 从从从从a a 到叶到叶到叶到叶 IF s IF skeyakeyakey key THEN pTHEN p：=a=alchild lchild；b b：=p=p；d d：=1=1 ELSE p ELSE p：=a=archild rchild；b b：=p=p；d d：=-1=-1；左子树插入，使左子树深度增左子树插入，使左子树深度增左子树插入，使左子树深度增左子树插入，使左子树深度增1 1，反

25、之右树深度增，反之右树深度增，反之右树深度增，反之右树深度增11 WHILE PS DO WHILE PS DO IF s IF skeypkeypkey key THEN p THEN pbfbf：=1=1；p p：=p=plchildlchild ELSE p ELSE pbfbf：=-1=-1；p p：=p=prchild;rchild;原来从原来从原来从原来从psps的所有结点的叶全部为的所有结点的叶全部为的所有结点的叶全部为的所有结点的叶全部为0 0，所以计算方法并不是用定义左深，所以计算方法并不是用定义左深，所以计算方法并不是用定义左深，所以计算方法并不是用定义左深右右右右深，方向

26、也不是从下到上深，方向也不是从下到上深，方向也不是从下到上深，方向也不是从下到上 9.2 9.2 动态查找表动态查找表（3）判）判a为根的子树是否失去平衡为根的子树是否失去平衡 balanced:=true;CAES abf=0：abf：=d 原来为原来为0,插入后为插入后为d abf+d=0：abf：=0 原来为原来为1(-1),插入插入-1/1后为后为0 ELSE 失去平衡失去平衡 IF d=+1 THEN CASE bbf=1：LL-rotation bbf=-1：LR-rotation ENDC；ELSE CASE bbf=-1：RR-rotation bbf=1：RL-rotatio

27、n ENDC；balanced：=false ENDC；9.2 9.2 动态查找表动态查找表IF NOT balanced THEN CASE RL，LR旋转处理后，旋转处理后，b：=c f=NIL:t：=b;b指向失去平衡调整后子树根指向失去平衡调整后子树根 flchild=a:flchild：=b;frchild=a:frchild：=b ENDC；ENDP；ins_AVLtree平衡树查找时间复杂度为平衡树查找时间复杂度为O(logn)9.3 9.3 哈希查找表哈希查找表 前面介绍的查找算法前面介绍的查找算法前面介绍的查找算法前面介绍的查找算法,有一个共同特点有一个共同特点有一个共同特点

28、有一个共同特点:就是以待查关键字就是以待查关键字就是以待查关键字就是以待查关键字k k在表中，通过一系列在表中，通过一系列在表中，通过一系列在表中，通过一系列比较比较比较比较来确定该记录在表中的来确定该记录在表中的来确定该记录在表中的来确定该记录在表中的“地址地址地址地址”。这一节将介绍另一种通过这一节将介绍另一种通过这一节将介绍另一种通过这一节将介绍另一种通过计算计算计算计算来查找的新型方法来查找的新型方法来查找的新型方法来查找的新型方法-哈希哈希哈希哈希法（法（法（法（HashHash）或称杂凑法、散列法。）或称杂凑法、散列法。）或称杂凑法、散列法。）或称杂凑法、散列法。设关键字集合为设关

29、键字集合为设关键字集合为设关键字集合为A A，地址空间为，地址空间为，地址空间为，地址空间为D D，哈希法就是在，哈希法就是在，哈希法就是在，哈希法就是在A A和和和和D D之之之之间建立一种函数关系间建立一种函数关系间建立一种函数关系间建立一种函数关系HH，通过计算函数，通过计算函数，通过计算函数，通过计算函数HH（k k），就能得到关键），就能得到关键），就能得到关键），就能得到关键字字字字KK的地址。的地址。的地址。的地址。关键字集关键字集关键字集关键字集A A m m地址空间地址空间地址空间地址空间D D n n哈希函数哈希函数哈希函数哈希函数 H H（k k）9.3 9.3 哈希查找

30、表哈希查找表 设设设设D D是长度为是长度为是长度为是长度为n n的表，的表，的表，的表，A A是含是含是含是含mm个记录的关键字集合，个记录的关键字集合，个记录的关键字集合，个记录的关键字集合，如果存在一个如果存在一个如果存在一个如果存在一个函数函数函数函数HH，使得对，使得对，使得对，使得对A A中任一关键字中任一关键字中任一关键字中任一关键字KKi i，均有，均有，均有，均有，0H 0H（K Ki i ）n-1 i=1 n-1 i=1，2 2，mm 同时同时同时同时,K,Ki i 所标识的记录所标识的记录所标识的记录所标识的记录R R i i在表在表在表在表D D中的地址是中的地址是中的

31、地址是中的地址是H(KH(Ki i)，则称函数则称函数则称函数则称函数HH为关键字集合为关键字集合为关键字集合为关键字集合A A到地址空间到地址空间到地址空间到地址空间D D之间的哈希函数，之间的哈希函数，之间的哈希函数，之间的哈希函数，地址空间地址空间地址空间地址空间D D为哈希表。为哈希表。为哈希表。为哈希表。哈希函数并不一定是一对一的，例如，当哈希函数并不一定是一对一的，例如，当哈希函数并不一定是一对一的，例如，当哈希函数并不一定是一对一的，例如，当mmn n时，对任何时，对任何时，对任何时，对任何哈希函数哈希函数哈希函数哈希函数HH，至少存在两个关键字，至少存在两个关键字，至少存在两个

32、关键字，至少存在两个关键字KKi i K Kj j ，使得，使得，使得，使得H(KH(Ki i)=H(K)=H(Kj j)，这种对不同关键字而得到同一地址的现象，成为，这种对不同关键字而得到同一地址的现象，成为，这种对不同关键字而得到同一地址的现象，成为，这种对不同关键字而得到同一地址的现象，成为冲突冲突冲突冲突。9.3 9.3 哈希查找表哈希查找表 因此，在应用哈希查找方法时，主要要解决两个因此，在应用哈希查找方法时，主要要解决两个因此，在应用哈希查找方法时，主要要解决两个因此，在应用哈希查找方法时，主要要解决两个技术问题：技术问题：技术问题：技术问题：一是构造好哈希函数的方法一是构造好哈希

33、函数的方法一是构造好哈希函数的方法一是构造好哈希函数的方法;二是研究解决冲突的方法。二是研究解决冲突的方法。二是研究解决冲突的方法。二是研究解决冲突的方法。一一一一.哈希函数构造方法哈希函数构造方法哈希函数构造方法哈希函数构造方法 一个好的哈希函数应满足下列两个条件：一个好的哈希函数应满足下列两个条件：一个好的哈希函数应满足下列两个条件：一个好的哈希函数应满足下列两个条件：计算简单容易计算简单容易计算简单容易计算简单容易 冲突极少冲突极少冲突极少冲突极少9.3 9.3 哈希查找表哈希查找表1 1直接哈希函数直接哈希函数直接哈希函数直接哈希函数 取关键字本身或关键字的某个线性函数值作为哈希地址，

34、取关键字本身或关键字的某个线性函数值作为哈希地址，取关键字本身或关键字的某个线性函数值作为哈希地址，取关键字本身或关键字的某个线性函数值作为哈希地址，即：即：即：即：H H（keykey）=key =key 或或或或HH（keykey）=a*key+b =a*key+b （a a，b b为常数）为常数）为常数）为常数）例如：有一个解放后出生人口调查表，每个记录包含年份、人例如：有一个解放后出生人口调查表，每个记录包含年份、人例如：有一个解放后出生人口调查表，每个记录包含年份、人例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为数等数据项，其中年

35、分为关键字，则哈希函数可取为数等数据项，其中年分为关键字，则哈希函数可取为数等数据项，其中年分为关键字，则哈希函数可取为:HH（keykey）=key+=key+（-1948-1948）这样就可以方便地存储和查找这样就可以方便地存储和查找这样就可以方便地存储和查找这样就可以方便地存储和查找19481948年后任一年的记录。年后任一年的记录。年后任一年的记录。年后任一年的记录。地址地址地址地址年份年份年份年份人数人数人数人数011949 2219709.3 9.3 哈希查找表哈希查找表2 2数字分析法数字分析法数字分析法数字分析法 设个位数的关键字，由个不同的符号组成，此个设个位数的关键字，由个

36、不同的符号组成，此个设个位数的关键字，由个不同的符号组成，此个设个位数的关键字，由个不同的符号组成，此个符号在关键字的各位出现的频率不一定相同，可能在某些位上符号在关键字的各位出现的频率不一定相同，可能在某些位上符号在关键字的各位出现的频率不一定相同，可能在某些位上符号在关键字的各位出现的频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近于次，而在另均匀分布，即每个符号出现的次数都接近于次，而在另均匀分布，即每个符号出现的次数都接近于次，而在另均匀分布，即每个符号出现的次数都接近于次，而在另一些位上分布不均匀。一些位上分布不均匀。一些位上分布不均匀。一些位上分布不均匀。则选择其

37、中分布均匀的则选择其中分布均匀的则选择其中分布均匀的则选择其中分布均匀的s s位作为哈希地位作为哈希地位作为哈希地位作为哈希地址，即址，即址，即址，即 H H（keykey）=“key=“key中数字均匀分布的中数字均匀分布的中数字均匀分布的中数字均匀分布的s s位位位位”，这便是数字，这便是数字，这便是数字，这便是数字分析哈希函数。分析哈希函数。分析哈希函数。分析哈希函数。例：由例：由例：由例：由8080个记录，关键字为个记录，关键字为个记录，关键字为个记录，关键字为8 8位十进制数，（位十进制数，（位十进制数，（位十进制数，（n=80n=80，r=10r=10，d=8d=8）对关键字的各位

38、进行分析，发现：第）对关键字的各位进行分析，发现：第）对关键字的各位进行分析，发现：第）对关键字的各位进行分析，发现：第1 1，2 2位都是位都是位都是位都是“8“8，1”1”，第，第，第，第3 3位只取位只取位只取位只取1 1，2 2，3 3或或或或4 4，第，第，第，第8 8位只取位只取位只取位只取2 2，5 5或或或或7 7，即，即，即，即1010个数在这四个数在这四个数在这四个数在这四位分布不均匀，不取。可在剩下的位分布不均匀，不取。可在剩下的位分布不均匀，不取。可在剩下的位分布不均匀，不取。可在剩下的4 4，5 5，6 6，7 7位中任取两位，位中任取两位，位中任取两位，位中任取两位

39、，作为哈希地址。作为哈希地址。作为哈希地址。作为哈希地址。9.3 9.3 哈希查找表哈希查找表3 3平方取中法平方取中法平方取中法平方取中法 取关键字平方后的中间几位作为哈希地址，即哈希函数为取关键字平方后的中间几位作为哈希地址，即哈希函数为取关键字平方后的中间几位作为哈希地址，即哈希函数为取关键字平方后的中间几位作为哈希地址，即哈希函数为:H H（keykey）=“key=“key2 2的中间几位的中间几位的中间几位的中间几位”其中，所取的位数由哈希表的大小确定。其中，所取的位数由哈希表的大小确定。其中，所取的位数由哈希表的大小确定。其中，所取的位数由哈希表的大小确定。9.3 9.3 哈希查

40、找表哈希查找表4 4折叠法折叠法折叠法折叠法将关键字分割成位数相等的几部分（最后一部分位数可以将关键字分割成位数相等的几部分（最后一部分位数可以将关键字分割成位数相等的几部分（最后一部分位数可以将关键字分割成位数相等的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去高位的进位）作为哈希地不同），取这几部分的叠加和（舍去高位的进位）作为哈希地不同），取这几部分的叠加和（舍去高位的进位）作为哈希地不同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。址。位数由存储地址的位数确定。址。位数由存储地址的位数确定。址。位数由存储地址的位数确定。相加时有两种方法：相

41、加时有两种方法：相加时有两种方法：相加时有两种方法：一是移位叠加法，即将每部分得最后一位对齐，然后相加；一是移位叠加法，即将每部分得最后一位对齐，然后相加；一是移位叠加法，即将每部分得最后一位对齐，然后相加；一是移位叠加法，即将每部分得最后一位对齐，然后相加；另一种是间界叠加法，即将关键字看作一纸条，从一端向另一另一种是间界叠加法，即将关键字看作一纸条，从一端向另一另一种是间界叠加法，即将关键字看作一纸条，从一端向另一另一种是间界叠加法，即将关键字看作一纸条，从一端向另一端沿间界逐次折叠，然后对齐相加。端沿间界逐次折叠，然后对齐相加。端沿间界逐次折叠，然后对齐相加。端沿间界逐次折叠，然后对齐相

42、加。9.3 9.3 哈希查找表哈希查找表设关键字设关键字设关键字设关键字key=dkey=d3 r3 rd d 2 r+12 r+1d d2 r2 rd d r+1r+1d d r rd d2 2d d1 1允许的存储地址有允许的存储地址有允许的存储地址有允许的存储地址有r r位。位。位。位。则则则则 移位叠加法为：移位叠加法为：移位叠加法为：移位叠加法为：d d r r d d2 2d d1 1 d d2 r 2 r d d r+1r+1 +)+)d d r r d d 2 r+12 r+1S Sr r S S2 2S S1 19.3 9.3 哈希查找表哈希查找表5 5除留余数法除留余数法除

43、留余数法除留余数法 取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长mm的数的数的数的数p p除后的余数为哈希除后的余数为哈希除后的余数为哈希除后的余数为哈希地址。地址。地址。地址。即即即即 H H（keykey）=key MOD p=key MOD p，pmpm p p的选择很重要，选得不好会产生很多冲突，的选择很重要，选得不好会产生很多冲突，的选择很重要，选得不好会产生很多冲突，的选择很重要，选得不好会产生很多冲突，通常，选择通常，选择通常，选择通常，选择 p m p m的某个质数。的某个质数。的某个质数。的某个质数。6 6随

44、机数法随机数法随机数法随机数法 选择一个随机函数，取关键字的随机函数值作为它的哈希地址。选择一个随机函数，取关键字的随机函数值作为它的哈希地址。选择一个随机函数，取关键字的随机函数值作为它的哈希地址。选择一个随机函数，取关键字的随机函数值作为它的哈希地址。即即即即 H H（keykey）=random=random（key key）9.3 9.3 哈希查找表哈希查找表二二二二.处理冲突的方法处理冲突的方法处理冲突的方法处理冲突的方法 冲突冲突冲突冲突是指由关键字得到的是指由关键字得到的是指由关键字得到的是指由关键字得到的HashHash地址上已有其他记录地址上已有其他记录地址上已有其他记录地址

45、上已有其他记录,处理冲突处理冲突处理冲突处理冲突就是为该关键字找到另一个就是为该关键字找到另一个就是为该关键字找到另一个就是为该关键字找到另一个“空空空空”的的的的HashHash地址。地址。地址。地址。1.1.开放定址法开放定址法开放定址法开放定址法 H Hi i=（HH（keykey）+d+di i）mod m i=1mod m i=1，2 2m-1;m-1;其中其中其中其中:HHi i 为第为第为第为第i i次冲突的地址次冲突的地址次冲突的地址次冲突的地址,HH（keykey）为为为为HashHash函数值函数值函数值函数值,m m 为为为为HashHash表表长表表长表表长表表长,d

46、di i 为增量序列为增量序列为增量序列为增量序列9.3 9.3 哈希查找表哈希查找表 H Hi i=（HH（keykey）+d+di i）mod m i=1mod m i=1，2 2m-1;m-1;其中其中其中其中:d di i为增量序列为增量序列为增量序列为增量序列,有三种取法：有三种取法：有三种取法：有三种取法：d di i=1=1，2 2，3 3m-1 m-1 称为线性探测再散列称为线性探测再散列称为线性探测再散列称为线性探测再散列 d di i=1=12 2,-1,-12 2,2,22 2,-2,-22 2,3,32 2kk2 2|k|m-1|k|m-1 称为二次探测再散列称为二次探

47、测再散列称为二次探测再散列称为二次探测再散列 d di i=伪随机序列伪随机序列伪随机序列伪随机序列 称为伪随机探测再散列称为伪随机探测再散列称为伪随机探测再散列称为伪随机探测再散列例：设例：设例：设例：设m=16,m=16,表中已有关键字表中已有关键字表中已有关键字表中已有关键字,分别为：分别为：分别为：分别为：1919，7070，3333三个记录，三个记录，三个记录，三个记录，Hash Hash函数取为函数取为函数取为函数取为HH（keykey）=key mod13=key mod13，现第四个关键字为，现第四个关键字为，现第四个关键字为，现第四个关键字为1818的记的记的记的记录要填入表

48、中，由录要填入表中，由录要填入表中，由录要填入表中，由HashHash函数得地址函数得地址函数得地址函数得地址5 5，产生冲突，产生冲突，产生冲突，产生冲突 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1570 19 3370 19 3370 19 33 1870 19 33 18 H1 H2 H3 18 70 19 3318 70 19 33H2 H170 19 3370 19 33线性线性线性线性二次二次二次二次伪随机伪随机伪随机伪随机伪随机数序列伪随机数序列伪随机数序列伪随机数序列 9 9

49、 H H1 14 mod 16 =144 mod 16 =14 18189.3 9.3 哈希查找表哈希查找表2.2.再哈希法再哈希法再哈希法再哈希法 H Hi i=RH=RHi i（keykey）i=1 i=1，2 2n;n;RH RHi i 为不同哈希函数为不同哈希函数为不同哈希函数为不同哈希函数 用用用用n n个不同哈希函数排成一个序列个不同哈希函数排成一个序列个不同哈希函数排成一个序列个不同哈希函数排成一个序列,当发生冲突时当发生冲突时当发生冲突时当发生冲突时,由由由由RHRHi i确定第确定第确定第确定第i i次冲突的地址次冲突的地址次冲突的地址次冲突的地址HHi i3.3.链地址法链

50、地址法链地址法链地址法 将关键字发生冲突的记录存储在同一个线性链表中。将关键字发生冲突的记录存储在同一个线性链表中。将关键字发生冲突的记录存储在同一个线性链表中。将关键字发生冲突的记录存储在同一个线性链表中。例：例：例：例：HH（keykey）=key mod 13 =key mod 13 对关键字对关键字对关键字对关键字1919，1414，2323，0101，6868，2020，8484，2727，5555，1111，1010，7979 处理的结果为：处理的结果为：处理的结果为：处理的结果为：0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 910101111121