【文档说明】课件】计算机算法设计与分析-[105页].ppt，共(105)页，2.000 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-77580.html

以下为本文档部分文字说明：

计算机算法设计与分析Chapter4.数据集合上的搜索(Searching)算法4.1动态数据集(DynamicSet)与抽象数据类型(ADT)4.2二叉搜索树(BinarySearchTrees)4.3随机二叉搜索树(Rand

omlyBuiltBinarySearchTree)4.4红黑树(Red-BlackTree)4.52-3-4树4.6Hashing技术4.1动态数据集(DynamicSet)与抽象数据类型(ADT)静

态数据集（StaticSet）中的数据是固定不变的。动态数据集（DynamicSet）则是由不断变动的同类型数据元素组成的数据集合。动态数据集（DynamicSet）可以表示为一个数据元素的数组：classDynamicSet{intsetSize;Objectelements[setSiz

e];...}//Object为数据元素的类型，setSize为当前集合中的元素个数用数组表示集合操作方便，但当集合中的元素个数不断增加时，数组的长度必须扩大。一般采用空间倍增（arraydoubling）技术，即另外申请一个

加倍长度的新数组，把集合中的数据传送过来，取代原有的空间。其过程为：arrayDouble(set){newSize=2*arraySize;newElements=newObject(newSize);Transferalle

lementsfromtheset.elementstothenewElement;set.elements=newElements;set.setSize=newSize;}更为灵活的存储形式是利用指针和链表（例如

线性链表和树结构），这种存储形式在搜索算法中经常用到。搜索问题：在集合中检索出其关键字域的值等于给定值的数据元素。已知：动态数据集类型DynamicSet的一个实例set和值x。求：集合set中一个元素Obje

ctelement，使element.key=x。数据集合上的操作（operation）可以分为两类：.查询（queries）操作：对数据集不做任何变动，仅仅返回有关集合的某些信息；.修改（modifyingoperations）操作

：要对数据集合的某些域进行改动。一些典型的操作：.Search(S,k)：搜索，一个查询操作。对于给定的数据集合S和一个关键字值k，返回S中一个元素（element）的指针x，使得x->key=k。当S中没有符合条件的元素时，返回的指针为空（NULL）。.Inser

t(S,x)：插入，一个修改操作。把由x指向的数据元素加入到集合S中，一般假定在x指向的数据元中，与集合运算相关的所有分量（域）都已经初始化。.Delete(S,x)：删除，一个修改操作。给定指向集合S中一个元

素的指针x，将此元素从S中删除。.Minimum(S)：求最小元，一个查询操作。若集合S中所有数据元素的关键字值为一全序集，则返回具有最小关键字值的数据元素的指针。.Maximum(S)：求最大元，一个查询操作。返回具有最大关键字值的数据元素的指针。.Deletemin(S)：删除最小元，

一个修改操作。它相当于Minimum(S)和Delete(S,x)的联合，即：Delete(S,Minimum(S))。.Successor(S,x)：求后继数据元，一个查询操作。若S中的数据元素按关键字值从小到大排列，x是指向S中某一数据元素的指针，则返回x所指向的数据元素的下

一个数据元素的指针。若x指向最后一个数据元素，则返回NULL。.Predecessor(S,x)：求前导数据元，一个查询操作。返回x所指向的数据元素的前一个数据元素的指针。若x指向第一个数据元素，则返回

NULL。搜索算法（及相关操作算法）的设计实际上是实现适合各种不同应用需要的ADT，例如：字典（Dictionary）作为抽象数据类型，可以分为两类：·静态字典：（静态数据集S，Search）；·动态字典：（动态数据集S，Search，Insert，Del

ete）。优先队列（PriorityQueue）：（动态数据集S，Insert，Deletemin）。4.2二叉搜索树二叉搜索树又称为二元字典树，是一种最常用的动态数据集的数据结构，可以用于实现字典和优先队列等ADT。4.2.1二叉搜索树（BinarySearchTre

es）BST的一个结点与一个数据项相对应，除了数据项Object或数据项的指针之外，结点主要由关键字key域和指针域组成，即关键字key与指针left、right和p，三个指针分别指向该结点的左儿子、右儿子和父结点。BST中结点的关键字值应满足BST性质：即

，设x是二叉搜索树的一个结点，结点y位于结点x的子树中，x、y的关键字值应满足以下关系：PKEYLeftRight如果y是x的左子树中的一个结点，则y->key≤x->key；如果y是x的右子树中的一个结点，则y->key>x->key。Fig.4.1给出了由6个结点（数据项）组成的两个二叉

搜索树。两个BST(a)和(b)有不同的树高，前者比后者的查询效率更高。遍历二叉搜索树的所有结点可以采用中序遍历（inordertreewalk）算法，即可将与二叉搜索树结点相对应的数据项按关键字从小到大排列出来。中序遍历（Inorder_Tree_Walk）算法4.2.2查询

（Querying）的实现对二叉搜索树的查询主要是Search、Minimum、Maximum、Successor、Predecessor等操作，这些操作都可在O(h)时间内完成，其中h是二叉树的高。如Fig.4.2所

示，BST查询操作为Tree_Search(root,k)，即搜索BST上关键字值为k的结点。Tree_Search算法求最小元（或最大元）的操作只需从根开始沿着左指针（或右指针）一直搜索至某一结点x，

其left或right指针为NULL，这时结点x的关键字x->key为最小（或最大）。求最小元的算法Tree_Minimum(root)求最大元的算法Tree_Maximum(root)求数据项的后继与前导项的操作要相对复杂，如Fig.4.2，结点15（指关键

字为15的结点)的后继是结点17，它是结点15的右子树中的最小元。然而对于没有右子树的结点，例如13、4和17，其后继分别为15、6和18，显然计算这三个结点的后继时需要使用父结点指针x->p。求后继项的操作算法Successor(x)15的前导是左子树中的最大元17的

前导是其第一个左祖先Successor(x)操作根据条件x->right!=NULL决定两种情形：第一种情况从结点x下行，直到叶结点，其路长显然不超过树高h；第二种情况从结点x上行，路长同样不超过h。因此有下面的结论：定理4.1动态数据集合

的查询操作Search、Minimum、Maximum、Successor、Predecessor可通过二叉搜索树实现，其算法可在O(h)时间内完成，其中h为二叉搜索树的高。4.2.3插入与删除操作动态数据集上的Insert(S,x)、Delete(S,x)操作与查询操作不同，它们会引起

二叉搜索树本身的变化。(插入一定是插入到最底层)插入操作算法Tree_InsertFig.4.3表示把新的数据项14（关键字值为14）作为新结点插入到二叉搜索树的过程。从二叉搜索树中删除一个结点的算法比较复杂，假定待删除结点指针z不为NULL，有三种情形：（1）

结点z没有子结点，可直接删除；（2）结点z只有一个子结点，可使z的父结点z->p直接指向z的子结点z->left或z->right；（3）结点z有两个子结点，则z的后继结点y必然在z的右子树中，且y无左子结点，按步骤（

1）或（2）删除结点y，用y的数据取代z的数据。过程如图所示：删除操作算法Tree_Delete这个算法除了调用函数Tree_Successor(root,z)的时间代价为O(h)外，其余各处的时间代价均为O(1)阶。Tree_Insert(root,z)的运行是在从根

到某一个叶结点的一条路径上进行的，因此有下面的结论。定理4.2动态数据集的Insert(S,x)、Delete(S,x)操作可通过二叉搜索树实现，其算法可在O(h)时间内完成，其中h为二叉搜索树的高。4.3随机二叉搜索树随机二叉

搜索树（RandomlyBuiltBinarySearchTree）：一个由n个结点（具有n个不同的关键字）按随机顺序，经过n次Tree_Insert操作插入到一个原始空树而得到的二叉搜索树，称为随机二叉搜索树（RBST）。这里的按随机顺序是指，n个不同关键字的n!种不同排列的出现是

等可能的。定理4.3由n个不同的关键字组成的随机二叉搜索树的平均树高为h=O(logn)。该定理的证明基本思路与步骤：1.有关概率分布的假设：假定关键字输入序列k1,k2,...,kn为n个不同值的一种排列，设各种不同排序为等可能的，因此这一特定排序出现的可能性为1/

n!。假定：对任一j值（1≤j≤n），kj取n个关键字其中任意一个的概率为1/n，也是等可能的。2.在RBST中结点x为结点y的祖先的充要条件：首先分析从根到树上任一结点y（y->key=kj,1<j≤n）的

路径上的结点特征。分析的结果是，在这条路上的每个结点x（x->key=ki）都具有下列特征：·其对应的关键字ki在输入关键字序列中位于kj之前，即1≤i<j≤n；·ki值必为两种情形之一：①ki是k1,k2,...,ki中大于kj的若干值中的最小者；②ki是k1,k2

,...,ki中小于kj的若干值中的最大者。上述情形是充分必要的，它可以叙述为：命题4.1设二叉搜索树T是依次把不同关键字k1,k2,...,kn插入到一个原始为空的二叉搜索树而得到的结果，则结点x（x

->key=ki）在T中是结点y(y->key=kj)的祖先的充要条件是：}1:max{}1:min{jllijllikkandilkkorkkandilkk在Fig.4.5中，kj=17。从图(a)中可以看到，从根到结点17的路径上的4个结点的关键字都符合上述条件，

而且，从(b)表中的关键字序列中可以看出，关键字17前面的10个关键字中满足命题4.1条件的关键字21、19、9、12全是结点17的祖先。命题4.1证明证明：分为两种情况，1）证明Ki是从1（根）至i中值大于kj的结点中值最小者（命题前部）设k’为从1（根

）至ki中路径上的点，且k’>kj，则为证明上述命题，只需证明k’>ki。为证明这一点，采用反证法，设k’<ki。由于k’,ki,kj在一个路径上，则由于k’<ki，则ki，kj一定在k’的右子树中，因此一定有k’<kj成立，这与k’>kj矛盾。2)同理

可证命题右部.}1:max{}1:min{jllijllikkandilkkorkkandilkk3.求RBST中任一结点的深度d(kj,T)：从命题4.1立即可以计算出T中任一（与关键字kj对应的）结点

的深度d(kj,T)恰恰等于满足命题4.1条件的（祖先）结点的个数，即：命题4.2在上述的随机二叉搜索树T中，对于给定的关键字kj(1≤j≤n)，令即kl是所有的先于ki输入并大于kj的值；令即kl是所有的先于ki输入并小于kj的值。则从根到y（y->key=kj）的路径上，结点的关键字集合恰

为Gj∪Lj，且d(kj,T)=|Gj|+|Lj|。}kkthatsuchilallforkkkandji1:k{Gjljilij}kkthatsuchilallforkkkandji1:k{Ljljilij从Fig4.5的实例中可以看到，对于kj=17，Gj={21

，9}，Lj={9。12}，所以kj的深度为4。定理:对于n≥1,插入n个随机元素到初始为空的二叉搜索树,需要的期望比较次数为:)log()(nnOnT证明:由序列a1,a2,…,an创建一棵二叉查找树时,令T(n)为序列元素之间需要的比较次数。T(0)=0，令b1,b2,…,bn为已按

升序排好的序列。如果a1,a2,…,an是随机的，则对于某元素ai,任意j(1≤j≤n),ai等可能地为bj，(ai)bj为最终树的根，则b1,b2,…,bj-1位于bj的左子树(j-1个元素)，bj+1,…,bn位于右子树((n-j)个元素。)aib1,…

,bj-1bj+1,…,bnb1,…,bj-1插入到最终树中，每个都一定与根比较一次，然后就是插入到左子树中(与ai插入到整棵树中过程相同，即递归实现)，对于j-1个结点，共需要j-1+T(j-1)次比较；同理bj+1,…,bn插入到右子树中的比较次数为：n-j+T(n-j)，即

将ai插入最终n个结点的搜索树中且ai为bj(根)的比较次数为上述两部分之和，即n-1+T(j-1)+T(n-j)。由于j等可能地取1,2,…,n中的任意值，所以：njjnTjTnnnT1))()1(1(1)(也即：10)(21)(njjTnnnT由此可

得：T(n)≤cnlogn该定理:建一棵n个结点的二叉搜索树的期望比较次数为O(nlogn)由于插入n个结点的总时间代价为:O(nlogn),因此对于树中的某一个结点而言,找到该结点的总比较次数为T(n)

/n,即为O(logn)平衡二叉树的树高为)(logn)4.4红黑树（Red-BlackTree）4.4.1Red-Black树的性质Red-Black(RB)树是一种二叉搜索树，它的每个结点有五个域：color（取值为red或blac

k）、key、left、right和p（省略了相关数据或指针）。RB树把包含key域的结点作为内部结点，而以NULL（空）作为其“外部结点”，这些外部结点与left、right、p域中的NULL指针值相

对应（见Fig.4.6），空结点与实际的数据元素或关键字都无关。一个在结构上做了上述改变的二叉搜索树称为一个RB树。pkeyleftrightcolorRB树满足下面的性质：1.每个结点的color域必须为red或black

；2.每个叶结点（NULL）的color为black；3.如果一个结点的color为red，则其子结点全为black结点。4.从某一结点到其子树上任意一个叶结点的所有简单路径，包含相同个数的black

结点。（如上图所示）从一个结点x到（其子树中的）任一叶结点的简单路径上的黑结点的个数称为结点x的black高（black-height），表示为bh(x)。定理4.4具有n个内部结点的RB树的树高h≤2log(n+1)。证明：1.首先用归纳法证明以RB树上

任一结点x为根的子树至少包含个内部结点。12)x(bh1°递归基础：对于高度为0的结点x，即x为叶结点（NULL），以其为根的子树有0个内部结点，即至少有个内部结点。命题成立。2°设对于高度为h-1的结点命题成立。3°考察高为h(>

0)的结点x，由于h>0，x是RB树的内部结点，必有两个子结点x1、x2，其高为h-1，且有根据归纳假设，以x1、x2为根的两子树分别至少有个内部结点，∴以x为根的子树至少有(两个子树结点数之和再加1,即)个内部结点。012120)x(bh

blackx,1)x(bhredx,)x(bh)x(bh111blackx,1)x(bhredx,)x(bh)x(bh222121)(xbh121)12()12()x(bh1)x(bh1)x(bh2.证明对于RB树的根r，设其高为h，bh(r)≥h/2。这一点由

性质3，即从根到叶的任一条路上，red结点数不超过一半即可证明。3.由上面两个命题可知：高为h的RB树，其内部结点数n至少为，即。故有，定理得证。定理4.4说明，动态数据集上的基本操作在RB树上的执行代价为O(h)=O(logn)阶。换句话说，用RB树的形

式实现动态数据集，在任何时刻，树高h总能保持在O(logn)阶。12122/h)x(bh2/)1log(21122/2/hnnnhh)1log(2nh查找、求最大、最小、求前

导、后继、插入、删除4.4.2Red-Black树的插入与删除算法在插入或删除结点时，为了使树重新具有Red-Black性质，除了要改变结点间的指针链接关系外，还要对某些结点的着色进行调整。对于结点间指针链接关系的修改归结为旋转（Rot

ation）操作，旋转是调整树的平衡状态的基本手段。Rotation操作对二叉搜索树上的某一局部进行调整，通过交换一对父子结点的父子关系，在保持树结点间的有序关系的条件下（即保持其中序遍历的结果为单调序列），改变该子树的平衡状态

。Rotation操作分为左旋（Left-Rotation）和右旋(Right-Rotation)，如Fig.4.7所示。左旋算法Left_Rotation(root,x)Fig.4.8给出一次左旋转的实例的图示。Right_Rotation(root,x)的算法与Left_Rota

tion(root,x)类似。这个算法主要完成两件事：1°把结点x与其右子结点y的父子关系进行调整，即把x->p—x—y的父子关系改变为x->p—y—x的顺序；2°把y的左子树变为x的右子树。(右旋转)1.把结点x与其左子结点y的父子关

系进行调整即把x->p—x—y的父子关系改变为x->p—y—x的顺序2.把y的右子树变为x的左子树算法不存在与结点数n相关的操作，因此时间代价为O(1)阶。RB树的插入操作：1）调用Tree_Insert(root,x)函数完成二叉搜索树的插入操作2）调用Tree

_Rotation(root.x)函数，并对结点的着色进行调整，使之恢复为一个RB树。插入操作算法RB_Insert(root,x)Fig.4.9给出了一个简单的实例，作为RB_Insert()算法运行的示意图。

从算法RB_Insert()的执行过程可以看出：0°(原RB树中不存在连续两层结点,其颜色均为红(R),若某结点为R,则其父结点一定为B)1°对于空树或插入后x->p为black结点的情形，无需进一步处理；(插入时从最底层插入,所以从插点的x以下均为违规

)2°x->p为red结点时，按x的父结点x->p是其父结点x->p->p的左、右子结点两种情况（对称）处理。若为左，则y指向x->p的右兄弟（否则y指向左兄弟）3°这时y的颜色分为两种情况，如果y->c=R，则按case1处理，即调整x->p、y及其父x->p->p的颜色，

并将x指向x->p->p进行新一轮向上调整。4°如果y->c=B,则若x为x->p的右子，则按case2处理，即以x->p为x进行左旋，同时变为case3,再进行case3处理5°否则（即，x为x->p左子）即为case3,(首先按case1处理，对以x->p->p为根的

子树进行调整，然后向上扩展，分别按case2、case3处理。)case1:(x为红,x->p为红,x->p的兄弟为红)否则(x->p的兄弟为B)case2(x为右孩子),变为case3case3(x为左孩子)RB树的Delete算法与R

B_Insert()算法的思路是一致的，首先按二叉搜索树的删除方法删去需要删除的结点。在删除过程中会出现三种情形，在第二、三种情形中，若被摘除（spliced-out）结点是black结点，这时Red-Black性质4可能被破坏，就需要对RB树进行恢

复，恢复方法与插入操作后的修复类似。xy4.4.3关于Red-Black树的几点讨论1.RB树是一种二叉搜索树，在其上进行的查询操作Search、Minimum、Maximum、Successor、Predecessor等与一般二叉搜索树的查询操作完

全相同，而且算法简明，也即RB树具有一般二叉搜索树的优点。2.如定理4.4所指出的，RB树是平衡树，在其上进行的所有操作的时间代价都是O(logn)阶的，RB树的树高h总是保持在一个很小的范围，即h≤2ln(n-1

)。3.RB树与一般平衡树的平衡机制不同，虽然它不需要计算平衡因子，但Red-Black性质（特别是性质4）保证了整棵树的平衡性，即绝大多数内部结点有两个子结点。事实上，red结点不可能仅有一个black子结点，而只可能为以下两种情形之

一：有两个black（数据）子结点；或左、右子结点均为NULL。black结点的子结点有三种情形：有两个（数据）子结点；左右子结点为NULL；第三种情形只可能出现在树的下层，只有一个数据子结点，这时该子结点必为red，且子结点左右

儿子为空。如Fig.4.10所示。（以上情况均与性质4有关，即任一结点到结点的黑高相同)RB树几乎是一个2-树，不可能出现单链的情形，从而保证了整棵树的平衡性。建RB树例202019插入20,19,18,17,16201918case3201918201

91817case12019181720191817Root->c=B2019171618case3181920222019171818192220其他case14.另一种非二叉的平衡搜索树——2-3-4树，很容易转

变为Red-Black树。4.52-3-4树4.5.12-3-4树及其实例1.2-3-4树有三种不同的结点：2-结点、3-结点和4-结点。2-结点与二叉树的结点相同，除了关键字域key外，有三个指针域p、p1、p2，p指针指向父结点、p1指针为左指

针、p2指针为右指针。另外增加一个结点类型域type，用来区分结点类型。数据域保持数据元素的内容或指向数据元素的指针。3-结点有两个关键字域key1和key2，其中key1<key2，并增加一个指针域p3。当搜索

结点x时，用x->key与key1、key2进行比较，如相等即找到，不相等则根据比较结果的三种情形转入该结点的子树：x->key<key1转向p1；key1<x->key<key2转向p2；x->key>key2转向p3。4-结点与3-结点类似，增加了key3域和p4指针。在2-3-4树种，4-

结点是一种临时结点，在插入和删除过程中可能产生4-结点，但该结点可随时由三个2-结点取代。(key1<key2<key3,根据key与三者的关系分别转向相应子树)(由于4-结点是临时的,所以实为一棵3-序B树,否则为一棵4-

序B树)2.2-3-4树的最主要的特征是其所有的叶结点都在同一深度。如Fig.4.11所示：假定动态数据集的关键字值域为英语字母集合，即从小到大为A,B,C,D,E,...,X,Y,Z。图中的结点I是根，是一个2-结点，其左子树中的关键字值均小于I，右子树中的关键字值均大于I，该树

T中只有2-结点和3-结点。4.5.22-3-4树上的查询操作算法2-3-4树上的搜索算法与二叉搜索树上的搜索算法差别不大，只需要区别2-结点和3-结点。2-3-4树的搜索算法4.5.32-3-4树的构造过程2-3

-4树的插入算法是保证树的基本特征（即所有叶结点在同一深度）的关键。在插入时，2-结点可以变为3-结点，3-结点可以变为4-结点，当出现4-结点时，自动分裂为三个2-结点，并且把中间的2-结点插入到上一层的父结点中。在一般二叉搜索树中，每插入

一个结点是在最下层添加一个叶结点，而2-3-4树是在整体扩大的情况下进行向上扩展。(但开始时也是从最底层的内部结点开始,如下图中(4)插入R)每当树增加一层时，即是把根结点上升一层，于是树中所有结点的深度同时加1。在插入算法中，一旦产

生了4-结点就要进行分裂，这时就会利用到父结点指针p。在4-结点分裂时，存在三种情形：(1)4-结点是2-3-4树的根，这时，中间的2-结点作为新的根，树增加一层；(2)4-结点的父结点是一个2-结点，只需把4-结点中的中间关键字插入到2-

结点，该2-结点变为3-结点；(3)4-结点的父结点是一个3-结点，把4-结点的中间关键字插入到这个3-结点中，该3-结点又变成一个新的4-结点，于是继续向上分裂。假设插入时树高为h，插入过程在最坏情形下是从根到

叶、再从叶到根，至多进行2h次处理，因此插入算法的时间代价仍是O(h)阶的。4.5.42-3-4树的性能分析定理4.5由n个关键字生成的2-3-4树实际上是一个完全的2-3树(3-序B树)，设其高为h，结点数为n，则其结点数n介于同样高度为h的完全二叉树和完全三叉树的结点数之间，即：2h+1-

1≤n≤(3h+1-1)/2(m-序B树有:n≤(mh+1-1)/(m-1))故有n≥2h+1-1即h≤log(n+1)-1或h=θ(logn)，定理得证。由定理4.5可知，2-3-4树上的基本操作的代价在最坏情形下也是O(

logn)阶的。4.5.5有关2-3-4树的几点讨论1.2-3-4树实际上是一种2-3树(即为3-序B树)，4-结点是临时结点，不会占用较多空间，可以分配临时性的工作单元存放4-结点。2.可以采用同一种数据类型来

表示2-结点和3-结点（按3-结点来设计），只在type域用不同的标记来区分结点类型即可。3.为了减少插入算法的代价，还有一种把分裂4-结点的工作分摊到不同的操作中去的方案，即每次生成4-结点时进行一次分裂，如果其父结点又变为4-结点，则

不在这一次插入操作中继续分裂。当进行下次插入或搜索操作时，每遇到一个4-结点就进行一次分裂，这样可以减少一次插入操作的代价。4.与插入算法相比，删除操作Delete算法是一个逆过程。插入操作中，关键字要按规则逐层向上插入，

而删除操作应在删除其关键字后按一定规则逐层向下压，5.2-3-4树获得平衡性的方法很巧妙，但缺点是结点类型较为复杂，可以通过一种简单的变换把2-3-4树转化为二叉搜索树。方法是把2-3-4树中的3-结点（或4-结点）用一个2-结点结构来取代，取代的

方法如Fig.4.13所示。用上述变换将Fig.4.11中的2-3-4树转化为一个二叉搜索树，不难发现，这是一棵RB树。从中也可以看出RB树与2-3-4树的内在联系。4.6Hashing技术4.6.1Hash算法的基本思想与一般模型Has

h方法的基本思想是，首先产生从可能的关键字集合（又称全域）U=[0..N-1]到存储空间（Hash表）地址集合T=[0..m-1]的一个映射函数：h:U[0..m-1]。于是，要存储或检索关键字为x∈U的数据项只需计算函数h(x)，直接得到该数据项应在的地址。Fig.4.15中给出了一个简单的

实例，其中N=100，m=7，h(x)=xmod7。然而对不同的关键字x,y∈U，h(x)=h(y)的情况可能出现，这种情形称为冲突（collision）。由于一般的|U|远远大于m，冲突难以避免，因此Hash技术研究的基本问题是：(1)设计一个好的

Hash函数，计算简单，而又使数据项分布均匀以减少冲突；(2)设计解决冲突的策略和算法。集合为实际存于Hash表中的关键字集合，|S|=n≤N。=n/m称为负载因子（loadfactor）,值是决定哈希算法性能的主要因素。(值小于1,越小

越浪费空间,越接近1性能越下降)Hash算法的“散列”存储方式，使得它不能支持Minimum、Maximum、Successor、Predecessor这类的操作，而对于Search、Insert、Delete操作不但可以支持而且有较高的性能。US

从抽象数据类型（ADT）的观点来说，Hash算法用于实现字典（Dictionary）类型，实际关键字集合S为固定不变时，称为静态字典，只支持Search操作，S为可变时，即动态数据集，称为动态字典，动态字典支持搜索、插入和删除操作。4.6.2Hash函数的设

计Hash函数的设计一般应能兼顾计算简单和分布均匀，在大多数应用问题中，可能的关键字集合U往往远远大于地址空间的规模。例如以姓名字符串作为关键字，|U|=N是一个极大的值，而Hash表的长度m和实际关键字集合S（|S|=n）与N

相比小得多。因此，分布均匀的要求就是要对于使尽量小，|.|集合的势(求集合元素的个数)其中h-1(i)为被h映射至地址i的关键字全体。n|S|,US,)1m0(U:h1m0i21S)i(h

当且仅当时达到最小值，意味着将无任何冲突产生。无冲突的Hash函数称为完备Hash函数（PerfectHashFunction），简称PHF。事实上，无冲突的要求是极难达到的。“生日悖论”指出，在23个人中，有两个人的生日在同一天的概率为0.51，即当|S|=

n=23，m=365时，发生冲突的概率已经在50%以上。而当n=50时，发生冲突的概率已达0.97。在D.Knuth所举的实例中指出，当n=31，m=41时，无冲突的映射函数只占全部可能映射函数的1/107

。因此，在大多数情形下只能追求将冲突尽可能减少。常用的Hash函数设计方法：1.除式法（Divisionmethod）令h(x)取用m除x的余数，即h(x)=xmodm。nS)i(h1m0i21这种Hash函数计算速度最快。在设计时，m取值不要习惯性地取为2的n次幂。因为这会使得h(

x)的取值只依赖于关键字的2进制值的最后几位，这不利于数据在Hash表中的均匀分布。一般情况下m值最好取为不与某个2n值相近的素数。2.乘式法（Multiplicationmethod）可方便地取m=2p，映射函数可表示为：其中a为常数0<a<1，表示取乘积

的分数部分，即。常数a的选取会影响到Hash函数的性能，如何选取a的值与关键字值的特征有关。已有的研究指出取最好。此时，Hash函数表示为：例如，取m=1024，当x=42237时，h(x)=h(42237)=1024×(42237×0.618mod1)=477即关键字x=42237映射

到Hash表T[0...1023]中的位置是T[477]。)1modax(m)x(h1modaxaxaxax618.02/)15(a)1mod618.0x(m)x(h3.位选取法（Hash-bitExtraction）和平方取中法（Mid-square）基本思

想是：把地址空间T的大小m取作m=2p，p为某整数，例如m=216，即T[0..65535]。无论关键字x为数字或字符串，都一定可以转变为一个较长的二进制串，那么h(x)的值就可以取与关键字对应的二进制串中指定的16位所形成的二进制数。经常采用的平方取

中法的基本思想则是，首先计算关键字值的平方x2，在平方值的二进制序列中取中间的若干位，例如：U=[0..999]，x=459，m=210，x2=4592=(210681)10=(110011011100000101)2则h(x)=(1101110000)2=880由于在定义函数h(x)时

，到底选取二进制序列的哪些位带有任意性，映射后的地址可能有较均匀的分布，使得冲突减少。4.6.3解决冲突的策略不同策略之间的主要区别是：(1)冲突项存到何处：一种方法是把它们仍存到Hash表中；另一种方法则是另开辟溢出区（或链区）存放溢出数据。(2)如何从地址h(x)找到冲突项的存储位置：

一种方法是仍用计算的方式一次次地计算冲突项的地址；另一种方法就是用指针形成链表。1.开地址法（Openaddressing）开地址法是一种单区法，不需要额外的存储空间，冲突项放在Hash表T[0..m-1]的其它空位，数据元素存储位置

的确定也通过Hash函数计算。这时Hash函数的自变量除了关键字之外，还有一个查找序号i，最简单的映射方法称作线性查找Hash函数：,i=0,1,2,...。USxmmod)i)x('h()i,x(h例如：设h

‘(x)=(5x)mod8，关键字为6个年代：1055、1492、1776、1812、1918、1945。直接存入Hash表会产生一次冲突：x=1492、x=1812都映射到地址4，如Fig.4.16所示。采用线性开地址方法

，函数h(x,i)把这6个关键字依次插入到表中。每次插入过程中，刚开始时i的取值为0，若T[h(x,0)]为空则进行插入，若T[h(x,0)]已被占用，i值加1，继续检查T[h(x,1)]是否也被占用，如此重复直到完成。Hash表的插入算

法Hash_Insert该实例中，Hash_Insert(T,x)的执行过程为：h(1055,0)=h'(1055)=3存入T[3]；h(1492,0)=4存入T[4]；h(1776,0)=0存入T[

0]；h(1812,0)=4，已占用h(1812,1)=5存入T[5]；h(1918,0)=6存入T[6]；h(1945,0)=5，已占用h(1945,1)=6，已占用h(1945,2)=7存入T[7]。Fig.4.17为执行结果。线性开地址法的搜索算法Hash_Search另一种更一般的开地

址函数称为二次Hashing函数（DoubleHashing），其映射函数表示为：这种Hash函数缓解了由于顺序查找空位造成的Hash表的局部拥挤现象，适当选择h2(x)，可以使查找序列也具有随机性，有利于提高

查找算法的性能。例如：在插入关键字=1613的过程中，当地址h(x,i)已被其它关键字占用时，查找空位的下标序列为：1、9、4、12、7、2、10、5、0、8、3、11、6…，显然折衷方案有利于关键字在Hash表中的均匀分布

。不过在选择h1(x)和h2(x)时必须使上述的查找空位的下标序列遍历整个Hash表。为此可设计映射函数为：其中取m为一素数，m'为略小于m的整数。mmod))x(hi)x(h()i,x(h2113mod))11mod1(13mod(),(xixixh)'mod(1)(,mod)(

21mxxhmxxh再重复1、9、4、12开地址Hashing算法的分析分两种情形：当动态数据集的所有数据的关键字都被映射到同一地址时，最坏情形发生，这时的时间代价显然是O(n)阶的。由于影响问题的因素有：Hash函数的选择、冲突的处理策略、关键

字集合S在全集U中的分布情形和Hash表的大小，计算Hash函数的平均时间代价较难，但最为重要。均匀Hashing（uniformhashing）为了对开地址Hash算法的搜索与插入时间代价进行统一概率分析，首先要假

定它是一种均等状态。即假定：每个关键字有相同的机会被映射到Hash表的不同位置；每个关键字的查找下标序列，应等可能的作为0,1,...,m-1的一个排列。命题4.3在uniformhashing的条件下，对于开地址Hash表的不成功搜索（或插

入）操作所需的期望查找（probes）次数至多为次，其中。命题4.4在uniformhashing的条件下，对于开地址Hash表的成功搜索操作所需的期望查找（probes）次数至多为次，其中。对于Hash表的不成功搜索，指搜索

的关键字x不在表中，因此查找的代价应与插入一个新数据项的代价相同。命题说明：利用Hash技术实现的字典抽象数据类型（ADT），其搜索和插入代价与数据项数n无关，也就是说时间代价是O(1)阶的。这说明了对于大数据集合的组织与检索，Hash技术的效

率优于平衡树。)1/(11m/n1))1/(1ln(11m/n负载因子的值对算法性能有影响，在接近于1时，算法性能明显降低。很小会浪费存储空间，接近于1则算法性能降低，所以应取适当的值。开地址法有增加冲突链长的趋势。例如在Fig4.17的例子中，关键字x=194

5，本应第一次就映射到T[5]，但T[5]却被本应映射到T[4]的关键字1812所占，因此1945不得不放到T[7]的位置，去占用“本不该属于它的位置”。这种“喧宾夺主”的现象扩大了因冲突造成的负面影响。而链接法避免了这种缺陷。2.链接法（Chainedhas

hing）又称闭地址法。它打破了数据项存于Hash表T[0..m-1]之内的限制。实际上它是一个双区法，即冲突项不存于表内。这时的T是一个由m个链表组成的数组，T[i](i=0,1,...,m-1)表示映射到地址i的关键字序列，也可以把T[i]作为这个链表的首项（或头指

针）。在这种情况下，表长m可以小于数据集S的大小n，负载因子n/m实际为平均表长，也就是不成功搜索和插入操作的期望代价。而成功搜索的期望代价，大致为负载因子的一半。除了每个数据项必须增加一个指针域之外，Hash表本身可能包含较

多的冗余信息，m值取得越小，负载因子越大，直接影响搜索的性能。3.单区链接法它是对开地址法的改进。全部数据项置于Hash表中，但搜索中的查找序列不是通过计算而是通过指针链接。例如把关键字序列17、52、9、41、15、13、11按

Hash函数h(x)=xmod7依单区链接法插入。Fig.4.19是插入的结果。这种方法用指针操作代替二次Hashing函数的计算，性能有所提高。但与开地址法一样，单区法因地址的互相占用，使映射到不同地址的

冲突链合并到一起，往往使冲突链长大大增加，使搜索效率降低。4.调谐式（Tuning）链接法其基本思想是把Hash表分为两个区：T:[0..m’-1]为整个存储区，T[0..m-1]为Hash区，T[m..m’-1]为链接区。，，为调谐因子。关键字经Hash函数h(x)映射到Has

h区T[0..m-1]，如若发生冲突，首先把冲突项存于链接区T[m..m‘-1]，避免了冲突链的交叉、加长，仅在链接区装满时再链接到Hash区。这种方法把大部分冲突链置于链接区，吸取了链接法的优点，同时又有一定

的限度，避免了链接区的空间分配难以控制的缺点。Fig.4.20是一个简单实例的示意图。(发生冲突时按单区链接法)调谐式Hash方法的性能与调谐因子和负载因子有关，在值确定时，可以求出一个最优的值。相关的研究指出，当取时，较好，这时的期望搜索代价

为1.79次查找，而在一般情况下，取较好。4.6.4Hash算法的优劣分析Hash方法独特的按内容寻址的检索方式是一种高级的“联想”式存储与检索技术。它的期望时间代价为O(1)阶，与数据集规模无关。不足之处：1.按内容寻址的方式决定了它

是把数据“散列”（scattering）到Hash表中，因此它不适用于涉及数据内容之间关系的查询。例如，求最大、最小元，删除最小元，后继，前导，求关键字key值在某一范围内的一组数据等等。2.Hash算法的最坏情形时间代价为O(n)阶，使其不能在诸如防空系统、空中交通调度系统等“紧

急”系统中采用，因为一旦出现一次最坏情形，会造成重大事故。3.前文对Hash算法的性能分析过程中，所有的分析结果都是在“实际关键字集合S是全域U的一个随机子集”等条件下得到的。如果全集U中的关键字不是等可能性地出现在Hash表中，这种情况在实际问题中是经

常遇到的，例如关键字为程序中的标识符名，有些名称如m、n、m1、m2、m3等等，出现的概率远远多于其它名称，在这种情形下，期望性能可能变差。对此，也有一些方法予以解决，如泛Hash（UniversalHashing）方法。4.命题4.3、4

.4指出Hash算法的性能与负载因子的值密切相关。在数据集不断增加时，负载因子逐渐增大，并接近于1，会使系统性能明显下降。例如或>0.95时，扩大Hash区，即所谓空间倍增（arraydoubling）技术，需要把数据集

中的所有数据按照新的Hash函数重新转存入新的Hash区，这一工作代价很大。为解决空间倍增所需的高代价问题，可采用线性扩张Hash算法。基本思想是指定一对负载因子的上限和下限，在可能关键字集合S的大小n改变的过程中，一旦超过，存储区扩充一个桶（可存放b条数据项），当小于时，存储区缩减

一个桶。这样就保证动态数据集上的操作总是在良好的性能下工作。*4.6.5Hash技术的几种新发展(选讲)完备Hash函数（PerfectHashFunction）(引文1,引文2)(ZbigniewJ.Czech,Anoptimala

lgorithmforgeneratingminimalperfecthashfunctions,InformationProcessingLetters,43(5):257-264,1992)完备哈希函数（

PHF）又称无冲突哈希函数。即PHF的地址映射不产生冲突，一次计算即可找到目标数据项。因此，用PHF实现的检索算法的最好、平均和最坏情形时间复杂度都为O(1)阶。其定义可叙述为：对任一实际关键字集合，函数h：称为S的完备哈希函数（PHF），如果对任意，必有。当m=

n时，h称为集合S的最小完备哈希函数（MPHF）。给定n（n不太大）个关键字集合和Hash表长m，有几种PHF的构造技术：1）针对字符串关键字集合的启发式算法假定集合中的关键字为字符串，设关键字k∈U为一个Σ={a,b,c,…,x,y,z}上的字符串，len

gth(k)为字符串的长，F(k)，L(k)分别为k的首末字符。求形如h(k)=length(k)+Value(F(k))+Value(L(k))的Hash函数。为了使h(k)为完备Hash函数，须对于函数Value：Σ→Z的值进行适当的定义

，即要为Value(a)，Value(b)，…，Value(z)赋予适当的值，使得对于S中的所有关键字，h(k)∈[0…m-1]有不同的值。Sager提出的一种改进方法，是求形如：h(k)=(h0(k)+g(h1(k)+g(h2(k)))modn的最小完备Hash

函数。这种方法首先选定适当的函数h0(k)，h1(k)，h2(k)，然后根据h0，h1，h2来确定函数g。2）Hash索引表法（HIT法）对于关键字集合S和Hash表地址集[0…m-1]，取t个Hash

函数hj：S→[0…m-1](j=1…t)。按一定的算法计算出一个一维数组：array[0…m-1]∈[1…t]，称为HIT表。在h1，h2，…ht和HIT确定的条件下，定义完备Hash函数：h：S→[0…m-1]，使得对于关键字k∈S，h(k)=hj(k)，其中j∈

{1,2,…,t}，满足条件：HIT[hj(k)]=j。ProceduretoConstructHIT:t个hash函数beginKEYSET:={K1K2…Kn};setHIT()=0;//清HITforj=1tosbeginforallelementsinKEYS

ETdoHIT(d):=jifHIT(d)=0andhj(Kr)=d且不存在Kr’hj(Kr’)=d;KEYSET=KEYSET-{Kr|满足上述条件的Kr},endend在构造HIT时，取第一个h1(),由于除k2与k8对应的h1()无重复外，其他取值均有重复。因此HIT表中5

，9元素均为1，即HIT(5)=1,HIT(9)=1；取h2()时（此时，k2,k8可略），首先h2(k1)=5,而HIT(5)已经为1，所以略过，除k4外，其他关键字对应的h2()值有重复，所以只将k4对应的HIT表项HIT(2)

赋值为2，即HIT(2)=2；同理，在取h3()时（此时，k2,k4,k8可略），首先，由于HIT中的5，2，9项均已赋值，所以k3,k5,k7略过，对于k1,k6,将HIT表中相应项赋值，即HIT(4)=3,HIT(7)=3。在已知t

个Hash函数h1，h2，…ht和HIT表的条件下，用这个PHF把关键字k∈S插入到Hash表T[0…m-1]的算法为：voidwriteHIT(keyK){intj=1;while((HIT[hj(k)]!=j)&&(j<=t))j++;if(j<

=t)T[hj(k)]=k;elsecout<<"failure!";}如果h1，h2，…ht和HIT表选择正确，“failure”的情况不会出现。相应的检索算法为：inth(keyk){intj=1;while((HIT[hj(k)]!=j)&&(j

<=t))j++;if(j<=t)returnhj(k);elsereturn(-1);}与第一种方法类似，PHF的构造过程是：首先选择t个Hash函数h1h2…ht，然后，确定HIT表HIT[0…m-1]∈{1,2,…,t}的m个值，使得所定义的函数h为PHF，即对任何x,y∈S，x≠y有

h(x)≠h(y)。这个确定HIT表的过程类似于迷宫问题，八后问题，等组合问题，可以用回溯等搜索算法完成。如果满足条件的HIT表不存在，可以在调整t值和t个Hash函数后重新构造满足条件的HIT表。(t越大，性能越

不好)3）Fredman构造法Fredman通过构造法证明了，对任意的关键字集合至多取m=3n（即），一定可以在形如的Hash函数中找到S的完备哈希函数。构造方法：已知：实际关键字集合，且|U|=N为素数。①对此

S，先构造函数h'(x)=((kx)modN)modn。用枚举法选择k值，使得其中bi=|Si|，(i=0,1,…,n-1)，Si={x|x∈S,h'(x)=i}。Si是被h'映射为i的关键字集合。已经证明，满足条件的k值一定存在。②对此每个Si，(i=0,1,…,n-1)选择适当的ki，构造函

数hi(x)=((kix)modN)modCi。其中Ci=1+bi(bi-1)，使得为单一映射函数（无冲突）。由于这时的集合Si较小，Ci值也不大，因此ki一定存在。③取，定义函数使对于任意x∈Sh(x)=C0+C1+…+Ci-1+((kix)modN)

modCi。其中i=h‘(x)=((kx)modN)modn。----x为第i组原文如下：1.选择合适的k,利用hash函数h‘(x)=((kx)modN)modn将关键字集合分为n块，即S1,S2,…,Sn,使得，其中b

i=|Si|。2.在hash表T中,T[0]存放k值，T[1],T[2],…,T[n]分别存放n块的hash表指针。3.依次为块Si分配(bi)2+2个单元（i=1,2,…,n），其中第1个单元地址即为存放在T[i]中的指针

。4.块Si对应的前两个单元分别存放ki,bi。5.对于块Si中的关键字x,利用hash函数hi(x)=((kix)modN)modCi进行存取（其中Ci=(bi)2）举例:N=31,n=6,S={2,4,5,15,18,30},(K取1比下面取2更好)27101622T(0)T(1)T(2

)T(3)T(4)T(5)T(6)114T(7)T(8)T(9)C2K2152T(10)T(11)T(12)T(13)T(14)T(15)C4K4231830T(16)T(17)T(18)T(19)T(20

)T(21)C5K51115T(22)T(23)T(24)C6K6每一组多用2个单元存放C与K存放每组的指针K2不难证明，函数h(x)是S∈U的一个完备哈希函数。上述构造过程实际上要计算2n+1个值：k，k0，k1，…，kn-1和C0，C1，…，Cn-1。时间代价估计为

O(n·N)，空间代价为5n+C。4）利用中国余数定理构造MPHF中国余数定理指出：对于任意的n个整数R1，R2，…，Rn，和n个互素整数M1，M2，…，Mn，总可以找到一个常数C，使得Ri=CmodMi对i=1…n成立。为了对关键字集

合S={k1,k2,…,kn}构造MPHF，只须把地址空间[0…m-1]=[0…n-1](m=n)的每一地址0，1，2，…，n-1视为中国余数定理中的R1，R2，…，Rn。k1k2…kn与n个素数建立1－1对应关系：P(ki)=Mii=1,2,…,n。于是

构造MPHF的任务归结为找到中国余数定理中的常数C。即令h(ki)=CmodP(ki)i=1,2,…,n。这种方法的难点是当n较大时，C值的计算代价很高，下面是一种实用的构造方法，设关键字ki为字符串型。①对关键字集合S={k1,k2,…,kn}中的每一个ki选其中两个（或三个…）字符ki

1，ki2，使不同关键字ki，kj对应的字符对{ki1,ki2}和{kj1,kj2}也不同。②按每个关键字ki的第一个字符ki1把集合S分为r组，使每组关键字对应的字符对的第一个字符相同，不同组相异。这r个关键字组按字典顺序记为G1,G2,…,Gr。若关键字ki∈Gj，则令为前j-1

组的关键字总和。③把n个关键字对应的n个字符对中的第二个字符k12，k22，…，kn2（它们中可能有相同的字符）按不同字符在其中出现的频率由大到小分别对应于最小的若干素数：2，3，5，7，…。例如，字符‘e’在其中出现频率排在第三位，则令P(‘e’)=5。④对于

关键字组Gj(j=1,2,…,r)，设其对应的字符对中第一字符位u（相同），第二字符位v1，v2，…，vt，则依中国余数定理一定可找到一个常数Cj使1≡CjmodP(v1),2≡CjmodP(v2),…t≡CjmodP(vt)。其中t=|Gj

|（在Gj中对应的字符对中第二字符都是不同的）。⑤令函数C(u)=Cj，h(ki)=d(ki1)+C((ki1)modP(ki2))即为所求之最小完备Hash函数。2.泛哈希（UniversalHashing）技术集合称为Hash函数的泛类。如果H满

足条件：对任意的x,y∈U，x≠y，有这时，把H称为一个C级泛类。换言之，一个C级泛类H，对全域U中任二个不等元x，y，H中使它们发生冲突（即h(x)=h(y)）的Hash函数的个数不大于总数|H|的C/m。C值越小，泛类的性能越好。Carter给出了两个泛类（记为H1和H2）：(1)C

arter指出H1是级的。已经证明，任何泛类的级C的下界是1-m/N。一般m远小于N，因此接近于1。而泛类H1的级C=1，因此它几乎是最优的。(2)其中，hr(x)=xmodPr，gc,d(z)=((cz+d)modP2t)modm，Pr：为从

小到大排列的第r个素数。对于泛哈什算法进行的复杂分析指出：采用C级泛类H时，其期望检索代价应为1+Cα（α=n/m为负载因子）；n次操作（包括查找，插入，删除）序列的期望代价为(1+Cα/2)n。它们与用户所取的关键字集合S的随机性无关。3.可扩展哈希方法（ExtendibleHash

ing）可扩展哈希技术主要针对动态HashFile。可扩展哈希算法采用一种可随HashFile中记录总数（实际关键字集合S的大小）的变化而逐渐变化的动态HashFile，其基本方法是：设HashFile的原始区T由m个数据块（block或bucket）组

成，T[0…m-1]。每个数据块（桶）T[i]可包含b个记录。存储区T可由一端扩展或收缩。存储区的线性扩展由哈希文件的负载因子α值来控制，当新的记录插入，使得α值超过预先确定的某一上界αmax时，存储区扩展一个数据块（桶）。这一扩展，又使动态变化的α值降了下来。若干次插入后，使α值再次

超过αmax，存储区再扩展一个数据块。原始区扩展m次后，容量扩大了一倍，形成了新的原始区，完成了一次Hash文件的倍增。如果继续插入，又开始了新的扩展和倍增。动态Hash文件也有删除操作，为负载因子α

设一下界αmin，缩进与扩展操作相类似。与泛Hashing技术相类似，可扩展Hashing算法也采用一族Hash函数，以适应HashFile动态变化的特点。下面是一种简单的常用形式：①Hash函数族H由Hash函数序列h0，h1，…组成

；②设U={0,1}q，T[0…m-1]中包含m=2p个数据项（p<q），则可令h0:{0,1}q→{0,1}p为一普通函数；③令hi:{0,1}q→{0,1}p+i(i=1,2,…)，且对任意关键字k∈U，hi(k)等可能的取值为hi-1(k)或hi-1(k)+2p+i-1。一个典型的实

用选择是用平方取中法构造h0，h1，h2，…，即对任意的关键字k∈{0,1}q，取hi(k)=k2的二进制位行的中间p+i位构成的二进制数（i=0,1,2…），显然hi(k)∈{0,1}p+i。可扩展Hash算法的原

始取T[0…m-1]由m个数据块组成，每个数据块可存储b条记录。当完成一次Hash区的倍增时，空间扩大一倍，m*=2；。在算法运行过程中，在原始区之外，Hash区已经扩展了l个数据块（0≤l≤m）。这时

，有相继的两个Hash函数hi，hi+1在工作。当一个新的关键字k要进行检索或插入时，系统根据扩展块指针l和当前Hash函数的序号i。计算h(k)的值，即关键字k的映射地址：inth(keyy){if(hi(k)<l)returnhi+1(k);els

ereturnhi(k);}从上面的程序可以看出，在运行的某一时刻，当前Hash函数序列号为i，扩展块指针为l（已扩展了l个block），Hash地址计算由函数hi，hi+1分别完成，前者负责T[l…m-1]区域的计算，而hi+1负责[0…m-1]和[m…m+l-1]两段区域的地址计算。

Hash区域的线性扩展，由负载因子α=n/((m+l)*b)计算，其中n为已插入到Hash文件中的记录数。每插入一条新的记录，n加1，α有所增加，一旦使得α>αmax，Hash区向右扩展一个数据块，即令指针l加1（这时还应把原来由hi映射到数据块

T[l]的记录重新由hi+1映射到T[l]和T[m+l-1]两个block中）。系统继续运行，直到l增加到m，这时完成一次扩展，如果Hash文件继续扩展，应由hi+1，hi+2负责计算，即令序号i加1，同时原始区倍增m=2*m，l=0。对于删除操作，可以类似地设置αmin，在n减少

导致α<αmin时，缩小一个数据块，与扩展类似。第四章完HASH函数的应用(安全方面):1.完整性验证。由HASH函数的抗碰撞性，它相当于文件的指纹.完整性验证是指数据未经授权不能进行改变，即信息在存储或传输过程中

不被修改的特性。它保证收到的数据是授权实体所发的数据，如果文件的HASH值没有变，我们就可以确定消息没有变化。HASH函数这种性质的应用是非常广泛的。病毒检测中的校验和算法就是通过定期的计算文件的HASH值并存储，只要HASH值和上

次计算的结果相比没有变化，就可以肯定文件没有被病毒感染2.数字签名。由于其易于计算的特性，HASH函数可以用于数字签名中。在这种签名协议中，双方必须事先协商好双方都支持的HASH函数和签名算法。因为在数字签名中使用公钥算法

，公钥算法的缺点是运算速度较慢，先对文件算HASH值，再对HASH值进行签名，这样一是可以提高计算速度，另外也可以更安全。3.认证协议。有些协议使用询问应答机制。通信两方分别为A和B，双方共享一个授权口令。通信时，

A发送一个随机串发起询问，B对随机串和共享口令这个整体计算HASH值k，把k作为应答发送给A，A也计算随机串和共享口令的HASH值K1，若k和K1相等，协议就可以进行，这样既可以进行消息来源验证，又保护了双方的共享口令.4.加密算法。HASH函数可以采用不同方式产生

加密算法。一种方式是将HASH函数作为Feistel结构密码算法的F一函数。每轮的输入明文可以用作HASH函数的链变量，密钥可用于数据输入。另一方式是用于产生密钥流生成器.(MD5算法与攻击,---后例)MDx与S

HA算法的结构:王小云文章HowtoBreakMD5andOtherHashFunctions,EUROCRYPT2005,LNCS3494,pp.19–35,2005中序遍历（Inorder_Tree_Walk）算法voidInorder_Tree_Walk(TreeNo

de*x){if(x!=NULL){Inorder_Tree_Walk(x->left);//从左子树返回时输出cout<<x->key;//结点的值,再遍历右子树,Inorder_Tree_Walk(x->right);//所以为称为中序}}返回遍历左子

树遍历右子树输出结点Tree_Search算法TreeNode*Tree_Search(TreeNode*x,intk){if((x==NULL)||(k==x->key))returnx;if(k<x->key)returnTr

ee_Search(x->left,k);elsereturnTree_Search(x->right,k);}//该算法的非递归形式为：TreeNode*Tree_Search(TreeNode*x,intk){while((x!=NULL)&&(k!=x->key)){if(k<x-

>key)x=x->left;elsex=x->right;}returnx;}返回求最小元的算法Tree_Minimum(root)TreeNode*Tree_Minimum(TreeNode*x){whil

e(x->left!=NULL)x=x->left;returnx;}返回求最大元的算法Tree_Maximum(root)TreeNode*Tree_Maximum(TreeNode*x){while(x->right!=NULL)x=x->right;returnx;}返回求后继项的操作算法

Successor(x)TreeNode*Tree_Successor(TreeNode*x){TreeNode*y;if(x->right!=NULL)returnTree_Minimum(x->right);y=x->p;while((y!=NULL)&&(x

==y->right)){x=y;//第一个’右’祖先y即为所求.如果y是y’的左子结点,则y’->ky=y->p;//一定大于y->key,如果y是y’’的右子结点,则}//y’’->key一定小于x->key,所以有上述结论

returny;}返回插入操作算法Tree_InsertvoidTree_Insert(TreeNode*root,TreeNode*z){TreeNode*x,*y;y=NULL;x=root;while(x!=NULL){//未考虑x->

key==Z->key情况,会插入到相等y=x;//结点的右子树中最左后继结点处if(z->key<x->key)x=x->left;elsex=x->right;}z->p=y;if(y==NULL)root

=z;elseif(z->key<y->key)y->left=z;elsey->right=z;}返回删除操作算法Tree_DeletevoidTree_Delete(TreeNode*root,TreeNode*z){if((Z->left==NULL)||(z->right==NUL

L))y=z;//情形1、2,,只有一个或无子结点elsey=Tree_Successor(root,z);//情形3,找到结点的后继if(y->left!=NULL)x=y->left;//x为NULL或左子结点elsex=y->right;//x为NULL或右子

结点if(x!=NULL)x->p=y->p;//子结点指向父结点if(y->p==NULL)root=x;//要删除的结点为rootelseif(y==y->p->left)y->p->left=x;/若y是其父结点的左子结点,左子针

指向xelsey->p->right=x;;/若y是其父结点的右子结点,右子针指向xif(y!=z){/y是z的后继,用y的内容代替z的内容z->key=y->key;//把y的数据内容拷贝到z;}}返回yx左旋算法Left_Rotation(root，x)voidLeft_Rotati

on(TreeNode*root,TreeNode*x){y=x->right;x->right=y->left;//把y的左子树作为x的右子树if(y->left!=NULL)y->left->p=x;y->p=x->p;//把x的父结点作为y的父结点if(x

->p==NULL)root=y;elseif(x==x->p->left)x->p->left=y;elsex->p->right=y;y->left=x;//把x作为y的左儿子x->p=y;}返回插入操作算法RB_Inse

rt(root，x)voidRB_Insert(TreeNode*root,TreeNode*x){Tree_Insert(root,x);x->color=red;//设为红色，可保持所有结点的bh()不变while((x!=root)&&(x->p->color==red)){//因x的c为R

（红），所以若其父结点的c也为R则违规//原树为空树或x->p为black结点时，无需下面的处理if(x->p==x->p->p->left){y=x->p->p->right;//y指向x父结点的右兄弟结点if(y->color==red){x->p->color=b

lack;//case1y->color=black;//case1x->p->p->color=red;//case1x=x->p->p;}返回下一页如果一个结点的c值为R，则其子结点的c全为B（规则3）xx插入操作算法RB_Inser

t(root，x)else{if(x==x->p->right){x=x->p;//case2Left_Rotation(root,x);//case2}x->p->color=black;//case3x-

>p->p->color=red;//case3Right_Rotation(root,x->p->p);//case3}}else{x->p为x->p->p的右子结点，处理类似};}root->color=black;}返回上一页2-3-4树的搜索

算法TreeNode*2_3_4_Tree_Search(TreeNode*x,intk){while((x!=NULL)&&(k!=x->key)){//k为要查找的关键字值if(k<x->key)x=x->p1;elseif(x->type==1)x=x->p2;//如果是2-结点e

lseif(k<x->key2)x=x->p2;//是3-结点,则比较key2elsex=x->p3;returnx;}返回Hash表的插入算法Hash_InsertintHash_Insert(Table*T,intx){inti=0;do{intj=h(x,

i);if(T[j]==NULL）{T[j]=x;returnj;}elsei++;}while(i!=m)cout<<"Hashtableoverflow!\n";return-1;}返回线性开地址法的搜索算法Hash_SearchintHash_Sea

rch(Table*T,intx){inti=0;do{intj=h(x,i);if(T[j]==x)returnj;i++;}while(i!=m)cout<<"Searchfailure!\n";return-1;}返回