第7章 查找 丽水学院工学院

教学内容 7.1　查找的基本概念 7.2　线性表的查找 7.3　树表的查找 7.4　哈希表的查找

教学目标 1.熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法； 2.熟练掌握二叉排序树的构造和查找算法及其性能分析方法； 3.掌握二叉排序树的插入算法，掌握二叉排序树的删除方法； 4.熟练掌握哈希函数（除留余数法）的构造 5.熟练掌握哈希函数解决冲突的方法及其特点

7.1 查找的基本概念 查找表: 由同一类型的数据元素（或记录）构成的集合 静态查找表： 查找的同时对查找表不做修改操作（如插入和删除） 是一种数据结构 查找表: 由同一类型的数据元素（或记录）构成的集合 静态查找表： 查找的同时对查找表不做修改操作（如插入和删除） 动态查找表： 查找的同时对查找表具有修改操作 关键字 记录中某个数据项的值，可用来识别一个记录 主关键字： 唯一标识数据元素 次关键字： 可以标识若干个数据元素

关键字的平均比较次数，也称平均搜索长度ASL(Average Search Length) 查找算法的评价指标 关键字的平均比较次数，也称平均搜索长度ASL(Average Search Length) n：记录的个数 pi：查找第i个记录的概率 ( 通常认为pi =1/n ) ci：找到第i个记录所需的比较次数

7.2 线性表的查找 一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、分块查找

顺序查找 应用范围： 顺序表或线性链表表示的静态查找表 表内元素之间无序 顺序表的表示 typedef struct { 　　顺序表或线性链表表示的静态查找表 　　表内元素之间无序 typedef struct { ElemType *R; //表基址 int length; //表长 }SSTable; 顺序表的表示

第2章在顺序表L中查找值为e的数据元素 int LocateELem(SqList L,ElemType e) { for (i=0;i< L.length;i++) if (L.elem[i]==e) return i+1; return 0;} 改进：把待查关键字key存入表头（“哨兵”），从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

int Search_Seq( SSTable ST , KeyType key ){ //若成功返回其位置信息，否则返回0 ST.R[0].key =key; for( i=ST.length; ST.R[ i ].key!=key; - - i ); //不用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++) return i; }

顺序查找的性能分析 空间复杂度：一个辅助空间。 时间复杂度： 1) 查找成功时的平均查找长度 设表中各记录查找概率相等 ASLs(n)=(1+2+ ... +n)/n =(n+1)/2 2)查找不成功时的平均查找长度 ASLf =n+1

顺序查找算法有特点 算法简单，对表结构无任何要求（顺序和链式） n很大时查找效率较低 改进措施：非等概率查找时，可按照查找概率进行排序。

练习:判断对错 n个数存在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度ASL不同。 查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其ASL要比无序表ASL小。

折半查找 若k==R[mid].key，查找成功 若k<R[mid].key，则high=mid-1 若k>R[mid].key，则low=mid+1 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid

若k<R[mid].key，则high=mid-1 若k>R[mid].key，则low=mid+1 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid

直至low>high时，查找失败 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high

折半查找（非递归算法） 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k==R[mid].key，查找成功 若k<R[mid].key，则high=mid-1 若k>R[mid].key，则low=mid+1 重复上述操作，直至low>high时，查找失败

【算法描述】-算法7.3 int Search_Bin(SSTable ST,KeyType key){ //若找到，则函数值为该元素在表中的位置，否则为0 low=1;high=ST.length; while(low<=high){ mid=(low+high)/2; if(key==ST.R[mid].key) return mid; else if(key<ST.R[mid].key) high=mid-1;//前一子表查找 else low=mid+1; //后一子表查找 } return 0; //表中不存在待查元素 }

折半查找（递归算法） int Search_Bin (SSTable ST, keyType key, int low, int high) { if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2; if(key等于ST.elem[mid].key) return mid; else if(key小于ST.elem[mid].key) ……..//递归 else……. //递归 }

- Software Engineer position Facebook - Software Engineer position Given the numbers 1 to 1000, what is the minimum number of guesses needed to find a specific number, if you are given the hint "higher" or "lower" for each guess you make ??

折半查找的性能分析－判定树 -1 3-4 6-7 9-10 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11- 6 3 9 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 -1 3-4 6-7 9-10 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11- 6 3 9 1 4 7 10 2 5 8 11 h 外结点 内结点 > < = 若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。

练习:假定每个元素的查找概率相等，求查找成功时的平均查找长度。 -1 3-4 6-7 9-10 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11- 6 3 9 1 4 7 10 2 5 8 11 h 外结点 内结点 > < = ASL＝1/11*(1*1＋2×2＋4×3+4*4 )＝33/11=3

查找成功时比较次数：为该结点在判定树上的层次数，不超过树的深度 d =  log2 n  + 1 -1 3-4 6-7 9-10 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11- 6 3 9 1 4 7 10 2 5 8 11 h 外结点 内结点 > < = 查找成功时比较次数：为该结点在判定树上的层次数，不超过树的深度 d =  log2 n  + 1 查找不成功的过程就是走了一条从根结点到外部结点的路径d或d-1。

折半查找的性能分析 查找过程：每次将待查记录所在区间缩小一半，比顺序查找效率高,时间复杂度O(log2 n) 适用条件：采用顺序存储结构的有序表，不宜用于链式结构

分块查找（块间有序，块内无序） 索引表 最大关键字 起始地址 第1块 第2块 第3块 分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。 索引表 最大关键字 22 48 86 起始地址 1 7 13 22 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 48 86 第1块 第2块 第3块

分块查找过程 ① 对索引表使用折半查找法（因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；

分块查找性能分析 查找效率：ASL=Lb+Lw 例如，当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5 S为每块内部的记录个数，n/s即块的数目 例如，当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5

分块查找优缺点 优点：插入和删除比较容易，无需进行大量移动。 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。 适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

7.3 树表的查找 二叉排序树 平衡二叉树 B-树 B+树 键树 表结构在查找过程中动态生成 对于给定值key 若表中存在，则成功返回；

二叉排序树 二叉排序树或是空树，或是满足如下性质的二叉树： (1)若其左子树非空，则左子树上所有结点的值均小于根结点的值； (2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值； (3)其左右子树本身又各是一棵二叉排序树

练习 下列图形中，哪个不是二叉排序树 ？

练习 中序遍历二叉排序树后的结果有什么规律？ 递增 得到一个关键字的递增有序序列 45 12 53 3 37 24 100 61 90 78 3，12，24，37，45，53，61，78，90，100 递增 得到一个关键字的递增有序序列

二叉排序树的操作－查找 若查找的关键字等于根结点，成功 否则 若小于根结点，查其左子树 若大于根结点，查其右子树 在左右子树上的操作类似 　若小于根结点，查其左子树 　若大于根结点，查其右子树 在左右子树上的操作类似 122 250 300 110 200 99 105 230 216

【算法思想】 （1）若二叉排序树为空，则查找失败，返回空指针。 （2）若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较： ① 若key等于T->data.key，则查找成功，返回根结点地址； ② 若key小于T->data.key，则进一步查找左子树； ③ 若key大于T->data.key，则进一步查找右子树。

【算法描述】 BSTree SearchBST(BSTree T,KeyType key) { if((!T) || key==T->data.key) return T; else if (key<T->data.key) return SearchBST(T->lchild,key); //在左子树中继续查找 else return SearchBST(T->rchild,key); //在右子树中继续查找 } // SearchBST

二叉排序树的操作－插入 插入的元素一定在叶结点上 若二叉排序树为空，则插入结点应为根结点 否则，继续在其左、右子树上查找 树中已有，不再插入 树中没有，查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子 插入的元素一定在叶结点上

二叉排序树的操作－插入 45 12 53 3 37 24 100 61 90 78 20 插入结点20

二叉排序树的操作－生成 从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树 {10， 18， 3， 8， 12， 2， 7}

不同插入次序的序列生成不同形态的二叉排序树 二叉排序树的操作－生成 不同插入次序的序列生成不同形态的二叉排序树 40，24，12，37，55 12，24，37，40，55 12 24 37 40 55 40 24 55 12 37

二叉排序树的操作－删除 将因删除结点而断开的二叉链表重新链接起来 防止重新链接后树的高度增加

北京林业大学信息学院 2018年9月19日

删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。 被删结点缺右子树，可以拿它的左子女结点顶替它的位置，再释放它。 被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。 被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。

查找的性能分析 第i层结点需比较i次。在等概率的前提下，上述两图的平均查找长度为： 12 24 37 40 55 40 24 55 12

查找的性能分析 平均查找长度和二叉树的形态有关，即， 最好：log2n（形态匀称，与二分查找的判定树相似） 最坏: （n+1)/2（单支树） 40 24 55 12 37

平衡二叉树 问题：如何提高二叉排序树的查找效率？ 尽量让二叉树的形状均衡 平衡因子:该结点左子树与右子树的高度差 左、右子树是平衡二叉树； 所有结点的左、右子树深度之差的绝对值≤ 1 平衡因子:该结点左子树与右子树的高度差

1989奥斯卡是最佳短片奖--《Balance》 世界需要平衡，破坏平衡的一方，也许会一时很强势的称霸，最终的结局逃不过孤立和落空

任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树； 对于一棵有n个结点的AVL树，其高度保持在O(log2n)数量级，ASL也保持在O(log2n)量级。

练习：判断下列二叉树是否AVL树？ 2 -1 -1 1 -1 1 1 (a) 平衡树 (b) 不平衡树

如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。 LL平衡旋转 RR平衡旋转 LR平衡旋转 RL平衡旋转 保证二叉排序树的次序不变

1）LL平衡旋转： 2）RR平衡旋转： A B C 若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。

3）LR平衡旋转： 4）RL平衡旋转： A B C A B C 若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。 (以插入的结点C为旋转轴） A B C 4）RL平衡旋转： A B C A B C 若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。 (以插入的结点C为旋转轴） A B C

练习：请将下面序列构成一棵平衡二叉排序树 （ 13，24，37，90，53） 练习：请将下面序列构成一棵平衡二叉排序树 （ 13，24，37，90，53） 需要RL平衡旋转 (绕C先顺后逆） 13 37 24 -1 24 13 -2 13 -1 13 24 37 90 53 -1 37 -2 37 -1 24 需要RR平衡旋转 (绕B逆转,B为根） 90 37 1 90 53 90 53 37

变种的AVL树－－红黑树

红黑树之歌 The Red-Black Tree Song 滚石乐队

红黑树之歌 The Red-Black Tree Song 滚石乐队 I see a brand new node I want to paint it black. We need a balanced tree, we've got to paint it black. I want to find my key in log n time -- thats all, Rotating sub-trees 'round sure can be a ball. Can't have a lot of red nodes, We must paint them black. Unfortunately, coding them can be a bitch. If we had half a brain to splay trees we would switch. I see a brand new node I want to paint it black. No time for AVL trees we must paint it BLACK. And if they're still confusing, you should have no fear. Because outside this class, of them you'll never hear. I wanna paint 'em BLACK. Paint nodes black. Again and again.

红黑树定义 Red-Black tree, 简称RB-Tree 它是在1972年由鲁道夫·贝尔发明的，他称之为“对称二叉B树”，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的 特点：利用对树中的结点 “红黑着色”的要求，降低了平衡性的条件，达到局部平衡，有着良好的最坏情况运行时间，它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。 2018/9/19

红黑树的应用 C++ STL中的关联式容器：集合set、多重集合multiset、映射map、多重映射multimap JAVA集合框架：TreeSet和TreeMap 在Linux内核中，用于组织虚拟区间的数据结构也是红黑树 代码参见： linux/include/linux/rbtree.h linux/lib/rbtree.c 2018/9/19

红黑树的定义 平衡的扩充二叉搜索树，满足下面条件： 颜色特征：每个结点为“黑色”或“红色” 根特征：根结点永远是“黑色”的 外部特征：扩充外部叶结点都是空的“黑色”结点 内部特征：“红色”结点的两个子结点都是“黑色”的，即：不允许两个连续的红色结点 深度特征：对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同 2018/9/19

红黑树示例 树结点的结构 Key Data Color parent lchild rchild 2018/9/19

7.3 哈希表的查找 基本思想：记录的存储位置与关键字之间存在对应关系，Loc(i)=H(keyi) 哈希函数 集合 存储地址 hash 优点：查找速度极快O(1),查找效率与元素个数n无关

7.3 哈希表的查找 关键字 集合 存储地址 hash 北京林业大学信息学院

例1 若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V[01]单元； …… 将2001011810231的所有信息存入V[31]单元。 查找2001011810216的信息，可直接访问V[16]！

例2 数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。 … 14 11 9 内容 24 23

如何查找 根据哈希函数H（k）＝k 查找key=9,则访问H(9)=9号地址，若内容为9则成功； … 14 11 9 内容 地址 39 25 24 23 根据哈希函数H（k）＝k 查找key=9,则访问H(9)=9号地址，若内容为9则成功； 若查不到，则返回一个特殊值，如空指针或空记录。

哈希函数(杂凑函数)：哈希方法中使用的转换函数 有关术语 哈希方法(杂凑法) 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放； 查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。 哈希函数(杂凑函数)：哈希方法中使用的转换函数

有关术语 哈希表(杂凑表)：按上述思想构造的表 冲 突：不同的关键码映射到同一个哈希地址 同义词：具有相同函数值的两个关键字 … 14 11 9 内容 地址 39 25 24 23 冲 突：不同的关键码映射到同一个哈希地址 key1key2，但H(key1)=H(key2) 同义词：具有相同函数值的两个关键字

冲突现象举例 有冲突 （14，23，39，9，25，11） 哈希函数：H(k)=k mod 7 0 1 2 3 4 5 6 6个元素用7个 0 1 2 3 4 5 6 6个元素用7个 地址应该足够! 14 23 39 9 25 H(14)=14%7=0 11 H(25)=25%7=4 H(11)=11%7=4 同义词 有冲突

哈希函数在信息安全领域中的应用

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

点击QQ主界面下方的“QQ游戏”，游戏自动登录。 在“命令提示符”中输入“wmic process get>c:\123.txt”并回车。这条命令的作用是执行“wmic process get”命令并将结果保存在c盘的123.txt文件中。 打开此文件，按下“Ctrl”+“F” ，以“QQgame”为关键字进行搜索，在进程的末尾处会看见类似的语句： START QQUIN:12345678 PWDHASH: sjTC1t9/B5zJKZWg9u236g== INCOG:1。 将“PWDHASH”和“INCOG”之间的内容复制下来。这个就是QQ密码在经过MD5加密后再进行BASE64编码所得的结果。

打开MD5在线破解网站：www.md5.com.cn，在其中的文本框中输入刚才得到的密文，点击“MD5”碰撞就可以对密文进行解密了。

如何减少冲突 冲突是不可能避免的 构造好的哈希函数 制定一个好的解决冲突方案

哈希函数的构造方法 根据元素集合的特性构造 　地址空间尽量小 　均匀 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法

直接定址法 Hash(key) = a·key + b (a、b为常数) 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。 缺点：要占用连续地址空间，空间效率低。

直接定址法 例： {100，300，500，700，800，900}， 哈希函数Hash(key)=key/100 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100

除留余数法 （最常用重点掌握） Hash(key)=key mod p (p是一个整数) 关键：如何选取合适的p？ 技巧：设表长为m，取p≤m且为质数

构造哈希函数考虑的因素 ① 执行速度（即计算哈希函数所需时间）； ② 关键字的长度； ③ 哈希表的大小； ④ 关键字的分布情况； ⑤ 查找频率。

处理冲突的方法 1.开放定址法 2.链地址法

基本思想：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 1.开放定址法（开地址法） 基本思想：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 线性探测法 二次探测法 伪随机探测法

线性探测法 Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中：m为哈希表长度 di 为增量序列 1，2，…m-1，且di=i 一旦冲突，就找下一个空地址存入

线性探测法 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11； 哈希函数为Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 10 11 16 92 22 3 29 8 47 7 △ ▲ △ △ ① 47、7、11、16、92没有冲突 ② Hash(29)=7，有冲突，由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入 ③ 3 连续移动了两次

优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。 线性探测法的特点 优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素。 缺点：可能使第i个哈希地址的同义词存入第i+1个地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，产生“聚集”现象，降低查找效率。 解决方案：二次探测法

二次探测法 关键码集为 {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 10 8 29 7 16 92 47 3 22 11 △ ▲ △ △ Hash(3)=3，哈希地址冲突，由 H1=(Hash(3)+12) mod 11=4，仍然冲突； H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。

伪随机探测法 Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中：m为哈希表长度 di 为随机数

开放地址法建立哈希表步骤 step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的存储 空间还没有被占用，则将该元素存入；否则执行step2解决冲突。 step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若下一个存储地址仍被占用，则继续执行step2，直到找 到能用的存储地址为止。

2.链地址法(拉链法） 基本思想：相同哈希地址的记录链成一单链表，m个哈希地址就设m个单链表，然后用用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11

链地址法建立哈希表步骤 step1 取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行step2解决冲突。 step2 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。

链地址法的优点： 非同义词不会冲突，无“聚集”现象 链表上结点空间动态申请，更适合于表长不确定的情况

哈希表的查找 给定k值 计算H(k) 此地址为空 关键字==k 查找失败 查找成功 按处理冲突 方法计算Hi Y N 给定值与关键字比较

哈希表的查找 ASL=(1*6+2+3*3+4+9)/12=2.5 1 2 1 4 3 1 1 3 9 1 1 3 2018年9月19日 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等 (1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 1 68 27 55 19 20 84 79 23 11 10 1 2 1 4 3 1 1 3 9 1 1 3 H(19)=6 H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 H(14)=1 H(23)=10 H(1)=1 冲突，H1=(1+1) MOD16=2 H(68)=3 H(20)=7 2018年9月19日

哈希表的查找 ASL=(1*6+2*4+3+4)/12=1.75 (2) 用链地址法处理冲突 (2) 用链地址法处理冲突 关键字(19,14,23,1,68,20,84,27,55,11,10,79) 0 1 2 3 4 5 6 7 8 9 10 11 12 14 ^ 1 27 79 68 55 19 84 20 23 10 11

思考 关键字(19,14,23,1,68,20,84,27,55,11,10,79) 无序表查找ASL? 有序表折半查找ASL?

哈希表的查找效率分析 O(1)? 使用平均查找长度ASL来衡量查找算法，ASL取决于 哈希函数 处理冲突的方法 哈希表的装填因子 　　哈希函数 　　处理冲突的方法 　　哈希表的装填因子  越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

哈希表的查找效率分析 ASL与装填因子有关！既不是严格的O(1)，也不是O(n)

几点结论 对哈希表技术具有很好的平均性能，优于一些传统的技术 链地址法优于开地址法 除留余数法作哈希函数优于其它类型函数

哈希表应用举例 构造Hash函数的方法： 编译器对标识符的管理多是采用哈希表 将标识符中的每个字符转换为一个非负整数 将得到的各个整数组合成一个整数（可以将第一个、中间的和最后一个字符值加在一起，也可以将所有字符的值加起来） 将结果数调整到0~M-1范围内，可以利用取模的方法，Ki%M（M为素数）

POJ 3349 Snowflake Snow Snowflakes ACM题目描述 写一个程序判断是否有两片雪花是否相同。 每片雪都有六个角，每个角都有长度。如果两片雪花相对应的角的长度都相同，则认为这两片雪是相同的。

POJ 3349 Snowflake Snow Snowflakes 输入 第一行为雪花数n(0<n<=100000)，接下来n行，每行描述一片雪花，包括六个整数，代表六个角的长度，其长度大于等于0，小于10000000，该六个整数都是按照时针顺序描述的，可以是顺序针，也可以是反时针，同时可以从任意位置开始，即1 2 3 4 5 6 和4 3 2 1 6 5可以认为是相同的雪花。

POJ 3349 Snowflake Snow Snowflakes 输出 如果所有的雪花都是不相同的，则输出 “No two snowflakes are alike.”， 如果存在两片雪花是相同的，则输出 “Twin snowflakes found.”。

POJ 3349 Snowflake Snow Snowflakes 解题思路 根据题意，雪花数最多可达100000片，而每两片雪花的比较次数最多可达12种，每种情况要比较6个数，如果采用逐个比较，则最多情况要求比较100000*100000*12*6=720000000000，即7200亿次，这显然是一个天大的数字。 每片雪花有六个角，将六个角的长度累加，得到一个代表该雪花的总长度。初步设想是将总长度相同的雪花放在一起，如果要判断某片雪花，只要和总长度与它相同的组中的每片雪花进行比较，如果都不相同，就将该雪花也放入该组。

POJ 3349 Snowflake Snow Snowflakes 解题思路 如果每个组都代表不同的总长度，由于雪花各个角的长度取值范围是0至10000000，则每片雪花的总长度取值范围达0至60000000，采用不同总长度设一个组，将要一个长度为60000000的数组，显然也是不合理的。

POJ 3349 Snowflake Snow Snowflakes 解题思路 采用一种折中的方案，取一个自定义的素数，尽可能大，但不又超大，如99991，即定义一个99991个空间的数组，将各雪花总长度与99991取模，作为该雪花的存放组，而每一个组采用升序链表存储。该方法即采用哈希查找方法，哈希函数为H(Key)=K%99991。 如果要判断某片雪花，先求得其总长度，并与99991取模，找到其所在的链表，在该链表找到总长与之相同的雪花进行比较，如果成功，直接输出并结束。如果总长度相同的全比较完而没有找到匹配的，则直接插入该处，以保持链表的升序。

参考代码 typedef struct node { int arm[6]; //六个角的长度 struct node *next; int sum; //雪花六个角的总长度 }LNode;

参考代码 //判断是否有两片雪花相同，如果有，返回1， 否则返回0并插入该雪花 int isOk(LNode *p,int loc) { 用b数组存放p的排序结果 while(链表中总长度不大于p的每片雪花q) 如果总长度不相同，直接比较下一个 如果总长相同，则作如下操作 用a存放q的排序结果 如果a与b相同，则轮换进行比较，相同则返回1 如果a与b不相同，则比较下一个 } //如果前面没有返回，则插入该结点并保持有序 return 0;

小结 4.掌握平衡二叉树的定义 1.熟练掌握顺序表和有序表（折半查找）的查找算法及其性能分析方法； 2.熟练掌握二叉排序树的构造和查找算法及其性能分析方法； 3.熟练掌握二叉排序树的插入算法，掌握删除方法； 4.掌握平衡二叉树的定义 5.熟练掌握哈希函数（除留余数法）的构造 6.熟练掌握哈希函数解决冲突的方法及其特点 开放地址法（线性探测法、二次探测法） 链地址法 给定实例计算平均查找长度ASL，ASL依赖于装填因子