数据结构、算法与应用 第7章

1Chapter7SkipListsandHashing数据结构算法与应用东校区实验中心[e-mail]信息科学与技术学院黄方军2Bird’s-EyeView•SkipLists•Hasing数据结构算法与应用37.1Dictionaries数据结构算法与应用•Collectionofpairs.–(key,element)–Pairshavedifferentkeys.•Operations.–Search(k,x)–Insert(x)–Delete(k,x)4Application•Collectionofstudentrecordsinthisclass.–(key,element)=(studentname,linearlistofassignmentandexamscores)–Allkeysaredistinct.•GettheelementwhosekeyisJohnAdams.•UpdatetheelementwhosekeyisDianaRoss.–Insert()implementedasupdatewhenthereisalreadyapairwiththegivenkey.–Delete()followedbyinsert().5DictionaryWithDuplicates•Keysarenotrequiredtobedistinct.•Worddictionary.–Pairsareoftheform(word,meaning).–Mayhavetwoormoreentriesforthesameword.•(bolt,athreadedpin)•(bolt,acrashofthunder)•(bolt,toshootforthsuddenly)•(bolt,agulp)•(bolt,astandardrollofcloth)•etc.6•L=(e0,e1,e2,e3,…,en-1)•Eacheiisapair(key,element).•5-pairdictionaryD=(a,b,c,d,e).–a=(aKey,aElement),b=(bKey,bElement),etc.7.2LinearListRepresentation数据结构算法与应用7ArrayRepresentationabcde•search(k,x)–O(size)time•insert(x)–O(size)timetoverifyduplicate,O(1)toaddatrightend.•delete(k,x)–O(size)time.8SortedArrayABCDE•elementsareinascendingorderofkey.•search(k,x)–O(logsize)time•insert(x)–O(logsize)timetoverifyduplicate,O(size)toadd.•delete(k,x)–O(size)time.9UnsortedChain•search(k,x)–O(size)time•insert(x)–O(size)timetoverifyduplicate,O(1)toaddatleftend.•delete(k,x)–O(size)time.abcdenullfirstNode10SortedChain•ElementsareinascendingorderofKey.•search(k,x)–O(size)time•insert(x)–O(size)timetoverifyduplicate,O(1)toputatproperplace.ABCDEnullfirstNode11SortedChain•ElementsareinascendingorderofKey.ABCDEnullfirstNode•delete(k,x)–O(size)time.12SortedChaintemplateclassE,classKclassSortedChain{public:SortedChain(){first=0;}~SortedChain();boolIsEmpty()const{returnfirst==0;}intLength()const;boolSearch(constK&k,E&e)const;SortedChainE,K&Delete(constK&k,E&e);SortedChainE,K&Insert(constE&e);SortedChainE,K&DistinctInsert(constE&e);voidOutput(ostream&out)const;private:SortedChainNodeE,K*first;//pointertofirstnode};13SortedChaintemplateclassE,classKclassSortedChainNode{friendSortedChainE,K;private:Edata;SortedChainNodeE,K*link;};14SortedChaintemplateclassE,classKboolSortedChainE,K::Search(constK&k,E&e)const{SortedChainNodeE,K*p=first;//searchformatchwithkwhile(p&&p-datak)p=p-link;//verifymatchif(p&&p-data==k)//yes,foundmatch{e=p-data;returntrue;}returnfalse;//nomatch}157.3SkipListRepresentation数据结构算法与应用•Worst-casetimeforsearch,insert,anddeleteisO(size).•ExpectedtimeisO(logsize).•We’llskipskiplists.16•Worst-casetimeforsearch,insert,anddeleteisO(size).•ExpectedtimeisO(1).7.4HashTableRepresentation数据结构算法与应用17IdealHashing•Usesa1Darray(ortable)table[0:b-1].–Eachpositionofthisarrayisabucket.–Abucketcannormallyholdonlyonedictionarypair.•Usesahashfunctionfthatconvertseachkeykintoanindexintherange[0,b-1].–f(k)isthehomebucketforkeyk.•Everydictionarypair(key,element)isstoredinitshomebuckettable[f[key]].18[0][1][2][3][4][5][6][7](85,f)(22,a)(33,c)(3,d)(73,e)IdealHashingExample•Pairsare:(22,a),(33,c),(3,d),(73,e),(85,f).•Hashtableistable[0:7],b=8.•Hashfunctioniskey/11.•Pairsarestoredintableasbelow:•search,insert,anddeletetakeO(1)time.19WhatCanGoWrong?•Wheredoes(26,g)go?•Keysthathavethesamehomebucketaresynonyms.–22and26aresynonymswithrespecttothehashfunctionthatisinuse.•Thehomebucketfor(26,g)isalreadyoccupied.[0][1][2][3][4][5][6][7](85,f)(22,a)(33,c)(3,d)(73,e)20WhatCanGoWrong?•Acollisionoccurswhenthehomebucketforanewpairisoccupiedbyapairwithadifferentkey.•Anoverflowoccurswhenthereisnospaceinthehomebucketforthenewpair.•Whenabucketcanholdonlyonepair,collisionsandoverflowsoccurtogether.•Needamethodtohandleoverflows.(85,f)(22,a)(33,c)(3,d)(73,e)21HashTableIssues•Choiceofhashfunction.•Overflowhandlingmethod.•Size(numberofbuckets)ofhashtable.22HashFunctions•Twoparts:–Convertkeyintoanintegerincasethekeyisnotaninteger.•DonebythemethodhashCode().•Mapanintegerintoahomebucket.–f(k)isanintegerintherange[0,b-1],wherebisthenumberofbucketsinthetable.23MapIntoAHomeBucket•MostcommonmethodisbyhomeBucket=Math.abs(theKey.hashCode())%divisor;•divisorequalsnumberofbucketsb.•0=homeBucketdivisor=b[0][1][2][3][4][5][6][7](85,f)(22,a)(33,c)(3,d)(73,e)24UniformHashFunction•LetkeySpacebethesetofallpossiblekeys.•AuniformhashfunctionmapsthekeysinkeySpaceintobucketssuchthatapproximatelythesamenumberofkeysgetmappedintoeachbucket.[0][1][2][3][4][5][6][7](85,f)(22,a)(33,c)(3,d)(73,e)25UniformHashFunction•Equivalently,theprobabilitythatarandomlyselectedkeyhasbucketiasitshomebucketis1/b,0=ib.•Auniformhashfunctionminimizesthelikelihoodofanoverflowwhenkeysareselectedatrandom.[0][1][2][3][4][5][6][7](85,f)(22,a)(33,c)(3,d)(73,e)26HashingByDivision•keySpace=allints.•Foreveryb,thenumberofintsthatgetmapped(hashed)intobucketiisapproximately232/b.•Therefore,thedivisionmethodresultsinauniformhashfunctionwhenkeySpace=allints.•Inpractice,keystendtobecorrelated.•So,thechoiceofthedivisorbaffectsthedistributionofhomebuckets.27SelectingTheDivisor•Becauseofthiscorrelat