数据结构第7章查找

1、 2022年4月13日 2022年4月13日 2022年4月13日 第第7 7章查找章查找7.17.1查找的基本概念查找的基本概念7.27.2线性表的查找线性表的查找7.37.3树表的查找树表的查找7.47.4哈希表的查找哈希表的查找教学内容教学内容 2022年4月13日 1.熟练掌握顺序表和有序表（熟练掌握顺序表和有序表（折半查找折半查找）的查找算）的查找算法及其性能分析方法；法及其性能分析方法；2.熟练掌握熟练掌握二叉排序树的构造和查找二叉排序树的构造和查找算法及其性能算法及其性能分析方法；分析方法；3.掌握二叉排序树的掌握二叉排序树的插入插入算法，了解二叉排序树的算法，了解二叉排序树的删

2、除算法；删除算法；4.熟练掌握哈希函数熟练掌握哈希函数（除留余数法）（除留余数法）的构造的构造5.熟练掌握哈希函数熟练掌握哈希函数解决冲突的方法解决冲突的方法及其特点及其特点 教学目标教学目标 2022年4月13日 7.1 7.1 查找的基本概念查找的基本概念 查找表查找表: :由同一类型的数据元素（或记录）构成的集合由同一类型的数据元素（或记录）构成的集合 静态查找表：静态查找表：对查找表没有修改操作对查找表没有修改操作 动态查找表：动态查找表：对查找表具有修改操作对查找表具有修改操作 关键字关键字记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 主关键字：主

3、关键字：唯一标识数据元素唯一标识数据元素 次关键字：次关键字：可以标识若干个数据元素可以标识若干个数据元素是一种数据结构是一种数据结构 2022年4月13日 关键字的平均比较次数关键字的平均比较次数，也称，也称平均搜索长度平均搜索长度ASLASL( (AverageAverage Search Length Search Length) )n n：记录的个数：记录的个数pipi：查找第：查找第i i个记录的概率个记录的概率 ( ( 通常认为通常认为pi =1/n )pi =1/n )cici：找到第：找到第i i个记录所需的比较次数个记录所需的比较次数niiicpASL1查找算法的评价指标查找

4、算法的评价指标 2022年4月13日 7.2 7.2 线性表的查找线性表的查找一、顺序查找（线性查找）一、顺序查找（线性查找）二、折半查找（二分或对分查找）二、折半查找（二分或对分查找） 2022年4月13日 顺序查找顺序查找应用范围：应用范围：顺序表或线性链表表示的静态查找表顺序表或线性链表表示的静态查找表表内元素之间无序表内元素之间无序typedef struct ElemType *R; /表基址表基址 int length; /表长表长SSTable;顺序表的表示顺序表的表示 2022年4月13日 int LocateELem(SqList L,ElemType e) for (i=0

5、;i0; - -i) =n; i0; - -i) 或或 for(ifor(i=1; i=n; i+)=1; i=n; i+) return i; 2022年4月13日 空间复杂度：一个辅助空间。空间复杂度：一个辅助空间。 时间复杂度：时间复杂度：1) 1) 查找成功时的平均查找长度查找成功时的平均查找长度 设表中各记录查找概率相等设表中各记录查找概率相等 ASLASLs s(n(n)=(1+2+ . +)=(1+2+ . +n)/nn)/n =(n+1)/2 =(n+1)/22)2)查找不成功时的平均查找长度查找不成功时的平均查找长度 ASLASLf f =n+1=n+1顺序查找的性能分析顺序

6、查找的性能分析 2022年4月13日 算法简单，对表结构无任何要求（顺序和链式）算法简单，对表结构无任何要求（顺序和链式） n n很大时查找效率较低很大时查找效率较低 改进措施：改进措施：非等概率非等概率查找时，可按照查找概率进查找时，可按照查找概率进行排序。行排序。顺序查找算法有特点顺序查找算法有特点 2022年4月13日 n n个数存在一维数组个数存在一维数组A1.nA1.n中，在进行顺序查找时，中，在进行顺序查找时，这这n n个数的排列个数的排列有序或无序有序或无序其平均查找长度其平均查找长度ASLASL不同不同。 练习练习: :判断对错判断对错查找概率相等时，查找概率相等时，ASL相同

7、；相同；查找概率不等时，如果从前向后查找，则按查找概率查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其由大到小排列的有序表其ASL要比无序表要比无序表ASL小。小。 2022年4月13日 lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid

8、折半查找折半查找若若k=Rmid.key，查找成功，查找成功若若kRmid.key，则，则low=mid+1 2022年4月13日 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid若若k=Rmid.key，查找成功，查找成功若若kRmid.key，则，则l

9、ow=mid+1 2022年4月13日 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid直至直至lowhigh时，查找失败时，查找失败 2022年4月13日 折半查找（非递归算法）折半查找（非递归算法） 设表长为设表长为n n，lowlow、highhigh和和midmid分别指向待查元素所分别指向待查元素所在区间的上界、下界和中点在区间的上界、下界和中点, ,k k为给定值为给定值 初始时，

10、令初始时，令low=1,high=low=1,high=n,midn,mid= = (low+high)/2(low+high)/2 让让k k与与midmid指向的记录比较指向的记录比较若若k=k=Rmid.keyRmid.key，查找成功查找成功若若kkkRmid.keyRmid.key，则则low=mid+1low=mid+1 重复上述操作，直至重复上述操作，直至lowhighlowhigh时，查找失败时，查找失败 2022年4月13日 折半查找（递归算法）折半查找（递归算法）int Search_Bin (SSTable ST, keyType key, int low, int hi

11、gh) if(lowhigh) return 0; /查找不到时返回查找不到时返回0 mid=(low+high)/2; if(key与与ST.elemmid.key) return mid; else if(key小于小于ST.elemmid.key) ./递归递归 else. /递归递归 2022年4月13日 -13-46-79-101-22-34-55-67-88-910-1111-639147102581112h外结点外结点内结点内结点data.key进行比较：进行比较： 若若key等于等于T-data.key，则查找成功，返回根结点地，则查找成功，返回根结点地址；址； 若若key小于

12、小于T-data.key，则进一步查找左子树；，则进一步查找左子树； 若若key大于大于T-data.key，则进一步查找右子树。，则进一步查找右子树。【算法思想算法思想】 2022年4月13日 BSTree SearchBST(BSTree T,KeyType key) if(!T) | key=T-data.key) return T; else if (keydata.key) return SearchBST(T-lchild,key);/在左子树中继续查找在左子树中继续查找 else return SearchBST(T-rchild,key); /在右子树中继续查找在右子树中继续查

13、找 / SearchBST【算法描述算法描述】 2022年4月13日 二叉排序树的操作插入二叉排序树的操作插入插入的元素插入的元素一定在一定在叶结点上叶结点上若二叉排序树为空，则插入结点应为若二叉排序树为空，则插入结点应为根结点根结点否则，继续在其左、右子树上查找否则，继续在其左、右子树上查找树中已有，不再插入树中已有，不再插入树中没有，树中没有，查找查找直至某个叶子结点的左子树直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该或右子树为空为止，则插入结点应为该叶子结叶子结点点的左孩子或右孩子的左孩子或右孩子 2022年4月13日 4512533372410061907820插入结点插

14、入结点2020二叉排序树的操作插入二叉排序树的操作插入 2022年4月13日 10， 18， 3， 8， 12， 2， 710101810183101838101838 12101838 122101838 1227从空树出发，经过一系列的查找、插入操作之后，从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树可生成一棵二叉排序树二叉排序树的操作生成二叉排序树的操作生成 2022年4月13日 不同插入次序的序列生成不同形态的二叉排序树不同插入次序的序列生成不同形态的二叉排序树4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序树的

15、操作生成二叉排序树的操作生成 2022年4月13日 二叉排序树的操作删除二叉排序树的操作删除 2022年4月13日 2022年4月13日 2022年4月13日 第第i i层结点需比较层结点需比较i i次。在等概率的前提下，上述次。在等概率的前提下，上述两图的两图的平均查找长度平均查找长度为：为：)(35/ )54321 ()(2 . 25/ )23221 (11右图左图niiiniiicpcp40245512371224374055查找的性能分析查找的性能分析 2022年4月13日 平均查找长度和二叉树的形态有关，即，平均查找长度和二叉树的形态有关，即，最好：最好：loglog2 2n n（形

16、态匀称，与二分查找的判定树相似）（形态匀称，与二分查找的判定树相似）最坏最坏: : （n n+1)/2+1)/2（单支树）（单支树）查找的性能分析查找的性能分析40245512371224374055)( 35/ ) 54321 ()( 2 . 25/ ) 23221 (11右图左图niiiniiicpcp 2022年4月13日 问题：如何提高二叉排序树的查找效率？问题：如何提高二叉排序树的查找效率？尽量让二叉树的形状均衡尽量让二叉树的形状均衡左、右子树是平衡二叉树；左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 1 1平衡因子平衡因子: :该

17、结点左子树与右子树的高度差该结点左子树与右子树的高度差 2022年4月13日 v任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1-1、0 0 或或 1 1；如果；如果树中任意一个结点的平衡因子的绝对值大于树中任意一个结点的平衡因子的绝对值大于1 1，则这棵二叉树就失去平衡，不再是则这棵二叉树就失去平衡，不再是AVLAVL树；树；v对于一棵有对于一棵有n n个结点的个结点的AVLAVL树，其树，其高度保持在高度保持在O(logO(log2 2n n) )数量级，数量级，ASLASL也保持在也保持在O(logO(log2 2n n) )量级。量级。 2022年4月13日 (a) (a) 平

18、衡树平衡树 (b) (b) 不平衡树不平衡树练习：判断下列二叉树是否练习：判断下列二叉树是否AVLAVL树？树？0 00 00 01 11 1-1-1-1-10 00 00 01 1-1-1 2022年4月13日 如果在一棵如果在一棵AVLAVL树中插入一个新结点，就有可能造树中插入一个新结点，就有可能造成失衡，此时必须成失衡，此时必须重新调整树的结构重新调整树的结构，使之恢复，使之恢复平衡。我们称调整平衡过程为平衡。我们称调整平衡过程为平衡旋转平衡旋转。LLLL平衡旋转平衡旋转RRRR平衡旋转平衡旋转LRLR平衡旋转平衡旋转RLRL平衡旋转平衡旋转保证二叉排序树保证二叉排序树的次序不变的次序

19、不变 2022年4月13日 若在若在A A的的左子树的左子树上插入左子树的左子树上插入结点，使结点，使A A的平衡因子从的平衡因子从1 1增加至增加至2 2，需要进行一次，需要进行一次顺时针旋转顺时针旋转。( (以以B B为旋转轴）为旋转轴）若在若在A A的的右子树的右子树上插入右子树的右子树上插入结点，使结点，使A A的平衡因子从的平衡因子从-1-1增加增加至至-2-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。( (以以B B为旋转轴）为旋转轴） 2022年4月13日 若在若在A的的右右子树的子树的左左子树上插入子树上插入结结点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2

20、，需要需要先进行先进行顺顺时针旋转，再时针旋转，再逆逆时时针旋转针旋转。(以插入的结点以插入的结点C为旋转轴）为旋转轴）若在若在A的的左左子树的子树的右右子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至2，需要，需要先进行先进行逆逆时针旋转，再时针旋转，再顺顺时针旋转。时针旋转。(以插入的结点以插入的结点C为旋转轴）为旋转轴） 2022年4月13日 0 013130 037370 024240 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）0 09090-1-12424-1-

21、137370 053531 190903737需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）0 037370 090900 053530 037370 090900 05353 2022年4月13日 变种的变种的AVLAVL树树红红黑树黑树 2022年4月13日 I see a brand new nodeI want to paint it black. We need a balanced tree,weve got to paint it black. I want to find my key in log n time - thats all,Rotating sub-tr

22、ees round sure can be a ball. I see a brand new nodeI want to paint it black. Cant have a lot of red nodes,We must paint them black. Unfortunately, coding them can be a bitch.红红黑树之歌黑树之歌The Red-Black Tree SongIf we had half a brain to splay trees we would switch. I see a brand new nodeI want to paint

23、 it black. No time for AVL treeswe must paint it BLACK. And if theyre still confusing, you should have no fear.Because outside this class, of them youll never hear. I wanna paint em BLACK. Paint nodes black. Again and again. 2022年4月13日 7.3 7.3 哈希表的查找哈希表的查找 基本思想：基本思想：记录的存储位置与关键字之间存在记录的存储位置与关键字之间存在对应关

24、系，对应关系，Loc(iLoc(i)=)=H(keyiH(keyi) ) 优点：优点：查找速度极快查找速度极快O(1),查找效率与元素个数查找效率与元素个数n无关无关哈希函数哈希函数关键字关键字集合集合存储地址存储地址集合集合hash 2022年4月13日 若将学生信息按如下方式存入计算机，如：若将学生信息按如下方式存入计算机，如：将将20010118102200101181020101的所有信息存入的所有信息存入VV0101 单元；单元；将将20010118102200101181020202的所有信息存入的所有信息存入VV0202 单元；单元；将将200101181022001011810

25、23131的所有信息存入的所有信息存入V31V31单元。单元。查找查找20010118102200101181021616的信息，可直接访问的信息，可直接访问V16V16！例例1 1 2022年4月13日 数据元素序列数据元素序列(14(14，2323，3939，9 9，2525，11)11)，若规定每个，若规定每个元素元素k k的存储地址的存储地址H H（k k）k k，请画出存储结构图。，请画出存储结构图。141411119 9内容内容地址地址3939252524242323141411119 9232325253939例例2 2 2022年4月13日 根据哈希函数根据哈希函数H（k）k

26、查找查找key=9,key=9,则访问则访问H(9)=9H(9)=9号地址，若内容为号地址，若内容为9 9则成功；则成功；若查不到，则返回一个特殊值，如空指针或空记录。若查不到，则返回一个特殊值，如空指针或空记录。 如何查找如何查找141411119 9内容内容地址地址3939252524242323141411119 9232325253939 2022年4月13日 哈希方法哈希方法( (杂凑法杂凑法) )选取某个选取某个函数函数，依该函数按关键字计算元素的存储位置，依该函数按关键字计算元素的存储位置，并按此存放；并按此存放；查找时，由同一个函数对给定值查找时，由同一个函数对给定值k k计算

27、地址，计算地址，将将k k与地址与地址单元中元素关键码进行比单元中元素关键码进行比，确定查找是否成功。，确定查找是否成功。哈希函数哈希函数( (杂凑函数杂凑函数) )：哈希方法中使用的哈希方法中使用的转换函数转换函数有关术语有关术语 2022年4月13日 冲冲 突：突：不同的关键码映射到同一个哈希地址不同的关键码映射到同一个哈希地址哈希表哈希表( (杂凑表杂凑表) )：按上述思想构造的表按上述思想构造的表有关术语有关术语141411119 9内容内容地址地址3939252524242323141411119 9232325253939同义词：同义词：具有具有相同函数值相同函数值的两个关键字的两

28、个关键字key1 key2，但但H(key1)=H(key2) 2022年4月13日 （14，23，39，9，25，11）哈希函数：哈希函数：H(k)=k mod 72539239146个元素用个元素用7个个地址应该足够地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4同义词同义词 0 1 2 3 4 5 6冲突现象举例冲突现象举例 2022年4月13日 哈希函数在信息安全领域中的应用哈希函数在信息安全领域中的应用 2022年4月13日 wmic全称全称Windows Management Instrumentation Command-line（Win

29、dows管理规范命令行），它提管理规范命令行），它提供了从命令行接口和批命令脚本执行系统管理的支供了从命令行接口和批命令脚本执行系统管理的支持。通过它我们可以执行一些复杂的命令，从而更持。通过它我们可以执行一些复杂的命令，从而更为有效地管理系统。为有效地管理系统。 点击点击“开始开始”菜单菜单“运行运行”，输入，输入“cmd”运行运行“命令提示符命令提示符”，在其中输入如下命令，在其中输入如下命令“wmic process get”。第一次使用。第一次使用wmic时，它会提示你安装，时，它会提示你安装，安装过程只需几秒钟。安装过程只需几秒钟。MD5破解破解QQ密码密码 2022年4月13日 点

30、击点击QQ主界面下方的主界面下方的“QQ游戏游戏”，游戏自动登录。，游戏自动登录。在在 “ 命 令 提 示 符命 令 提 示 符 ” 中 输 入中 输 入 “ w m i c p ro c e s s getc:123.txt”并回车。这条命令的作用是执行并回车。这条命令的作用是执行“wmic process get”命令并将结果保存在命令并将结果保存在c盘的盘的123.txt文件中。文件中。打开此文件，按下打开此文件，按下“Ctrl”+“F” ，以，以“QQgame”为为关键字进行搜索，在进程的末尾处会看见类似的语句：关键字进行搜索，在进程的末尾处会看见类似的语句：START QQUIN:1

31、2345678 PWDHASH: sjTC1t9/B5zJKZWg9u236g= INCOG:1。将将“PWDHASH”和和“INCOG”之间的内容复制下之间的内容复制下来。这个就是来。这个就是QQ密码在经过密码在经过MD5加密后再进行加密后再进行BASE64编码所得的结果。编码所得的结果。 2022年4月13日 打开打开MD5在线破解网站：在线破解网站：，在其，在其中的文本框中输入刚才得到的密文，点击中的文本框中输入刚才得到的密文，点击“MD5”碰撞就可以对密文进行解密了。碰撞就可以对密文进行解密了。 2022年4月13日 冲突是不可能避免的冲突是不可能避免的如何减少冲突如何减少冲突构造好的

32、哈希函数构造好的哈希函数制定一个好的解决冲突方案制定一个好的解决冲突方案 2022年4月13日 哈希函数的构造方法哈希函数的构造方法根据元素集合的特性构造根据元素集合的特性构造地址空间尽量小地址空间尽量小均匀均匀1.1. 直接定址法直接定址法 2.2. 数字分析法数字分析法3.3. 平方取中法平方取中法4.4. 折叠法折叠法5.5. 除留余数法除留余数法6.6. 随机数法随机数法 2022年4月13日 Hash(key) = akey + b ( (a、b为常数为常数) )优点：优点：以关键码以关键码keykey的某个线性函数值为哈希的某个线性函数值为哈希地址，不会产生冲突。地址，不会产生冲突

33、。缺点：缺点：要占用连续地址空间，空间效率低。要占用连续地址空间，空间效率低。 直接定址法直接定址法 2022年4月13日 例：例： 100，300，500，700，800，900， 哈希函数哈希函数Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100直接定址法直接定址法 2022年4月13日 Hash(key)=key mod p (p是一个整数是一个整数)关键：关键：如何选取合适的如何选取合适的p？技巧：技巧：设表长为设表长为m，取，取pm且为且为质数质数 除留余数法除留余数法 （最常用重点掌握）（最常用重点掌握） 2022年4月13

34、日 执行速度（即计算哈希函数所需时间）；执行速度（即计算哈希函数所需时间）； 关键字的长度；关键字的长度； 哈希表的大小；哈希表的大小； 关键字的分布情况；关键字的分布情况； 查找频率。查找频率。构造哈希函数考虑的因素构造哈希函数考虑的因素 2022年4月13日 1.开放开放定址法定址法处理冲突的方法处理冲突的方法2.链地址法链地址法 2022年4月13日 基本思想：基本思想：有冲突时就去有冲突时就去寻找下一个空寻找下一个空的哈希地的哈希地址，只要哈希表足够大，空的哈希地址总址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。能找到，并将数据元素存入。 1.1.开放定址法（开地址法）

35、开放定址法（开地址法）线性探测法线性探测法二次探测法二次探测法伪随机探测法伪随机探测法 2022年4月13日 Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m为哈希表长度为哈希表长度 di 为增量序列为增量序列 1，2，m-1，且，且di=i一旦冲突，就找下一个空地址存入一旦冲突，就找下一个空地址存入线性探测法线性探测法 2022年4月13日 关键码集为关键码集为 47，7，29，11，16，92，22，8，3，设：设：哈希表表长为哈希表表长为m=m=11； 哈希函数为哈希函数为Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 1

36、0477 291116922283 47、7、11、16、92没有冲突没有冲突 Hash(29)=7，有冲突，由，有冲突，由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8为空，因此将为空，因此将29存入存入 线性探测法线性探测法 2022年4月13日 线性探测法的特点线性探测法的特点优点：优点：只要哈希表未被填满，只要哈希表未被填满，保证能找到保证能找到一个空一个空地址单元存放有冲突的元素。地址单元存放有冲突的元素。缺点：缺点：可能使第可能使第i个哈希地址的同义词存入第个哈希地址的同义词存入第i+1个个地址，这样本应存入第地址，这样本应存入第i+1个哈希地址的元素个哈希地

37、址的元素变成了第变成了第i+2个哈希地址的同义词，个哈希地址的同义词，产，产生生“聚集聚集”现象，降低查找效率。现象，降低查找效率。解决方案：解决方案：二次探测法二次探测法 2022年4月13日 二次探测法二次探测法关键码集为关键码集为 47，7，29，11，16，92，22，8，3，设：设： 哈希函数为哈希函数为Hash(key)=key mod 11 Hi=(Hash(key)di) mod m其中：其中：m为哈希表长度，为哈希表长度，m要求是某个要求是某个4k+3的质数的质数； di为增量序列为增量序列 12，-12，22，-22，q2 0 1 2 3 4 5 6 7 8 9 10829

38、716924732211 Hash(3)=3，哈希地址冲突，由，哈希地址冲突，由H1=(Hash(3)+12) mod 11=4，仍然冲突；，仍然冲突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。找到空的哈希地址，存入。 2022年4月13日 伪随机探测法伪随机探测法Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中：m为哈希表长度为哈希表长度 di 为随机数为随机数 2022年4月13日 2.2.链地址法链地址法( (拉链法）拉链法）基本思想：基本思想：相同哈希地址的记录链成一单链表，相同哈希地址的记录链成一单链表，m个哈个哈希地址就设

39、希地址就设m个单链表个单链表，然后用用一个数组将，然后用用一个数组将m个单个单链表的表头指针存储起来，形成一个动态的结构链表的表头指针存储起来，形成一个动态的结构0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011 2022年4月13日 链地址法的优点：链地址法的优点： 非同义词不会冲突，无非同义词不会冲突，无“聚集聚集”现象现象 链表上结点空间动态申请，更适合于表长不确链表上结点空间动态申请，更适合于表长不确定的情况定的情况 2022年4月13日 哈希表的查找哈希表的查找给定给定k k值值计算计算H(kH(k) )此地址为空此地址为空关键字

40、关键字=k=k查找失败查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiHiY YN NY YN N给定值与关键字比较给定值与关键字比较 2022年4月13日 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：哈希函数为：H(keyH(key)=key MOD 13, )=key MOD 13, 哈希表长为哈希表长为m=16m=16， 设每个记录的查找概率相等设每个记录的查找概率相等(1) (1) 用线性探测再散列处理冲突，即用线性探测再散列处理

41、冲突，即Hi=(Hi=(H(key)+diH(key)+di) MOD m) MOD m0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 1 68 27 55 19 20 84 79 23 11 101 2 1 4 3 1 1 3 9 1 1 3 H(19)=6H(14)=1H(23)=10H(1)=1 冲突，冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(27)=1 冲突，冲突，H1=(1+1)MOD16=2 冲突，冲突，H2=(1+2)MOD16=3 冲突，冲突，H3=(1+3)MOD16=4ASL=(1*6+2+3*3+4+9)/12=2.5哈希表的查找哈希表的查找 2022年4月13日 (2) (2) 用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 141277968551984202