第九章 查找(Search) 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 Hash表.

Presentation on theme: "第九章 查找(Search) 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 Hash表."— Presentation transcript:

1 第九章 查找(Search) 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 Hash表

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

3 9.1 基本概念 查找的过程是怎样的？ 对查找表常用的操作有哪些？
给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录，否则输出查找不成功的信息。 对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。

4 9.1 基本概念 如何评估查找方法的优劣？ 查找的过程就是将给定的值与文件中各记录的关键字逐项进行比较的过程。所以用比较次数的平均值来评估算法的优劣，称为平均查找长度（ASL：average search length）。 其中： n是文件记录个数； Pi是查找第i个记录的查找概率； Ci是找到第i个记录时所经历的比较次数。 显然，ASL值越小，时间效率越高。

5 9.2 静态查找（搜索）表 静态查找表抽象数据类型 ADT StaticSearchTable { Data: SET
Operations: Create(&ST, n): 创建具有n个元素的查找表。 Destroy( &ST): 销毁查找表。 Search(ST,key): 查找具有关键字key 的元素。 Traverse( ST,visit()): 遍历查找表。 }ADT StaticSearchTable

6 9.1 静态查找（搜索）表 静态查找表可用顺序表或单链表存储， 本章只讨论顺序表。 一、顺序查找（线性查找） 二、折半查找（二分或对分查找）
三、分块查找（索引顺序查找）

7 一、顺序查找（Linear search,又称线性查找）
所谓顺序查找，又称线性查找，主要用于在线性结构中进行查找。 设若表中有 n 个记录，则顺序查找从表的先端开始，顺序用各记录的关键码与给定值x进行比较，直到找到与其值相等的记录，则称查找成功，给出该记录在表中的位置。 若整个表都已检测完仍未找到关键码与x相等的记录，则查找失败，给出失败信息。

8 一、顺序查找 1).顺序表的机内存储结构： typedef struct { ElemType *elem; //表基址，0号单元留空。表容量为全部元素 int length; //表长，即表中数据元素个数 }SSTable;

9 一、顺序查找 2).算法的实现： 编程技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度（避免每一次查找都检测整个表是否查找完毕）。 若将待查找的特定值key存入顺序表的首部 （如0号单元），则顺序查找的算法思想为： 从后向前逐个比较！ 例：

10 一、顺序查找 2).算法的实现： int Search_Seq( SSTable ST , KeyType key ){
ST.elem[0].key =key; for( i=ST.length; ST.elem[ i ].key!=key; - - i ); //不要用for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++) return i; } // Search_Seq 同学们自己考虑对单链表如何线性查找？

11 一、顺序查找 3).顺序查找算法的平均查找长度(ASL) 为确定记录在查找表中的位置，需给定值进行比较的关键字个数的期望值
其中: n 为表长，Pi 为查找表中第i个记录的概率，假设每次查找都是成功的,则有pi=1 Ci为找到该记录时，比较过的关键字的个数， Ci = n-i+1，ASL = nP1 +(n-1)P2 +…+2Pn-1+Pn，如果要查找的元素在表中的任何位置的概率是相等的，p=1/n，ASL=(n+1)/2

12 3).顺序查找算法的平均查找长度(ASL) 如果有查找不成功的情况时，假设要查找的元素在表中的概率是p,查找不成功的概率为q=1-p 查找成功的平均查找长度为ASL=p(n+1)/2 查找不成功的平均查找长度为q(n+1) 平均查找长度为

13 3).顺序查找算法的平均查找长度(ASL) 在不等概率查找的情况下， ASLss 在Pn≥Pn-1≥···≥P2≥P1时取极小值 若查找概率事先无法测定，则为了提高查找效率，可以在每个记录中附设一个访问频度域，使顺序表中的记录保持按访问频度非递减有序排列，使得查找频率大的记录在查找过程中不断往后移，以便在以后的查找中减少比较次数，或者将刚刚查找到的记录直接移至表尾的位置上。

14 4）优缺点 优点：算法简单且适应面广。 缺点：平均查找长度较大。

15 要求n个记录存放在一个顺序表L中，并按其关键码从小到大排好了序，称此表为有序表。
二、折半查找（二分或对分查找） 1)算法思想： 要求n个记录存放在一个顺序表L中，并按其关键码从小到大排好了序，称此表为有序表。 先求位于查找区间正中的记录的下标mid，用其关键码与给定值x比较: L[mid].Key == x，查找成功； L[mid].Key> x，把查找区间缩小到表的前半部分，再继续进行对分查找； L[mid].Key< x，把查找区间缩小到表的后半部分，再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找区间已缩小到一个记录，仍未找到想要查找的记录，则查找失败。

16 查找成功的例子 查找失败的例子 比较序列：4[4],6[8],5[6] [4],6[8],5[6]

17 2)算法思想： 1 设n个记录存放在一个有序顺序表L中，并按其关键码从小到大排好了序。查找范围为l=0, r=n-1; 2 求区间中间位置mid=（l+r）/2； 3 比较： L[mid].Key = x，查找成功，返回mid，结束； L[mid].Key > x，r=mid-1; L[mid].Key < x，l=mid+1; 4 若l<=r 转2，否则查找失败，返回 0； 考虑对单链表结构如何折半查找？ ——无法实现！

18 2)算法实现： int Search_Bin ( SSTable ST, KeyType key ) {
// 若找到，则函数值为该元素在表中的位置，否则为0。 low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if (key == ST.elem[mid].key) return mid; // 找到待查元素 else if ( key < ST.elem[mid].key) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin

19 3）算法分析： List[]: 15 6 24 27 20 10 2 4 8 13 18 22 25 30 折半查找的判定树：有2n+1个结点， 高度不超过完全二叉树。

20 最多的比较次数不超过完全二叉树的高度： 所以： 最坏情况下的查找长度是： 查找成功的平均查找长度： 设查找任一记录的概率都相等，即：pi=1/n 在第k层上最多有2k-1 个结点，在第k层上的结点需 比较k次。

21 可以用归纳法证明 这样

22 ，且关键字有序

23 三、静态树表的查找（自学） 在概率不等的查找情况下，折半查找不是有序表最好的查找方法。 关键字: A B C D E 例如:
Pi: Ci: 例如: 此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4 若改变Ci的值 则 ASL=20.2+10.3+30.05+20.3+30.15=1.9

24 定义: 使 达最小的判定树称为最优查找树， 其中:

25 介绍一种次优二叉树的构造方法: 选择二叉树的根结点， 使 达最小 为便于计算，引入累计权值和 并设 wl-1 = 0 和 swl-1 = 0， 则推导可得

26 l h h 例如: l h h 2 3 8 11 15 18 23 21 18 12 4 3 3 10 18 9 6 8 5 3 3 1 1 2 A C E G

27 所得次优二叉树如下: E 和折半查找相比较 C G D B F A D F A C E G B 查找比较“总次数” = 32+21+35+13 +34+23+35 = 59 查找比较“总次数” = 32+41+25+33 +14+33+25 = 52

28 构造次优二叉树的算法 Status SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high) { // 由有序表R[low..high]及其累计权值表sw // 递归构造次优查找树T。 选择最小的ΔPi值 if (!(T = (BiTree)malloc(sizeof(BiTNode)))) return ERROR; T->data = R[i]; // 生成结点

29 if (i==low) T->lchild = NULL; // 左子树空
else SecondOptimal(T->lchild, R, sw, low, i-1); // 构造左子树 if (i==high) T->rchild = NULL; // 右子树空 else SecondOptimal(T->rchild, R, sw, i+1, high); // 构造右子树 return OK; } // SecondOptimal

30 Status CreateSOSTre(SOSTree &T, SSTable ST) { // 由有序表 ST 构造一棵次优查找树 T。
次优查找树采用二叉链表的存储结构 Status CreateSOSTre(SOSTree &T, SSTable ST) { // 由有序表 ST 构造一棵次优查找树 T。 // ST 的数据元素含有权域 weight if (ST.length = 0) T = NULL; else { FindSW(sw, ST); // 按照有序表 ST 中各数据元素 // 的 weight 值求累计权值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); } return OK; } // CreatSOSTree

31 三、索引顺序表的查找(分块查找) 索引顺序表的查找是鉴于顺序查找和折半查找的一种查找。 索引顺序表是由索引表和顺序表两部分组成。
索引顺序表的特点是把若干个数据元素分成若干块，每一块称为一个顺序表，要求块与块之间要有序，即第i+1块的所有元素的关键字要大于第i块的所有元素的关键字。 为了查找方便，为每一块建立一个索引项： 索引项：(key,addr), key 域标记该块中最大记录的关键字， addr域指向该块的起始地址。 索引表是由若干索引项组成的有序表。

32 例： 最大关键字(key) 起始地址(addr) 第一块 索引表 第三块 第二块

33 三、索引顺序表的查找(分块查找) 有必要时可以在索引表上再建立索引表 稠密索引: 为每条记录设一个索引项。 稀疏索引：一组记录设一个索引项。

34 三、索引顺序表的查找(分块查找) 分块查找的数据结构： D={d1,d2,….,dn}
1. 将n个数据元素分为s个块 B1,B2, …, Bs ； 2. 块之间有序：Bi+1中的任一元素小于Bi中的任一元 素(i=1,2,…,n-1)； 3. 为每个Bi块设一索引项(keyi, addri)； 4. s个索引项构成索引表； 5. 块内可有序也可无序;

35 三、索引顺序表的查找(分块查找) 在索引顺序表中查找的基本思想:
首先在索引表中查找，确定该查找的元素在哪个块中(可以是折半查找，也可以是顺序查找)。 2. 然后在块中查找(只能是顺序查找)。

36 三、索引顺序表的查找(分块查找) 算法分析： 设在索引表中和块内都是顺序查找。 索引表中查找：ALSindex=(s+1)/2
块中查找： ALSlock=(n/s+1)/2 所以： ALSbs= (s+1)/2 + (n/s+1)/2=(n/s+s)/2+1 显然它与s 的取值有关。当 时，ASLbs有 最小值

37 例 n=10000; s=100; 则顺序查找： ASL=(n+1)/2 ≈ 5000次 ≈ 100次 分块查找: ASLbs=
(n/s+s)/2+1 ≈ 100次 分块查找: Min(ASLbs)= ( ) 折半查找: ASL ≈14 次 当s=n时, 索引顺序表退化成有序表, 即可进行折半查找 当s=1时, 索引顺序表退化成顺序表, 即可进行顺序查找

38 9.2 动态查找（搜索）表 动态查找的特点是，表结构本身是在查找过程中动态生成的，即对给定关键字值key ，表中有具有此值的记录，则查找成功返回，否则插入此关键字的新记录。

39 数据对象D：具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据关系R：数据元素同属一个集合。
动态查找表的抽象数据类型 ADT DynamicSearchTable { 数据对象D：具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据关系R：数据元素同属一个集合。 基本操作: InitDSTable(&DT); //构造一个空的动态查找表DT DestroyDStable( &DT); // 销毁查找表DT。 SearchDSTable(DT,key); //查找具有关键字key 的元素。 InsertDSTable(&DT,e); //插入新记录。 DeleteDSTable(&DT,key );//删除记录。 TraverseDSTable(DT,visit()); //遍历查找表。 } ADT DynamicSearchTable

40 9.2 动态查找（搜索）表 一、二叉排序树 二、平衡二叉树

41 一、二叉排序树 1.二叉排序树的定义 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
 若它的左子树不空,则左子树上所有结点的关键字都 小于根结点的关键字。  若它的右子树不空,则右子树上所有结点的关键字都 大于根结点的关键字。  左子树和右子树分别是二叉排序树。

42 二叉排序树的例子 不是二叉排序树 50 30 80 20 90 10 85 40 35 25 23 88 66

43 二叉排序树的定义 如果对一棵二叉排序树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来， 2.二叉排序树的存储结构（二叉链表） typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; ElemType data; } BiTNode, *BiTree;

44 3.二叉排序树的查找 算法思想： (1) p指向根； (2) p的关键字与key比较，有三种情况： p->data.key==key; 查找成功，返回p, 结束； p->data.key>key; 到左子树中找，p指向它左子女； p->data.key<key; 到右子树中找， p指向它右子女； (3) 重复(2)直到p为空，查找失败，返回空；

45 二叉排序树的查找 50 50 50 50 50 50 30 30 80 80 20 40 40 90 90 35 35 85 32 88 查找关键字 == 50 , 35 , 90 , 95 ,

46 二叉排序树的查找 从上述查找过程可见， 在查找过程中，生成了一条查找路径: 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功 或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 ——查找不成功

47 该算法可设计为递归算法，请大家自己设计。
二叉排序树的查找 查找算法： BiTree search(BiTree T, KeyType k) { p=T; while (p) if (k==p->data.key) return p; //查找成功，返回p else if (k<p->data.key) p=p->lchild; //到左子树中找 else p=p->rchild; //到右子树中找 return p; //查找失败，返回空 } // search 该算法可设计为递归算法，请大家自己设计。

48 在插入之前，先使用查找算法在树中检查要插入元素有还是没有。 查找成功: 树中已有这个元素，不再插入。
4.二叉排序树的插入 6 2 8 1 4 7 9 3的插入位置 在插入之前，先使用查找算法在树中检查要插入元素有还是没有。 查找成功: 树中已有这个元素，不再插入。 查找不成功: 树中原来没有关键码等于给定值的结点，把新元素加到查找操作停止的地方。

49 二叉排序树的插入 为找到插入位置的双亲，查找算法做如下改动： BiTree search(KeyType k，BiTree &pre, BiTree T) { pre=NULL; p=T; while (p) if (k==p->data.key) return p; //查找成功，返回p else { pre=p; if (k<p->data.key) p=p.lchild; //到左子树中找 else p=p->rchild; } //到右子树中找 return p; //查找失败，返回空 } // search

50 二叉排序树的插入 void insert(ElemType e, BiTree &T) { p=search(e.key, &pre,T); if (!p) { //树中无e，插入。 q=(BiTree)malloc(sizeof( BiTNode)); q->data=e; q->lchild=q->rchild=NULL; if (!pre) T=q; else if (e.key<pre->data.key) pre->lchild=q; //插到左子女 else pre->rchild=q; //插到右子女 } } // insert

51 每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。
二叉排序树的插入 二叉查找树的查找 插入新结点88 每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。

52 建立二叉排序树 输入数据序列 { 53,78,65,17,87,09,81,45,23}

53 输入数据，建立二叉排序树 输入顺序不同，建立起来的二叉排序树的形态也不同。 这直接影响到二叉排序树的查找性能。 如果输入序列选得不好，会建立起一棵单支树，使得二叉查找树的高度达到最大，这样必然会降低查找性能。 例：3 个数据{ 1, 2, 3 }， 1 1 2 3 3 2 3 1 3 1 2 3 2 {2, 1, 3} {2, 3, 1} 2 1 {3, 2, 1} {3, 1, 2} {1, 3, 2} {1, 2, 3}

54 5.二叉排序树的删除 和插入相反，删除是在查找成功时进行的，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 三种情况讨论： （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。

55 二叉排序树的删除 （1）被删除的结点是叶子结点 其双亲结点中相应指针域的值改为“空” 被删关键字 = 20 88 例如: 50 30 80
40 90 35 85 32 88

56 （2）被删除的结点只有左子树或者只有右子树
二叉排序树的删除 （2）被删除的结点只有左子树或者只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。 删除40，80 50 30 80 20 40 90 35 85 32 88

57 将被删结点的左孩子代替被删结点,被删结点的右子树改为B的右子树;
二叉排序树的删除 （3）被删结点的左、右子树都存在 找到被删结点在中序下的前驱,设为B 将被删结点的左孩子代替被删结点,被删结点的右子树改为B的右子树; 将B代替被删结点,被删结点的右子树改为B的右子树,B的左子树成为B的双亲的右子树.

58 二叉排序树的删除 删除50 40 50 30 80 20 40 40 90 35 85 32 88

59 二叉排序树的删除算法 Void delete(BiTree T,KeyType k) { if (T) { // 树不空 p=search(k,&pre,T); //查找到被删除结点p及其双亲pre； if (p) { // 查找成功 if (!p->lchild) // p无左子女 if (!pre) T=p -> rchild; else if (pre -> lchild==p) pre -> lchild=p -> rchild; else pre -> rchild=p -> rchild; else if (!p -> rchild) // p无右子女 if (!pre) T=p -> lchild; else if (pre -> lchild==p) pre -> lchild=p -> lchild; else pre -> rchild=p -> lchild;

60 二叉排序树的删除算法 else { // p左右子女都不空 rr=p; r=p->lchild; //在 p 的左子树中找出最大结点 while (r->rchild) { rr=r; r=r->rchild; } rr->rchild=r->lchild; p->data=r->data; //将r中元素复制到 p中 free(r); } } // if (p) } // if (root)

61 查找、插入和删除算法的T(n) 均与二叉排序树的高度成正比。
6. 插入删除算法分析 查找、插入和删除算法的T(n) 均与二叉排序树的高度成正比。 1 6 2 2 8 4 6 7 1 4 7 9 8 9

62 若树退化成单分支,设树的深度为n, 则ASL=(n+1)/2
在最坏情况下： 在平均情况下,二叉排序树的的平均查找长度和 logn是同数量级的.

63 二、平衡二叉树(Balanced Binary Tree)
当确定搜索树的高度总是O(logn)时，能够保证每个搜索树操作所占用的时间为O(logn)。高度为O(logn)的树称为平衡树(balanced tree) 1962年，俄国数学家提出了一种非常流行的平衡树——AVL树(AVL tree）。

64 二、平衡二叉树(Balanced Binary Tree)
一个结点的左子树的高度减去右子树的高度所得的高度差称为该结点的平衡因子 。 一棵AVL树或者是空树，或者是具有下列性质的二叉排序树：任一个结点的平衡因子的绝对值不超过1(只能取 -1，0和 1)。 如果一棵二叉查找树是高度平衡的，它就成为 AVL树,如果它有n个结点，其高度可保持在O(log2n)，平均查找长度也可保持在O(log2n)。

65 2. 平衡化调整 如果在一棵平衡的二叉排序树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化调整有4类：
LL型调整 LR型调整 RR型调整 RL型调整

66 1) RR型调整 A A C B C B C A E h D h D D E E h + 1 B h h h h + 1 h h
-1 A C -2 -1 B C B C A E h D h D D E E h + 1 B h h h h + 1 h h (a) (b) (c) 失衡原因:当在A的右孩子的右子树上插入一个新结点而导致A的平衡因子由-1变成-2。 调整操作:将C成为新子树的根结点上,A成为C的左孩子,同时将C原来的左子树D调整为A的右子树.

67 2) LR型调整 D h C E B A E A A B C B D h D E h h h h (a) (b) (c)
- 1 A 2 E 1 A A B -1 -1 C B D h D E h h h - 1 h h h - 1 h - 1 (a) (b) (c) 失衡原因:当在A的左孩子的右子树上插入一个新结点而导致A的平衡因子由1变成2。 调整操作:将E成为新子树的根结点,A成为E的右孩子, B成为E的左孩子,同时将E原来的左子树调整为B的右子树,E原来的右子树成为A的左子树.

68 3) LL型调整 A A B C B B C D A D E h D E h E C h + 1 h h h + 1 h h h
1 A A 2 B C B B 1 C D A D E h D E h E C h + 1 h h h + 1 h h h (a) (b) (c) 失衡原因:当在A的左孩子的左子树上插入一个新结点而导致A的平衡因子由1变成2。 调整操作:将B成为新子树的根结点上,A成为B的右孩子,同时将B原来的右子树E调整为A的左子树.

69 4) RL型调整 A A C B B B A h C h C h h h h h h (a) (b) (c) h - h 1 - 1
-2 C -1 B 1 B B A -1 h C h C 1 h h h h - 1 h h h - 1 h h - 1 h - 1 (a) (b) (c) 失衡原因:当在A的右孩子的左子树上插入一个新结点而导致A的平衡因子由-1变成-2。 调整操作:将C成为新子树的根结点上,A成为C的左孩子, B成为C的右孩子,同时将C原来的左子树调整为A的右子树,C原来的右子树成为B的左子树.

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

71 总结: 在AVL树上进行查找所需时间为 O(log2n)。 二叉排序树适合于组织在内存中的较小的索引(或目录)。对于存放在外存中的较大的文件系统，用二叉排序树来组织索引不太合适。 在文件检索系统中大量使用的是用B_树或B+树做文件索引。

72 9.3 哈希（HASH）表 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作

73 一、哈希表是什么？ 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系。
查找的过程为给定值依次和关键字集合中各个关键字进行比较， 查找的效率取决于和给定值进行比较的关键字个数。

74 只有一个办法：预先知道所查关键字在表中的位置，
对于频繁使用的查找表，希望 ASL = 0。 只有一个办法：预先知道所查关键字在表中的位置， 要求：记录在表中位置和其关键字之间存在一种确定的关系。 例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份)。 若以下标为000 ~ 999 的顺序表表示之。 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。

75 对于动态查找表而言， 1) 表长不确定； 2) 在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。 因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key) 为哈希函数。用Hash函数构造的查找表可进行查找、插入、删除，此表称为Hash表。

76 例1： 学生档案 学号 姓名 性别 专业 年级 AHZNG 男 CS WANG 男 CS LI 女 CS WU 男 CS BAI 男 CS GONG 女 CS PAN 女 CS 1 2 3 4 34 35 61

77 学号是关键字， Hash函数：h(key)=key 如：key= addr= – = 34 有时会出现： keyi <>keyj 但 h(keyi)=h(keyj) 这种现象称为冲突（碰撞） 称 keyi 和 keyj 是同义词；

78 {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei}
例2：对于如下 9 个关键字 {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei} 设 哈希函数 f(key) = (Ord(第一个字母) -Ord('A')+1)/2 Chen Zhao Qian Sun Li Wu Han Ye Dei 问题: 若添加关键字 Zhou , 怎么办？

79 要解决2个主要问题： （1）如何设计Hash 函数 （2）如何解决冲突 在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。

80 ADT HashTable is Data HashTable; Operations initiate() 初始化Hash表 hash(key) Hash函数 search(key) 查找key insert(key) 插入key delete(key) 删除key reCreate(size) 重建Hash表, 新表空间大于旧表,旧表中的元素按新表的Hash函数插入新表中 Ens ADT HashTable

81 二、哈希函数的构造方法 原则： 值在值域中分布均匀（减少冲突） 计算简单 值域落在表地址范围内；
1 、 直接定址法： h(key)=a* key + b a, b是常数 如上面的例子。 2 、数字分析法：对关键字集要有充分的了解。

82 2、 数字分析法：对关键字集要有充分的了解。
表地址为 0…99 取2位：4，5，6位分布 比较均匀，因此可取4,5位 做位Hash值。 一般情况： 表地址为： s…t, (t-s+1)是r位； 取分布较均匀的r位，组成addr H(key)=addr*t/10r + s

83 3 、平方取中法 H(key)=取(key)平方的中间r位； r取决于表长； 例： key=235, key2= 55225 表长是100， 则r=2； 取H(key)=22 4、折叠法与位移法 对key由左到右每r位分为一组，折叠相加； 例： key= ，表长1000， 则:r=3 分组： key=242’335’665’67

84 242’335’665’67 折叠法：H(key)=516 位移法：H(key)=912 242 335 665 + 67 1912 242 533 665 1516 5、除留余数法： H(key)=key MOD p p<=m , m 是表长； p的选择是很重要的： 通常取p为小于等于m的质数； 6、随机数法： 选择一个随机函数random()，H(key)=random(key); 通常key的长度不等时易采用此方法。

85 三、处理冲突的方法 开放定址法 （Open Address Hash） 冲突处理 封闭定址法 （Closed Address Hash）
封闭定址法： Hash表链表数组，地址空间是H[0….n-1]; Hash表单元H[i]是一个链表，存放若干数据元素，他们是同义词; 它的基本思想是： 将同义词防在key的hash 码对应的链表中；

86 例： H(key)=key mode 8 Keys: 1051 1492 1779 1812 1917 1945
1 2 3 4 5 6 7 1051 1779 1492 1812 1917 1945

87 查找：对给定的key， 计算hash码 i=H(key)； 在链表H[i]中顺序查找key； 算法分析： 计算hash码，很少的工作量，是常数 a； 在链表H[i]中顺序查找，（Li+1）/2, Li是该链表长度； 所以 其中： m是表长，n是数据元素个数； 请大家自己写出插入、删除算法

88 开放定址法： Hash表是数组，地址空间是H[0….n-1]; Hash表单元H[i]只存放一个数据元素; 它的基本思想是： 如果一个元素的Hash地址对应的Hash单元已被另一个元素占有（冲突），我们需定义一个候选地址序列，每当发生冲突时，选择下一个地址去试探。这个序列称为探测序列 Key的探测序列：d0, d1, ……, dm-1, m是表长； d0=H(key) d1, ……, dm-1,需要我们定义， 计算d1, ……, dm-1,的过程称为rehash(再Hash);

89 Rehash： 1). 最简单的rehash是线性探测再散列 （Linear Probing Rehash） di=(di-1+1) mod m or di=(d0+i) mod m or rehash(j)=(j+1) mod m j是最近一次探测的地址； 例： H(key)=key mode 8

90 Keys: d0= d1= d2= H 例： H(key)=key mode 8 Keys: d0= d1= d2= …………………………..

91 发生了大量的冲突，冲突位置集中，这种现象是聚集 2) 随机探测再散列 方法很多： di=(di-1+p) mod m p是一质数；
H 发生了大量的冲突，冲突位置集中，这种现象是聚集 2) 随机探测再散列 方法很多： di=(di-1+p) mod m p是一质数； di=(di-1+hashk(key)+1) mod m di=(di-1+(-1)i i) mod m

92 四、哈希表的查找 Int search(KeyType K, boolean &empty) {
ans=-1; empty=false; // 缺省查找不成功； code=H(K); // 计算d0， code是起始探测位置， loc=code; //loc是当前探测位置 while (H[loc]!=emptyCell) if (H[loc]==K) {ans=loc; break; } //查找成功 loc=rehash(loc); if (loc==code) break; // 查找失败 } // while if (H[loc]!=emptyCell) empty=true; // 找到空位置 return ans; } // search

93 五、哈希表的插入和删除 插入算法 Boolean insert(KeyType K) { loc=search(K,&empty);
if (loc>-1 && !empty) return false; //已有key if (empty) { H[loc]=K; return true; } //插入 reCreate(size*2); // 无空位置, 重建Hash表; H[loc]=K; return true; } // insert

94 删除 Keys: d0= d1= d2= H 插入1945 删除1918后, 查找1945, 探测H[5], 冲突, 再探测 H[6],空,认为无1945 查找1945 断桥现象

95 解决办法: 删除一个元素后,在其位置上做一删除标记 delete； 查找时遇到delete，认为是冲突； 插入时遇到delete，认为是空，可以插入； 算法分析: 负载因子（Load factor）α=n/m 其中n是表中元素个数， m是表长； 显然， α越大，冲突的可能性越大，从而ASL越大。

96 查找成功的ASL: 线性探测再散列： 随机探测再散列： 封闭定址法： 查找不成功的ASL:

97 本章小结 1.顺序表、有序表和索引顺序表的查找方法； 2.二叉查找树的构造方法和查找算法； 3.平衡二叉树的维护平衡的方法； 4.哈希表的构造方法，深刻理解哈希表的与其他结构的表的实质性的差别； 5.各种查找方法在等概率情况下查找成功时的平均查找长度。 本章重点：静态查找表和动态查找表的查找；平衡二叉树的维护平衡的方法；哈希表的构造方法

98 作 业 书面作业： p56: 9.3题, p57: 9.21题 p58: 9.26题 上机作业: 设计哈希表(p166)