数据结构课程的内容.

Presentation on theme: "数据结构课程的内容."— Presentation transcript:

1 数据结构课程的内容

2 第8章 查找 8.1 基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表
第8章 查找 8.1 基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表 教材第8、11和12章省略，因《操作系统》课程会涉及。

3 8.1 基本概念 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字
是一种数据结构 8.1 基本概念 查找表 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——由同一类型的数据元素（或记录）构成的集合。 ——查询(Searching)特定元素是否在表中。 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） ——只查找，不改变集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志 ) ——可以唯一标识一个记录的关键字 例如“学号” ——识别若干记录的关键字 例如“女”

4 讨论： （1）查找的过程是怎样的？ （2）对查找表常用的操作有哪些？ （3) 有哪些查找方法？
给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 （2）对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 “特定的”=关键字 （3) 有哪些查找方法？ 查找方法取决于表中数据的排列方式; 例如查字典 针对静态查找表和动态查找表的查找方法也有所不同。

5 （4）如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度（ASL：average search length）。 统计意义上的数学期望值 其中： n是文件记录个数； Pi是查找第i个记录的查找概率（通常取等概率,即Pi =1/n）; Ci是找到第i个记录时所经历的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。

6 8.2 静态查找表 静态查找表的抽象数据类型参见教材P216。 针对静态查找表的查找算法主要有： 一、顺序查找（线性查找）
二、折半查找（二分或对分查找） 三、静态树表的查找 四、分块查找（索引顺序查找）

7 一、顺序查找（ Linear search，又称线性查找 ）
顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何线性查找？见下页之例或教材P216； 对单链表结构如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”； 对非线性树结构如何顺序查找?可借助各种遍历操作！ （1）顺序表的机内存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable;

8 int Search_Seq( SSTable ST , KeyType key ){
（2）算法的实现： 技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。 若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！ 例： int Search_Seq( SSTable ST , KeyType key ){ //在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0 ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当n>1000时，查找时间将减少一半。 for( i=ST.length; ST.elem[ i ].key!=key; - - i ); //不要用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++) return i; //若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。 } // Search_Seq

9 ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。
讨论① 查不到怎么办？ ——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。 讨论② 查找效率怎样计算？ ——用平均查找长度ASL衡量。 讨论③ 如何计算ASL？ 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； …… 查找第n个元素所需的比较次数为n； 未考虑查找不成功的情况：查找哨兵所需的比较次数为n+1 总计全部比较次数为：1＋2＋…＋n = (1+n)n/2 若求某一个元素的平均查找次数，还应当除以n（等概率）， 即： ASL＝（1＋n）/2 ，时间效率为 O(n) 这是查找成功的情况

10 二、折半查找（又称二分查找或对分查找） 讨论④ 顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。
讨论④ 顺序查找的特点： 优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL 太长，时间效率太低。 如何改进？ 二、折半查找（又称二分查找或对分查找） 这是一种容易想到的查找方法。 先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。 对顺序表结构如何编程实现折半查找算法？ ——见下页之例，或见教材（P219） 对单链表结构如何折半查找？ ——无法实现！因全部元素的定位只能从头指针head开始 对非线性(树)结构如何折半查找？ ——可借助二叉排序树来查找（属动态查找表形式）。

11 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。
折半查找举例： 已知如下11个元素的有序表： （ ）, 请查找关键字为 和85的数据元素。 Low指向待查元素所在区间的下界 mid指向待查元素所在区间的中间位置 high指向待查元素所在区间的上界 解：① 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 ② 运算步骤： (1) low =1,high =11 ,mid =6 ，待查范围是 [1,11]； (2) 若 ST.elem[mid].key < key，说明 key[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ (low+high)/2；. (3) 若 ST.elem[mid].key > key，说明key[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 ST.elem[ mid ].key = key，说明查找成功，元素序号=mid; 结束条件： （1）查找成功 ： ST.elem[mid].key = key （2）查找不成功 ： high≤low （意即区间长度小于0） 此例作为自测卷的算法题之一，建议上机验证。

12 讨论① 若关键字不在表中，怎样得知和停止？
——典型标志是：当查找范围的上界≤下界时停止查找。 讨论② 二分查找的效率（ASL） 1次比较就查找成功的元素有1个（20），即中间值； 2次比较就查找成功的元素有2个（21），即1/4处（或3/4）处； 3次比较就查找成功的元素有4个（22），即1/8处（或3/8）处… 4次比较就查找成功的元素有8个（23），即1/16处（或3/16）处… …… 则第m次比较时查找成功的元素会有（2m-1）个； 为方便起见，假设表中全部n个元素＝ 2m-1个，此时就不讨论第m次比较后还有剩余元素的情况了。 推导过程 全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1 ＝

13 平均每个数据的查找时间还要除以n，所以：
（详细推导过程见教材P221的附录1） 课堂练习（多项选择）： 使用折半查找算法时，要求被查文件： Ａ．采用链式存贮结构 Ｂ．记录的长度≤128 Ｃ．采用顺序存贮结构 Ｄ．记录按关键字递增有序 √ √ 思考：假设在有序线性表a[20]上进行折半查找，则平均查找长度为 。

14 折半查找效率分析法2（参见教材P220）： 查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。 找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。 比较的关键字个数：为该结点在判定树上的层次数。 查找成功时比较的关键字个数最多不超过树的深度 d : d =  log2 n  + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程 就是走了一条从根结点到外部结点的路径。

15 三、静态树表的查找 讨论1：对有序表还有其他查找算法吗？ 有，如斐波那契查找和插值查找等（参见教材P221—222）
讨论2：当有序表中各记录的查找概率不相等时，该如何查找？ 首先要明确，此时用折半查找法未必最优！（参见教材P222例） 改进：若将各记录概率看作是二叉树之权值，则转为研究带权路径长度最小的二叉树（类似最优二叉树）。 三、静态树表的查找 静态最优查找树算法——时间代价高； 实用算法：近似最优查找树（次优查找树） （参见教材P222—225）

16 四、分块查找（索引顺序查找） 这是一种顺序查找的另一种改进方法。
先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。 例： 索引表 特点：块间有序，块内无序 最大关键字 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 第3块 第1块 第2块

17 ① 对索引表使用折半查找法（因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
查找步骤分两步进行： ① 对索引表使用折半查找法（因为索引表是有序表）； ② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）； 查找效率：ASL=Lb+Lw 对索引表查找的ASL 对块内查找的ASL S为每块内部的记录个数，n/s即块的数目 例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5

18 8.3 动态查找表 典型的动态表———二叉排序树 一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树
8.3 动态查找表 特点： 表结构在查找过程中动态生成。 要求： 对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回； 否则插入关键字等于key 的记录。 典型的动态表———二叉排序树 一、二叉排序树的定义 二、二叉排序树的插入与删除 三、二叉排序树的查找分析 四、平衡二叉树

19 一、二叉排序树的定义 （a） （b） ----或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值；
（2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 练：下列2种图形中，哪个不是二叉排序树 ？ （a） （b） 讨论：对(a)中序遍历后的结果是什么？

20 二、二叉排序树的插入与删除 将数据元素构造成二叉排序树的优点： ① 查找过程与顺序结构有序表中的折半查找相似，查找效率高；
② 中序遍历此二叉树，将会得到一个关键字的有序序列（即实现了排序运算）； ③ 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。 ——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。 注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！

21 例：输入待查找的关键字序列=（45，24，53，45，12，24，90）
讨论1：二叉排序树的插入和查找操作 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 查找成功，返回 查找成功，返回 则生成二叉排序树的过程为： 45 24 53 12 90 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90）， 查找成功，返回 查找成功，返回 24 则生成的二叉排序树形态不同： 12 53 90 45

22 二叉排序树的查找&插入算法如何实现？ 查找算法参见教材P228算法9.5（a）; 插入算法参见教材P228算法9.5（b）; 一种“二合一”的算法如下：

23 BSTSEARCH(K, t) //K为待查关键字，t为根结点指针 p=t; //p为查找过程中进行扫描的指针 while(p
BSTSEARCH(K, t) //K为待查关键字，t为根结点指针 p=t; //p为查找过程中进行扫描的指针 while(p!=NULL){ case { K=data(p): {查找成功，return } K<data(p): {q=p；p=L_child(p) } //继续向左搜索 K>data(p): {q=p；p=R_child(p) } //继续向右搜索 } } Get(s); data(s)=K; L_child(s)=NULL; R_child(s)=NULL; //查找不成功，生成一个新结点s，插入到二叉排序树中 case { t=NULL： p=s; //若t为空，则插入的结点s作为根结点 K<data(q): L_child(q)=s; K>data(q): R_child(q)=s; } return OK }

24 讨论2：二叉排序树的删除操作 对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。
（对链表进行删除操作是很方便的） 如何删除一个结点？ 假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针； *f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况： PR 为 * S 的右子树； SL 为 Q（ * S的双亲结点）右孩子 *p为叶子： 删除此结点时，直接修改*f指针域即可； *p只有一棵子树（或左或右）：令PL或PR为*f的左孩子即可； *p有两棵子树：情况最复杂 →

25 *p有两棵子树时，如何进行删除操作？ 分析： 设删除前的中序遍历序列为： …. s p PR …. //显然p的直接前驱是s 希望删除p后，其它元素的相对位置不变。有两种解决方法： 法1：令*p的左子树为 *f的左子树，*p的右子树为*s的右子树； //即FL=PL ; FR=PR ; 法2：令*s代替*p // *s为*p左子树最右下的叶子

26 例：请从下面的二叉排序树中删除结点P。 法1: 法2: F F P C P PR CL C PR Q QL CL S Q SL PR QL

27 三、二叉排序树的查找分析 1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度），即 log2 n+1 2) 一棵二叉排序树的平均查找长度为： 其中： ni 是每层结点个数； Ci 是结点所在层次数； m 为树深。 最坏情况：即插入的n个元素从一开始就有序， ——变成单支树的形态！ 此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。

28 最好情况：即：与折半查找中的判定树相同（形态比较均衡）
树的深度为：log 2n  +1 ； ASL=log 2(n+1) –1 ；与折半查找相同。 3）对有 n 个关键字的二叉排序树的平均查找长度: 设每种树态出现概率相 同 ，查找每个关键字也是等概率的。 则ASL求解过程可推导。 （详见教材P232） 结论：二叉排序树的ASL≤2（1＋1/n）ln n

29 平衡二叉树又称AVL树，它是具有如下性质的 二叉树：
四、平衡二叉树 平衡二叉树又称AVL树，它是具有如下性质的 二叉树： 左、右子树是平衡二叉树； 所有结点的左、右子树深度之差的绝对值≤ 1 即|左子树深度-右子树深度|≤ 1 为了方便起见，给每个结点附加一个数字，给 出该结点左子树与右子树的高度差。这个数字 称为结点的平衡因子balance。这样，可以得到 AVL树的其它性质：

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

31 如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。
平衡旋转可以归纳为四类： LL平衡旋转 RR平衡旋转 LR平衡旋转 RL平衡旋转 现分别介绍这四种平衡旋转。

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

33 这种调整规则可以保证二叉排序树的次序不变
3）LR平衡旋转： 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 这种调整规则可以保证二叉排序树的次序不变

34 例：请将下面序列构成一棵平衡二叉排序树： （ 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

35 8.4 哈希查找表 一、哈希表的概念 二、哈希函数的构造方法 三、冲突处理方法 四、哈希表的查找及分析

36 一、哈希表的概念 哈希表：即散列存储结构。
散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！ 例1：若将学生信息按如下方式存入计算机，如： 将 的所有信息存入V[01]单元； 将 的所有信息存入V[02]单元； …… 将 的所有信息存入V[31]单元。 欲查找学号为 的信息，便可直接访问V[16]！

37 例2 ： 讨论：如何进行散列查找？ 缺点：空间效率低！
有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k，请画出存储结构图。 （注：H（k）＝k称为散列函数） 例2 ： 解：根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……， 对应散列存储表（哈希表）如下： 地址 … 9 11 14 23 24 25 39 内容 9 11 14 23 25 39 讨论：如何进行散列查找？ 根据存储时用到的散列函数H(k)表达式，迅即可查到结果！ 例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功； 若查不到，应当设法返回一个特殊值，例如空指针或空记录。 缺点：空间效率低！

38 若干术语 哈希方法 (杂凑法) 哈希函数 (杂凑函数) 哈 希 表 (杂凑表) 冲 突 哈希方法中使用的转换函数称为哈希函数(杂凑函数)
选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。 哈希方法 (杂凑法) 哈希函数 (杂凑函数) 哈 希 表 (杂凑表) 冲 突 哈希方法中使用的转换函数称为哈希函数(杂凑函数) 按上述思想构造的表称为哈希表(杂凑表) 通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。

39 冲突现象举例： 有冲突！ 有6个元素的关键码分别为：（14，23，39，9，25，11）。
选取关键码与元素位置间的函数为H(k)=k mod 7 6个元素用7个 地址应该足够! 通过哈希函数对6个元素建立哈希表： 14 23 39 9 25 H(14)=14%7=0 11 H(25)=25%7=4 H(11)=11%7=4 有冲突！

40 在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。
所以，哈希方法必须解决以下两个问题： 1）构造好的哈希函数 （a）所选函数尽可能简单，以便提高转换速度； （b）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。 2）制定一个好的解决冲突的方案 查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

41 二、哈希函数的构造方法 直接定址法 除留余数法 乘余取整法 数字分析法 平方取中法 折叠法 随机数法
要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。 要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。 直接定址法 除留余数法 乘余取整法 数字分析法 平方取中法 折叠法 随机数法 常用的哈希函数构造方法有：

42 Hash(key) = a·key + b (a、b为常数)
1、直接定址法 Hash(key) = a·key + b (a、b为常数) 优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突. 缺点：要占用连续地址空间，空间效率低。 例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下： 900 800 700 500 300 100

43 Hash(key)=key mod p (p是一个整数)
2、除留余数法 Hash(key)=key mod p (p是一个整数) 特点：以关键码除以p的余数作为哈希地址。 关键：如何选取合适的p？ 技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是不包含小于20质因子的合数）。 自练：自测卷简答题第4小题 （A*key mod 1） 就是取A*key 的小数部分 3、乘余取整法 Hash(key)=  B*( A*key mod 1 )  (A、B均为常数，且0<A<1，B为整数) 特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。 例：欲以学号最后两位作为地址，则哈希函数应为： H(k)=100*(0.01*k % 1 ) 其实也可以用法2实现： H(k)=k % 100

44 4、数字分析法 特点：某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。
例：有一组（例如80个）关键码，其样式如下： 讨论： ① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。 ② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。 位号：① ② ③ ④ ⑤ ⑥ ⑦

45 5、平方取中法 6、折叠法 特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。 理由：因为中间几位与数据的每一位都相关。
例：2589的平方值为 ，可以取中间的029为地址。 6、折叠法 特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。 适用于：每一位上各符号出现概率大致相同的情况。 法1：移位法 ── 将各部分的最后一位对齐相加。 法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。 例：元素 , 用法1： 427＋518＋96=1041 用法2： —> =1311

46 Hash(key) = random ( key ) (random为伪随机函数)
7、随机数法 Hash(key) = random ( key ) (random为伪随机函数) 适用于：关键字长度不等的情况。造表和查找都很方便。 小结：构造哈希函数的原则： ① 执行速度（即计算哈希函数所需时间）； ② 关键字的长度； ③ 哈希表的大小； ④ 关键字的分布情况； ⑤ 查找频率。

47 三、冲突处理方法 常见的冲突处理方法有： 开放定址法（开地址法） 链地址法（拉链法） 再哈希法（双哈希函数法） 建立一个公共溢出区

48 Hi=(Hash(key)+di) mod m ( 1≤i < m )
1、开放定址法（开地址法） 设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 具体实现： 1.线性探测法 Hi=(Hash(key)+di) mod m ( 1≤i < m ) 其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1，2，…m-1，且di=i 含义：一旦冲突，就找附近（下一个）空地址存入。

49 例： 关键码集为 {47，7，29，11，16，92，22，8，3}， 设：哈希表表长为m=11；
哈希函数为Hash(key)=key mod 11； 拟用线性探测法处理冲突。建哈希表如下： 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存入。 ③ 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。 其中3 还连续移动了两次（二次聚集）

50 讨论： 线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素； 线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……， 因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。 解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。

51 2. 二次探测法 3. 若di＝伪随机序列，就称为伪随机探测法 仍举上例，改用二次探测法处理冲突，建表如下：
Hi=(Hash(key)±di) mod m 其中：Hash(key)为哈希函数 m为哈希表长度，m要求是某个4k+3的质数； di为增量序列 12，-12，22，-22，…，q2 11 22 3 47 92 16 7 29 8 △ ▲ △ △ 注：只有3这个关键码的冲突处理与上例不同， Hash(3)=3，哈希地址上冲突，由 H1=(Hash(3)+12) mod 11=4，仍然冲突； H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。 3. 若di＝伪随机序列，就称为伪随机探测法

52 2、链地址法(拉链法） 基本思想：将具有相同哈希地址的记录链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 例： 设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为： Hash(key)=key mod 11， 用拉链法处理冲突，则建表如右图所示。 1 2 3 4 5 6 7 8 9 10 22 11 89 47 37 92 29 16 50  注：有冲突的元素可以插在表尾,也可以插在表头

53 3、再哈希法（双哈希函数法） 4. 建立一个公共溢出区 Hi=RHi(key) i=1, 2, …，k
优点：不易产生聚集； 缺点：增加了计算时间。 4. 建立一个公共溢出区 思路：除设立哈希基本表外，另设立一个溢出向量表。 所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。

54 四、哈希表的查找及分析 明确：散列函数没有“万能”通式，要根据元素集合的特性而分别构造。 算法：见教材P259
讨论：哈希查找的速度是否为真正的O（1）？ 不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。 一般地，ASL依赖于哈希表的装填因子,它标志着哈希表的装满程度。 0≤≤1  越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

55 讨论： 1） 散列存储的查找效率到底是多少？ 答：ASL与装填因子有关！既不是严格的O(1)，也不是O(n) 2）“冲突”是不是特别讨厌？
答：不一定！正因为有冲突，使得文件加密后无法破译（不可逆，是单向散列函数，可用于数字签名）。 利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。

56 本章小结 重点：顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。 难点：二叉排序树的删除算法