数据结构课程的内容

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

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

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

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

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

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

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

——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址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) 这是查找成功的情况

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

已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和85的数据元素。 折半查找举例： 已知如下11个元素的有序表： （05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21 和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） 此例作为自测卷的算法题之一，建议上机验证。

讨论① 若关键字不在表中，怎样得知和停止？ ——典型标志是：当查找范围的上界≤下界时停止查找。 讨论② 二分查找的效率（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 ＝

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

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

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

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

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

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

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

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

例：输入待查找的关键字序列=（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

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

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 }

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

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

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

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

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

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

任一结点的平衡因子只能取：-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平衡旋转： 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

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

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

例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则成功； 若查不到，应当设法返回一个特殊值，例如空指针或空记录。 缺点：空间效率低！

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

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

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

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

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， 则存储结构（哈希表）如下： 0 1 2 3 4 5 6 7 8 9 900 800 700 500 300 100

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

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

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

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

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

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 含义：一旦冲突，就找附近（下一个）空地址存入。

例： 关键码集为 {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存入。 ③ 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。 其中3 还连续移动了两次（二次聚集）

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

2. 二次探测法 3. 若di＝伪随机序列，就称为伪随机探测法 仍举上例，改用二次探测法处理冲突，建表如下： Hi=(Hash(key)±di) mod m 其中：Hash(key)为哈希函数 m为哈希表长度，m要求是某个4k+3的质数； di为增量序列 12，-12，22，-22，…，q2 0 1 2 3 4 5 6 7 8 9 10 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＝伪随机序列，就称为伪随机探测法

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  注：有冲突的元素可以插在表尾,也可以插在表头

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

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

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

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