第8章(查找表)

1、第八章第八章 查找表查找表 基本概念基本概念 静态查找表静态查找表 动态查找表动态查找表 Hash Hash法法 查找表：查找表：用于查找的数据元素集合称为查找表。查找用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成表由同一类型的数据元素（或记录）构成。 是一种以集合为逻辑结构，以查找为核是一种以集合为逻辑结构，以查找为核 心运算，同时包心运算，同时包括其他运算的数据结构。括其他运算的数据结构。 基本概念基本概念静态查找表静态查找表：若只对查找表进行如下两种操作：若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，）在查找表中查看某个特

2、定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，）检索某个特定元素的各种属性，则称这类查找表为静态查找表。则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。对静态查找表进行的查找操作称为静态查找。动态查找表动态查找表：若在查找过程中可以将查找表中不存在的：若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会查找表为动态查找表。动态查

3、找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。发生变化。对动态查找表进行的查找操作称为动态查找。 查找表查找表静态查找表静态查找表动态查找表动态查找表1.建表：建表：Create(st)2.查找：查找：Search(st,k)3.读表元：读表元：Get(st,pos)2.查找：查找：Search(st,k)3.读表元：读表元：Get(st,pos)1.初始化：初始化：Initiate(st)4.插入：插入：Insert(st,k)5.删除：删除：Delete(st,k)22121398334244382448605874471234567891011121314

4、15第一块第一块第二块第二块第三块第三块1611224474关键字表关键字表小小大大指针表指针表: :应该指向各块的第一个关键字。应该指向各块的第一个关键字。分成三块分成三块每块每块5 5个个关键字关键字分块查找的方法分块查找的方法: :1)1)由于索引表按关键字有序，则确定由于索引表按关键字有序，则确定k k在哪一块的查找在哪一块的查找 可以用顺序查找，也可用折半查找。可以用顺序查找，也可用折半查找。 (1)动态查找(2)ASL(3)二叉排序树(4)平衡二叉树例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如图7-4所示。如对上述二叉排序树进行

5、中根遍历可以得到一个关键字有序序列如对上述二叉排序树进行中根遍历可以得到一个关键字有序序列（12, 15, 35,46, 57,62,65,68,79），这是二叉排序树的一个重要特征），这是二叉排序树的一个重要特征，也正是由此将其称为，也正是由此将其称为二叉排序树二叉排序树 “二叉排序树的构造方法：二叉排序树的构造方法：设设R=R1,R2,Rn为一数列为一数列,按下面的原按下面的原则建立二叉树：则建立二叉树：1)令令R1为二叉树的根；为二叉树的根；2)若若R2R1，则令，则令R2为为R1的左子树的根结的左子树的根结点，否则令点，否则令R2为为 R1的右子树的根结点；的右子树的根结点；3)对对R

6、3,R4,Rn重复上述步骤重复上述步骤2)；例：给定例：给定R=10,18,3,8,12,2,7,3R=10,18,3,8,12,2,7,3按上面的原则构造二按上面的原则构造二 叉排序树如下：叉排序树如下：R2R1R310R1R1为根节点为根节点R3R1R3R1R2R2R2比比R1R1大大R4R4R1 R4R3 R4R3 右边右边R5R5R1 R5R1 右边右边R5R2 R5R2 左边左边R6R6R1 R6R1 左边左边R6R3 R6R3 左边左边R710181018310183810183812101838122101838122710183812273R8R7R1 R7R3 R7R3 右边

7、右边R&R4 R&R4 左边左边R8R1 R8R3 R8R3 右边右边R8R4 R8R4 左边左边R8R7 R8key != k )if (k key ) p = p - lchild;else p = p - rchild; return ( p); 已知46,57,84,32,73,36,15,48,90,20要求:(1)按键值排列次序构造一棵二叉排序树.(2)在等概率的情况下,该二叉排序树查找成功的平均查找长度.(3)针对上述十个键值,对于不同的排列次序,构造不同形态的二叉排序树中,最好和最坏的情况下,二叉排序树的高度各是多少?平衡二叉树平衡二叉树(balanced bi

8、nary tree)平衡二叉树平衡二叉树：或者是一棵空树，或者是具有下列性质的或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过树和右子树的深度之差的绝对值不超过1 1。平衡因子平衡因子：二叉树中任一结点的左子树的深度与它的右二叉树中任一结点的左子树的深度与它的右子树的深度之差称为平衡因子。子树的深度之差称为平衡因子。例例: :2-1=12-1=10-0=00-0=01-0=11-0=10-0=00-0=0平衡二叉树平衡二叉树2-3=-12-3=-1ABCDFG1-1=01-1=

9、00-0=00-0=00-2=-20-2=-21-0=11-0=10-0=00-0=00-0=00-0=0非平衡二叉树非平衡二叉树ABCDE二叉排序树的平衡化二叉排序树的平衡化 假设表中的关键字序列为假设表中的关键字序列为(13,24,37,90,53)(13,24,37,90,53)空树和一个结点空树和一个结点 的的二叉树显然是平衡二叉树二叉树显然是平衡二叉树 . .插入插入2424后仍平衡后仍平衡131324-10 插入插入 后结点后结点 的平衡因子为的平衡因子为0-2=-20-2=-2，不平衡，不平衡把把 从从 的右下侧的右下侧左转到左转到 的右上侧的右上侧原来原来 的左为的左为 的右的

10、右, ,新的新的 的左为的左为1324 24370-1-1-2-2RRRR型即逆时针旋转型即逆时针旋转371313243724131324132413 插入插入90,5390,53后后, ,又失去平衡又失去平衡, , 可经过下列步骤转化为平衡二叉树可经过下列步骤转化为平衡二叉02_101324379053 第一次旋转第一次旋转( (顺时针顺时针) )以以 为轴心为轴心, ,把把 从从 的右上的右上, ,转到转到的右下的右下, , 的右是的右是 , , 的右为的右为 , ,原原 的右变成新的右变成新 的左。的左。RLRL型的第一次旋转型的第一次旋转( (顺时针顺时针)

11、)1324539037RLRL型的第二次旋转型的第二次旋转( (逆时针逆时针) ) 以以 为轴心为轴心, ,把把 从从 的左上转到的左上转到 的左下的左下, ,使得使得 的左的左是是 ; ;右是右是 ，原，原 的左变成了的左变成了 的右。的右。53905353375353905390533753535337905337 一般情况下，假设由于二叉排序树上插入结点而失去一般情况下，假设由于二叉排序树上插入结点而失去平衡的最小子树的根结点指针为平衡的最小子树的根结点指针为a a（即（即a a是离插入结点最是离插入结点最近近, ,且平衡因子绝对值超过且平衡因子绝对值超过1 1的祖先结点），则失去平衡的

12、祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况后进行调整的规律可归纳为下列四种情况: : RRRR型平衡旋转型平衡旋转: :ba br a1 b1RRab a1 b1 br-2-1hh-1h-1插入节点插入节点 把结点把结点b b从从a a的右下侧逆时针的右下侧逆时针( (左转左转) )转到转到a a的右上侧，的右上侧，原原b b的左成为的左成为a a的右，新的右，新b b的左为的左为a a 0hh-10h-12.LL2.LL型平衡旋转型平衡旋转: :LL21hh-1h-1ab ar br b1a b1 br ar00 把结点把结点b b从左下侧顺转从左下侧顺转( (右转右转) )

13、转到转到a a的左上侧的左上侧, ,原原b b的右的右成为成为a a的左的左, ,新新b b的右为的右为a a。3.RL3.RL型平衡旋转型平衡旋转: :-21h-11h-1 a1 c c1 cr brh-1h-2RL(RL(顺时针顺时针) ) c1 a1 cr brbabacb hh-1h-1h-2h-1h-1-1-1-2 以以c c为轴心，把为轴心，把b b从从c c的右上侧顺时针（右转的右上侧顺时针（右转) )到到c c的右的右下侧，从而下侧，从而a a的右是的右是c c，c c的右是的右是b b，原，原c c的右变成的右变成b b的左。的左。 以以c c为轴心，把为轴心，把a a从从c

14、 c的左上方，转到的左上方，转到c c的左下方，使的左下方，使得得c c的左是的左是a a，右是，右是b b，原，原c c的左子树变成的左子树变成a a的右。的右。RL(RL(逆时针逆时针) ) c1 a1 cr br4.LR4.LR型平衡旋转型平衡旋转: :cab 以以c c为轴心把为轴心把b b从从c c的左上侧，逆时针（左转）到的左上侧，逆时针（左转）到c c的左的左下侧，从而下侧，从而a a的左是的左是c,cc,c的左是的左是b b，原，原c c的左变成新的左变成新b b的右。的右。 c1 a1 cr bracbh-1h-2h-1h-1-1-1-2h-1h-2h-1-100LR(LR(

15、逆时针逆时针) ) c1 ar cr bl2-11h-1h-1h-2 ar c1 cr b1h-1LR(LR(顺时针顺时针) ) c1 ar cr bl 再以再以c c为轴心，把为轴心，把a a从从c c的左上方转到的左上方转到c c的右下方，使得的右下方，使得c c的右是的右是a a，左是，左是b b，原，原c c的右子树变成的右子树变成a a的左。的左。abcacbcbah-1h-1h-2h-1022a c1 ar cr blcbh-1h-1h-2h-1022h-10h-2h-1-10将8,6,3,1,2,5,9,7,4中的数依次插入到时一棵空的平衡二叉排序树中,求在等概率的情况下,查找成

16、功的平均检索长度,查找失败时对键值的最多 比较次数.B-B-树树B-B-树：一棵树：一棵m m阶的阶的B-B-树，或为空树，或为具有下列性质树，或为空树，或为具有下列性质 的的m m叉树：叉树： 1)1)树中每个结点有树中每个结点有mm个儿子；个儿子； 2)2)除根和叶子结点之外的结点有除根和叶子结点之外的结点有Upper(m/2)Upper(m/2)个儿子；个儿子； 3)3)根结点至少要有两个儿子根结点至少要有两个儿子( (除非它本身又是一个除非它本身又是一个 叶子叶子) )； 4)4)所有的非终端结点中包含下列信息数据所有的非终端结点中包含下列信息数据(n,A(n,A0 0 , , k k

17、1 1 ,A ,A1 1 , , k k2 2 ,k,kn n ,A,An n) )； n n：本结点中关键字的个数：本结点中关键字的个数m-1m-1 k ki i ：关键字，从左到右其值按递增次序排列：关键字，从左到右其值按递增次序排列 A Ai i ：指向一个所有关键字都在：指向一个所有关键字都在k ki i和和k ki+1i+1间的子树形间的子树形 5)5)所有的叶子结点都在同一层次上，并且不带信所有的叶子结点都在同一层次上，并且不带信 息息( (可以看作是查找失败的结点，实际上这些结可以看作是查找失败的结点，实际上这些结 点不存在，指向这些结点的指针为空点不存在，指向这些结点的指针为空

18、) )；118111127135139199243783475364abcdefgh上图中上图中, ,结点形式为结点形式为: :n n 指针指针 关键字关键字 指针指针 关键字关键字.p0p0k1k1p1p1k2k2 每一个结点每一个结点( (除了根结点和叶子除了根结点和叶子),),有有Upper(4/2)Upper(4/2)到到4 4个儿子，个儿子，所以可以有所以可以有1 1，2 2或或3 3个关键字，根结点允许有个关键字，根结点允许有1 1至至3 3关键字，此时关键字，此时所有的所有的叶子都在第四层上。叶子都在第四层上。例：下图所是为一棵例：下图所是为一棵4阶的阶的B-树，深度为树，深度为

19、4在在B-B-树上进行查找所需时间的分析树上进行查找所需时间的分析 从上述过程可知，在从上述过程可知，在B-B-树上进行查找所需时间取决于两个因树上进行查找所需时间取决于两个因素：素： 等于给定值的关键字所在的层次数等于给定值的关键字所在的层次数; ; 结点中关键字的数目。结点中关键字的数目。( (较大时可用折半查找较大时可用折半查找) ) 显然，节点所在的最大层次数即为树的深度。那么，含有显然，节点所在的最大层次数即为树的深度。那么，含有N N个个关键字的关键字的m m阶阶B-B-树的最大深度是多少？树的最大深度是多少？ 根据根据B-B-树的定义树的定义 第一层至少有第一层至少有1 1个结点

20、个结点 第二层至少有第二层至少有2 2个结点个结点 第三层至少有第三层至少有2 2* * m/2 m/2 个结点个结点 ( (因为除根之外的每个非终端结点至少有因为除根之外的每个非终端结点至少有 m/2 m/2 个个) ) 第四层至少有第四层至少有2 2* * m/2 m/2 2 2个结点个结点最末层最末层L+1L+1层有层有2 2* * m/2 m/2 L-1L-1个结点个结点 ( (因为最末层为叶子因为最末层为叶子,m,m阶阶B B树中有树中有N N个关键字个关键字, ,则叶子结点为则叶子结点为N+1N+1个个, ,由此有由此有 N+12N+12* *( m/2 )( m/2 )L-1L-

21、1 N+1N+12 2 ( m/2 )( m/2 )L-1L-1两边取对数两边取对数log( )log( )N+1N+12 2 (L-1)(L-1)log( m/2 )log( m/2 )L-1L-1log( )log( )N+1N+12 2log( m/2 )log( m/2 )换底换底= =log ( )log ( )m/2m/2N+1N+12 2loglogm/2m/22 2log ( )log ( )m/2m/2m/2m/2loglogm/2m/22 2= =log ( )log ( )m/2m/2N+1N+12 21 1log ( )log ( )m/2m/2N+1N+12 2LL

22、log ( )log ( )m/2m/2N+1N+12 2+1+1 这就是说，在含有这就是说，在含有N N个关键字的个关键字的B-B-树上，进行查找时，从根树上，进行查找时，从根j j结点到关键字所在结点的路径上涉及的结点数不超过结点到关键字所在结点的路径上涉及的结点数不超过log ( )log ( )m/2m/2N+1N+12 2+1+1 个个例如例如: :当当N=1999998N=1999998且且m=199m=199时时,L,L最多为最多为3 3。 这就是说，在最坏情况下，一次查找至多需要存取这就是说，在最坏情况下，一次查找至多需要存取3 3个结点。个结点。B-B-树的插入：树的插入：

23、B-B-树的生成也是从空树起，逐个插入关键字。但由树的生成也是从空树起，逐个插入关键字。但由于于B-B-树结点中的关键字个数必须大于树结点中的关键字个数必须大于Upper(m/2)-1Upper(m/2)-1，因，因此，每次插入一个关键字，不是在树中添加一个叶子结此，每次插入一个关键字，不是在树中添加一个叶子结点，而是首先在最底层的某个非终端结点中添加一个关点，而是首先在最底层的某个非终端结点中添加一个关键字，若该结点的关键字不超过键字，若该结点的关键字不超过m-1m-1，则插入完成，否，则插入完成，否则要产生结点则要产生结点“分裂分裂”。例例: :在如下的在如下的3 3阶阶B-B-树上分别插

24、入树上分别插入30,26,8530,26,85和和7 7454550501001002424373753 90 3 1261 70a ab bc cd de ef fg gh h( (图一图一) )插入插入303045455050100100242453 90 3 1261 70a ab bc cd de ef fg gh h( (图二图二) ) 30 37插入插入262645455050100100242453 90 3 1261 70a ab bd de ef fg g( (图三图三) ) 26 30 37c c将将2626插入插入d d后，由于后，由于d d中的关键字数目超过中的关键字数

25、目超过2 2，此时将，此时将d d分裂为两个分裂为两个结点结点, ,关键字关键字2626及其前后两个指针留在及其前后两个指针留在d d中，而中，而3737及其前后两个指及其前后两个指针存储到新产生的结点针存储到新产生的结点dd中，同时将中，同时将3030和指示结点和指示结点dd的指针插入的指针插入到双亲节点到双亲节点b b中。由于中。由于3030插入插入b b后没超过后没超过2,2,则插入完成。则插入完成。h h454550501001002653 90 3 1261 70a ab bc cd de ef fg gh h( (图四图四) ) 24 3037dd插入插入8585454550501

26、001002653 90 3 1261 70 85a ab bc cd de ef fg gh h( (图五图五) ) 24 3037dd8585插入插入g g后后, ,需分裂成两个结点需分裂成两个结点g,g,70g,g,70插入到插入到e e中中, ,由于由于e e中关键中关键字字22个个, ,所以所以,e,e又分裂为又分裂为e,ee,e，7070插入插入a a中。中。g,eg,e分裂后的图分分裂后的图分别见图六、图七：别见图六、图七：4550501001002653 70 90 3 12a ab bc cd de ef fg gh h( (图六图六) ) 24 3037dd61gg8550

27、501001002645 70 3 12a ab bc cd deef fg gh h( (图七图七) ) 24 3037dd61gg855390e e插入插入7 750501001002645 70 3 7 12a ab bc cd deef fg gh h( (图八图八) ) 24 3037dd61gg855390e e50501001002645 70a ab bc cd deef fg gh h( (图九图九) ) 7 24 3037dd61gg855390e e312cc50501001002624 45 70a ab bc cd deef fg gh h( (图十图十) )37dd

28、61gg855390e e312cc730505010010026a ab bc cd deef fg gh h( (图十一图十一) )37dd61gg855390e e312cc730bbbb247045aam m 一般情况，结点可如下实现一般情况，结点可如下实现“分裂分裂”。 假设假设p p节点中已有节点中已有m-1m-1个关键字，但插入一个关键字之后，结点中含有信息为：个关键字，但插入一个关键字之后，结点中含有信息为：此时此时, ,可将可将P P节点分裂为节点分裂为P P和和PP两个节点两个节点: P PP PPP 即把关键字即把关键字K K 插入到它的父亲结点中，因此在父亲结点中插入到

29、它的父亲结点中，因此在父亲结点中指针指针P P和和PP是按如下顺序被放置的。是按如下顺序被放置的。 .,P,K ,P.,P,K ,P.m/2 m/2 m/2 m/2 m m，A A0 0 ，K K1 1 ，A A1 1 ，K K2 2 ，A A2 2 ，. . ，K Km m A Am m，A A0 0 ，K K1 1 ，A A1 1 ，K K ，A Am/2 -1m/2 -1m/2 1m/2 1m/2 -1m/2 -1m- m/2 ,A ,K ,A ,.Km,Amm- m/2 ,A ,K ,A ,.Km,Amm/2 m/2 m/2 +1m/2 +1m/2 +1m/2 +1 纵观以上两节讨论的

30、表示查找表的各种结构，有一纵观以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系，因此，查找的过程为给定值依次和关一个确定的关系，因此，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。给定值进行比较的关键字个数。 因此，用这类方法表示的查找表，其平均查找长度因此，用这类方法表示的查找表，其平均查找长度都不为零，不同表示方法的差别仅在于：和给定值进行都不为零，不同表示方法的差别仅在于：和给定值进行

31、比较的关键字的顺序不同。比较的关键字的顺序不同。 对于频繁使用的查找表，希望对于频繁使用的查找表，希望ASL=0ASL=0。即不需要从。即不需要从“比较比较”的结果来确定查找成功，只有一个办法：预先知的结果来确定查找成功，只有一个办法：预先知道所查关键字在表中的位置，也就是说，记录在表中位道所查关键字在表中的位置，也就是说，记录在表中位置和其关键字之间存在一种确定的关系置和其关键字之间存在一种确定的关系。 Hash法法什么是什么是HashHash表表？例如：为每年招收的例如：为每年招收的10001000名新生建立一张查找表，其关名新生建立一张查找表，其关键字为键字为xx000-xx999(xx

32、000-xx999(前两位为年份前两位为年份) )。则可以下标为。则可以下标为000-999 000-999 的顺序表表示之。由于关键字和记录在表中的的顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。序号相同，则不需要经过比较即可确定待查关键字。但是，对于动态查找表而言，但是，对于动态查找表而言，1) 1) 表长不确定；表长不确定；2)2)在设计在设计查找表时，只知道关键字所属范围，而不知道确切的关键查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况，需建立一个函数关系，以字。因此，一般情况，需建立一个函数关系，以f(key)f(key)作

33、作为关键字为为关键字为keykey的记录在表中的位置，通常称这个函数的记录在表中的位置，通常称这个函数f(key)f(key)为哈希函数。为哈希函数。( (注意：这个函数并不一定是数学函注意：这个函数并不一定是数学函数数) )简单地说，简单地说，哈希表是基于哈希函数建立的一种查找表。哈希表是基于哈希函数建立的一种查找表。例如：对于如下例如：对于如下9 9个关键字个关键字 Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei 13 896 1114122设设 从这个例子可见，从这个例子可见，哈希函数是一个映象，即：将关键字的集合映射到哈希函数是一个映象，即：将关键字的集合映射到

34、某个地址集合上，它的设置很灵活，只要这个地址某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可集合的大小不超出允许范围即可; ; 由于哈希函数是一个压缩映象，因此，在一般情况由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生下，很容易产生“冲突冲突”现象，即：现象，即：key1key2key1key2，而而 f(key1) = f(key2),f(key1) = f(key2),并且，改进哈希函数只能减并且，改进哈希函数只能减少冲突，而不能避免冲突。少冲突，而不能避免冲突。因此，在设计哈希函数时，一方面要考虑选择一个因此，在设计哈希函数时，一方面要考虑选择一个“好

35、好”的哈希函数的哈希函数; ;另一方面要选择一种处理冲突的方法。另一方面要选择一种处理冲突的方法。所谓所谓“好好”的哈希函数，指的是，对于集合中的任意一个的哈希函数，指的是，对于集合中的任意一个关键字，经哈希函数关键字，经哈希函数“映象映象”到地址集合中任何一个地址到地址集合中任何一个地址的概率是相同的。称这类哈希函数为的概率是相同的。称这类哈希函数为“均匀的均匀的”哈希函数哈希函数。根据设定的哈希函数根据设定的哈希函数H(key)H(key)和所选中的处理冲突的方法，和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集将一组关键字映象到一个有限的、地址连续的地址集( (区

36、区间间) )上，并以关键字在地址集中的上，并以关键字在地址集中的“象象”作为相应记录在作为相应记录在表中的存储位置，这种表被称为哈希表。表中的存储位置，这种表被称为哈希表。HashHash法的关键在于哈希表的构造和冲突的处理法的关键在于哈希表的构造和冲突的处理哈希函数的构造方法哈希函数的构造方法对数字的关键字可有下列哈希函数的构造方法，若对数字的关键字可有下列哈希函数的构造方法，若是非数字关键字，则需先对其进行数字化处理。是非数字关键字，则需先对其进行数字化处理。1.1.直接定址法直接定址法 哈希函数为关键字的线性函数哈希函数为关键字的线性函数H(key) = key H(key) = key

37、 或者或者 H(key) = aH(key) = a* *key + bkey + b 仅限于：地址集合的大小仅限于：地址集合的大小 = = 关键字集合的大小关键字集合的大小 例例 有一个从有一个从1 1到到100100岁的人口数字统计表岁的人口数字统计表, ,用年龄做关键字，用年龄做关键字，它采用的它采用的hashhash函数是第一种函数是第一种H(K)=K,H(K)=K,即即j=kj=k。地址地址 01 02 03 25 26 27 28 10001 02 03 25 26 27 28 100年龄年龄 1 2 3 25 26 27 28 1001 2 3 25 26 27 28 100人数

38、人数 3000 2000 5000 1020 2070 7001 7200 103000 2000 5000 1020 2070 7001 7200 102.2.数字分析法数字分析法 例例 有七个有七个8 8位十进制的关键字（有七个关键字，每个关键字位十进制的关键字（有七个关键字，每个关键字都具有八位十进制数），将其散列在地址为都具有八位十进制数），将其散列在地址为10-9010-90的表中。的表中。 地址地址 k1k1：5 4 2 4 2 2 4 2 425 4 2 4 2 2 4 2 42 k2 k2：5 4 2 8 1 3 6 7 835 4 2 8 1 3 6 7 83 k3 k3：5

39、 4 2 2 2 8 1 7 285 4 2 2 2 8 1 7 28 k4 k4：5 4 2 3 8 9 6 7 395 4 2 3 8 9 6 7 39 k5 k5：5 4 2 5 4 1 5 7 515 4 2 5 4 1 5 7 51 k6 k6：5 4 2 6 8 5 3 7 655 4 2 6 8 5 3 7 65 k7 k7：5 4 2 1 9 3 5 5 135 4 2 1 9 3 5 5 13仅限于：能预先估计出全体关键字的每一位上各种数字仅限于：能预先估计出全体关键字的每一位上各种数字出现的频度。出现的频度。假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是

40、由s s位数字组成位数字组成(k(k1 1, k, k2 2, , k, , kn n) )，分析关键字集中的全体，并从中，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。提取分布均匀的若干位或它们的组合作为地址。3.3.平方取中法平方取中法 若关键字的每一位都有某些数字重复出现频度很高的若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过现象，则先求关键字的平方值，以通过“平方平方”扩大差别扩大差别，同时平方值的中间几位受到整个关键字中各位的影响，同时平方值的中间几位受到整个关键字中各位的影响. .4.4.折迭法折迭法 若关键字的位数特别多，

41、则可将其分割成几部分，若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为哈希地址。相加的方法有移位法然后取它们的叠加和为哈希地址。相加的方法有移位法和折叠法。和折叠法。折叠法：把一关键字看承一张纸条，从一端向另一端折叠法：把一关键字看承一张纸条，从一端向另一端沿边界逐层折叠，再把相应的位数加在一起。沿边界逐层折叠，再把相应的位数加在一起。移位法：将各部分的最后一位对齐，然后相加。移位法：将各部分的最后一位对齐，然后相加。假定关键字假定关键字:K=d1d2d3drdr+1d2rd2r+1d3r:K=d1d2d3drdr+1d2rd2r+1d3r允许允许有的存储地址有有的存储地址有r

42、 r位。位。 移位法移位法： d1 d2 drd1 d2 dr dr+1 dr+2 d2r dr+1 dr+2 d2r + d2r+1d2r+2d3r + d2r+1d2r+2d3r高进位不要了高进位不要了得到得到r r位的存储地址位的存储地址折叠法折叠法: d3r d3r-1d2r+1: d3r d3r-1d2r+1 dr+1dr+2 d2r dr+1dr+2 d2r + dr dr-1 d1 + dr dr-1 d1 d1 d2 dr d1 d2 dr高进位不要了高进位不要了得到得到r r位的存储地址位的存储地址例如：例如：K=32834872K=32834872，允许存储地址为三位十进制

43、数。，允许存储地址为三位十进制数。 位移法：位移法： 328 328 折叠法：折叠法： 2727 348 348 348 348 + 72 + 823 + 72 + 823 748 1198 748 1198 H(K)=748 H(K)=198 H(K)=748 H(K)=1985.5.除留余数法除留余数法 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况合的情况(包括关键字的范围和形态包括关键字的范围和形态)，总的原则是使产生冲突的可，总的原则是使产生冲突的可能性降到尽可能地小。能性降到尽可能地小。设给出关键字设给出

44、关键字k k，存储单元数为，存储单元数为m,m,则可选一数则可选一数p(p=m)p(p=m)去去除除k k得到余数得到余数r(r(以以p p为模为模) )，再用一线性函数，再用一线性函数f f将将r r转换为转换为散列地址散列地址j,j,即即r=(k) mod p, j=f(r)r=(k) mod p, j=f(r)例例 有一组关键字从有一组关键字从000001-859999000001-859999，指定的存储单元地址为，指定的存储单元地址为1000000-1005999,1000000-1005999,即即m=6000m=6000。选。选p=5999 k=172148p=5999 k=17

45、2148 r=(172148) mod 5999=4176(mod 5999) r=(172148) mod 5999=4176(mod 5999) f=1000000+r=1004176 f=1000000+r=1004176在这里选择在这里选择p p是关键步骤，若是关键步骤，若P P为偶数，则凡是奇数的关键字，为偶数，则凡是奇数的关键字， 都转换为奇数地址，则凡是偶数的关键字地都转换为偶数地址，都转换为奇数地址，则凡是偶数的关键字地都转换为偶数地址， 显然会出现冲突。一般情况：显然会出现冲突。一般情况：(1)P(1)P尽量接近尽量接近m;(2)pm;(2)p为质数。为质数。8.3.2处理冲

46、突的方法处理冲突的方法 处理冲突的方法处理冲突的方法开放定址法开放定址法链地址法链地址法线性探测再散列线性探测再散列二次探测再散列二次探测再散列伪随机探测再散列伪随机探测再散列探测：探测：检查关键字是否与检查关键字是否与hashhash向量元素相匹配。向量元素相匹配。一、开放定址法一、开放定址法假设哈希空间为假设哈希空间为T(0:m-1),T(0:m-1),哈希函数为哈希函数为j=H(key)j=H(key)。为求得下一个哈希地址，可取为求得下一个哈希地址，可取j ji i=(j+d=(j+di i) MOD m) MOD m， i=1,2,3,.,s(s1),i=1,2,3,.,s(s1),

47、其中其中m m为哈希表的表长为哈希表的表长d di i为增量序列。为增量序列。1.1.当取当取d di i=1,2,3,.,s=1,2,3,.,s时称为时称为线性探测再散列线性探测再散列 例如：例如：有一个关键字序列有一个关键字序列19, 7019, 70，3333，已存入长度，已存入长度为为1616的哈希表中。的哈希表中。取哈希函数为除留余数法取哈希函数为除留余数法: j=k MOD 13: j=k MOD 13；01456781570193318现在要把关键字为现在要把关键字为1818的记录填入表中：的记录填入表中：j=18 MOD 13=5 j=18 MOD 13=5 冲突冲突 1 1次

48、次j j1 1=(5+1)MOD 16=6 =(5+1)MOD 16=6 冲突冲突j j2 2=(5+2)MOD 16=7 =(5+2)MOD 16=7 冲突冲突j j3 3=(5+3)MOD 16=8 =(5+3)MOD 16=8 不冲突不冲突 Hash地址地址 是否冲突是否冲突 冲突次数冲突次数2 2次次3 3次次j=19 MOD 13=6j=19 MOD 13=6；j=70 MOD 13=5j=70 MOD 13=5；j=33 MOD 13=7j=33 MOD 13=7 2.2.当取当取d di i=1=12 2 ,-1 ,-12 2 ,2 ,22 2,-2,-22 2,n,n2 2 ,

49、-n ,-n2 2 时称为时称为: : 二次探测再散列二次探测再散列仍以上例为例，仍以上例为例，7070，1919，3333已填入哈希表中，再已填入哈希表中，再填入关键字为填入关键字为1818的记录的记录: : j j1 1=(5+1) MOD 16=6=(5+1) MOD 16=601456781570193318j=18 MOD 13=5 j=18 MOD 13=5 冲突冲突 1 1次次Hash地址地址 是否冲突是否冲突 冲突次数冲突次数j j2 2=(5-1) MOD 16=4 =(5-1) MOD 16=4 不冲突不冲突2 2次次冲突冲突设散列表为HT13, 散列函数为 H (key)

50、 = key %13。用二次探测再散列二次探测再散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。说明：说明： 线性探测法可以探测到

51、哈希表中的各个位置，但线性探测法可以探测到哈希表中的各个位置，但它容易产生它容易产生“堆聚堆聚”现象。例如，关键字为现象。例如，关键字为2121的记录，的记录，由哈希函数得到哈希地址为由哈希函数得到哈希地址为8 8，则产生冲突。但是这，则产生冲突。但是这种冲突不是由同义词所引起的，而是在解决同义词冲种冲突不是由同义词所引起的，而是在解决同义词冲突的过程中又添加出的非同义词冲突。这种现象会使突的过程中又添加出的非同义词冲突。这种现象会使探测次数增加，对查找极为不利。探测次数增加，对查找极为不利。 二次探测法可减少二次探测法可减少“堆聚堆聚”，但由于它不能保证，但由于它不能保证探测到哈希表中的所有位置