数据结构“ 查找表”课件

1、第第 6 章章 查找表查找表6.1 6.1 基本概念基本概念查找表是一种查找表是一种以集合为逻辑结构以集合为逻辑结构、以查找、以查找为为“核心核心”运算、同时包括其它运算的数据结运算、同时包括其它运算的数据结构。构。 6.1.1 6.1.1 集合的基本概念集合的基本概念集合：由任意一些可分辨的对象构成的整集合：由任意一些可分辨的对象构成的整体。例如，所有整数放在一起构成一个集合，体。例如，所有整数放在一起构成一个集合，称为整数集。空集是不含任何元素的集合，记称为整数集。空集是不含任何元素的集合，记为为。 在数据结构课程中，通常只考虑那些由具在数据结构课程中，通常只考虑那些由具有相同类型的数据元

2、素构成的集合。有相同类型的数据元素构成的集合。 6.1.2 6.1.2 查找表的基本概念查找表的基本概念 查找是一种常用运算，其功能是从大查找是一种常用运算，其功能是从大量的数据元素中找出某个特定的数据元素。量的数据元素中找出某个特定的数据元素。标识数据元素的数据项称为标识数据元素的数据项称为关键字关键字，简称简称键键。该数据项的值称为。该数据项的值称为键值键值。能够唯一地标识能够唯一地标识数据元素数据元素的的关键字称关键字称为为主关键字主关键字。不不能唯一地标识能唯一地标识数据元素数据元素的的关键字称关键字称为为次关键字次关键字。查找运算的功能的确切表述：根据查找运算的功能的确切表述：根据给

3、定的某个值给定的某个值K，在查找表中寻找一个，在查找表中寻找一个其键值等于其键值等于K的数据元素。若找到一个的数据元素。若找到一个这样的数据元素，则查找成功，运算结这样的数据元素，则查找成功，运算结果为该数据元素在表中的位置；否则，果为该数据元素在表中的位置；否则，查找不成功，此时的运算结果为一个特查找不成功，此时的运算结果为一个特殊标志。殊标志。查找表：具有同一类型的数据元素组成的集合。查找表：具有同一类型的数据元素组成的集合。静态查找表包括下列三种基本运算：静态查找表包括下列三种基本运算： 建表建表CREATE(ST), 其作用是生成一个由用户给其作用是生成一个由用户给定的若干数据元素组成

4、的静态查找表定的若干数据元素组成的静态查找表ST。 查找查找SEARCH(ST，K)，若，若ST中存在关键字值中存在关键字值等于等于K的数据元素，运算结果为该数据元素在的数据元素，运算结果为该数据元素在ST中中的位置；否则，运算结果为一特殊标志。的位置；否则，运算结果为一特殊标志。 读表元读表元GET(ST，pos)，其运算结果是，其运算结果是ST中中pos位置上的数据元素。位置上的数据元素。 (静态查找表是仅对查找表进行查找操作，而不能静态查找表是仅对查找表进行查找操作，而不能被改变的表。被改变的表。) )动态查找表动态查找表 包括包括查找查找读表元以及下读表元以及下列三种基本运算：列三种基

5、本运算：插入插入INSERT(ST，K)，若，若ST中不存在中不存在关键字值等于关键字值等于K的数据元素，则将一个关键的数据元素，则将一个关键字值等于字值等于K的新数据元素插入到的新数据元素插入到ST中。中。删除删除DELETE(ST，K)，当，当ST中存在关中存在关键字值等于键字值等于K的数据元素时，将其删除。的数据元素时，将其删除。初始化初始化INITIATE(ST)，其作用是设置一，其作用是设置一个空的动态查找表个空的动态查找表ST。 (动态查找表：除了对查找表进行查找操作动态查找表：除了对查找表进行查找操作外，还能向表中插入数据元素，或删除表中外，还能向表中插入数据元素，或删除表中的数

6、据元素，因而表可以被改变。的数据元素，因而表可以被改变。) )6.2 6.2 静态查找表的实现静态查找表的实现6.2.1 6.2.1 顺序表上的查找顺序表上的查找 静态查找表的顺序表的类型定义如下：静态查找表的顺序表的类型定义如下：#definemaxsize静态查找表的表长；静态查找表的表长；typedefstructkeytypekey;/*关键字关键字*/./*其它域其它域*/rec;typedefstructrecitemmaxsize+1;intn;/*最后一个数据元素的下标最后一个数据元素的下标*/sqtable;静态查找表中的数据元素存放在上述数组静态查找表中的数据元素存放在上述

7、数组的第的第1 1到第到第n n个单元，第个单元，第n+1n+1到最后一个单元为到最后一个单元为备用区。不同的是，这里多说明了一个单元备用区。不同的是，这里多说明了一个单元即第即第0 0个单元，该单元被用于设置个单元，该单元被用于设置 岗哨岗哨 以便以便简化查找运算的实现。简化查找运算的实现。在上述存储结构上实现查找运算的一种直在上述存储结构上实现查找运算的一种直观方法是观方法是 顺序查找法顺序查找法 ：从表的第：从表的第n n个位置开个位置开始，从后往前依次将各个位置上的数据元素始，从后往前依次将各个位置上的数据元素的键值与给定值的键值与给定值K K比较。若某个位置上的数据比较。若某个位置上

8、的数据元素的键值与元素的键值与K K相等则查找成功，回送该位置相等则查找成功，回送该位置作为结果；若所有数据元素的键值均与作为结果；若所有数据元素的键值均与K K不等，不等，回送回送0,0,标记查找不成功。标记查找不成功。 顺序查找算法顺序查找算法intsearch-sqtable(sqtableR,keytypeK)R.item0.key=K;/*设置岗哨设置岗哨*/i=R.n;/*设置比较位置初值设置比较位置初值*/While(R.itemi.key!=K)i-;/*未找到时修改比较位置继续查找未找到时修改比较位置继续查找*/return(i);18714 18 21 23 29 31 3

9、5 38 42 46 49 52012345678910 11 12 13R.nk=18顺序查找算法顺序查找算法(顺序表采用普通数组形式顺序表采用普通数组形式)intsearch-sqtable(intitem,intn,intk)inti;item0=k;/*在数组的低端设置监视哨在数组的低端设置监视哨*/While(itemi!=k)i-;/*从后往前找从后往前找*/returni;/*找不到时，找不到时，i为为0*/岗哨岗哨R.item0的作用是：保证的作用是：保证while循环一定终止循环一定终止(即使查找不成功、即即使查找不成功、即R中无键值等于中无键值等于K的数据元素，当的数据元素

10、，当i=0时时循环终止条件循环终止条件被迫被迫成立成立)。因此，不。因此，不必将必将i0写入循环条件从而使循环条写入循环条件从而使循环条件得到简化件得到简化(对比第对比第2章定位算法章定位算法locate_sqlist)。有关测试表明：当。有关测试表明：当n1000时，进行一次查找所花费的时时，进行一次查找所花费的时间平均减少约一半。间平均减少约一半。查找运算通常以查找运算通常以 数据元素的键值与给定值的比较数据元素的键值与给定值的比较 作为标准操作，也就是用作为标准操作，也就是用 数据元素的键值与给定值数据元素的键值与给定值的比较次数的比较次数 来作为查找算法的时间性能。上述比较来作为查找算

11、法的时间性能。上述比较次数称为次数称为 查找长度查找长度 。显然，查找长度与键值等于给。显然，查找长度与键值等于给定值定值K K的元素在顺序表中的位置有关。的元素在顺序表中的位置有关。若顺序表中第若顺序表中第n n个元素的键值为个元素的键值为K K，则顺序查找算法，则顺序查找算法的查找长度为的查找长度为1 1；若第；若第1 1个元素的键值为个元素的键值为K K，则查找长，则查找长度为度为n n；若表中无键值等于；若表中无键值等于K K的元素的元素( (查找不成功查找不成功) )，则，则查找长度为查找长度为n+1n+1。可见差别很大。较合理的办法是以。可见差别很大。较合理的办法是以 查找成功时的

12、查找成功时的平均查找长度平均查找长度(记为记为ASL)ASL)作为查找算法作为查找算法时间性能的度量，其定义为：时间性能的度量，其定义为： n nASLASL P Pi iC Ci i i=1i=1顺序查找算法的平均查找长度顺序查找算法的平均查找长度ASL:查找成功：查找成功：ASL=(n+1)/2查找失败：查找失败：ASL=n+1可见，顺序查找算法时间复杂度为可见，顺序查找算法时间复杂度为O(n)6.2.2 6.2.2 有序表上的有序表上的查找查找( (二分查找二分查找)有序表：对于任何一个顺序表，若有序表：对于任何一个顺序表，若其中的所有数据元素按键值的某种次其中的所有数据元素按键值的某种

13、次序序( (升序或降序升序或降序) )排列，则称为有序表。排列，则称为有序表。由于有序表中所有元素按键值递增的次序排由于有序表中所有元素按键值递增的次序排列，若将表中任一元素的键值列，若将表中任一元素的键值R.itemi.keyR.itemi.key与与给定值给定值K K比较，可根据三种比较结果区分出三种比较，可根据三种比较结果区分出三种情况：情况：R.itemi.key=KR.itemi.key=K，查找成功，查找成功，R.itemiR.itemi即为待查元素；即为待查元素；R.itemi.keyKR.itemi.keyK，说明待查元素若在表中，说明待查元素若在表中，则一定排在则一定排在R.

14、itemiR.itemi之前；之前；R.itemi.keyKR.itemi.keyK，说明待查元素若在表中，说明待查元素若在表中，则一定排在则一定排在R.itemiR.itemi之后。之后。因此，在一次比较之后，若沿未找到待查元因此，在一次比较之后，若沿未找到待查元素，则可根据比较结果缩小进一步查找的区间。素，则可根据比较结果缩小进一步查找的区间。二分查找法的基本思想：首先选取表二分查找法的基本思想：首先选取表中间位置的元素，将其关键码与给定值进行中间位置的元素，将其关键码与给定值进行比较，若相等，则查找成功；若给定值比该比较，若相等，则查找成功；若给定值比该关键码小，则要找的元素一定在表的左

15、半区，关键码小，则要找的元素一定在表的左半区，则继续对左半区进行折半查找。若给定值比则继续对左半区进行折半查找。若给定值比该关键码大，则要找的元素一定在表的右半该关键码大，则要找的元素一定在表的右半区，则继续对右半区进行折半查找。如此递区，则继续对右半区进行折半查找。如此递推，直到查找成功或查找区间长度为推，直到查找成功或查找区间长度为0(0(查找查找不成功不成功) )为止。为止。二分查找算法中的变量含义：二分查找算法中的变量含义：lowlow : : 查找区间的下界；查找区间的下界；highig: : 查找区间的上界；查找区间的上界；midmid=(low+hig)/2=(low+hig)/

16、2：区间的中间位置；：区间的中间位置；K K ：给定值：给定值 ( ( 如如 K=18 )K=18 )。二分查找算法如下：二分查找算法如下： int binsearch(sqtable R, keytype K)int binsearch(sqtable R, keytype K)low=1; hig=R.n; /low=1; hig=R.n; /* *置查找区间初值置查找区间初值* */ / while(low=hig) / while(low=hig) /* *区间长度不为区间长度不为0 0时继续查找时继续查找* */ / mid=(low+hig)/2; / mid=(low+hig)/

17、2; /* *找出区间的中间位置找出区间的中间位置* */ /switchswitch case K=R.itemmid.key: return mid case K=R.itemmid.key: return mid； case KR.itemmid.key: hig=mid-1; break;case KR.itemmid.key: low=low+1; break case kR.itemmid.key: low=low+1; break / /* *调整到右半区调整到右半区* */ / return(0); return(0); / /* *返回返回0 0，表示查找不成功，表示查找不成

18、功* */ / 15 17 18 22 35 51 60 88 930123456789hig=9low=1mid=5hig=4low=1 mid=2hig=4low=3mid=3K=18 K=18 ( (查找成功的例子查找成功的例子) )15 17 18 22 35 51 60 88 930123456789hig=9low=1mid=5hig=4low=1 mid=2hig=4low=3 mid=3K=20 K=20 ( (查找不成功的例子查找不成功的例子) )low=4hig=4 mid=4hig=3 low=4二分查找算法每进行一次键值与给定值的二分查找算法每进行一次键值与给定值的比较

19、，查找区间的长度至少减小为原来二分比较，查找区间的长度至少减小为原来二分之一之一(“二分查找二分查找”由此得名由此得名)。由此易推算出。由此易推算出二分查找的查找长度不超过二分查找的查找长度不超过log2n+1。二分查找的平均查找长度为：二分查找的平均查找长度为：ASLblog2(n+1)-1二分查找的时间复杂性为：二分查找的时间复杂性为：T(n)=O(log2n)由此可见，二分查找的时间性能比由此可见，二分查找的时间性能比顺序查找好。但二分查找要求以有序顺序查找好。但二分查找要求以有序表作为存储表示。当采用的存储结构表作为存储表示。当采用的存储结构不是顺序表、或者表中元素未按键值不是顺序表、

20、或者表中元素未按键值的次序的次序( (递增或递减递增或递减) )排列时，则不能排列时，则不能进行二分查找。而顺序查找则无此限进行二分查找。而顺序查找则无此限制。制。6.2.3 6.2.3 索引顺序表上的查找索引顺序表上的查找 索引顺序表是按索引存储方式构造的一种索引顺序表是按索引存储方式构造的一种存储结构。一个索引顺序表由两个部分组成：存储结构。一个索引顺序表由两个部分组成：一个顺序表和一个索引表。其中的顺序表在一个顺序表和一个索引表。其中的顺序表在组织形式上与普通的顺序表完全相同；而索组织形式上与普通的顺序表完全相同；而索引表本身在组织形式上也是一个顺序表。索引表本身在组织形式上也是一个顺序

21、表。索引顺序表的特点表现为以下两个方面引顺序表的特点表现为以下两个方面 ：顺序表中的数据元素顺序表中的数据元素“按块有序按块有序”；索引表反映了这些索引表反映了这些“块块”的有关特性。的有关特性。所谓所谓 按块有序按块有序 是指：顺序表中的数据元是指：顺序表中的数据元素被划分成一些子表素被划分成一些子表( (块块) )；并且对其中任意；并且对其中任意两个相邻表来说，排在前面的子表中的任一两个相邻表来说，排在前面的子表中的任一数据元素的键值小于排在后面的子表中的所数据元素的键值小于排在后面的子表中的所有数据元素的键值。有数据元素的键值。图图6-16-1中的顺序表被分成三块中的顺序表被分成三块:(

22、22:(22，1212，1313，8 8，9 9，20)20)，(33(33，4242，4444，3838，2424，4848，) )，(60(60，5858，7474，4747，8686，53)53)，并且，并且它们中的数据元素是按块有序的它们中的数据元素是按块有序的( (但每一块但每一块中的数据元素不要求有序中的数据元素不要求有序) )。224886171322 12 138920 33 42 44 38 24 48 60 58 74 47 86 5312345678910 11 12 13 14 15 16 17 18图图6-16-1 索引顺序表示例索引顺序表示例 索引表索引表块内最大键

23、值块内最大键值块起始位置块起始位置 索引顺序表上的查找分两个阶段：索引顺序表上的查找分两个阶段：确定待查元素所在的块；确定待查元素所在的块；在块内查找待查的元素。在块内查找待查的元素。以以6-16-1所示的索引顺序为例。假如给定所示的索引顺序为例。假如给定K=24K=24，应先将应先将K K与索引表中的各个块内最大键值比较，与索引表中的各个块内最大键值比较，得知只能在第二块，然后在第二块中进行查找。得知只能在第二块，然后在第二块中进行查找。第二阶段只能采用顺序查找法，而第一阶段既第二阶段只能采用顺序查找法，而第一阶段既可采用顺序查找法，也可采取二分查找法可采用顺序查找法，也可采取二分查找法(

24、(索索引表中的索引项按引表中的索引项按 块内最大键值块内最大键值 域的值有域的值有序序) )。索引顺序表上的上述查找方法称为分块查找。索引顺序表上的上述查找方法称为分块查找。 6.3 6.3 树表树表 前面所述的静态查找表所含数据元素前面所述的静态查找表所含数据元素(在检索在检索阶段内阶段内)是固定不变的。而动态查找表则不然，是固定不变的。而动态查找表则不然，其所含数据元素可以经插入、删除运算而不断其所含数据元素可以经插入、删除运算而不断的改变。动态查找表的这种动态特性要求我们的改变。动态查找表的这种动态特性要求我们采用灵活的存储表示方法来组织动态查找表中采用灵活的存储表示方法来组织动态查找表

25、中的数据元素。的数据元素。本节介绍几种用来表示动态查找表的树表本节介绍几种用来表示动态查找表的树表(主主要是二叉排序树和平衡二叉排序树。要是二叉排序树和平衡二叉排序树。6.3.1 6.3.1 二叉排序树二叉排序树一棵一棵二叉排序树二叉排序树(又称又称二叉查找树二叉查找树)或者是一棵或者是一棵空树，或者是一棵同时满足下列条件的二叉树：空树，或者是一棵同时满足下列条件的二叉树：1若它的左子树不空，则左子树上所有结点若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值；的键值均小于它的根结点的键值；2若它的右子树不空，则右子树上所有结点若它的右子树不空，则右子树上所有结点的键值均大于它的

26、根结点的键值；的键值均大于它的根结点的键值；3它的左、右子树也分别为二叉排序树。它的左、右子树也分别为二叉排序树。37图图6-26-2 二叉排序树示例二叉排序树示例2151632852333606563559042981067584583例如例如:是二叉排序树。是二叉排序树。66不不70二叉排序树给查找运算的实现提供了二叉排序树给查找运算的实现提供了便利条件：在表示一棵二叉排序树的二便利条件：在表示一棵二叉排序树的二叉链表上，要找键值比某结点叉链表上，要找键值比某结点X X的键值小的键值小( (大大) )的结点，只需通过结点的结点，只需通过结点X X的左指针的左指针( (右指针右指针) )到它

27、的左到它的左( (右右) )子树中去找。子树中去找。二叉排序树具有下述重要性质；中二叉排序树具有下述重要性质；中根遍历一棵二叉排序树所得的结点访问根遍历一棵二叉排序树所得的结点访问序列是键值的递增有序序列。序列是键值的递增有序序列。 1 1二叉排序树上的查找二叉排序树上的查找(1)(1)若查找树为空，则查找失败；若查找树为空，则查找失败；(2)(2)若查找树非空，将若查找树非空，将给定值与给定值与查找树的查找树的根结点关键码比较；根结点关键码比较；(3)(3)若相等，则查找成功；否则若相等，则查找成功；否则 若给定值小于根结点关键码，则继若给定值小于根结点关键码，则继续在左子树上进行查找；续在

28、左子树上进行查找； 若给定值大于根结点关键码，则继若给定值大于根结点关键码，则继续在右子树上进行查找。续在右子树上进行查找。50308020908540358832例如例如:二叉排序树二叉排序树查找关键码查找关键码=50,505035,503040355090,50809095,2 2二叉排序树的插入二叉排序树的插入在二叉排序树上进行插入的原则是：在二叉排序树上进行插入的原则是：(1)(1)必须保证插入一个结点之后仍为必须保证插入一个结点之后仍为一棵二叉排序树。一棵二叉排序树。(2)(2)仅当二叉排序树上不存在键值等仅当二叉排序树上不存在键值等于于 K K 的结点时才插入一个这样的结点。的结点

29、时才插入一个这样的结点。因此，插入算法必须包含查找过程；因此，插入算法必须包含查找过程；并且当查找不成功时实施插入新结点的并且当查找不成功时实施插入新结点的操作。操作。在动态查找表的定义中没有生成运算，在动态查找表的定义中没有生成运算，只有初始化运算。这是因为动态查找表只有初始化运算。这是因为动态查找表是从空表开始经反复的插入是从空表开始经反复的插入( (及删除及删除) )而而动态生成的。另一方面，假如需要的话，动态生成的。另一方面，假如需要的话，可以通过调用初始化算法和插入算法而可以通过调用初始化算法和插入算法而实现生成运算。实现生成运算。 63559042981067584583从空树开始

30、建立二叉排序树的过程从空树开始建立二叉排序树的过程70【例】已知关键码序列为【例】已知关键码序列为: : 63,90,70,55,67,42,98,83,10,45,58 63,90,70,55,67,42,98,83,10,45,58建立一棵二叉排序树的过程建立一棵二叉排序树的过程3 3二叉排序树的删除二叉排序树的删除 与插入相反，删除在查找成功之后进与插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。结点之后，仍然保持二叉排序树的特性。 可分三种情况讨论：可分三种情况讨论：(1)(1)被删除的结点是叶子；被

31、删除的结点是叶子；(2)(2)被删除的结点只有左子树或只有右子被删除的结点只有左子树或只有右子树；树；(3)(3)被删除的结点既有左子树，也有右子被删除的结点既有左子树，也有右子树。树。50308020908540358832(1)被删除的结点是叶子结点叶子结点例如例如:被删关键码被删关键码=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832(2)被删除的结点只有左子树只有左子树或者只有右子树只有右子树其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被

32、删关键码被删关键码=408050308020908540358832(3)被删除的结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键码被删关键码=50可以证明，在随机情况下，含有可以证明，在随机情况下，含有n n个结个结点的二叉排序树的平均查找长度为点的二叉排序树的平均查找长度为1+4log1+4log2 2n n 其时间效率很高。同时，其它运算如其时间效率很高。同时，其它运算如插入和删除亦易于实现。相对而言，有插入和删除亦易于实现。相对而言，有序表上的二分查找效率也很高；但若在序表上的二分查

33、找效率也很高；但若在有序表上进行插入和删除显然十分不便有序表上进行插入和删除显然十分不便且低率。且低率。333262321232163233图图6-86-8 单支二叉排序树示例单支二叉排序树示例 二叉排序的查找效率与树的形态有关。二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵深度为当二叉排序树退化为一棵深度为n n的单的单支树时，查找算法退化为顺序查找，平支树时，查找算法退化为顺序查找，平均查找长度上升为均查找长度上升为(n+1)/2(n+1)/2。为了避免。为了避免出现这种情况，需要在二叉排序树的动出现这种情况，需要在二叉排序树的动态变化过程中随时调整其形态，使之保态变化过程中随时

34、调整其形态，使之保持持“平衡平衡”。当二叉排序树的形态比较。当二叉排序树的形态比较匀称时，它的平均查找长度接近于匀称时，它的平均查找长度接近于loglog2 2n n。6.3.2 6.3.2 平衡二叉排序树平衡二叉排序树 一棵平衡二叉排序树一棵平衡二叉排序树( (简称简称AVLAVL树树) )或或者是一棵空树，或者是一棵任一结点者是一棵空树，或者是一棵任一结点的左子树与右子树的高度至多差的左子树与右子树的高度至多差1 1的二的二叉排序树。叉排序树。 对于二叉排序树上的任何结点，其平衡对于二叉排序树上的任何结点，其平衡因子定义为该结点左子树的高度减去该结因子定义为该结点左子树的高度减去该结点右子

35、树的高度。易知平衡二叉排序树上点右子树的高度。易知平衡二叉排序树上任一结点的平衡因子只可能是任一结点的平衡因子只可能是 -1-1、0 0、1 1。反之，一棵二叉排序树上只要有一个结点反之，一棵二叉排序树上只要有一个结点的平衡因子不是的平衡因子不是-1-1、0 0或或1 1，则此二叉排序，则此二叉排序树不是平衡的。树不是平衡的。 1511112008037121-151-160320760230图图6-9(a)AVL树的例子树的例子3301521112008037021-151-260320761230图图6-9(b)非非AVL树的例子树的例子3301411306006.4 6.4 散列表散列表

36、 散列表又名哈希表散列表又名哈希表, ,因其英文单词因其英文单词HashHash而得名。而得名。前几节讨论的查找方法的共同特点是：前几节讨论的查找方法的共同特点是：数据元素的存储位置与关键码之间不存在数据元素的存储位置与关键码之间不存在确定的关系，查找的过程为给定值依次和确定的关系，查找的过程为给定值依次和各个关键码进行比较，查找的效率取决于各个关键码进行比较，查找的效率取决于和给定值进行比较的关键码个数。理想的和给定值进行比较的关键码个数。理想的情况是依据关键码直接得到其对应的数据情况是依据关键码直接得到其对应的数据元素位置。元素位置。 散列表散列表: :按散列存储方式构造的存储结构按散列存

37、储方式构造的存储结构称为散列表。散列技术的核心是散列函数。称为散列表。散列技术的核心是散列函数。散列函数散列函数: :是一种将键值映射为散列表中是一种将键值映射为散列表中的存储位置的函数。的存储位置的函数。对任意给定的动态查找表对任意给定的动态查找表T T，如果选定了某，如果选定了某个个“理想的理想的”散列函数散列函数H H及相应的散列表及相应的散列表L L，则，则对对T T中的每个数据元素中的每个数据元素X X，函数值，函数值 H(X.key) H(X.key)就就是是X X在散列表在散列表L L中的存储位置。插入中的存储位置。插入( (或建表或建表) )时时数据元素数据元素X X将被安置在

38、该位置上，并且查找将被安置在该位置上，并且查找X X时时也到该位置上去查找。也到该位置上去查找。散列地址散列地址: :由散列函数决定的数据元素在由散列函数决定的数据元素在散列表中的存储位置称为散列地址。散列表中的存储位置称为散列地址。散列的基本思想散列的基本思想: :通过由散列函数决定的通过由散列函数决定的键值键值(X.key)(X.key)与散列地址与散列地址(H(X.key)(H(X.key)之间的对之间的对应关系来实现存储组织和查找运算。应关系来实现存储组织和查找运算。在理想的情况下，散列函数是一个一一对应，在理想的情况下，散列函数是一个一一对应，即每个键值对应于一个散列地址，且不同的键

39、即每个键值对应于一个散列地址，且不同的键值对应不同的散列地址。但在实际应用中，这值对应不同的散列地址。但在实际应用中，这种情况很少出现。在大多数情况下，出现种情况很少出现。在大多数情况下，出现“同同义词义词”并发生并发生“冲突冲突”是不可避免的。是不可避免的。同义词同义词: :设有散列函数设有散列函数H H和键值和键值k1k1、k2k2，若，若k1k2k1k2且且H(k1)=H(k2)H(k1)=H(k2)，则称，则称k1k1、k2k2是是同义词同义词。冲突：假如动态查找表中有两个数据元素冲突：假如动态查找表中有两个数据元素X1X1、X2X2存入同一个散列表，而且它们的键值是存入同一个散列表，

40、而且它们的键值是同义词，这种情况称为同义词，这种情况称为冲突冲突。我们希望同义词尽量少以便减少冲突。另一我们希望同义词尽量少以便减少冲突。另一方面，由于冲突的不可避免性，又必须考虑在方面，由于冲突的不可避免性，又必须考虑在冲突发生时的处理办法。因此，采用散列技术冲突发生时的处理办法。因此，采用散列技术时需要考虑的两个问题是：时需要考虑的两个问题是：如何构造如何构造( (选择选择)均匀的均匀的 散列函数？散列函数？用什么方法解决冲突？用什么方法解决冲突？冲突：冲突： 通常关键码的集合比哈希地址集合大得通常关键码的集合比哈希地址集合大得多，因此经过哈希函数变换后，可能将不多，因此经过哈希函数变换后

41、，可能将不同的关键码映射到同一个地址上，这种现同的关键码映射到同一个地址上，这种现象称为象称为冲突冲突。 同义词同义词: : 映射到同一个地址上的关键码称为映射到同一个地址上的关键码称为同义同义词词。6.4.1 6.4.1 散列函数的构造法散列函数的构造法 这里介绍几种常用的构造方法。按这这里介绍几种常用的构造方法。按这些方法构造出来的散列函数计算简单而些方法构造出来的散列函数计算简单而且比较且比较 均匀均匀(即同义词较少即同义词较少) )。以下假。以下假定散列地址是自然数。另外假定键值也定散列地址是自然数。另外假定键值也都是自然数都是自然数( (事实上，键值通常总可以事实上，键值通常总可以转

42、换为自然数转换为自然数) )。 数字分析法数字分析法数字分析法又称为数字选择法数字分析法又称为数字选择法, ,适用适用于下述场合于下述场合: :事先知道所有可能出现的事先知道所有可能出现的键值键值, ,并且键值的位数比散列地址的位并且键值的位数比散列地址的位数多数多. .在这种情况下可以对键值的各位在这种情况下可以对键值的各位进行分析进行分析, ,选择分布较均匀的若干位组选择分布较均匀的若干位组成散列地址。成散列地址。假定已知可能出现的所有键值中的一假定已知可能出现的所有键值中的一部分如下：部分如下：0 0 10 0 1 3 3 1 1 9 9 4 4 2 2 1 10 0 1 6 1 8 3

43、 0 90 0 1 6 1 8 3 0 90 0 1 7 3 9 4 3 40 0 1 7 3 9 4 3 40 0 1 6 4 1 5 1 60 0 1 6 4 1 5 1 60 0 1 8 1 6 3 7 80 0 1 8 1 6 3 7 80 0 1 1 4 3 3 9 50 0 1 1 4 3 3 9 50 0 1 2 4 2 3 6 30 0 1 2 4 2 3 6 30 0 1 9 1 5 4 0 90 0 1 9 1 5 4 0 9 ( (左起左起) )前三位分布不均匀，第前三位分布不均匀，第5 5、7 7位亦有很多重位亦有很多重复，故应将这五位丢弃。剩下的第复，故应将这五位丢弃

44、。剩下的第4 4、6 6、8 8、9 9位都位都是分布较均匀的，可考虑它们或它们中的几位组合是分布较均匀的，可考虑它们或它们中的几位组合起来作为散列地址。起来作为散列地址。2.除余法除余法( (重点重点) ) 选择一个适当的正整数选择一个适当的正整数p，以键值除以，以键值除以p所所得的余数作为散列地址，即令散列函数得的余数作为散列地址，即令散列函数H为为H(key)keymodp这一方法的关键在于这一方法的关键在于p的选取。若选的选取。若选p为为偶数，则所得的散列函数总是将奇数键值映偶数，则所得的散列函数总是将奇数键值映射成奇数地址。偶数键值映射为偶数地址。射成奇数地址。偶数键值映射为偶数地址

45、。因而增加了冲突的机会。通常选因而增加了冲突的机会。通常选p为大于或为大于或等于散列表容量的最小素数。等于散列表容量的最小素数。 【例】【例】 已知已知1111个元素的关键码序列个元素的关键码序列: : 18,27,1,20,22,6,10,13,41,15,25 18,27,1,20,22,6,10,13,41,15,25 选取关键码与数据元素位置间的函数为选取关键码与数据元素位置间的函数为f(key) = key mod 11f(key) = key mod 11(1) (1) 建立散列表：建立散列表：01234567891022113251527618412010(2) (2) 查找时，

46、对给定值查找时，对给定值 kx kx 通过该函数计通过该函数计算出地址，再与该地址单元中的元素进行算出地址，再与该地址单元中的元素进行比较，若相等，查找成功。比较，若相等，查找成功。3.平方取中法平方取中法一个数的平方的中间几位与这个数的一个数的平方的中间几位与这个数的每一位都有关。利用这一特点，平方取每一位都有关。利用这一特点，平方取中法以键值平方的中间几位作为散列地中法以键值平方的中间几位作为散列地址。这一方法计算简单且不需要事先掌址。这一方法计算简单且不需要事先掌握键值的分布情况。又因取平方中能扩握键值的分布情况。又因取平方中能扩大键值差别，所得散列地址比较均匀。大键值差别，所得散列地址

47、比较均匀。4.4.基数转换法基数转换法将键值看成另一种进制的数再转换成原来进将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。例如，制的数，然后选其中几位作为散列地址。例如，对于十进制键值对于十进制键值210485210485，先把它看成是十三进，先把它看成是十三进制的数，并转换为十进制数：制的数，并转换为十进制数：21048521048513132 213135 5+1+113134 4+0+013133 3+4+413132 2+8+813+813+87719357719351010然后从中选取几位作为散列地址。通常要求然后从中选取几位作为散列地址。通常要求两个基数

48、互素，且新基数比原基数大。两个基数互素，且新基数比原基数大。5.5.随机数法随机数法选择一个随机函数选择一个随机函数randomrandom，以键值，以键值在该函数下的值作为散列地址：在该函数下的值作为散列地址：H(key)= random (key)H(key)= random (key)当各个键值的位数不同时采用此法当各个键值的位数不同时采用此法较好。较好。6.4.2 6.4.2 动态查找表在开散列表上的实现动态查找表在开散列表上的实现(拉链法拉链法) 采用散列技术需考虑的第二个主要问题是如采用散列技术需考虑的第二个主要问题是如何何解决解决“冲突冲突”。而处理冲突的方法与散列表。而处理冲突的方法与散列表本身的组织形式有关。按组织形式的不同，通本身的组织形式有关。按组织形式的不同，通常有两类散列表：开散列表与闭散列表。一旦常有两类散列表：开散列表与闭散列表。一旦选定了散列函数和散列表的组织形式，就可以选定了散列函数和散列表的组织形式，就可以确定相应的解决冲突的方法，进而可以给出动确定相应的解决冲突的方法，进而可以给出动态查找表的一个具体实现。态查找表的一个具体实现。 开散列表的组织方式如下。设选定的散列函开散列表的组织方式如下。设选定的散列函数为数为H ，H的值域的值域(即散列地址的集合即散列地址的集合)为为0.n-1。设置一个设置一个地址数组地址数组pointer