本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用,第7章1Chapter7SkipListsandHashing數(shù)據(jù)布局算法與應(yīng)用數(shù)據(jù)布局算法與應(yīng)用東校區(qū)測驗(yàn)中心B501東校區(qū)測驗(yàn)中心B501huangfj信息科學(xué)與技術(shù)學(xué)院黃方軍信息科學(xué)與技術(shù)學(xué)院黃方軍2BirdsEyeViewSkipListsHasing數(shù)據(jù)布局算法與應(yīng)用數(shù)據(jù)布局算法與應(yīng)用371Dictionaries數(shù)據(jù)布局算法與應(yīng)用數(shù)據(jù)布局算法與應(yīng)用CollectionofpairskeyelementPairshavedifferentkeysOperationsSearchkxInsertxDeletekx4ApplicationCollectionofstudentrecordsinthisclasskeyelementstudentnamelinearlistofassignmentandexamscoresAllkeysaredistinctGettheelementwhosekeyisJohnAdamsUpdatetheelementwhosekeyisDianaRossInsertimplementedasupdatewhenthereisalreadyapairwiththegivenkeyDeletefollowedbyinsert5DictionaryWithDuplicatesKeysarenotrequiredtobedistinctWorddictionaryPairsareofthewordmeaningMayhavetwoormoreentriesforthesamewordboltathreadedpinboltacrashofthunderbolttoshootforthsuddenlyboltagulpboltastandardrollofclothetc6Le0e1e2e3en1Eacheiisapairkeyelement5pairdictionaryDabcdeaaKeyaElementbbKeybElementetc72LinearListRepresentation數(shù)據(jù)布局算法與應(yīng)用數(shù)據(jù)布局算法與應(yīng)用7ArrayRepresentationabcdesearchkxOsizetimeinsertxOsizetimetoverifyduplicateO1toaddatrightenddeletekxOsizetime8SortedArrayABCDEelementsareinascendingorderofkeysearchkxOlogsizetimeinsertxOlogsizetimetoverifyduplicateOsizetoadddeletekxOsizetime9UnsortedChainsearchkxOsizetimeinsertxOsizetimetoverifyduplicateO1toaddatleftenddeletekxOsizetimeabcdenullfirstNode10SortedChainElementsareinascendingorderofKeysearchkxOsizetimeinsertxOsizetimetoverifyduplicateO1toputatproperplaceABCDEnullfirstNode11SortedChainElementsareinascendingorderofKeyABCDEnullfirstNodedeletekxOsizetime12SortedChaintemplateclassSortedChainpublicSortedChainfirst0SortedChainboolIsEmptyconstreturnfirst0intLengthconstboolSearchconstKSortedChainSortedChainSortedChainvoidOutputostreamprivateSortedChainNodefirstpointertofirstnode13SortedChaintemplateclassSortedChainNodefriendSortedChainprivateEdataSortedChainNodelink14SortedChaintemplateboolSortedChainSearchconstKsearchformatchwithkwhilepverifymatchifpreturntruereturnfalsenomatch1573SkipListRepresentation數(shù)據(jù)布局算法與應(yīng)用數(shù)據(jù)布局算法與應(yīng)用WorstcasetimeforsearchinsertanddeleteisOsizeExpectedtimeisOlogsizeWellskipskiplists16WorstcasetimeforsearchinsertanddeleteisOsizeExpectedtimeisO174HashTableRepresentation數(shù)據(jù)布局算法與應(yīng)用數(shù)據(jù)布局算法與應(yīng)用17IdealHashingUsesa1Darrayortabletable0b1EachpositionofthisarrayisabucketAbucketcannormallyholdonlyonedictionarypairUsesahashfunctionfthatconvertseachkeykintoanindexintherange0b1fkisthehomebucketforkeykEverydictionarypairkeyelementisstoredinitshomebuckettablefkey180123456785f22a33c3d73eIdealHashingExamplePairsare22a33c3d73e85fHashtableistable07b8Hashfunctioniskey11PairsarestoredintableasbelowsearchinsertanddeletetakeO1time19WhatCanGoWrongWheredoes26ggoKeysthathavethesamehomebucketaresynonyms22and26aresynonymswithrespecttothehashfunctionthatisinuseThehomebucketfor26gisalreadyoccupied0123456785f22a33c3d73e20WhatCanGoWrongAcollisionoccurswhenthehomebucketforanewpairisoccupiedbyapairwithadifferentkeyAnoverflowoccurswhenthereisnospaceinthehomebucketforthenewpairWhenabucketcanholdonlyonepaircollisionsandoverflowsoccurtogetherNeedatohandleoverflows85f22a33c3d73e21HashTableIssuesChoiceofhashfunctionOverflowhandlingSizenumberofbucketsofhashtable22HashFunctionsTwopartsConvertkeyintoanintegerincasethekeyisnotanintegerDonebythehashCodeMapanintegerintoahomebucketfkisanintegerintherange0b1wherebisthenumberofbucketsinthetable23MapIntoAHomeBucketMostcommonisbyhomeBucketMathabstheKeyhashCodedivisordivisorequalsnumberofbucketsb0homeBucketdivisorb0123456785f22a33c3d73e24UniHashFunctionLetkeySpacebethesetofallpossiblekeysAunihashfunctionmapsthekeysinkeySpaceintobucketssuchthatapproximatelythesamenumberofkeysgetmappedintoeachbucket0123456785f22a33c3d73e25UniHashFunctionEquivalentlytheprobabilitythatarandomlyselectedkeyhasbucketiasitshomebucketis1b0ibAunihashfunctionminimizesthelikelihoodofanoverflowwhenkeysareselectedatran