哈希算法(精品).ppt

《哈希算法(精品).ppt》由会员分享，可在线阅读，更多相关《哈希算法(精品).ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Hash Tables 1Comp 122,Spring 2004hashtables-2Lin/DeviDictionary wDictionary:Dynamic-set data structure for storing items indexed using keys.Supports operations Insert,Search,and Delete.Applications:Symbol table of a compiler.Memory-management tables in operating systems.Large-scale distributed syste

2、ms.wHash Tables:Effective way of implementing dictionaries.Generalization of ordinary arrays.Comp 122,Fall 2003hashtables-3Lin/DeviDirect-address Tables wDirect-address Tables are ordinary arrays.wFacilitate direct addressing.Element whose key is k is obtained by indexing into the kth position of th

3、e array.wApplicable when we can afford to allocate an array with one position for every possible key.i.e.when the universe of keys U is small.wDictionary operations can be implemented to take O(1)time.Details in Sec.11.1.Comp 122,Fall 2003hashtables-4Lin/DeviHash TableswNotation:U Universe of all po

4、ssible keys.K Set of keys actually stored in the dictionary.|K|=n.wWhen U is very large,Arrays are not practical.|K|U|.wUse a table of size proportional to|K|The hash tables.However,we lose the direct-addressing ability.Define functions that map keys to slots of the hash table.Comp 122,Fall 2003hash

5、tables-5Lin/DeviHashingwHash function h:Mapping from U to the slots of a hash table T0.m1.h:U 0,1,m1wWith arrays,key k maps to slot Ak.wWith hash tables,key k maps or“hashes”to slot Thk.whk is the hash value of key k.Comp 122,Fall 2003hashtables-6Lin/DeviHashing0m1h(k1)h(k4)h(k2)=h(k5)h(k3)U(univers

6、e of keys)K(actualkeys)k1k2k3k5k4collisionComp 122,Fall 2003hashtables-7Lin/DeviIssues with HashingwMultiple keys can hash to the same slot collisions are possible.Design hash functions such that collisions are minimized.But avoiding collisions is impossible.Design collision-resolution techniques.wS

7、earch will cost(n)time in the worst case.However,all operations can be made to have an expected complexity of(1).Comp 122,Fall 2003hashtables-8Lin/DeviMethods of ResolutionwChaining:(拉链法)Store all elements that hash to the same slot in a linked list.Store a pointer to the head of the linked list in

8、the hash table slot.wOpen Addressing（线性探测法）All elements stored in hash table itself.When collisions occur,use a systematic(consistent)procedure to store elements in free slots of the table.k20m1k1k4k5k6k7k3k8Comp 122,Fall 2003hashtables-9Lin/DeviCollision Resolution by Chaining0m1h(k1)=h(k4)h(k2)=h(

9、k5)=h(k6)h(k3)=h(k7)U(universe of keys)K(actualkeys)k1k2k3k5k4k6k7k8h(k8)XXXComp 122,Fall 2003hashtables-10Lin/Devik2Collision Resolution by Chaining0m1U(universe of keys)K(actualkeys)k1k2k3k5k4k6k7k8k1k4k5k6k7k3k8Comp 122,Fall 2003hashtables-11Lin/DeviHashing with ChainingDictionary Operations:wCha

10、ined-Hash-Insert(T,x)Insert x at the head of list Th(keyx).Worst-case complexity O(1).wChained-Hash-Delete(T,x)Delete x from the list Th(keyx).Worst-case complexity proportional to length of list with singly-linked lists.O(1)with doubly-linked lists.wChained-Hash-Search(T,k)Search an element with ke

11、y k in list Th(k).Worst-case complexity proportional to length of list.Comp 122,Fall 2003hashtables-12Lin/DeviAnalysis on Chained-Hash-SearchwLoad factor=n/m=average keys per slot.m number of slots.n number of elements stored in the hash table.wWorst-case complexity:(n)+time to compute h(k).wAverage

12、 depends on how h distributes keys among m slots.wAssume Simple uniform hashing.Any key is equally likely to hash into any of the m slots,independent of where any other key hashes to.O(1)time to compute h(k).wTime to search for an element with key k is Q(|Th(k)|).wExpected length of a linked list=lo

13、ad factor=n/m.Comp 122,Fall 2003hashtables-13Lin/DeviExpected Cost of an Unsuccessful SearchProof:wAny key not already in the table is equally likely to hash to any of the m slots.wTo search unsuccessfully for any key k,need to search to the end of the list Th(k),whose expected length is.wAdding the

14、 time to compute the hash function,the total time required is(1+).Theorem:An unsuccessful search takes expected time(1+).Comp 122,Fall 2003hashtables-14Lin/DeviExpected Cost of a Successful SearchProof:wThe probability that a list is searched is proportional to the number of elements it contains.wAs

15、sume that the element being searched for is equally likely to be any of the n elements in the table.wThe number of elements examined during a successful search for an element x is 1 more than the number of elements that appear before x in xs list.These are the elements inserted after x was inserted.

16、wGoal:Find the average,over the n elements x in the table,of how many elements were inserted into xs list after x was inserted.Theorem:A successful search takes expected time(1+).Comp 122,Fall 2003hashtables-15Lin/DeviExpected Cost of a Successful SearchProof(contd):wLet xi be the ith element insert

17、ed into the table,and let ki=keyxi.wDefine indicator random variables Xij=Ih(ki)=h(kj),for all i,j.wSimple uniform hashing Prh(ki)=h(kj)=1/m EXij=1/m.wExpected number of elements examined in a successful search is:Theorem:A successful search takes expected time(1+).No.of elements inserted after xi i

18、nto the same slot as xi.Comp 122,Fall 2003hashtables-16Lin/DeviProof Contd.(linearity of expectation)Expected total time for a successful search=Time to compute hash function+Time to search=O(2+/2 /2n)=O(1+).Comp 122,Fall 2003hashtables-17Lin/DeviExpected Cost InterpretationwIf n=O(m),then=n/m=O(m)/

19、m=O(1).Searching takes constant time on average.wInsertion is O(1)in the worst case.wDeletion takes O(1)worst-case time when lists are doubly linked.wHence,all dictionary operations take O(1)time on average with hash tables with chaining.Comp 122,Fall 2003hashtables-18Lin/DeviGood Hash FunctionswSat

20、isfy the assumption of simple uniform hashing.Not possible to satisfy the assumption in practice.wOften use heuristics,based on the domain of the keys,to create a hash function that performs well.wRegularity in key distribution should not affect uniformity.Hash value should be independent of any pat

21、terns that might exist in the data.E.g.Each key is drawn independently from U according to a probability distribution P:k:h(k)=j P(k)=1/m for j=0,1,m1.An example is the division method.Comp 122,Fall 2003hashtables-19Lin/DeviKeys as Natural NumberswHash functions assume that the keys are natural numb

22、ers.wWhen they are not,have to interpret them as natural numbers.wExample:Interpret a character string as an integer expressed in some radix notation.Suppose the string is CLRS:ASCII values:C=67,L=76,R=82,S=83.There are 128 basic ASCII values.So,CLRS=671283+76 1282+821281+831280 =141,764,947.Comp 12

23、2,Fall 2003hashtables-20Lin/DeviDivision MethodwMap a key k into one of the m slots by taking the remainder of k divided by m.That is,h(k)=k mod mwExample:m=31 and k=78 h(k)=16.wAdvantage:Fast,since requires just one division operation.wDisadvantage:Have to avoid certain values of m.Dont pick certai

24、n values,such as m=2pOr hash wont depend on all bits of k.wGood choice for m:Primes,not too close to power of 2(or 10)are good.Comp 122,Fall 2003hashtables-21Lin/DeviMultiplication MethodwIf 0 A 1,h(k)=m(kA mod 1)=m(kA kA)where kA mod 1 means the fractional part of kA,i.e.,kA kA.wDisadvantage:Slower

25、 than the division method.wAdvantage:Value of m is not critical.Typically chosen as a power of 2,i.e.,m=2p,which makes implementation easy.wExample:m=1000,k=123,A 0.6180339887h(k)=1000(123 0.6180339887 mod 1)=1000 0.018169.=18.Comp 122,Fall 2003hashtables-22Lin/DeviMultiplication Mthd.Implementation

26、wChoose m=2p,for some integer p.wLet the word size of the machine be w bits.wAssume that k fits into a single word.(k takes w bits.)wLet 0 s 2w.(s takes w bits.)wRestrict A to be of the form s/2w.wLet k s=r1 2w+r0.wr1 holds the integer part of kA(kA)and r0 holds the fractional part of kA(kA mod 1=kA

27、 kA).wWe dont care about the integer part of kA.So,just use r0,and forget about r1.Comp 122,Fall 2003hashtables-23Lin/DeviMultiplication Mthd Implementationks=A2wr0r1w bitsh(k)extract p bitswWe want m(kA mod 1).We could get that by shifting r0 to the left by p=lg m bits and then taking the p bits th

28、at were shifted to the left of the binary point.wBut,we dont need to shift.Just take the p most significant bits of r0.binary pointComp 122,Fall 2003hashtables-24Lin/DeviHow to choose A?wAnother example:On board.wHow to choose A?The multiplication method works with any legal value of A.But it works better with some values than with others,depending on the keys being hashed.Knuth suggests using A (5 1)/2.Comp 122,Fall 2003