程序设计与算法基础课件.ppt

《程序设计与算法基础课件.ppt》由会员分享，可在线阅读，更多相关《程序设计与算法基础课件.ppt（86页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序设计与算法基础程序设计与算法基础(6)潘爱民2006/10/30OutlinelHash tableslBloom filterlInverted indexSearching problem againlFor a linked list,-O(n)lFor a sorted array,-O(logn)lCan we expect O(1)?which meanslRegardless of the number of elements being searched,the run time is always the samelGiven a key,the position in

2、the table can be accessed directlyOperations on hash tableslCollection of pairsl(key,element),here key maybe a string,number,record,etc.lPairs have different keyslOperationslGet(theKey)lDelete(theKey)lInsert(theKey,theElement)Ideal HashinglUses a 1D array(or table)table0m-1.lEach position of this ar

3、ray is a bucketlA bucket can normally hold only one pairlUses a hash function h that converts each key k into an index in the range 0,m-1lh(k)is the home bucket for key klEvery pair(key,element)is stored in its home bucket tablehkey01234567Ideal Hashing ExamplelPairs are:(22,a),(33,c),(3,d),(73,e),(

4、85,f)lHash table is table07,m=8lHash function is h(key)=key/11 lPairs are stored in table as below(85,f)(22,a)(33,c)(3,d)(73,e)Get,Insert,and Delete take O(1)timeWhat Can Go Wrong?lWhere does(26,g)go?lKeys that have the same home bucket are synonymsl22 and 26 are synonyms with respect to the hash fu

5、nction that is in use.lThe home bucket for(26,g)is already occupied.01234567(85,f)(22,a)(33,c)(3,d)(73,e)What Can Go Wrong?lA collision occurs when the home bucket for a new pair is occupied by a pair with a different keylAn overflow occurs when there is no space in the home bucket for the new pairl

6、When a bucket can hold only one pair,collisions and overflows occur togetherlNeed a method to handle overflows(85,f)(22,a)(33,c)(3,d)(73,e)Hash Table IssueslChoice of hash functionslCollision resolutionlSize of hash tablelThe size of bucket&number of bucketsHash functionslDefinition:lA hash function

7、 transforms a key K into an index in the table used for storing items of the same type as KlIf hash function h transforms different keys into different numbers,it is called a perfect hash function lTherefore,a hash function is a mapping from n items to m positionslTotal number of possible mappings i

8、s mnlIf n m,the number of perfect hash functions is m!/(m-n)!Hash FunctionslTwo partslConvert a key into an integer in case the key is not an integerlh(k)lMap an integer into a home bucketlf(k)is an integer in the range 0,m-1,where m is the number of buckets in the tableString To Non-negative Intege

9、rlEach character is 1 byte longlAn int is 4 byteslA two-character string s may be converted into a unique 4 byte non-negative int using the code:lint answer=s.at(0);lanswer=(answer 8)+s.at(1);lStrings that are longer than 3 characters do not have a unique non-negative int representationString To Non

10、negative Integerunsigned long operator()(const string theKey)/Convert theKey to a nonnegative integer.unsigned long hashValue=0;int length=(int)theKey.length();for(int i=0;i length;i+)hashValue=5*hashValue +theKey.at(i);return hashValue;Map into a home bucketlMost common method is by division homeBu

11、cket=h(theKey)%divisor;ldivisor equals the number of buckets ml0 homeBucket divisor=m01234567(85,f)(22,a)(33,c)(3,d)(73,e)Uniform Hash FunctionLet keySpace be the set of all possible keysA uniform hash function maps the keys in keySpace into buckets such that approximately the same number of keys ge

12、t mapped into each bucket01234567(85,f)(22,a)(33,c)(3,d)(73,e)Uniform Hash Function Equivalently,the probability that a randomly selected key has bucket i as its home bucket is 1/m,0 i m A uniform hash function minimizes the likelihood of an overflow when keys are selected at random01234567(85,f)(22

13、,a)(33,c)(3,d)(73,e)Hashing By DivisionlkeySpace=all intslFor every m,the number of ints that get mapped(hashed)into bucket i is approximately 232/mlTherefore,the division method results in a uniform hash function when keySpace=all intslIn practice,keys tend to be correlatedlSo,the choice of the div

14、isor m affects the distribution of home bucketsSelecting The DivisorlBecause of this correlation,applications tend to have a bias towards keys that map into odd integers(or into even ones)lWhen the divisor is an even number,odd integers hash into odd home buckets and even integers into even home buc

15、ketsl20%14=6,30%14=2,8%14=8l15%14=1,3%14=3,23%14=9lThe bias in the keys results in a bias toward either the odd or even home bucketsSelecting The DivisorlWhen the divisor is an odd number,odd(even)integers may hash into any homel20%15=5,30%15=0,8%15=8l15%15=0,3%15=3,23%15=8lThe bias in the keys does

16、 not result in a bias toward either the odd or even home bucketslBetter chance of uniformly distributed home bucketslSo do not use an even divisorSelecting The DivisorlSimilar biased distribution of home buckets is seen,in practice,when the divisor is a multiple of prime numbers such as 3,5,7,lThe e

17、ffect of each prime divisor p of m decreases as p gets largerlIdeally,choose m so that it is a prime numberlAlternatively,choose m so that it has no prime factor smaller than 20Hashing by foldinglThe key is divided into several parts,and these parts are combined or folded togetherlShift foldinglUsin

18、g a simple operation such as addition to combine them in a certain waylFor example,the social security number(SSN),123-45-6789(123+456+789)%m(m=1000)lBoundary foldinglThe pieces of the keys are folded on the borders between different parts,for example(123+654+789)%m(m=1000)About foldinglSimple and f

19、ast,bit pattern can be used instead of numerical valueslIn the case of stringslXoring the characters together,and using the result for the addresslXoring the chunks of strings rather than single characters.The length of a chunk is equal to the number of bytes in an integerlTypically,the result of fo

20、lding processing are divided modulo mHashing by a Mid-square functionlThe key is squared and the middle or mid part of the result is used as the hash valuelEntire key participates in generating the hash value,so a better chance that the different values are generated for different keyslIn practice,i

21、t is more efficient to choose a power of 2 for the size of the table,m,and extract the mid part of the bit representation of the square of a key,just using a mask and a shift operationlFor example,31212=100101001010000101100001,the mid part 101000010=322Hashing by extractionlOnly a part of the key i

22、s used to compute the addresslIf the part is distributed uniformly,it can be sufficient for hashing(provided the omitted portion distinguishes the keys only in an insignificant way)lFor example,in the student ID,some digits are safely omitted in a hash functionlISBN code is similarHashing by radix t

23、ransformationlThe key is transformed into another number baselFor example,K is the decimal number 345,then its value in base 9 is 423(9)lThen it is divided modulo m in original base,the resulting number is used as the hash valuelIf m=100,345(10)and 245(10)are not hashed to the same value,but 345(10)

24、and 264(10)will be hashed to a same value,23Hashing by cryptographic hash algorithmslStrong hash algorithmslA change of any bit in the input will cause the change of any bit in the output with 0.5 probability approximatelylThe encryption algorithm has similar featurelUsing cryptographic algorithms t

25、o hash a keylFor example,compute the MD5(key)or SHA1(key)or encrypt the key with a fixed encryption key,DESk(key)lThen divided modulo mCollision resolutionlAvoid collisionlIncreasing the table size may lead to better hashing,but sometimes notlThe two factors hash function and table size may minimize

26、 the number of collisions,but they can not completely eliminate them(if the size of key space is larger than the table size)lSome strategieslOpen addressinglChaininglBucket addressingCollision resolution by opening addressinglA collision occurs when the home bucket for a new pair(key,element)is occu

27、piedlWe may handle collisions by:lSearch the hash table in some systematic fashion for a bucket that is not occupied.lLinear probinglQuadratic probinglRandom probinglEliminate overflows by permitting each bucket to keep a list of all pairs for which it is the home bucketlDynamic arrayllinked listOpe

28、ning addressinglIf the position h(K)is occupied,then the positions in the probing sequencenorm(h(K)+p(1),norm(h(K)+p(2),norm(h(K)+p(m)are tried until leither an available cell is found lor the same positions are tried repeatedly lor the table is fulllIn the probing sequence,lFunction p is probing fu

29、nctionli is a probelnorm is a normalization function,(division modulo to the size of the table)Linear probinglIn the open addressinglp(i)=c*i,so if c=1,then the position to be tried is(h(K)+i)lIn linear probing,lInsertion:the position to store a key is found by sequentially searching all positions s

30、tarting from the position calculated by the hash function until an empty cell is found lTendency to create clusters in the table,the empty cells following clusters have a much greater chance to be filled than other positionsLinear Probing Get And Insertldivisor=m(number of buckets)=17lHome bucket=ke

31、y%170481216Insert pairs whose keys are 6,12,34,29,28,11,23,7,0,33,30,45612 2934281123 70333045Quadratic probinglIn the open addressinglIn general,p(i)=c2*i2+c1*i,for example,p(i)=(-1)i-1(i+1)/2)2,so the position to be tried is h(K),h(K)+1,h(K)-1,h(K)+4,h(K)-4,h(K)+(m-1)2/4,h(K)(m-1)2/4lThe experienc

32、e value of m(table size)is a prime in the form of 4j+1lQuestion:lWhy not use p(i)=i2,0i m 5/4*1000=1250.lPick m(equal to divisor)to be a prime number or an odd number with no prime divisors smaller than 20Collision resolution:chaininglEach bucket keeps a linear list of all pairs for which it is the

33、home bucketlNever overflow if the capacity of the linear list is unlimitedlThe linear list may or may not be sorted by key.lThe linear list may be an array linear list or a chainlPerformancelIncreasing the length of the lists can degrade retrieval performancelRequire additional space for pointersPut

34、 in pairs whose keys are 6,12,34,29,28,11,23,7,0,33,30,45Home bucket=key%17.Sorted Chains0481216126342928112370333045Expected PerformancelNote that LF 0.lExpected chain length is LF.lSn 1+LF/2(in the case of unsorted list)lUn LFCoalesced hashing(coalesced chaining)lCombine linear probing and chainin

35、gh(K)=K%17 Insert pairs whose keys are 6,12,34,29,28,11,23,7,0lAlternatively,the colliding key can be put in an overflow area(called a cellar)0481216612 2934281123 70Bucket addressinglAssociate a bucket with each address,and a bucket is a block of space enough to store multiple itemslCollision is no

36、t totally avoided,if a bucket is full,thenlA new item hashed to the bucket can be stored in the next bucket,just as does in the open addressing approachlThe new item can also be stored in an overflow area.The bucket will be marked with a flag indicating it has additional items to be searchedPerfect

37、hash functionslPerfect hash functions or ideal hash functionslIt hashes a key to its proper position,and no collisions occurlAn assumption is that the key set is knownlIf the number of cells in the table is equal to the number of data items,it is called a minimal perfect hash functionso no space is

38、wastedlExampleslReserved words used by assemblers,compilers,files on unerasable optical disks,dictionaries,lIt is not easy to obtain a perfect hash functionCichellis method to construct a minimal perfect hash functionlDeveloped by Richard J.CichellilUsed to hash a relatively small number of reserved

39、 wordslThe function is of the formh(word)=(length(word)+g(firstletter(word)+g(lastletter(word)mod mwhere g is the function to be constructedCichellis algorithmlChoose a value for MaxlCompute the number of occurrences of each first and last letter in the set of all wordslOrder all words in accordance

40、 to the frequency of occurrence of the first and the last letterslExamples:Calliope,Clio,Erato,Euterpe,Melpomene,Polyhymnia,Terpsichore,Thalia,Uranial=E(6),A(3),C(2),O(2),T(2),M(1),P(1),U(1)lEuterpe,Calliope,Erato,Terpsichore,Melpomene,Thalia,Clio,Polyhymnia,UraniaCichellis algorithm(cont.)Search(wo

41、rdList)if wordList is emptyhalt;word=first word from wordList;wordList=wordList with the first word detached;if the first and the last letters of word are assigned g-valuestry(word,-1,-1)/-1 signifies value already assignedif successSearch(wordList)put word at the beginning of wordList and detach it

42、s hash value;else if neigher the first nor the last letters has a g-valuefor each n,m in 0,Max)try(word,n,m);if successSearch(wordList)put word at the beginning of wordList and detach its hash value;else if either the first or the last letter has a g-valuefor each n in 0,Max)try(word,-1,n);if succes

43、sSearch(wordList)put word at the beginning of wordList and detach its hash value;Cichellis algorithm(cont.)try(word,firstLetterValue,lastLetterValue)if h(word)has not been claimedreserve h(word);if not-1(i.e.,not reserved)assign firstLetterValue and/or lastLetterValue as g-values of firstletter(word

44、)and/or lastletter(word)return successreturn failureA invocations of the searching procedurereserved hash valuesEuterpe E=0 h=77 Calliope C=0 h=878 Erato O=0 h=5578Terpsichore T=0 h=22578 MelpomeneM=0h=002578 Thalia A=0 h=6025678 Clio h=40245678 PolyhymniaP=0h=101245678Urania U=0 h=6*01245678Urania

45、U=1 h=7*01245678Urania U=2 h=8*01245678Urania U=3 h=0*01245678Urania U=4 h=1*01245678 PolyhymniaP=1h=2*0245678 PolyhymniaP=2h=3 02345678Urania U=0 h=6*02345678Urania U=1 h=7*02345678Urania U=2 h=8*02345678Urania U=3 h=0*02345678Urania U=4 h=1012345678About cichellis algorithmlA brute-force search fo

46、r g-function,so the search process is exponentiallIt is not applicable to a large number of wordslIt does not guarantee that a perfect hash function can be foundlExtensionsl(1)The second to last letters in the word are involved in the hash functionsl(2)h(word)=length(word)+g1(firstletter(word)+gleng

47、th(word)(lastletter(word)l(3)h(word)=bucketgr(word)+hgr(word)(word)FHCD algorithmlSearch for a minimal perfect hash function of the formh(word)=h0(word)+g(h1(word)+g(h2(word)h0:key space-0,m)h1:key space-0,r)h2:key space-r,2r)lSteps:lMapping(dependency graph):between h1 to h2 for each wordlOrdering:

48、first determine the node with more linkslSearching:assign hash values to keys by choosing appropriate g-value for each vertexFor each vertex,either g(h1(word)or g(h2(word)is knownExtensible hashing0001101100011001100010110011110111110001100010112221b00b01b1h(k)=11001h(k)=0000100011011000110011000101

49、1001101100010112222b00b01b101101111100110012b1100000101001100011000011001101100010113322b000b01b101101111100110012b1110010111011100110001013b001An example of hash functionlIn distributed environments,how to partition a large number of jobs(or records)into a cluster of machineskeyv=h(key)Linear hashi

50、nglNo index is neededlThe bucket is split if necessarylAt each level of splitting,linear hashing maintain two hash functions,hlevel and hlevel+1,such that hlevel=K mode(TSize*2level)0001001000110101011110001001101111001101STL hash_maplSimply uses a divisor that is an odd numberlThis simplifies imple