Data Structure(C++) Slides-ENG 数据结构课件Chapter-7-Search-English

2020

DataStructuresChapter7

SearchBasicConceptsofSearch7.1DataStructuresChapter7SearchBasicConceptsofSearchKey:canidentifyadataitemofarecord.KeyValue:thevalueofakey.PrimaryKey:akeythatcanuniquelyidentifyarecord.SecondaryKey:akeythatcannotuniquelyidentifyarecord50FemaleLiShuang000525FemaleQiMei000447FemaleLiuNan000325MaleZhangLiang000238MaleWangGang0001AgeGenderNameEmployeeID1972Year9Month2003Year7Month1979Year9Month2003Year7Month1990Year4MonthStartWork7.1Search:findrecordssatisfyingagivenconditioninasetofrecordsofthesametype.Searchresult:Ifarecordmatchingthegivenvalueisfoundinthesearchset,thesearchsucceeds;otherwise,thesearchfails.7.1BasicConceptsofSearchDataStructuresChapter7Search50FemaleLiShuang000525FemaleQiMei000447FemaleLiuNan000325MaleZhangLiang000238MaleWangGang0001AgeGenderNameEmployeeID1972Year9Month2003Year7Month1979Year9Month2003Year7Month1990Year4MonthStartWorkBasicConceptsofSearchStaticsearch:searchthatdoesnotinvolveinsertionordeletion.Staticsearchissuitablewhen:onceasearchsetiscreated,onlysearchoperationsareperformedonit,withnoinsertionordeletion;orafteraperiodofsearching,insertionanddeletionmodificationsareperformedinbatches;Dynamicsearch:searchinvolvinginsertionanddeletionoperations.Dynamicsearchissuitablewhen:search,insertion,anddeletionoccurinthesamestage;forexample,whenasearchsucceeds,thefoundrecordisdeleted;whenasearchfails,thetargetrecordisinserted.7.1BasicConceptsofSearchDataStructuresChapter7SearchSearchStructure:thedatastructuretargetedbysearchoperations,thatis,thedatastructureonwhichthesearchisbased.Searchstructuresdiscussedinthischapter:Linearlist:suitableforstaticsearch,mainlyusingsequentialsearchandbinarysearchTreetable:suitablefordynamicsearch,mainlyusingbinarysearchtreetechniquesHashTable:suitableforbothstaticanddynamicsearch,mainlyusinghashingtechniquesSearchStructureSearchMethod7.1BasicConceptsofSearchDataStructuresChapter7SearchPerformanceofSearchAlgorithmsThetimeperformanceofasearchalgorithmismeasuredbythenumberofkeycomparisons.⑴problemsize⑵thepositionofthekeytobesearchedinthesearchset;Thetimecomplexityofasearchalgorithmisafunctionofproblemsizenandthepositionkofthekeyinthesearchset,denotedT(n,k).Whatfactorsaffectthenumberofkeycomparisons?7.1BasicConceptsofSearchDataStructuresChapter7SearchPerformanceMeasurementofSearchAlgorithmsAverageSearchLength:Themathematicalexpectationofthenumberofkeycomparisonsperformedbyasearchalgorithmisdefinedastheaveragesearchlength.Theformulais:where:n:problemsize,numberofrecordsinthesearchset;

pi:probabilityofsearchingforthei-threcord;

ci:numberofkeycomparisonsrequiredtofindthei-threcord.cidependsonthealgorithm;piisindependentofthealgorithm,dependsonthespecificapplication.Ifpiisknown,theaveragesearchlengthisonlyafunctionoftheproblemsize.7.1BasicConceptsofSearchDataStructuresChapter7SearchASLå==niiicp17.1ThirdClassParticipationStudyB-treesindependentlyandexplain:B-treesandtheB-treeinsertionalgorithmB-treesandtheB-treedeletionalgorithmRequirements:Time:nextWednesday,pleasevolunteerorrecommendtwostudentsaspresenters7.2ChapterExperimentChapterExperimentBasicrequirement:Refertothebinarysearchalgorithm,asearchalgorithmbasedonthegolden-sectionpointEnhancements(optional):BinarySearchTreeBalancedBinaryTreeHashTableLinearListSearch7.2SearchTechniquesforLinearLists01SequentialSearchBinarySearch027.2SequentialSearchBasicidea:comparekeyswiththegivenvalueonebyonefromoneendofthelinearlisttotheother,ifequal,thesearchsucceeds,returnthepositionoftherecordinthetable;ifnokeyequaltothegivenvalueisfoundafterscanningthewholetable,thenfailedsearch,returnfailureinformationExample:Searchk=357.2intSeqSearch1(intr[],intn,intk)//arrayr[1]~r[n]storesthesearchset{i=n;while(i>0&&r[i]!=k)i--;returni;}

101524612354098550123456789iiii7.2Improvedsequentialsearch:seta"sentinel".thesentinelisthevaluetobesearched,placeitattheendofthesearchdirection,eliminatingtheneedtocheckwhetherthesearchpositionisoutofboundsaftereachcomparison,therebyimprovingsearchspeedExample:Searchk=25SearchdirectionintSeqSearch2(intr[],intn,intk)//arrayr[1]~r[n]storesthesearchset{r[0]=k;i=n;while(r[i]!=k)i--;returni;}ASL=å=iicp1i=å+-=niiinp1)1(=(n+1)/2=O(n)101524612354098550123456789iii25iiiiiiiSequentialSearch7.2Disadvantagesofsequentialsearch:theaveragesearchlengthislarge,especiallywhenthesearchsethasmanyelements,searchefficiencyislow.Advantagesofsequentialsearch:thealgorithmissimpleandwidelyapplicable.thereisnorequirementonthestorageofrecordsinthetable,bothsequentialstorageandlinkedstoragecanbeused;thereisnorequirementonwhethertherecordsareordered,recordsmaybeorderedbykeyornot.

WhensearchsucceedsWhensearchfailsTimecomplexityT(n)=O(n)15151515SequentialSearchBinarySearch7.2Conditions:recordsinthelinearlistmustbeorderedbykey;sequentialstoragemustbeused.Basicidea:Inanorderedtable,takethemiddlerecordasthecomparisonobject,ifthegivenvalueequalsthekeyofthemiddlerecord,thensuccessfulsearch;ifthegivenvalueislessthanthekeyofthemiddlerecord,continuesearchinginthelefthalf;ifthegivenvalueisgreaterthanthekeyofthemiddlerecord,continuesearchingintherighthalf.repeatthisprocess,untilthesearchsucceeds,orthesearchareahasnorecordsandthesearchfails.

[r1………rmid-1]rmid[rmid+1………rn]

ifk<rmidifk>rmidsearchthelefthalf

searchtherighthalfk（mid=(1+n)/2）7.2RecursivealgorithmintBinSearch1(intr[],intlow,inthigh,intk){//arrayr[1]~r[n]storesthesearchset

if(low>high)return0;else{mid=(low+high)/2;//mid=low+(high-low)/2if(k<r[mid])returnBinSearch1(r,,,k);elseif(k>r[mid])returnBinSearch1(r,,,k);elsereturnmid;}}BinarySearch7.2Example:processofsearchingforthevalue14:0123456789101112137141821232931353842464952low=1mid=7high=6mid=3high=2mid=131>1418>147<14low=2mid=214=14BinarySearch7.2Example:processofsearchingforthevalue22:0123456789101112137141821232931353842464952low=1mid=7high=6mid=3high=4mid=531>2218<2223>22low=4mid=421<22low=5low>highBinarySearch7.2BinarySearch----Non-recursivealgorithmintBinSearch2(intr[],intn,intk){//arrayr[1]~r[n]storesthesearchset

low=1;high=n;while(low<=high){mid=(low+high)/2;if(k<r[mid])high=mid-1;elseif(k>r[mid])low=mid+1;elsereturnmid;}return0;}BinarySearch7.2BinarySearchDecisionTreeDecisiontree:Thebinarysearchprocesscanbedescribedbyabinarytree,eachnodeinthetreecorrespondstoonerecordintheorderedtable,thenodevalueisthepositionofthatrecordinthetable.Thisbinarytreedescribingbinarysearchisusuallycalledabinarysearchdecisiontree,ordecisiontree.ConstructionmethodWhenn=0,thebinarysearchdecisiontreeisempty;Whenn>0,therootofthedecisiontreeistherecordwithindexmid=(n+1)/2intheorderedtable,theleftsubtreecorrespondstor[1]~r[mid-1],therightsubtreecorrespondstor[mid+1]~r[n].BinarySearch7.2InternalnodeExternalnodeConstructionofadecisiontree,assumingrecords1-11areordered－13－49－101－22－310－1111－8－97－86－74－55－63691011784512BinarySearch7.2PerformanceanalysisofbinarysearchThedepthofabinarysearchdecisiontreewithnnodesissuccessfulsearch:theprocessofsearchingforanyrecordinthetable,isthepathfromtheroottothatrecordnodeinthedecisiontree,thenumberofcomparisonswiththegivenvalueequalsthelevelofthatrecordnode.Failedsearch:afailedsearchfollowsapathfromtheroottoanexternalnode,thenumberofkeycomparisonswiththegivenvalueequalsthenumberofinternalnodesonthepath.-13-49-101-22-310-1111-8-97-86-74-55-6InternalnodeExternalnode3691011784512ëû1log2+nBinarySearchSearchTechniquesforTreeTables7.3SearchTechniquesforTreeTables7.3.1BinarySearchTreeBalancedBinaryTree7.3.2252525257.3BinarySortTree(BinarySearchTree):iseitheranemptybinarytree,orabinarytreewiththefollowingproperties:(1)ifitsleftsubtreeisnotempty,allnodevaluesintheleftsubtreearelessthantherootvalue(2)ifitsrightsubtreeisnotempty,allnodevaluesintherightsubtreearegreaterthantherootvalue(3)itsleftandrightsubtreesarealsobinarysearchtreesBinarySearchTree6588504055274880727.36390554258104567957063605582581045678370Non-binarySearchTree7.3PropertiesofBinarySearchTrees63905542581045678370sequenceorderedbykeyWhereistheminimumvalueinthebinarytree?？Whereisthemaximumvalueinthebinarytree?？Whatisobtainedbyinordertraversal?？bottom-rightbottom-leftBinarySearchTree7.3StorageStructureofBinarySearchTreesstoredasabinarylinkedlist;classdeclarationisasfollows:BinarySearchTreeclassBiSortTree{public:BiSortTree(inta[],intn);~BiSortTree();voidInsertBST(BiNode<int>*bt,BiNode<int>*s);voidDeleteBST(BiNode<int>*p,BiNode<int>*f);BiNode<int>*SearchBST(BiNode<int>*bt,intk);private:

BiNode<int>*root;};7.3InsertioninaBinarySearchTreevoidInsertBST(BiNode<int>*bt,BiNode<int>*s);Analysis:ifthebinarysearchtreeisempty,thenewlyinsertednodebecomesthenewroot;otherwise,thenewlyinsertednodemustbeanewleafnode,itsinsertionpositionisdeterminedbythesearchprocessExample:insertanodewithvalue98635590705898BinarySearchTree98∧∧sbt5563bt∧9058∧∧70∧∧∧voidBiSortTree::InsertBST(…..){if(bt==NULL)bt=s;elseif(s->data<bt->data)InsertBST(bt->lchild,s);elseInsertBST(bt->rchild,s);}7.3ConstructionofaBinarySearchTreeStartwithanemptybinarysearchtree,insertnodesonebyone.Example:Thekeysetis{63，90，70，55，58}，Theconstructionprocessofthebinarysearchtreeis:6355905870BinarySearchTreeBiSortTree::BiSortTree(intr[],intn){for(i=0;i<n;i++){s=newBiNode<int>;s->data=r[i];s->lchild=s->rchild=NULL;InsertBST(root,s);}}7.3Anunorderedsequencecanbeconvertedintoanorderedsequencebyconstructingabinarysearchtree;Eachnewlyinsertednodeisanewleafnodeinthebinarysearchtree;Afterfindingtheinsertionposition,noothernodesneedtobemoved;onlyapointerneedstobemodified;Thesearchprocessintheleft/rightsubtreeisthesameassearchingintheentiretree;Thenewnodedoesnotdestroytherelationshipsamongexistingnodes.DeletionofBinarySearchTreeAfterdeletinganodefromabinarysearchtree,itspropertiesmuststillbemaintained.Discussthreecases:thedeletednodeisaleaf;thedeletednodehasonlyaleftsubtreeoronlyarightsubtree;thedeletednodehasbothleftandrightsubtrees.BinarySearchTree7.3Case1--thedeletednodeisaleafnode50302080908588403532503020809085403532f->rchild=nullptr;fpBinarySearchTree7.3Case2--thedeletednodehasonlyaleftsubtreeoronlyarightsubtree50302080908588403532operation:setthecorrespondingpointerfieldoftheparentnodetotheleftsubtree(orrightsubtree)ofthedeletednode.503020908588403532fpprf->rchild=pr;BinarySearchTree7.3Case3--thedeletednodehasbothleftandrightsubtrees5030208090858840353230204035328090858840BinarySearchTree7.3Case3--thedeletednodehasbothleftandrightsubtrees50302080908588403532operation:replaceitwithitspredecessor(themaximumvalueintheleftsubtree),thendeletethatpredecessornode.302035328090858840psp->data=s-data;f->rchild=sl;fslBinarySearchTree7.3Case3--thedeletednodehasbothleftandrightsubtrees50302080908588403532Cantheminimumvalueintherightsubtreereplacethedeletednode?809085883020403532BinarySearchTree7.3DeletionAlgorithmforaBinarySearchTree-Pseudocode1.Ifnodepisaleaf,deletenodepdirectly;2.Ifnodephasonlyaleftsubtree,reconnectp'sleftsubtree;Ifnodephasonlyarightsubtree,reconnectp'srightsubtree;3.Ifbothleftandrightsubtreesofnodeparenonempty,then3.1findtheleftmostlowernodesinp‘srightsubtreeanditsparentpar;(minimumvalueintherightsubtree)3.2replacethedatafieldofdeletednodepwithnodes'sdatafield;3.3deletenodesfromthebinarysearchtree;(shasonlyarightsubtreeorisaleafnode)BinarySearchTree7.3ProcessofSearchingforaGivenValuekinaBinarySearchTree:⑴Ifrootisanemptytree,thesearchfails;⑵Ifk=root->data,thesearchsucceeds;otherwise⑶Ifk<root->data,searchinroot'sleftsubtree;otherwise⑷searchinroot'srightsubtree.Thisprocesscontinuesuntilkisfoundandthesearchsucceedsorthesubtreetobesearchedisemptyandthesearchfails.BinarySearchTreeTheefficiencyofbinarysearchtreesearchliesinsearchingonlyoneofthetwosubtrees.7.3Example:Processofsearchingforkeyvalues35and95inabinarysearchtree5030208090858840353250302080908588403532successfulsearchfailedsearchBinarySearchTree7.31Whatisthemainoperationofabinarysearchtree?？

5Whatdeterminesthedepth/heightofabinarysearchtree?Answer:theinitialsequenceusedtoconstructthebinarysearchtree3Givensearchset{40,30,20,10},constructabinarysearchtree403020104Givensearchset{30,40,10,20},constructabinarysearchtree40301020Answer:thedepth/heightofthebinarytree2Whatdeterminesthesearchefficiencyofabinarysearchtree?？Answer:Search.Bothinsertionanddeletionmustfirstusesearchtolocatethenode.ClassExerciseBinarySearchTreeBalancedBinaryTree7.3SearchPerformanceAnalysisofBinarySearchTrees12345312541.Fromsequence{1,2,3,4,5}obtainabinarysearchtree:ASL=(1+2+3+4+5)/5=32.Fromsequence{3,1,2,5,4}obtainabinarysearchtree:ASL=(1+2+3+2+3)/5=2.23.Thesearchperformanceofabinarysearchtreedependsonitsshape,rangingbetweenO(log2n)andO(n).4.Forabinarysearchtreewithnnodes,theminimumdepthisthedepthofacompletebinarytreeToimprovethesearchefficiencyofabinarysearchtree,weneedtomaintainabinarysearchtreeofminimumdepth,Howcanwecreateabinarysearchtreewithassmalladepthaspossible?7.3BalancedBinaryTree:iseitheranemptybinarysearchtree,orabinarysearchtreewiththefollowingproperties:⑴thedepthsoftheleftandrightsubtreesoftherootdifferbyatmost1;⑵theleftandrightsubtreesoftherootarealsobalancedbinarytrees.Balancefactor:anode'sbalancefactoristhedepthofitsleftsubtreeminusthedepthofitsrightsubtree,thatis:HL-HR548254821BalancedtreeUnbalancedtreeInabalancedtree,anode'sbalancefactorcanbe1,0,or-1BalancedBinaryTree7.3minimumunbalancedsubtree:duringconstructionofabalancedbinarytree,thesubtreerootedatthenearestnodetotheinsertednodewhoseabsolutebalancefactorisgreaterthan1.542814ConstructionofaBalancedBinaryTreeDuringconstructionofabinarysearchtree,eachtimeanodeisinserted,firstcheckwhethertheinsertionhasdestroyedthetree'sbalance,ifso,thenfindtheminimumunbalancedsubtree,whilepreservingthebinarysearchtreeproperty,adjustthelinksamongnodesintheminimumunbalancedsubtree,performthecorrespondingrotation,soitbecomesanewbalancedsubtreeBalancedBinaryTree7.3Example:Givensequence{20，35，40，15，30，25},

constructabalancedtree203540352040153025BalancedBinaryTree7.3352040153025202515354030354030202515BalancedBinaryTreeExample:Givensequence{20，35，40，15，30，25},

constructabalancedtree7.3BalancedBinaryTreeLetnodeAbetherootoftheminimumunbalancedsubtree,Balancingthissubtreecanbesummarizedintothefollowingfourcases:1.LLtype2.RRtype3.LRtype4.RLtypeBalancedBinaryTree7.3BalancedBinaryTree--LLTypeBeforeinsertionAfterinsertion,beforeadjustmentAfteradjustmentRotation:leverprinciple;Collision:rotationtakespriorityBalancedBinaryTreehBRh+1BLhAR00BAXh2BLhBRh1ARABXA1BLhBRh0ARhB7.3Example:LLtype61→2108791291012876BalancedBinaryTree7.3BalancedBinaryTree--RRTypeBalancedBinaryTreeA-1BLhBRh0ALhBXA-2BLhBRh0ALhBBLhBALh0BRh+1AX0BeforeinsertionAfterinsertion,beforeadjustmentAfteradjustment7.3BalancedBinaryTree--LRTypeAfterinsertion,beforeadjustmentfirstrotatecounterclockwiseleverprincipleBalancedBinaryTreeA2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh7.3Example:LRtype911871012987101112987101112BalancedBinaryTree7.3BalancedBinaryTree--LRType118101181081011BalancedBinaryTree7.3BalancedBinaryTree--RLTypeAfterinsertion,beforeadjustmentfirstrotateclockwisethenapplytheleverprincipleBalancedBinaryTreeXACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X0017.3Classexercise:

Givenkeysequence{5,4,2,8,6,9},constructabalancedtree542LLtype42586BalancedBinaryTree7.3Constructabalancedtree{5,4,2,8,6,9}8642562854RRtypeRotateoncePleasecompletethecorrectversionyourselvesProblematic！！！minimumunbalancedsubtreeBalancedBinaryTree7.3Example:constructabalancedtree{20,35,40,15,30,25,38}203540RRtype352040153025BalancedBinaryTree7.3Example:constructabalancedtree{20,35,40,15,30,25,38}LRtypeI203540153025LRtypeII35403020152530201525354038BalancedBinaryTree7.3Example:constructabalancedtree{20,35,40,15,30,25,38}354038RLtype30201525403835354038RLtypeAverageSearchLength？BalancedBinaryTreeASLå==niiicp1HashTable7.4HashTable7.4Whattaskdoessearchingessentiallycomplete?ValuektobesearcheddeterminethepositionofkinthestoragestructureCommonalityofthesearchtechniqueslearnedpreviously？SequentialSearch,BinarySearch,BinarySearchTreeSearchandothersearchtechniquesalluseaseriesofcomparisonsbetweenthegivenvalueandkeys,searchefficiencydependsonthenumberofcomparisonsbetweenthegivenvalueandkeysduringthesearch.Canwedeterminethestoragepositiondirectlyfromthekeywithoutcomparison?establishadeterministiccorrespondencebetweenstoragepositionandkey7.4Basicideaofhashing:establishadeterministiccorrespondencebetweenarecord'sstorageaddressanditskey.inthisway,thedesiredelementcanbeobtainedinonereadwithoutcomparison.KeySetkiriH(ki)............HHashTable7.4HashTable:recordsarestoredinacontiguousstoragespaceusinghashing,thiscontiguousspaceiscalledahashtable.HashFunction:afunctionthatmapskeystoappropriatestoragepositionsinthehashtable.HashAddress:thestoragepositionobtainedfromthehashfunction.KeySetkiriH(ki)............HHashTableArrayHashFunctionHashAddressIndexHashTable7.4OverviewHashingisbothasearchtechniqueandastoragetechnique.Hashinglocatesarecordonlythroughitskey,anddoesnotfullyexpresslogicalrelationshipsamongrecords,therefore,hashingismainlyasearch-orientedstoragestructure.Hashingisbestsuitedtoansweringthequestion:whichrecord,ifany,hasakeyequaltothevaluebeingsearchedfor.Hashingisgenerallynotsuitablewhenmultiplerecordsmayhavethesamekey.Hashingisalsounsuitableforrangesearch,suchasfindingrecordswithmaximum/minimumkeysorallrecordsinarangeHashTable7.4Keyissuesinhashing:⑴designofthehashfunction.howtodesignasimpleanduniformhashfunctionwithhighstorageutilization.⑵conflicthandling.howtouseanappropriatemethodtoresolvecollisions.Collision:fortwodifferentki≠kj，hasH(ki)＝H(kj),meaningtwodifferentrecordsneedtobestoredinthesamelocation,kiandkjarecalledsynonymswithrespecttoH.HashTable7.4HashFunction----directaddressingmethodsuitablewhenkeysareknowninadvance,andthekeysetisnotlargeandrelativelycontinuous. thehashfunctionisalinearfunctionofthekey,thatis:H(key)=a

key+b(a,bareconstants) Example:KeySet{10,30,50,70,80,90},HashFunctionasfollows,thenH(key)=key,thehashtableis:

H(key)=key/10,thehashtableis:HashTable7.4HashFunction----divisionremaindermethodHashfunctionis:H(key)=keymodpHowtochooseanappropriateptoproducefewersynonyms？HashAddress56494235282114KeyGenerally,choosepasaprimenumberoracompositenumberwithoutprimefactorslessthan20.Example:p=21HashTable7.4HashFunction----divisionremaindermethod

Example:givenasetofkeys(26，36，41，38，44，15，68，11，06，53),constructahashtableusingthedivision-remaindermethodH(key)=keymodp,n=10,takep=HashAddress68154438413626Key530611HashTable7.4HashFunction----digitanalysismethodtakepartofthekeytocomputetheaddress,accordingtothedistributionofdigitsineachpositionofthekey,selectseveralpositionswithrelativelyuniformdistributiontoformthehashaddress.Example:Keyasfollows,usedigitanalysistodesignthehashfunctionthekeyisan8-digitdecimalnumber,Applicablerequirement:thefrequencyofdigitsateachpositionofallkeyscanbeestimatedinadvance,differentkeysetsrequirereanalysis.thehashaddressusestwodecimaldigitsHashTable81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧7.4HashFunction----mid-squaremethodaftersquaringthekey,accordingtothehashtablesize,takeseveralmiddledigitsasthehashaddress(truncateaftersquaring).Example:ifthehashaddresshas2digits,thehashaddressofkey1234is:

(1234)2＝1522756

Scopeofapplication:thekeydistributionisunknowninadvanceandthenumberofkeydigitsisnotlargeHashTable7.4HashFunction----foldingmethodsplitthekeyfromlefttorightintoseveralpartswithequallength,addthesepartstogetherandtakethelastfewdigitsasthehashaddress.Example:Supposethekeyis25346358705,thehashaddresshasthreedigits.253463587+05───1308

shiftfolding253364587+50───1254

boundaryfoldingApplicablecondition:thekeyhasmanydigitsandthekeydistributionisunknowninadvance.shiftfolding:alignthelastdigitofeachpartandaddboundaryfolding:foldalongthedividinglineandaddwiththelastdigitsalignedHashTable7.4Designingahashfunctiongenerallyfollowstheseprinciples:⑴simplecomputation.thehashfunctionshouldnotrequireheavycomputation,otherwisesearchefficiencydecreases.⑵functionvalues,i.e.,hashaddresses,shouldbeuniformlydistributed.functionvaluesshouldbeasevenlydistributedaspossibleintheaddressspace,sostoragespaceiseffectivelyusedandcollisionsarereduced.HashTable7.4CollisionResolution--OpenAddressingoncethehashaddressobtainedfromthekeycausesacollision,findthenextemptyhashaddressandstoretherecordthere.ahashtableusingopenaddressingiscalledaclosedhashtable.MethodsforfindinganemptyhashaddresslinearprobingquadraticprobingrandomprobingHashTable7.4linearprobingWhenacollisionoccurs,startingfromthenextpositionafterthecollisionposition,lookforanemptyhashaddressinsequence.Forkeyvaluekey,letH(key)=dandtheclosedhashtablelengthbem,thenwhenacollisionoccurs,theformulaforfindingthenexthashaddressis:Hi=(H(key)＋di)%m

（di=1，2，…，m-1）HashTable7.4linearprobingExample:Thekeysetis{47,7,29,11,16,92,22,8,3},thehashtablelengthis11,HashfunctionH(key)=keymod11,uselinearprobingtoresolvecollisions,thehashtableis:47729111692292222883333Clustering:aphenomenonincollisionresolutionwherenon-synonymscompeteforthesamehashaddress.HashTable7.4linearprobingSearchalgorithm--pseudocode1.computehashaddressj;2.ifht[j]=k,thesearchsucceedsandreturnstheindex