算法与数据结构-查找

内查找整个查找过程都在内存中进行。外查找在查找过程中需要访问外存。平均查找长度ASL——查找方法时效的度量为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：

n：记录的个数

pi：查找第i个记录的概率，

(不特别声明时认为等概率pi=1/n)ci：找到第i个记录所需的比较次数约定：无特殊说明，一般默认关键字的类型为整型算法与数据结构-查找全文共65页，当前为第1页。8.2顺序表的查找01n-1nr[0..n]a0a1an-1r[n].key=K[算法描述]intseqsearch(int*a,constintn,constintK)

{inti=0;a[n]=K;while(a[i]!=K)i++;returni;}算法与数据结构-查找全文共65页，当前为第2页。[程序设计技巧]

设置监视哨，提高算法效率。[性能分析]空间：一个辅助空间。时间：

1)查找成功时的平均查找长度设表中各记录查找概率相等

ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功时的平均查找长度ASLf=n+1[算法特点]算法简单，对表结构无任何要求n很大=>查找效率较低改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。算法与数据结构-查找全文共65页，当前为第3页。8.3二分查找满足r[i].keyr[i+1].key,0i<n-1

仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。[折半(二分)查找法]

1234567891011

0513192137566475808892lowmidhigh=(low+high)/2

K=21lhmK=85

lhm111611161537119454101110109算法与数据结构-查找全文共65页，当前为第4页。[算法描述]intbinsearch(intK,intv[],intn){intlow,high,mid;low=1;high=n;while(low<=high){

mid=(low+high)/2;if(K<v[mid])

high=mid-1;elseif(K>v[mid])

low=mid+1;else/*找到了匹配的值*/returnmid;}return-1;/*没有查到*/}算法与数据结构-查找全文共65页，当前为第5页。[性能分析]

h=log2n+1{同完全二叉树，二叉树性质4}成功查找时的平均查找长度（等概率）：

ASLs=

例：ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找时的查找长度：h-1或h次-13-46-79-101-22-34-55-67-88-910-1111-639147102581112h判定树（描述查找过程的二叉树）外结点内结点><=算法与数据结构-查找全文共65页，当前为第6页。1.具有12个关键字的有序表，在等概率情况下，折半查找的平均查找长度（）

A.3.1B.4C.2.5D.5

2.折半查找的时间复杂度为（）A.O（n2）B.O（n）C.O（nlogn）D.O（logn）3.用二分（对半）查找表的元素的速度比用顺序法()A.必然快B.必然慢C.相等D.不能确定4.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键字比较次数为____.

在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__________。ADD46,9,11,12算法与数据结构-查找全文共65页，当前为第7页。8.4静态树表的查找[问题出发点]

讨论有序表中各记录查找概率不等时，查找成功时的ASLs。

12345

关键字1519364267

查找概率0.10.20.10.40.2

折半查找高概率为根

+折半

ASLs=2.3ASLs=1.8363151192424675424192675151363算法与数据结构-查找全文共65页，当前为第8页。[静态最优查找树]定义：查找性能最佳的判定树。性质：带权内路径长度之和PH为最小值。

PH=与ASLs成正比

其中n：二叉树上结点的个数(有序表长度)hi：第i个结点在二叉树上的层次数

wi=cpi：c为某个常量；

pi：第i个结点的查找概率最优查找体现的原则：

1）最先访问的结点应是访问概率最大的结点；

2）每次访问应使结点两边尚未访问的结点的被访概率之和尽可能相等。算法与数据结构-查找全文共65页，当前为第9页。[次优查找树的构造方法]PH值近似为最小比静态最优查找树易于构造，时间开销少已知按关键字有(升)序的记录序列：

(rl,rl+1,...,ri-1,ri,ri+1,...,rh-1,rh)1)选取记录ri作为根结点：计算所有pi(lih)

找出最小pi的对应的i；若相邻关键字的权值大，则确定为权值大的关键字对应的i算法与数据结构-查找全文共65页，当前为第10页。简化计算pi的方法：设定累计权值和swi=

则

pi=|(swh-swi)-(swi-1-swl-1)|=|(swh+swl-1)-swi-swi-1|

设sw-1=02)ri的左子树：(rl,rl+1,...,ri-1)构造的次优查找树3)ri的右子树：(ri+1,...,rh-1,rh)构造的次优查找树算法与数据结构-查找全文共65页，当前为第11页。设有一组数据black,blue,green,purple,red,white,yellow，它们的查找概率分别为0.10,0.08,0.12,0.05,0.20,0.25,0.20。试以它们的查找概率为权值，构造一棵次优查找树，并计算其查找成功的平均查找长度。关键字blackbluegreenpurpleredwhiteyellow

权值0.100.080.120.050.200.250.20j1234567SWj0.10.180.300.350.550.801.00△Pj0.90.720.520.350.100.350.80

（根）↑i△Pj0.250.070.130.300.200.25

↑i

↑i△Pj0.050.12

↑i

算法与数据结构-查找全文共65页，当前为第12页。8.5分块查找[索引表的构造]

索引表index[0..b-1]

最大关键字值224286

起始地址048

主表r[0..n-1]（分块有序/有序）

key12221382833384286765063

其它项

01234567891011[分块查找步骤]1)折半或者顺序查找索引表，确定所在块2)在已确定的块中顺序查找/折半查找算法与数据结构-查找全文共65页，当前为第13页。设b为索引表长度，s为块中记录个数顺序查找索引表+顺序查找被确定的块

ASLbs=

当s取时，ASLbs取最小值折半查找索引表+顺序查找被确定的块

ASLbs=[log2(b+1)-1]+(s+1)/2log2(n/s+1)+s/2实用中，各块大小不一定相等分块查找效率介于顺序查找和折半查找之间算法与数据结构-查找全文共65页，当前为第14页。1.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。(1)45(2)45(3)46

算法与数据结构-查找全文共65页，当前为第15页。8.6二叉排序树BST(二叉查找/搜索树)[定义]

二叉排序树或者是空树，或者是满足如下性质的二叉树：

1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；

2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；

3)其左右子树本身又各是一棵二叉排序树[性质]

中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列452453122890判别给定二叉树是否为二叉排序树的算法如何实现？？（用二叉链表存储）算法与数据结构-查找全文共65页，当前为第16页。方法1：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论。void

JudgeBST(BTreet,intflag){//全局指针pre，初值为NULL；调用时变量flag=TRUE

if(t!=NULL&&flag){JudgeBST(t->lc,flag)；//中序遍历左子树

if(pre==NULL)pre=t；//中序的第一个结点不判断

else

if(pre->data<t->data)pre=t；//前驱指针指向当前结点

elseflag=FLASE；//不是完全二叉树

JudgeBST(t->rc,flag)；//中序遍历右子树

}}算法与数据结构-查找全文共65页，当前为第17页。方法2：照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。boolJudgeBST(BTreet){

if(t==NULL)returnTRUE；

if(JudgeBST(t->lc)&&JudgeBST(t->rc)){m=max(t->llink)；

n=min(t->rlink)；//左子树中最大值和右子树中最小值

return(t->data>m&&t->data<n)；

}

else

returnFALSE；//不是}intmax(BTreep)//求左子树的最大值

{if(p==NULL)return-maxint；

//返回机器最小整数

else{

while(p->rc！=null)p=p->rc；

returnp->data；}}intmin(BTreep)//求右子最小值

{if(p==NULL)returnmaxint；

else{while(p->lc!=NULL)p=p->lc；

returnp->data；}}算法与数据结构-查找全文共65页，当前为第18页。[在二叉排序树上的操作][1.查找][例]K=28K=32bst45241228bst455390241228325390

查找步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。算法与数据结构-查找全文共65页，当前为第19页。BitreeSearchBST(BiTreeT,KeyTypekey)//在二叉分类树查找关键字之值为key的结点，找到返回该结//点的地址，否则返回空。T为根结点的指针。{

if((T==NULL)||(key==T->data))

return(T);

elseif(key<T->data.key)

return(SearchBST(T->lc,key));

elsereturn(SearchBST(T->rc,key));}[查找算法]算法与数据结构-查找全文共65页，当前为第20页。[2.插入]首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。[3.生成][算法步骤]反复执行以下操作a.读入一个记录，设其关键字为K；b.调用查找算法，确定插入位置；c.调用插入算法，实施插入结点的操作；算法与数据结构-查找全文共65页，当前为第21页。例：将序列122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099算法与数据结构-查找全文共65页，当前为第22页。[4.删除]依据被删除结点p的不同情况分析：1.p是叶子结点：修改其双亲指针即可2.p只有左孩子：用p的左子树代替以p为根的子树p只有右孩子：用p的右子树代替以p为根的子树3.p有两个孩子：找到p的中序后继(或前趋)结点q，q的数据复制给p，删除只有右子(或左子)/无孩子的q算法与数据结构-查找全文共65页，当前为第23页。例：(1)(2)(2)(3)5320901050869541241528891304539878992算法与数据结构-查找全文共65页，当前为第24页。voidDelete(BSTreeT,keytypeX)//在二叉排序树T上，删除为X的结点。

{BSTreef,p=T;while(p&&p->key!=X)//查找值为X的结点

if(p->key>X){f=p;p=p->lc;}//f为p的双亲

else{f=p;p=p->rc;}if(p==NULL){printf(“无关键字为X的结点\n”);exit(0);}if(p->lc==NULL)//被删结点无左子树

if(f->lc==p)f->lc=p->rc;//将被删结点的右子树接到其双亲上

elsef->rc=p->rc;else{//被删结点有左子树

q=p;s=p->lc;

while(s->rc!=NULL){//查左子树中最右下的结点（中序最后结点）

q=s;s=s->rc;}p->key=s->key;//结点值用其左子树最右下的结点的值代替

if(q==p)p->lc=s->lc;//被删结点左子树的根结点无右子女

elseq->rc=s->lc;//s是被删结点左子树中序序列最后一个结点

free(s);}}算法与数据结构-查找全文共65页，当前为第25页。[4.性能分析]给定树的形态，等概率查找成功时的ASL=ci/n最差(单支树)：(n+1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：1+4log2n关键字有序出现时，构造出“退化”的二叉排序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树算法与数据结构-查找全文共65页，当前为第26页。8.7平衡二叉树(AVL树)[1.定义]平衡二叉树或者是空树，或者是满足如下性质的二叉排序树：

1)它的左、右子树的高度之差的绝对值不超过1；

2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子：该结点的左子树高度减去右子树的高度。平衡二叉树非平衡二叉树302010252235383020353233001-10-1100-12-2平衡二叉树：每个结点的平衡因子都为＋1、－1、0的二叉排序树。算法与数据结构-查找全文共65页，当前为第27页。[2.结点的存储结构]lcbfkeyotherinforclc：左孩子指针

rc：右孩子指针

bf：平衡因子

key：记录的关键字

otherinfo：记录的其它数据成分算法与数据结构-查找全文共65页，当前为第28页。[4.在平衡二叉树上的操作][查找]查找方法同二叉排序树。[插入]插入新结点之后仍应保持平衡二叉树的性质不变。[例]平衡二叉树的生成过程15001525-1-2-1000000-1-1001-2-20000-11525353525152515359015253590651525653590算法与数据结构-查找全文共65页，当前为第29页。[调整范围的确定]

插入结点后，找到离插入结点最近且平衡因子绝对值超过1的祖先结点（危机节点），则以该危机节点为根的子树将是可能不平衡的最小子树，可将重新平衡的范围局限于这棵子树。[调整的类型]LL型-表示新插入结点在危机结点的左子的左子树上LR型-表示新插入结点在危机结点的左子的右子树上RL型-表示新插入结点在危机结点的右子的左子树上RR型-表示新插入结点在危机结点的右子的右子树上算法与数据结构-查找全文共65页，当前为第30页。[调整的方法]LL型平衡旋转——一次顺时针旋转AB+1h-10+2+1hh-1h-1LL型调整BLBRARBA0h0h-1h-1BLBRAR危机结点调整前：高度为h+1

中序序列：ABBLBRAR调整后：高度为h+1

中序序列：ABBLBR注意：调整后平衡因子为0ABAR算法与数据结构-查找全文共65页，当前为第31页。LR型平衡旋转——一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR型调整BLAR危机结点CBCCLCRh-2h-2h-10+1CB0h-1BLARACRh-2CLh-1-10ABBLARCCLCR调整后：高度为h+1

中序序列：ABBLARCCLCRA调整前：高度为h+1

中序序列：h-1情形A注意：调整后平衡因子为+1,0,0算法与数据结构-查找全文共65页，当前为第32页。LR型平衡旋转——一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR型调整BLAR危机结点调整前：高度为h+1

中序序列：注意：改组后平衡度为+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2+10ABBLARCCRCL调整后：高度为h+1

中序序列：AABBLARCCRCL情形B算法与数据结构-查找全文共65页，当前为第33页。注意：调整后平衡因子为0,0,0LR型平衡旋转——一次逆时针旋转+一次顺时针旋转AB+10+2-1LR型调整危机结点调整前：高度为2中序序列：CBC0ABCA新插入结点ABC调整后：高度为2中序序列：ca0b00情形C算法与数据结构-查找全文共65页，当前为第34页。RR型平衡旋转——一次逆时针旋转AB-1h-10-2-1hh-1h-1RR型调整BLBRALBA0h0h-1h-1BLAL危机结点调整前：高度为h+1

中序序列：BAALBLBR调整后：高度为h+1

中序序列：注意：调整后平衡因子为0ABBRBAALBLBR算法与数据结构-查找全文共65页，当前为第35页。RL型平衡旋转——一次顺时针旋转+一次逆时针旋转AALCRCLBRALCRCLBRALCLBRCRBCABCACB-100h-1h-2h-1h-211(-1)00(1)-1(0)危机结点算法与数据结构-查找全文共65页，当前为第36页。[删除]（思路同插入）将删除结点q转化为q最多有一个孩子的情形，即若q有两个孩子，则以其中序前驱/后继结点r取代它，删除r；若树的平衡性被破坏，利用单一/双重旋转恢复。[性能]定理：一个具有n个结点的平衡二叉树形，其高度h为

log2(n+1)h1.4404log2(n+2)-0.328

结论：最坏情况下，AVL树的高度约为1.44log2n，而完全平衡的二叉树高度约为log2n，因此AVL树是接近最优的，其平均查找长度与log2n同数量级。算法与数据结构-查找全文共65页，当前为第37页。8.7B+树与B-树[采用B+与B-树的意义]大量数据存放在外存中，由于是海量数据，不可能一次调入内存。因此，要多次访问外存，速度慢。所以，主要矛盾变为减少访外次数。内存算法与数据结构-查找全文共65页，当前为第38页。用用二叉树组织文件，需访问外存次数太多。如：当文件的记录个数为100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！502510751535609020304055708095索引文件数据文件文件头，可常驻内存文件访问示意图：索引文件存在内存、数据文件存在盘上算法与数据结构-查找全文共65页，当前为第39页。[B-树]B-树是一种平衡的多路查找树。应用于文件系统。1.定义一棵m阶B-树，或为空树，或为满足下列特性的m叉树：

1、树中每个结点最多有

m

棵子树；

2、若根结点不是叶子结点，则最少有两棵子树；

3、除根之外的所有非终端结点最少有m/2

棵子树；

4、所有非终端结点包含（n,A0,K1,A1,K2,…,Kn,An）信息数据；其中n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。

5、所有叶子结点在同一层上，且不带信息。算法与数据结构-查找全文共65页，当前为第40页。例如：m=4阶B_树。除根结点和叶子结点之外，每个结点的儿子个数至少为m/2=2个；结点的关键字个数至少为1。该B_树的深度为4。叶子结点都在第4层上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第1层第2层第3层(L层)第4层(L＋1层)m/2~m棵子树叶算法与数据结构-查找全文共65页，当前为第41页。2.B-树结点结构(n,A0,K1,A1,K2,A2,...,Kn,An)n:关键字的个数A0：<K1

的结点的地址（指在该B_树中）K1：关键字A2：>K1

且<K2

的结点的地址（指在该B_树中）其余类推………An：>Kn

的结点的地址（指在该B_树中）K1<=K2<=…...<=Kn算法与数据结构-查找全文共65页，当前为第42页。127阶B-树中每个结点最多有____个关键字；除根结点外所有非终端结点至少有____棵子树；65阶B+树中除根结点外所有结点至少有____个关键字；最多有____棵子树。高度为5（除叶子层之外）的三阶B-树至少有____个结点。31126643365思考：高度为h的m阶B-树（除叶子层）至少有多少个结点？算法与数据结构-查找全文共65页，当前为第43页。3.B-树查找过程类似于二叉树的查找。如查找关键字为KEY的记录。

从根开始查找，如果Ki=KEY则查找成功。若Ki<KEY<Ki+1;查找Ai

指向的结点若KEY<K1;查找A0

指向的结点若KEY>Kn;查找An指向的结点若找到叶子，则查找失败。算法与数据结构-查找全文共65页，当前为第44页。设关键字的总数为N，求m阶B_树的最大层次L。层次 结点数 关键字的个数（最少）

1 1 12 2 2(m/2-1)3 2(m/2) 2(m/2)(m/2-1) 4 2(m/2)2 2(m/2)2(m/2-1)………L 2(m/2)L-22(m/2)L-2(m/2-1)L+1 2(m/2)L-1

所以，N=2(m/2)L-1-1故：L＝logm/2((N+1)/2)+1设N＝1000，000且m＝256，则L<=3；最多3次访问外存可找到所有的记录。算法与数据结构-查找全文共65页，当前为第45页。4.B-树插入过程1、确定插入位置，将结点插入到第L层（注意：第L+1层为叶子结点）2、找到插入位置，将关键字和其它信息按序插入。3、若被插入结点的关键字个数>m-1,则该结点满。必须分裂成两个结点。否则不满结束。如结点原为：

(m-1,A0,K1,A1,K2,A2,…Km-1,Am-1)插入一个关键字之后变为：(m,A0,K1,A1,K2,A2,…Km,Am)该结点以Km/2为界，进行分裂：

………...(Km/2,p’)…………...(m/2-1,A0,(K1,A1)…(Km/2-1,Am/2-1)(m-m/2,Am/2,Km/2+1…Km,Am)生成新结点p’,将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。(Km/2,p’

)数据项插入上层结点之中PP’算法与数据结构-查找全文共65页，当前为第46页。例：3阶B_树的插入key=73，127243024，3045，7053902610039506185345，70539026100395061851230324457053902610039506185127303245390261003950618512745707插入算法与数据结构-查找全文共65页，当前为第47页。5.B-树删除过程1、查找具有给定键值的关键字Ki

2、如果在第L层，可直接删除（注意：第L+1层为叶子结点），转4。3、否则，则首先生成“替身”。用该关键字的右边子树中的最左面的结点的关键字取代。然后，删除第L层上的该关键字。4、从第L层开始进行删除。

A、不动：若删除关键字值的那个结点的关键字的个数仍处于m/2-1和m-1之间。则结束。

B、借：若删除关键字值的那个结点的关键字的个数原为m/2-1。而它们左\右兄弟结点的关键字个数>m/2-1;则借一关键字过来，结束。

C、并：若该结点的左\右兄弟结点的关键字的个数为m/2-1;则执行合并结点的操作。如结点原为：（………….(Ki,Ai),(Ki+1,Ai+1),………….）

（A0’,(K1’,A1’)………）

（A0’’,(K1’’,A1’’)………）

……K1………第L层：找到了被删结点的替身。算法与数据结构-查找全文共65页，当前为第48页。例如：3阶B_树的删除操作。324455390371005061，70被删关键字324456190371005370借：向被删结点方向旋转假定再删除该关键字32445903710061，703，24459010061，703，24459010061，70并并并并：和父结点的一个关键字、及兄弟合并。有可能进行到根，使B_树的深度降低一层！假定再删除该关键字算法与数据结构-查找全文共65页，当前为第49页。[B+树]B+树是一种B-树的变形树。应用于索引顺序文件系统。1.m阶B+

树与B-

树的不同之处1)有n棵子树的结点中有n个关键字；2)非叶结点可以看成是索引部分索引集Ai

：第i个子结点的指针Ki

：第i个子结点的最大（或最小）关键字3)所有叶子结点中包含了全部关键字的信息及指向这些关键字记录的指针，且叶子结点以关键字大小自小至大顺序链接；数据集算法与数据结构-查找全文共65页，当前为第50页。[结点结构]非叶结点(A1,K1,...,Ai,Ki,...,An,Kn)索引集Ai

：第i个子结点的指针Ki

：第i个子结点的最大（或最小）关键字叶结点全部关键字及指向关键字记录的指针数据集2153344047586727985390961052851323336785210513221141324阶B+树rootsqt算法与数据结构-查找全文共65页，当前为第51页。2.B+树上的基本运算1)查找方式1：从根结点开始，利用索引集结构，向下查找直到叶子结点方式2：从最小关键字开始，沿叶结点数据集的链结构顺序查找2)插入

仅在叶子结点上进行，关键字个数大于m则分裂3)删除也仅在叶子结点上进行，关键字个数小于m/2时，需进行合并算法与数据结构-查找全文共65页，当前为第52页。8.8哈希表[哈希表的基本思想]

在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，理想状态不经过比较，一次存取就能得到所查元素。[术语]

哈希表一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。

哈希函数记录的存储位置与它的关键字之间存在的一种对应关系。Loc(ri)=H(keyi)

冲突对于keyikeyj，ij，出现的H(keyi)=H(keyj)的现象。算法与数据结构-查找全文共65页，当前为第53页。

同义词在同一地址出现冲突的各关键字。

哈希(散列)地址根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。

装填因子表中填入的记录数n和哈希表表长m之比。

=n/m[设计哈希表的过程]1)明确哈希表的地址空间范围。即确定哈希函数的值域。

2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。

3)设定处理冲突的方法。哈希表bb+(m-1)L算法与数据结构-查找全文共65页，当前为第54页。[哈希函数的基本构造方法]构造原则：算法简单，运算量小；均匀分布，减少冲突。[1.直接定址法]H(key)=a*key+ba、b为常数e.g:令：a、b为1，有两个关键字k1,k2值为10、1000；选10、1000作为存放地址。特点：计算简单，冲突最少。[2.数字分析法/基数转换法]取关键字在某种进制下的若干数位作为哈希地址。e.g:key=236076基数为10，看成是13进制的。则：(236075)13=841547；选取4154作为散列地址(假设表长m=10000)。算法与数据结构-查找全文共65页，当前为第55页。[3.平方取中法]取关键字平方后的中间几位作为哈希地址。e.g:(4731)2=22382361；选取82（假设m=100）。[4.随机数法]

H(key)=random(key)特点：较适于关键字长度不等时的情况。[5.折叠法]

将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址。e.g:key=381，412，975选取768或570作为散列地址（假设m=1000）。38141297517689752143811570＋＋算法与数据结构-查找全文共65页，当前为第56页。[6.除留余数法]H(key)=keyMODp(pm)m:哈希表的表长；p:最好为素数最常用，余数总在0～p-1之间。通常p选<m的最大质数如：m=1024,则p=1019。e.g:选取p为质数的理由：设key值都为奇数，选p为偶数；则H(key)=keyMODp，结果为奇数， 一半单元被浪费掉。设key值都为5的倍数，选p为95；则H(key)=keyMODp，结果为：0、5、10、15、……90奇数。4/5的单元被浪费掉。算法与数据结构-查找全文共65页，当前为第57页。[处理冲突的常用方法][1.开放定址法(空缺编址法)]Hi=(H(key)+di)MODm

0H(key)m-1i=1,2,...,k(km-1)m:哈希表的表长；di:增量序列1)线性探测再散列

di=1,2,...,m-1缺陷：有聚集(堆积)现象—非同义词地址冲突。算法与数据结构-查