数据结构于算法分析 第8章 hash法

《数据结构于算法分析 第8章 hash法》由会员分享，可在线阅读，更多相关《数据结构于算法分析 第8章 hash法（88页珍藏版）》请在金锄头文库上搜索。

1、第八章 查找（Hash法）,本章要求 熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法； 复习二叉排序树的构造和查找方法； 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别； 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 本章难点 掌握哈希表的构造方法,第八章 查找,查找的基本概念 基于线性表的查找法 基于树的查找法 计算式查找法哈希法 要点小结,第八章 查找,查找的基本概念 基于线性表的查找法 基于树的查找法 计算式查找法哈希法 要点小结,Search Problem & Search Engine,Google Myth,Larry Pa

2、ge & Sergey Brin (Google Co-Founder) Originator of BackRub,Amit Singhal(Ph.D, India) (Google Fellow) Originator of PageRank,Google 查询的全过程,Search Engine Revolutionary,Ori Allon (Google Member) Originator of Orion,查找的基本概念,列表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现。 关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关

3、键字可以唯一标识列表中的一个数据元素， 则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时， 数据元素的值就是关键字。,查找的基本概念,查找： 根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。 若找到相应的数据元素， 则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。 对于表的查找，一般有两种情况： 静态查找：指在查找过程中只是对数据元素进行查找 动态查找：指在实施查找的同时，插入找不到的元素，或从查找表中删除查到的某个元素，即允许元素变化。,查找的基本概念,显然，查找算法

4、中涉及到三类参量： 查找对象K（找什么）； 查找范围L（在哪找）； K在L中的位置（查找的结果）。 其中、为输入参量， 为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。 平均查找长度：为确定数据元素在列表中的位置， 需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。,查找的基本概念,对于长度为n的列表， 查找成功时的平均查找长度为： 其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。,查找的基本概念,查

5、找的基本方法可以分为两大类： 比较式查找法 基于线性表的查找法 基于树的查找法 计算式查找法 也称为HASH（哈希）查找法,第八章 查找,查找的基本概念 基于线性表的查找法 顺序查找法 折半查找法 分块查找法 基于树的查找法 计算式查找法哈希法 要点小结,顺序查找(Sequential Search),顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。,顺序查找(Sequential Search),顺序查找(Sequential Search),第八章 查找,查找的基本概念 基于线性表的查找法 顺序查找法 折半查找法 分

6、块查找法 基于树的查找法 计算式查找法哈希法 要点小结,折半查找(Binary Search),折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是： 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功； 否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,折半查找(Binary Search),折半查找(Binary Search),【算法分析】用平均查找长

7、度(ASL)分析折半查找算法的性能。折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录， 左子树对应前一子表，右子树对应后一子表。 显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。,折半查找(Binary Search),由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为 +1。这样，折半查找成功时

8、，关键字比较次数最多不超过 +1。相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找成功时，关键字比较次数最多也不超过判定树的深度 +1。为便于讨论，假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等， 则折半查找成功时的平均查找长度为：,折半查找(Binary Search),含11个记录的有序表，其折半查找过程可用二叉判定树表示：,6,7,10,4,1,2,3,9,5,8,11,比较1次,比较2次,比较3次,比较4次,ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/1

9、1=3,折半查找(Binary Search)演示,折半查找(Binary Search),折半查找方法的优点： 查找速度快 平均性能好 折半查找方法的缺点： 要求待查表为有序表 插入删除困难 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。,第八章 查找,查找的基本概念 基于线性表的查找法 顺序查找法 折半查找法 分块查找法 基于树的查找法 计算式查找法哈希法 要点小结,分块查找法,分块查找法要求将列表组织成以下索引顺序结构： 首先将列表分成若干个块（子表）。一般情况下，块的长度均匀， 最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。 构造一个索引表。其中每个索引

10、项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。,分块查找法,下图为一个索引顺序表。其中包括三个块，第一个块的起始地址为0，块内最大关键字为25；第二个块的起始地址为5， 块内最大关键字为58；第三个块的起始地址为10，块内最大关键字为88。,分块查找法,分块查找的基本过程如下： 首先，将待查关键字K与索引表中的关键字进行比较， 以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。 进一步用顺序查找法，在相应块内查找关键字为K的元素。 例如，在上述索引顺序表中查找36。首先，将36与索引表中的关键字进行比较，因为253658，所以36

11、在第二个块中， 进一步在第二个块中顺序查找， 最后在8号单元中找到36。,分块查找法,分块查找的平均查找长度由两部分构成， 即查找索引表时的平均查找长度为LB，以及在相应块内进行顺序查找的平均查找长度为LW： ASLbs=LB+LW 假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有,分块查找法演示,第八章 查找,查找的基本概念 基于线性表的查找法 基于树的查找法 二叉排序树 平衡二叉排序树 B_树 计算式查找法哈希法 要点小结,二叉排序树,二叉树

12、排序又称二叉查找树，它是一种特殊的树。其定义为：二叉树排序树或者是一棵空树， 或者是具有如下性质的二叉树： 若它的左子树非空， 则左子树上所有结点的值均小于根结点的值； 若它的右子树非空， 则右子树上所有结点的值均大于根结点的值； 它的左右子树也分别为二叉排序树。 这是一个递归的定义。 注意：只要结点之间具有可比性即可。,二叉排序树,下图，(a)所示为数字值间的比较，(b)所示为单词字符的ASCII码间的比较。,二叉排序树的查找,二叉排序树的特性：根据二叉排序树的定义（左子树小于根结点，右子树大于根结点），根据二叉树的中序遍历的定义（先中序遍历左子树，访问根结点，再中序遍历右子树），因此，中序

13、遍历一个二叉排序树，可以得到一个递增有序序列。 中序遍历下面的二叉排序树，则可得到一个递增有序序列为：1,2,3,4,5,6,7,8,9。,二叉排序树的查找,因为二叉排序树可看作是一个有序表，所以在二叉排序树上进行查找与折半查找类似，也是一个逐步缩小查找范围的过程。 根据二叉排序树的特点，首先将待查关键字k与根结点关键字t进行比较，如果： (1) k=t， 则返回根结点地址； (2) kt， 则进一步查右子树。 显然， 这是一个递归过程。但可以用递归与非递归两种算法实现。,二叉排序树查找,显然，在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根到待查结点的路径。若不成功，则是从根

14、结点出发走了一条从根到某个叶子结点的路径。因此，二叉排序树的查找与折半查找过程类似，在二叉排序树中查找一个记录时，其比较次数不超过树的深度。 对长度为n的有序表而言，折半查找对应的判定树是唯一的，而含有n个结点的二叉排序树却是不唯一的。因为对于同一个关键字集合，关键字插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。,二叉排序树查找,二叉排序树的平均查找长度ASL与二叉排序树的形态有关，二叉排序树的各分支越均衡，树的深度浅，其平均查找长度ASL就越小。假设每个元素的查找概率相等，则它们的平均查找长度分别是： (a)ASL=1/6(1+2+2+3+3+3)=14/6 (b) ASL=

15、1/6(1+2+3+4+5+6)=21/6,二叉排序树查找,由此可见，二叉排序树的平均查找长度ASL与二叉排序树的形态有关。在最坏的情况下，二叉排序树是通过把一个有序表的n个结点一次插入生成的，由此得到的二叉排序树脱化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，也是(n+1)/2。 在最好的情况下，二叉排序树在生成过程中，树的形态比较均匀，最终得到的是一棵形态与折半查找的判定树相似的二叉排序树，其平均查找长度大约是log2n。 若考虑把n个结点按各种可能的次序插入到二叉排序树中，则有n!棵二叉排序树（其中有的形态相同），可以证明，对这些二叉排序树的查找长度求平均，其平均查

16、找长度仍然是O(log2n)。,二叉排序树查找,就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树上插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除、查找运算的表，宜采用二叉排序树结构。这也就是人们常常将二叉排序树称为二叉查找树的原因。,第八章 查找,查找的基本概念 基于线性表的查找法 基于树的查找法 计算式查找法哈希法 哈希函数的构造方法 处理冲突的方法 哈希表的查找过程 哈希法性能分析 要点小结,哈希(Hash)法,哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表(Hash Tables)。 基本思想是： 首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。 创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。,Hash,Hans Peter Luhn