算法与数据结构查找详解演示文稿

算法与数据结构查找详解演示文稿当前1页，总共65页。（优选）算法与数据结构查找当前2页，总共65页。内查找整个查找过程都在内存中进行。外查找在查找过程中需要访问外存。平均查找长度ASL——查找方法时效的度量为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。查找成功时的ASL计算方法：n：记录的个数pi：查找第i个记录的概率，(不特别声明时认为等概率pi=1/n)ci：找到第i个记录所需的比较次数约定：无特殊说明，一般默认关键字的类型为整型BUPTBUPTSCST当前3页，总共65页。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;}BUPTBUPTSCST当前4页，总共65页。[程序设计技巧]设置监视哨，提高算法效率。[性能分析]空间：一个辅助空间。时间：1)查找成功时的平均查找长度设表中各记录查找概率相等ASLs(n)=(1+2+...+n)/n=(n+1)/22)查找不成功时的平均查找长度ASLf=n+1[算法特点]算法简单，对表结构无任何要求n很大=>查找效率较低改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。BUPTBUPTSCST当前5页，总共65页。8.3二分查找满足r[i].keyr[i+1].key,0i<n-1仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。[折半(二分)查找法]

1234567891011

0513192137566475808892lowmidhigh=(low+high)/2

K=21lhmK=85

lhm111611161537119454101110109BUPTBUPTSCST当前6页，总共65页。[算法描述]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;/*没有查到*/}BUPTBUPTSCST当前7页，总共65页。[性能分析]

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判定树（描述查找过程的二叉树）外结点内结点><=BUPTBUPTSCST当前8页，总共65页。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,12BUPTBUPTSCST当前9页，总共65页。8.4静态树表的查找[问题出发点]讨论有序表中各记录查找概率不等时，查找成功时的ASLs。

12345关键字1519364267查找概率0.10.20.10.40.2

折半查找高概率为根+折半ASLs=2.3ASLs=1.8363151192424675424192675151363BUPTBUPTSCST当前10页，总共65页。[静态最优查找树]定义：查找性能最佳的判定树。性质：带权内路径长度之和PH为最小值。PH=与ASLs成正比

其中n：二叉树上结点的个数(有序表长度)hi：第i个结点在二叉树上的层次数wi=cpi：c为某个常量；pi：第i个结点的查找概率最优查找体现的原则：1）最先访问的结点应是访问概率最大的结点；2）每次访问应使结点两边尚未访问的结点的被访概率之和尽可能相等。BUPTBUPTSCST当前11页，总共65页。[次优查找树的构造方法]PH值近似为最小比静态最优查找树易于构造，时间开销少已知按关键字有(升)序的记录序列：

(rl,rl+1,...,ri-1,ri,ri+1,...,rh-1,rh)1)选取记录ri作为根结点：计算所有pi(lih)找出最小pi的对应的i；若相邻关键字的权值大，则确定为权值大的关键字对应的iBUPTBUPTSCST当前12页，总共65页。简化计算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)构造的次优查找树BUPTBUPTSCST当前13页，总共65页。设有一组数据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

BUPTBUPTSCST当前14页，总共65页。8.5分块查找[索引表的构造]

索引表index[0..b-1]最大关键字值224286起始地址048

主表r[0..n-1]（分块有序/有序）key12221382833384286765063其它项01234567891011[分块查找步骤]1)折半或者顺序查找索引表，确定所在块2)在已确定的块中顺序查找/折半查找BUPTBUPTSCST当前15页，总共65页。设b为索引表长度，s为块中记录个数顺序查找索引表+顺序查找被确定的块ASLbs=当s取时，ASLbs取最小值折半查找索引表+顺序查找被确定的块ASLbs=[log2(b+1)-1]+(s+1)/2log2(n/s+1)+s/2实用中，各块大小不一定相等分块查找效率介于顺序查找和折半查找之间BUPTBUPTSCST当前16页，总共65页。1.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。(1)45(2)45(3)46

BUPTBUPTSCST当前17页，总共65页。8.6二叉排序树BST(二叉查找/搜索树)[定义]二叉排序树或者是空树，或者是满足如下性质的二叉树：1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；3)其左右子树本身又各是一棵二叉排序树[性质]中序遍历一棵二叉排序树，将得到一个以关键字递增排列的有序序列452453122890判别给定二叉树是否为二叉排序树的算法如何实现？？（用二叉链表存储）BUPTBUPTSCST当前18页，总共65页。方法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)；//中序遍历右子树}}BUPTBUPTSCST当前19页，总共65页。方法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；}}BUPTBUPTSCST当前20页，总共65页。[在二叉排序树上的操作][1.查找][例]K=28K=32bst45241228bst455390241228325390

查找步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。BUPTBUPTSCST当前21页，总共65页。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));}[查找算法]BUPTBUPTSCST当前22页，总共65页。[2.插入]首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。[3.生成][算法步骤]反复执行以下操作a.读入一个记录，设其关键字为K；b.调用查找算法，确定插入位置；c.调用插入算法，实施插入结点的操作；BUPTBUPTSCST当前23页，总共65页。例：将序列122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。12212299122250991222501109912225030011099BUPTBUPTSCST当前24页，总共65页。[4.删除]依据被删除结点p的不同情况分析：1.p是叶子结点：修改其双亲指针即可2.p只有左孩子：用p的左子树代替以p为根的子树p只有右孩子：用p的右子树代替以p为根的子树3.p有两个孩子：找到p的中序后继(或前趋)结点q，q的数据复制给p，删除只有右子(或左子)/无孩子的qBUPTBUPTSCST当前25页，总共65页。例：(1)(2)(2)(3)5320901050869541241528891304539878992BUPTBUPTSCST当前26页，总共65页。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);}}BUPTBUPTSCST当前27页，总共65页。[4.性能分析]给定树的形态，等概率查找成功时的ASL=ci/n最差(单支树)：(n+1)/2最好(类似折半查找的判定树)：log2(n+1)-1随机：1+4log2n关键字有序出现时，构造出“退化”的二叉排序树，树深为n，各种操作代价O(n)。避免方法：采用平衡二叉树BUPTBUPTSCST当前28页，总共65页。8.7平衡二叉树(AVL树)[1.定义]平衡二叉树或者是空树，或者是满足如下性质的二叉排序树：1)它的左、右子树的高度之差的绝对值不超过1；2)其左右子树本身又各是一棵平衡二叉树。二叉树上结点的平衡因子：该结点的左子树高度减去右子树的高度。平衡二叉树非平衡二叉树302010252235383020353233001-10-1100-12-2平衡二叉树：每个结点的平衡因子都为＋1、－1、0的二叉排序树。BUPTBUPTSCST当前29页，总共65页。[2.结点的存储结构]lcbfkeyotherinforclc：左孩子指针

rc：右孩子指针

bf：平衡因子

key：记录的关键字

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

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

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

中序序列：ABBLBR注意：调整后平衡因子为0ABARBUPTBUPTSCST当前33页，总共65页。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,0BUPTBUPTSCST当前34页，总共65页。LR型平衡旋转——一次逆时针旋转+一次顺时针旋转AB+1h-10+2-1h-1LR型调整BLAR危机结点调整前：高度为h+1

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

中序序列：AABBLARCCRCL情形BBUPTBUPTSCST当前35页，总共65页。注意：调整后平衡因子为0,0,0LR型平衡旋转——一次逆时针旋转+一次顺时针旋转AB+10+2-1LR型调整危机结点调整前：高度为2中序序列：CBC0ABCA新插入结点ABC调整后：高度为2中序序列：ca0b00情形CBUPTBUPTSCST当前36页，总共65页。RR型平衡旋转——一次逆时针旋转AB-1h-10-2-1hh-1h-1RR型调整BLBRALBA0h0h-1h-1BLAL危机结点调整前：高度为h+1

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

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

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

1、树中每个结点最多有

m

棵子树；

2、若根结点不是叶子结点，则最少有两棵子树；3、除根之外的所有非终端结点最少有m/2棵子树；

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

5、所有叶子结点在同一层上，且不带信息。BUPTBUPTSCST当前42页，总共65页。例如：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棵子树叶BUPTBUPTSCST当前43页，总共65页。2.B-树结点结构(n,A0,K1,A1,K2,A2,...,Kn,An)n:关键字的个数A0：<K1的结点的地址（指在该B_树中）K1：关键字A2：>K1且<K2的结点的地址（指在该B_树中）其余类推………An：>Kn的结点的地址（指在该B_树中）K1<=K2<=…...<=KnBUPTBUPTSCST当前44页，总共65页。127阶B-树中每个结点最多有____个关键字；除根结点外所有非终端结点至少有____棵子树；65阶B+树中除根结点外所有结点至少有____个关键字；最多有____棵子树。高度为5（除叶子层之外）的三阶B-树至少有____个结点。31126643365思考：高度为h的m阶B-树（除叶子层）至少有多少个结点？BUPTBUPTSCST当前45页，总共65页。3.B-树查找过程类似于二叉树的查找。如查找关键字为KEY的记录。

从根开始查找，如果Ki=KEY则查找成功。若Ki<KEY<Ki+1;查找Ai指向的结点若KEY<K1;查找A0指向的结点若KEY>Kn;查找An指向的结点若找到叶子，则查找失败。BUPTBUPTSCST当前46页，总共65页。设关键字的总数为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次访问外存可找到所有的记录。BUPTBUPTSCST当前47页，总共65页。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’BUPTBUPTSCST当前48页，总共65页。例：3阶B_树的插入key=73，127243024，3045，7053902610039506185345，70539026100395061851230324457053902610039506185127303245390261003950618512745707插入BUPTBUPTSCST当前49页，总共65页。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层：找到了被删结点的替身。BUPTBUPTSCST当前50页，总共65页。例如：3阶B_树的删除操作。324455390371005061，70被删关键字324456190371005370借：向被删结点方向旋转假定再删除该关键字32445903710061，703，24459010061，703，24459010061，70并并并并：和父结点的一个关键字、及兄弟合并。有可能进行到根，使B_树的深度降低一层！假定再删除该关键字BUPTBUPTSCST当前51页，总共65页。[B+树]B+树是一种B-树的变形树。应用于索引顺序文件系统。1.m阶B+树与B-树的不同之处1)有n棵子树的结点中有n个关键字；2)非叶结点可以看成是索引部分索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字3)所有叶子结点中包含了全部关键字的信息及指向这些关键字记录的指针，且叶子结点以关键字大小自小至大顺序链接；数据集BUPTBUPTSCST当前52页，总共65页。[结点结构]非叶结点(A1,K1,...,Ai,Ki,...,An,Kn)索引集Ai：第i个子结点的指针Ki：第i个子结点的最大（或最小）关键字叶结点全部关键字及指向关键字记录的指针数据集2153344047586727985390961052851323336785210513221141324阶B+树rootsqtBUPTBUPTSCST当前53页，总共65页。2.B+树上的基本运算1)查找方式1：从根结点开始，利用索引集结构，向下查找直到叶子结点方式2：从最小关键字开始，沿叶结点数据集的链结构顺序查找2)插入

仅在叶子结点上进行，关键字个数大于m则分裂3)删除也仅在叶子结点上进行，关键字个数小于m/2时，需进行合并BUPTBUPTSCST当前54页，总共65页。8.8哈希表[哈希表的基本思想]

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

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

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

冲突对于keyikeyj，ij，出现的H(keyi)=H(keyj)的现象。BUPTBUPTSCST当前55页，总共65页。

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

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

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

=n/m[设计哈希表的过程]1)明确哈希表的地址空间范围。即确定哈希函数的值域。2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。3)设定处理冲突的方法。哈希表bb+(m-1)LBUPTBUPTSCST当前56页，总共65页。[哈希函数的基本构造方法]构造原则：算法简单，运算量小；均匀分布，减少冲突。[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)。BUPTBUPTSCST当前57页，总共65页。[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＋＋BUPTBUPTSCST当前58页，总共65页。[6.除留余数法]H(key)=keyMODp