程序设计与算法基础3优秀文档.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,程序设计与算法基础(6),潘爱民,2006/10/30,Outline,Hash tables,Bloom filter,Inverted index,Searching problem again,For a linked list,-O(,n,),For a sorted array,-O(log,n,),Can we expect O(1)?which means,Regardless of the number of elements being searched,the run time is always the same,Given a key,the position in the table can be accessed directly,Operations on hash tables,Collection of pairs,(,key,element,),here,key,maybe a string,number,record,etc.,Pairs have different keys,Operations,Get(theKey),Delete(theKey),Insert(theKey,theElement),Ideal Hashing,Uses a 1D array(or table),table,0,m,-1.,Each position of this array is a,bucket,A bucket can normally hold only one pair,Uses a hash function,h,that converts each key,k,into an index in the range 0,m,-1,h,(,k,)is the home bucket for key,k,Every pair(,key,element,)is stored in its home bucket,table,h,key,0,1,2,3,4,5,6,7,Ideal Hashing Example,Pairs are:,(22,a),(33,c),(3,d),(73,e),(85,f),Hash table is,table,07,m,=8,Hash function is,h,(,key,)=,key,/11,Pairs are stored in table as below,(85,f),(22,a),(33,c),(3,d),(73,e),Get,Insert,and,Delete,take,O(1),time,What Can Go Wrong?,Where does,(26,g),go?,Keys that have the same home bucket are synonyms,22,and,26,are synonyms with respect to the hash function that is in use.,The home bucket for,(26,g),is already occupied.,0,1,2,3,4,5,6,7,(85,f),(22,a),(33,c),(3,d),(73,e),What Can Go Wrong?,A,collision,occurs when the home bucket for a new pair is occupied by a pair with a different key,An,overflow,occurs when there is no space in the home bucket for the new pair,When a bucket can hold only one pair,collisions and overflows occur together,Need a method to handle overflows,(85,f),(22,a),(33,c),(3,d),(73,e),Hash Table Issues,Choice of hash functions,Collision resolution,Size of hash table,The size of bucket&number of buckets,Hash functions,Definition:,A hash function transforms a key,K,into an index in the table used for storing items of the same type as,K,If hash function,h,transforms different keys into different numbers,it is called a,perfect hash function,Therefore,a hash function is a mapping from,n,items to,m,positions,Total number of possible mappings is,m,n,If,n,m,the number of perfect hash functions is,m!/(m-n)!,Hash Functions,Two parts,Convert a key into an integer in case the key is not an integer,h,(,k,),Map an integer into a home bucket,f,(,k,),is an integer in the range,0,m,-1,where,m,is the number of buckets in the table,String To Non-negative Integer,Each character is,1 byte,long,An int is,4 bytes,A two-character string,s,may be converted into a unique 4 byte non-negative int using the code:,int answer=s.at(0);,answer=(answer 8)+s.at(1);,Strings that are longer than 3 characters do not have a unique non-negative int representation,String To Nonnegative Integer,unsigned 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 bucket,Most common method is by division,homeBucket,=h(,theKey,)%,divisor,;,divisor,equals the number of buckets,m,0,homeBucket,this key is not in the DI,try(word,n,m);,A change of any bit in the input will cause the change of any bit in the output with 0.,PageRank was developed at Stanford University by Larry Page and Sergey Brin for a search engine-Google,Information needed,Urania U=4 h=1012345678,Never overflow if the capacity of the linear list is unlimited,The probability of false positive decreases as m increases,Combine linear probing and chaining,k too small=probability of different keys having same signature is high.,Open addressing,put word at the beginning of wordList and detach its hash value;,Terpsichore T=0 h=22578,Build inverted indexes,Urania U=4 h=1012345678,Urania U=2 h=8*02345678,not reserved),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 random,0,1,2,3,4,5,6,7,(85,f),(22,a),(33,c),(3,d),(73,e),Hashing By Division,keySpace,=,all,int,s,For every,m,the number of,int,s that get mapped(hashed)into bucket,i,is approximately,2,32,/,m,Therefore,the division method results in a uniform hash function when,keySpace,=,all,int,s,In practice,keys tend to be correlated,So,the choice of the divisor,m,affects the distribution of home buckets,Selecting The Divisor,Because of this correlation,applications tend to have a bias towards keys that map into odd integers(or into even ones),When the divisor is an even number,odd integers hash into odd home buckets and even integers into even home buckets,20%14=6,30%14=2,8%14=8,15%14=1,3%14=3,23%14=9,The bias in the keys results in a bias toward either the odd or even home buckets,Selecting The Divisor,When the divisor is an odd number,odd(even)integers may hash into any home,20%15=5,30%15=0,8%15=8,15%15=0,3%15=3,23%15=8,The bias in the keys does not result in a bias toward either the odd or even home buckets,Better chance of uniformly distributed home buckets,So do not use an even divisor,Selecting The Divisor,Similar biased distribution of home buckets is seen,in practice,when the divisor is a multiple of prime numbers such as,3,5,7,The effect of each prime divisor,p,of,m,decreases as,p,gets larger,Ideally,choose,m,so that it is a prime number,Alternatively,choose,m,so that it has no prime factor smaller than,20,Hashing by folding,The key is divided into several parts,and these parts are combined or folded together,Shift folding,Using a simple operation such as addition to combine them in a certain way,For example,the social security number(SSN),123-45-6789,(123+456+789)%,m,(,m=1000,),Boundary folding,The pieces of the keys are folded on the borders between different parts,for example,(123+654+789)%,m,(,m=1000,),About folding,Simple and fast,bit pattern can be used instead of numerical values,In the case of strings,Xoring the characters together,and using the result for the address,Xoring the chunks of strings rather than single characters.The length of a chunk is equal to the number of bytes in an integer,Typically,the result of folding processing are divided modulo,m,Hashing by a Mid-square function,The key is,squared,and the middle or,mid,part of the result is used as the hash value,Entire key participates in generating the hash value,so a better chance that the different values are generated for different keys,In practice,it 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 operation,For example,31212=10010100,101000010,1100001,the mid part,101000010,=322,Hashing by extraction,Only a part of the key is used to compute the address,If the part is distributed uniformly,it can be sufficient for hashing(provided the omitted portion distinguishes the keys only in an insignificant way),For example,in the student ID,some digits are safely omitted in a hash function,ISBN code is similar,Hashing by radix transformation,The key is transformed into another number base,For example,K,is the decimal number,345,then its value in base,9,is,423,(9),Then it is divided modulo,m,in original base,the resulting number is used as the hash value,If,m,=100,345,(10),and,245,(10),are not hashed to the same value,but,345,(10),and,264,(10),will be hashed to a same value,23,Hashing by cryptographic hash algorithms,Strong hash algorithms,A change of any bit in the input will cause the change of any bit in the output with 0.5 probability approximately,The encryption algorithm has similar feature,Using cryptographic algorithms to hash a key,For example,compute the,MD5(,key,),or,SHA1(,key,),or encrypt the key with a fixed encryption key,DES,k,(,key,),Then divided modulo,m,Collision resolution,Avoid collision,Increasing the table size may lead to better hashing,but sometimes not,The two factors hash function and table size may minimize the number of collisions,but they can not completely eliminate them(if the size of key space is larger than the table size),Some strategies,Open addressing,Chaining,Bucket addressing,Collision resolution by opening addressing,A collision occurs when the home bucket for a new pair,(key,element),is occupied,We may handle collisions by:,Search the hash table in some systematic fashion for a bucket that is not occupied.,Linear probing,Quadratic probing,Random probing,Eliminate overflows by permitting each bucket to keep a list of all pairs for which it is the home bucket,Dynamic array,linked list,Opening addressing,If the position h(K)is occupied,then the positions in the probing sequence,norm(h(K)+p(1),norm(h(K)+p(2),norm(h(K)+p(m),are tried until,either an available cell is found,or the same positions are tried repeatedly,or the table is full,In the probing sequence,Function,p,is,probing function,i,is a,probe,norm,is a normalization function,(division modulo to the size of the table),Linear probing,In the open addressing,p(i),=,c,*,i,so if,c,=1,then the position to be tried is,(h(K)+i),In linear probing,Insertion,:the position to store a key is found by sequentially searching all positions starting from the position calculated by the hash function until an empty cell is found,Tendency to create clusters in the table,the empty cells following clusters have a much greater chance to be filled than other positions,Linear Probing Get And Insert,divisor=,m,(number of buckets),=17,Home bucket=key%17,0,4,8,12,16,Insert pairs whose keys are,6,12,34,29,28,11,23,7,0,33,30,45,6,12,29,34,28,11,23,7,0,33,30,45,Quadratic probing,In the open addressing,In general,p(i)=c,2,*i,2,+c,1,*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,/4,The experience value of,m,(table size)is a prime in the form of 4,j,+1,Question:,Why not use,p,(,i,)=,i,2,0,i,m,5/4*1000=1250,.,Pick,m,(equal to,divisor,)to be a prime number or an odd number with no prime divisors smaller than,20,Collision resolution:chaining,Each bucket keeps a linear list of all pairs for which it is the home bucket,Never overflow if the capacity of the linear list is unlimited,The linear list may or may not be sorted by key.,The linear list may be an array linear list or a chain,Performance,Increasing the length of the lists can degrade retrieval performance,Require additional space for pointers,Put in pairs whose keys are,6,12,34,29,28,11,23,7,0,33,30,45,Home bucket,=key%17,.,Sorted Chains,0,4,8,12,16,12,6,34,29,28,11,23,7,0,33,30,45,Expected Performance,Note that,LF,0,.,Expected chain length is,LF,.,S,n,1+LF/2,(in the case of unsorted list),U,n,LF,Coalesced hashing(coalesced chaining),Combine linear probing and chaining,h,(,K,)=,K,%17,Insert pairs whose keys are,6,12,34,29,28,11,23,7,0,Alternatively,the colliding key can be put in an overflow area(called a cellar),0,4,8,12,16,6,12,29,34,28,11,23,7,0,Bucket addressing,Associate a,bucket,with each address,and a bucket is a block of space enough to store multiple items,Collision is not totally avoided,if a bucket is full,then,A new item hashed to the bucket can be stored in the next bucket,just as does in the open addressing approach,The 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 searched,Perfect hash functions,Perfect hash functions,or,ideal hash functions,It hashes a key to its proper position,and,no collisions occur,An assumption is that the key set is known,If the number of cells in the table is equal to the number of data items,it is called a,minimal perfect hash function,so no space is wasted,Examples,Reserved words used by assemblers,compilers,files on unerasable optical disks,dictionaries,It is not easy to obtain a perfect hash function,Cichellis method to construct a minimal perfect hash function,Developed by Richard J.Cichelli,Used to hash a relatively small number of reserved words,The function is of the form,h,(,word,)=(,length,(,word,)+,g,(,firstletter,(,word,)+,g,(,lastletter,(,word,)mod,m,where,g,is the function to be constructed,reserve h(word);,Search cluster for pair(if any)to fill vacated bucket,The new item can also be stored in an overflow area.,These lists can be used to solve Boolean queries:,The key is divided into several parts,and these parts are combined or folded together,(key,element),here key maybe a string,number,record,etc.,Pick m(equal to divisor)to be a prime number or an odd number with no prime divisors smaller than 20,Mapping(dependency graph):between h1 to h2 for each word,Bucket addressing,k=2(2 hash functions),Bloom in 1970,Insert pairs whose keys are 6,12,34,29,28,11,23,7,0,Hash function is h(key)=key/11,Cichellis algorithm,Choose a value for Max,Compute the number of occurrences of each first and last letter in the set of all words,Order all words in accordance to the frequency of occurrence of the first and the last letters,Examples:,C,alliop,e,C,li,o,E,rat,o,E,uterp,e,M,elpomen,e,P,olyhymni,a,T,erpsichor,e,T,hali,a,U,rani,a,=,E(6),A(3),C(2),O(2),T(2),M(1),P(1),U(1),Euterpe,Calliope,Erato,Terpsichore,Melpomene,Thalia,Clio,Polyhymnia,Urania,Cichellis algorithm(cont.),Search(,wordList,),if,wordList,is empty,halt;,word,=first word from wordList;,wordList,=wordList with the first word detached;,if the first and the last letters of word are assigned g-values,try(,word,-1,-1)/-1 signifies value already assigned,if success,Search(,wordList,),put,word,at the beginning of,wordList,and detach its hash value;,else if neigher the first nor the last letters has a g-value,for each,n,m,in 0,Max),try(,word,n,m,);,if success,Search(,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-value,for each,n,in 0,Max),try(,word,-1,n,);,if success,Search(,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 claimed,reserve h(word);,if,not,-1(i.e.,not reserved),assign firstLetterValue and/or lastLetterValue as g-values of,firstletter(word)and/or lastletter(word),return,success,return,failure,A invocations of the searching procedure,reserved hash values,Euterpe E=0 h=77,Calliope C=0 h=878,Erato O=0 h=5578,Terpsichore T=0 h=22578,MelpomeneM=0h=002578,Thalia A=0 h=6025678,Clio h=40245678,PolyhymniaP=0h=101245678,Urania U=0 h=6*01245678,Urania U=1 h=7*01245678,Urania U=2 h=8*01245678,Urania U=3 h=0*01245678,Urania U=4 h=1*01245678,PolyhymniaP=1h=2*0245678,PolyhymniaP=2h=3 02345678,Urania U=0 h=6*02345678,Urania U=1 h=7*02345678,Urania U=2 h=8*02345678,Urania U=3 h=0*02345678,Urania U=4 h=1012345678,About cichellis algorithm,A brute-forc