chap_08_font_embedded

1、2011 by Fang, Can18.1 查找的基本概念8.3 基于树的查找法8.2 基于线性表的查找法8.4 计算式查找-哈希法1、 列表(查找表):是由同一类型的数据元 素(或记录)构成的集合, 可由任意数据 结构实现。2、关键字: 数据元素中某数据项的值, 用 以标识(识别)一个(组)数据元素(记录)。 若关键字可以唯一的识别一个记录，则称之为“主关键字”；若关键字识别的记录不唯一，则称之为“次关键字”。 根据某个给定值, 在列表中确定其关键字等于给定值的数据元素(记录)的过程称为查找。 若列表中存在待查记录, 则称“查找成功”。查找结果给出整个记录的信息, 或指示该记录在列表中的位置

2、； 若列表中不存在待查纪录, 则称“查找不成功”. 查找结果给出“空记录”或“空指针”。1)静态查找表:仅作查询和检索操作的列表。2)动态查找表:不仅作查询和检索操作，还 经常进行插入和删除操作的列表。 在查找算法中要用到三类参量，即：查找对象K（找什么）查找范围L（在哪找）查找的结果（K在L中的位置）其中为输入参量，在函数中不可缺少；为输出参量，可用函数返回值表示。为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。 对于长度为n的列表，查找成功时的平均查找长度为：nASL=P1C1+ P2C2+ PnCn =i=1PiCi其中：Pi

3、为查找列表中第i个数据元素的概率, Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。 有顺序查找、折半查找和分块查找法三种一、顺序查找法顺序查找的特点是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。 存储结构：顺序结构链式结构数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;1、顺序结构数据类型定义：、顺序结构数据类型定义：假设静态查找表的顺序存储结构为typedef struct elemMaxSize; / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空号单元留空

4、int length; / 表的长度 SSTable;ElemType或或ii假设给定值假设给定值 k=64,要求要求 elemi.key=k, 问问: i = ?结果结果: i = 7 21 37 88 19 92 21 37 88 19 92 5 5 64 56 80 75 13 64 56 80 75 13 9 90 1 2 3 4 5 6 7 8 9 10 11 n0 1 2 3 4 5 6 7 8 9 10 11 niiiiiiiint SeqSearch（SSTable l, KeyType k） i=l.length; while (i=1&l.elemi.key!=k)

5、 i-; if (i=1) return（i）else return(0); 循环条件循环条件i=1判断查找是否越界。判断查找是否越界。设置监视哨的顺序查找算法设置监视哨的顺序查找算法int SeqSearch（SSTable l, KeyType k） l.elem0.key=k; i=l.length; while (l.elemi.key!=k) i-; return（i）; l.r0为监视哨，可以防止越界。为监视哨，可以防止越界。 21 37 88 19 92 21 37 88 19 92 5 5 64 56 80 75 13 64 56 80 75 13 9 90 1 2 3 4 5

6、 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 n niik=56 21 37 88 19 92 21 37 88 19 92 5 5 64 56 80 75 13 64 56 80 75 13 9 90 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 n n5656结果结果: i = 8iik=606060结果结果: i = 0 i=1PiCi ASL=n 因为：因为：对顺序表而言对顺序表而言：Ci = n-i+1在等概率查找的情况下：在等概率查找的情况下：nPi121111n)i(nnASLniss顺序表

7、查找成功的平均查找长度顺序表查找成功的平均查找长度为：为：顺序表查找不成功的平均查找长度顺序表查找不成功的平均查找长度为：为： ASLus=n+1所以，顺序表查找的时间复杂度为所以，顺序表查找的时间复杂度为: :O(n)条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。 查找方法：由于列表是按关键字有序排列，所以可以基于“折半确定区间”的思想进行查找。优点：比较次数少，查找速度快;缺点：要求表为有序表，插入、删除困难。1、概念nk=64 的查找过程如下：lowhighmid mid midlow ：指示查找区间的下界high ：指示查找区间的上界mid = (low+high)/2:

8、每次比较、划分区 间的“点”low high0 1 2 3 4 5 6 7 8 9 10 1105 13 19 21 37 56 64 75 80 88 92int BinSrch （SqList l, KeyType k） low=1 ; high=l.length; /*置区间初值*/ while ( low=high) mid=(low+high) / 2; if (k=l.elemmid. key) return（mid）; /*找到待查元素*/ else if (k50时近似为时近似为分块查找要将列表组织成以下索引顺序结构：首先将列表分成若干个块(子表),一般情况下 块的长度均匀,最

9、后一块可以不满。每块中元 素任意排列(块内无序)，但块与块之间有序。 构造一个索引表,其中每个索引项对应一个块, 记录每块的起始位置及每块中的最大关键字 (或最小关键字)。索引表按关键字有序排列。 整个表由两部分组成：基本块表与索引表。22 48 86 1 6 11索索 引引 表表各块最大关键字各块最大关键字 各块起始地址各块起始地址22 12 13 22 12 13 8 8 9 9 33 42 38 24 48 74 49 33 42 38 24 48 74 49 1 2 3 4 5 6 7 8 9 10 11 12 13 1)由索引确定记录所在的块由索引确定记录所在的块(折半或顺序查折半或

10、顺序查);2)在块内进行查找在块内进行查找(顺序查顺序查)。索引可以根据查找表的特点来构造。索引可以根据查找表的特点来构造。可见可见: 索引顺序表查找索引顺序表查找的过程也是一个的过程也是一个 “缩小区间缩小区间”的查找过程。的查找过程。 分块查找的平均查找长度分块查找的平均查找长度 = 查找查找“索引索引”的平均查找长度的平均查找长度 + “块内块内” 查找的平均查找长度查找的平均查找长度 若若n个记录分为个记录分为b块，每块含块，每块含s个记录，个记录，则等概率情况下则等概率情况下, 顺序查找索引时：顺序查找索引时： ASL=(b+1)/2+(s+1)/2 =(n/s+s)/2+1 可以证

11、明：当可以证明：当s=n 时时,ASL取最小值取最小值n+1折半查找索引时：折半查找索引时：ASL=log2(n/s+1)+s/2 . 一、二叉排序树一、二叉排序树 二、平衡二叉排序树二、平衡二叉排序树 一、定义一、定义二、查找二、查找三、插入三、插入四、删除四、删除五、性能分析五、性能分析（1）若左子树不空，则左子树上所有结 点的值均小于根结点的值；二叉排序树：或者是一棵空树，或者是具有如下特性的二叉树：（3）左、右子树也分别为二叉排序树。（2）若右子树不空，则右子树上所有结 点的值均大于根结点的值；是二叉排序树是二叉排序树?不不50308020901085403525238866* * 中

12、序遍历一个二叉排序树中序遍历一个二叉排序树, ,可以得到一可以得到一 个递增有序序列。个递增有序序列。 typedef struct node KeyType key ; /*关键字的值关键字的值*/ struct node * *lchild,lchild,* *rchild;rchild;/ /* *左右指针左右指针* */ / bstnode,*BSTree; 通常用二叉链表作为二叉排通常用二叉链表作为二叉排序树的存储结构序树的存储结构根据二叉排序树的特点，查找过程如下：（1）k=t：则查找成功，返回根结点地址； （2）kt：则进一步查右子树。 显然这是一个递归过程，可用递归算法实现查找

13、。 若二叉排序树为空，则查找不成功；否则将待查关键字k与根结点关键字t进行比较，如果：50308020908540358832二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095从上述查找过程可见：在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 查找成功 查找不成功1、若二叉排序树为空树，则s成为二叉排序树 的根； 2、若二叉树排序树非空，则将key与二叉树排 序树根结点的值t进行比较，如果: 已知关键字值为K

14、ey的结点由指针s指示，将其插入二叉排序树的过程为：（1）key=t：不进行插入； （2）keyt：则将s插入右子树。 显然，可以用递归算法实现插入。fT设 key = 48fTfT22pfTfTTTTfffp302010403525234822给定一个元素序列，将二叉排序给定一个元素序列，将二叉排序树初始化为一棵空树，然后逐个读树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就入元素，每读入一个元素，就将新将新元素插入到当前已生成的二叉排序元素插入到当前已生成的二叉排序树中树中，直至元素序列插入完毕。，直至元素序列插入完毕。 元素输入序列为：元素输入序列为：45,24,53,12,28

15、,90,45,24,53,12,28,90,按上述算法生成的二叉排序树的过程：按上述算法生成的二叉排序树的过程： 对同样一组元素值，如果输入的顺序不同，所建的二叉排序树形态也不同。如将上述关键字顺序变为:24,53,90,12,28,45, 则生成的二叉排序树为：所以，二叉排序树的所以，二叉排序树的形态完全由一个形态完全由一个输入输入序列决定序列决定，一个无序，一个无序序列可以通过构造一序列可以通过构造一棵二叉排序树而得到棵二叉排序树而得到一个有序序列一个有序序列（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。可分三种情况讨论：

16、和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。50308020908540358832（1）被删除的结点是叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为“空”50308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 408050308020908540358832（3）被删除的结点既有左子树，也有右子树既有

17、左子树，也有右子树4040以其前驱（或者后继）以其前驱（或者后继）替代之，然后再删除该替代之，然后再删除该前驱结点前驱结点被删结点前驱结点被删关键字被删关键字 = 502011 by Fang, Can41左右孩子都不为空的结点删除，为了维持二叉排序树的特性： 必须在后代结点（左子树或者右子树）里面找一个替代被删除节点的位置； 这个结点，必须比左子树所有的结点都大，又比右子树所有的结点都小（不考虑同值时）； 故选择左子树中最大结点（左子树最右结点）或右子树中最小结点（右子树最左结点）； 把选定的结点复制过来，然后再删除被选定的结点； 删除方法同前述三种情况（叶子，单孩子，双孩子）Status

18、DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树 T 中存在其关键字等于 key 的 / 数据元素，则删除该数据元素结点，并返回 / 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; / 不存在关键字等于key的数据元素 else / DeleteBST算法描述如下：算法描述如下： if ( EQ (key, T-data.key) ) / 找到关键字等于key的数据元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; Delete

19、BST ( T-lchild, key ); / 继续在左子树中进行查找DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找 对于一组相同的关键字序列，关键字插入的先后次对于一组相同的关键字序列，关键字插入的先后次序不同，所构成的二叉排序树的形态及深度也不同。序不同，所构成的二叉排序树的形态及深度也不同。 二叉排序树的平均查找长度二叉排序树的平均查找长度ASLASL与二叉排序树的形与二叉排序树的形态有关态有关：二叉排序树的各分支越均衡：二叉排序树的各分支越均衡, ,树的深度越浅树的深度越浅，其平均查找长度其平均查找长度ASLASL越小越小。 例如：例如： 假设每

20、个元素的查找概率相等，则它们假设每个元素的查找概率相等，则它们的平均查找长度分别是：的平均查找长度分别是： ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6ASL=(1+2+3+4+5+6)/6=21/6 由此可见，由此可见，在二叉排序树上进行查找时的在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关平均查找长度和二叉排序树的形态有关。 若考虑把若考虑把n n个结点，按各种可能的次序插入个结点，按各种可能的次序插入到二叉排序树中，则有到二叉排序树中，则有n n！棵二叉排序树（其棵二叉排序树

21、（其中有的形态相同）中有的形态相同）, ,可以证明，这些二叉排序可以证明，这些二叉排序树的平均查找长度仍然是树的平均查找长度仍然是O(logO(log2 2n)n)。 已知长度为12的表：(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec)。例： 试按表中元素的顺序建立二叉排序树，并求试按表中元素的顺序建立二叉排序树，并求其在等概率情况下查找成功的平均查找长度。其在等概率情况下查找成功的平均查找长度。 若对表中元素先进行排序构成有序表，再求若对表中元素先进行排序构成有序表，再求在等概率情况下对此有序表进行折半查找时在等概率

22、情况下对此有序表进行折半查找时查找成功的平均查找长度。查找成功的平均查找长度。Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecASLsuss=(1+22+ 33 + 34 + 25 +6)/12 =42/12=3.5JanFebMarAprJuneMayAugJulySepDecOctNovApr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,SepASLsuss=(1+22+ 43+ 54)/12 =37/12 1 2 3 4 5 6 7 8 9 10 11 12315496711281210 对于二叉排

23、序树,高度越低查找速度就越快。为此可在构造二叉排序树的过程中进行树形的优化，即平衡化处理, 使其成为平衡二叉排序树。 树中每个结点的左、右子树深度之差的绝对值不大于1 ， 。1RLhh1、定义：平衡二叉树(AVL树)或是一颗空树，或者是具有如下特性的二叉排序树：5472是平衡树是平衡树不是平衡树不是平衡树547218结点的平衡因子：结点的左子树的深度减去它的右子树的深度。平衡二叉树上所有结点的平衡因子只可能是-1、0、1，否则不是平衡二叉树。B - 树和B树（1）定义（2）查找过程（3）插入操作 （4）删除操作（5）查找性能的分析1. B - 树2. B + 树（1）B-树的定义B-树是一种

24、平衡 的 多路 查找 树： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1 in） nm n 个指向记录的指针 Di（1in） n+1 个指向子树的指针 Ai（0in）多叉树的特性非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn ； Ai-1 所指子树上所有关键字均小于Ki ； Ai 所指子树上所有关键字均大于Ki ；查找树的特性平衡树的特性树中所有叶子结点均不带信息，且在树中的同一层次上；根结点或为叶子结点，或至少含有两棵子树；其余所有非叶结点均至少含有m/2棵子树，

25、至多含有 m 棵子树； 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个过程交叉进行。（2）查找过程：）查找过程： 若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置； 若查找不成功，则返回插入位置。 在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况：（3）插入）插入1）插入后，该结点的关键字个数nm，不修改指针; 2）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = m/2， 在原结点中保留 （A0，K1， ， Ks-1，As-1）； 建新结点 （As，Ks+1， ，Kn，An）； 将（Ks，

26、p）插入双亲结点；3）若双亲为空，则建新的根结点;例如:下列为 3 阶B-树50 20 40 80 插入关键字 = 60, 60 80 90, 60 80 90 90 50 80 60 30, 40 20 30 50 808030 50 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。（4）删除）删除 在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度。（5）查找性

27、能的分析）查找性能的分析问：含 N 个关键字的 m 阶 B-树可能达到的最大深度 H 为多少？第第 2 层层 2 个个先推导每一层所含最少结点数：第第 1 层层 1 个个第第 H+1 层层 2 ( m/2 ) H-1 个个第第 4 层层 2 ( m/2 )2 个个第第 3 层层 2m/2 个个反过来问： 深度为H的B-树中， 至少含有多少个结点？ 假设 m 阶 B-树的深度为 H+1，由于第 H+1 层为叶子叶子结点，而当前树中含有 N 个关键字，则叶子结点必为N+1 个， N+12( m/2 )H-1 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1由此可推得下

28、列结果： 在含在含 N 个关键字的个关键字的 B-树上树上进行一次查找，需访问的结点进行一次查找，需访问的结点个数不超过个数不超过 log m/2 (N+1)/2)+1结论：结论：（1）B+树的结构特点：每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；2. B+树：树：是B-树的一种变型 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。（2）查找过程 在 B+ 树上，既可以进行缩小范围的查 找

29、，也可以进行顺序查找； 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； 若在结点内查找时，给定值Ki， 则 应继续在 Ai 所指子树中进行查找。（3）插入和删除的操作 类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。 50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot 一、哈希表的定义二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找五、哈希法性能分析以上讨论的各种查找表的共同特点为： 记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程是“基于” 比较。查找的效

30、率取决于和给定值进行比较的次数, 这类方法的平均查找长度为O(logn)-O(n)。对频繁使用的查找表,希望 ASL-0。能否做到？ 能！ 只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为0 999 的顺序表表示之。如：为招收的 1000 名新生建立一张查找表, 其关键字为学号,其值的范围为xx000 xx999 (前两位为年份)。 则查找过程可以简单进行：取给定学号的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。 另例：1、各年龄人口信息统计表； 2、解放后各年国民经济信息统计表。 记录在表中的位置与其关键字之间存在

31、一种确定的对应关系, 按此对应关系可根据关键字的值寻址，从而获得待查纪录。这种查找表称为哈希表，关键字与记录地址间的对应关系称为哈希函数f(key) 。Zi, Qi, Su, Li, Wu, Ci, He, Ye, Du 又例：又例：对于如下对于如下 9 个关键字个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 CiZiQiSuLiWuHeYeDu问题问题: 若需添加关键字若需添加关键字 Zh , 怎么办？怎么办？此类问题称为此类问题称为“冲突冲突”，如何解决？，如何解决？ 0 1 2 3 4 5 6 7 8 9 10 11 12 1

32、3哈希表的构造、使用中有两个问题有待研究：1、如何根据关键字集合的特点，选择合适的哈希函数，使关键字均匀的散列到表中？2、当不同的关键字所得的哈希函数值相同时，即f(k1)=f(k2), 如何有效的处理这类“冲突”现象（碰撞），使建表、查找均能有效地进行？ 根据选定的函数 H(key) 和处理冲突的方法, 将一组关键字映象到一个有限的、连续的地址集 (区间) 上，并以每个关键字在地址集中的 “映象”作为相应记录在表中的存储位置，由此构造所得的查找表称为“哈希表” (散列表、杂凑表) , 所选择的函数H(key)称为哈希函数。 若是非数字关键字，则需先对其进行数字化处理。1. 直接定址法3. 平

33、方取中法5. 除留余数法4. 分段叠加法6. 随机数法2. 数字分析法 “好的”哈希函数应该是“均匀”的，对数字型关键字，一般有下列哈希函数的构造方法：哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b 其中a和b为常数(此哈希函数称为自身函数),所得的地址集合的大小等于关键字集合的大小,这种哈希函数不会发生冲突。此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, , us)，分析关键字集中的全体,去掉数字重复出现频度很高的位, 提取数字均匀分布的若干位或它们

34、的组合作为地址。 以关键字平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”, 平方值的中间几位与整个关键字中的每一位数字都相关。 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。 此方法适合于: 关键字的数字位数特别多，且每一位的数字分布大致均匀。设定哈希函数为: H(key) = key MOD p 其中其中：pm (表长表长) 这是一种简单且适用范围很广的哈希函数，但要求：1、P不能和关键字有质因数； 2、P应尽可能的取质数，或不包 含小于20的质因数

35、的合数； 3、P应尽可能的接近m。设定哈希函数为: H(key) = Random(key)其中，Random 为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。 实际造表时, 采用何种方法来构造哈希函数, 考虑的因素有：建表的关键字集合的情况(包括关键字的范围和形态), 哈希表的大小, 哈希函数计算时间和查找频率。总的原则是: 减少集聚现象, 在关键字取值范围内,使哈希函数值尽量均匀散列在函数值范围内, 从而使产生冲突的可能性尽量减小。为产生冲突的关键字寻找下一个哈希地址。为产生冲突的关键字寻找下一个哈希地址。1. 1. 开放定址法开放定址法2. 2. 链地址法链地址法 除了需要

36、选择一个除了需要选择一个“好好”( (尽可能少尽可能少产生冲产生冲突突) )的哈希函数之外；还需要找到的哈希函数之外；还需要找到一种一种“处理冲突处理冲突” 的方法。其含义是：的方法。其含义是：3. 3. 建立公共溢出区建立公共溢出区 为产生冲突的关键字为产生冲突的关键字 H(key) 求得一个探求得一个探测地址序列测地址序列(在其中逐个探测空哈希地址在其中逐个探测空哈希地址)： H0, H1, H2, , , Hs 1 sm-1其中：其中：H0 = H(key) Hi = ( H(key) + di ) MOD m di 为探测增量有三种，为探测增量有三种，i=1, 2, , m-1 (1)

37、 线性探测再散列线性探测再散列 di = c i 最简单的情况最简单的情况 c=1(2) 平方探测再散列平方探测再散列 di = 12, -12, 22, -22, , ,(3) 随机探测再散列随机探测再散列 di 是一组伪随机数列伪随机数列 或者 di=iH2(key) (又称双散列函数探测又称双散列函数探测)即：产生的即：产生的 Hi 均不相同均不相同, 且且m-1 个个Hi 值能值能覆盖覆盖 哈希表中所有地址。则要求：哈希表中所有地址。则要求： 注意：注意：增量增量 di 应具有应具有“完备性完备性” 随机探测时的随机探测时的 m 和和 di 应没有公因子；应没有公因子； 平方探测时的表

38、长平方探测时的表长 m 应为形如应为形如 4j+3 的素数的素数 （如（如: 7, 11, 19, 23, 等）；等）； 避免二次聚集。避免二次聚集。0 1 2 3 4 5 6 7 8 9 10例如哈希表长例如哈希表长m=11，现，现 有关键字集合：有关键字集合： 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数设定哈希函数 H(key) = key MOD 11 1901 23 145568(1)采用线性探测再散列处理冲突采用线性探测再散列处理冲突11 82 361 1 2 1 3 6 2 5 10 1 2 3 4 5 6 7 8 9 101901 23 1

39、468(2)采用平方探测再散列处理冲突采用平方探测再散列处理冲突551182361 1 2 1 2 1 4 1 2ASL=22/9ASL=15/9设：H2(key)=(3 key) MOD 10 + 1 di=iH2(key) 1901231455681182362 1 1 1 2 1 2 1 3ASL=14/90 1 2 3 4 5 6 7 8 9 10(3)采用双散列函数探测采用双散列函数探测线性探测处理冲突时：线性探测处理冲突时： ASL =双散列探测处理冲突时：双散列探测处理冲突时：ASL =22/914/9二次探测处理冲突时：二次探测处理冲突时： ASL = 15/9本例不同的处理冲

40、突方法的本例不同的处理冲突方法的ASL为：为：将所有哈希地址相同的记录将所有哈希地址相同的记录都链接在同一链表中。都链接在同一链表中。 012345614 0136198223116855 ASL=(61+22+3)/9=13/9设哈希函数为：设哈希函数为： H(key)=key MOD 7显然不会发生二次聚集显然不会发生二次聚集 按哈希函数的值域的范围设立按哈希函数的值域的范围设立向量为基本表向量为基本表,另设立同样大小的向另设立同样大小的向量为量为公共溢出区公共溢出区, ,将所有发生冲突的将所有发生冲突的记录都记录都顺序存放顺序存放在在公共溢出区公共溢出区中。中。 哈希表的查找过程和造表过

41、程一致。哈希表的查找过程和造表过程一致。 对于对于给定值给定值 K， 计算计算哈希地址哈希地址 i = H(K)若若 ri = NULL 则查找不成功则查找不成功若若 ri.key = K 则查找成功则查找成功否则否则 “求下一地址求下一地址 Hi” ，直至，直至 rHi = NULL (查找不成功查找不成功) 或或 rHi.key = K (查找成功查找成功) 为止。为止。 采用开放定址处理冲突，则采用开放定址处理冲突，则查找过程查找过程为：为：决定哈希表查找决定哈希表查找ASL的因素的因素： (1) 选用的选用的哈希函数哈希函数； (2) 选用的选用的处理冲突的方法处理冲突的方法； (3)

42、 哈希表饱和的程度，即哈希表饱和的程度，即装载因子装载因子 =n/m 值的值的大小大小（n记录数，记录数，m表的长度）表的长度） 从查找过程得知，哈希表查找的平均查从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。找长度实际上并不等于零。 一般情况下，可以认为选用的哈希一般情况下，可以认为选用的哈希函数是函数是“均匀均匀”的，则在讨论的，则在讨论ASL时，时，可以不考虑它的因素。可以不考虑它的因素。 因此，因此，哈希表的哈希表的ASL是是处理冲突方法处理冲突方法和和装载因子装载因子的函数。的函数。例如：前述例子例如：前述例子线性探测处理冲突时， ASL =链地址法处理冲突时， ASL =22