MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 6 006 Recitation Build 2008 14 Coming up next Open addressing Karp Rabin coming back from the dead to hunt us Open Addressing Goal use nothing but the table Hoping for less code better caching Hashing we must handle collisions Solution try another location Easy Collision handling h x standard hash function if T h x is taken try T h x 1 then T h x 2 then T h x 3 just like parking a car h 29 h 29 1 h 29 2 h 29 3 0 1 2 3 4 5 6 7 8 9 taken taken taken taken taken here taken Collision Handling Abstracting it Up h k grows up to H k i where i is the attempt number rst try T H k 0 0 1 2 3 4 5 6 7 8 H 29 0 9 taken taken taken taken taken taken taken taken taken taken Collision Handling Abstracting it Up h k grows up to H k i where i is the attempt number rst try T H k 0 then T H k 1 0 H 29 1 1 2 3 4 5 6 7 8 H 29 0 9 taken taken taken taken taken taken taken taken taken taken Collision Handling Abstracting it Up h k grows up to H k i where i is the attempt number rst try T H k 0 then T H k 1 then T H k 2 0 H 29 1 1 2 3 H 29 2 4 5 6 7 8 H 29 0 9 taken taken taken taken taken taken taken taken taken taken Collision Handling Abstracting it Up h k grows up to H k i where i is the attempt number rst try T H k 0 then T H k 1 then T H k 2 stop after trying all H 29 3 H 29 1 H 29 4 H 29 9 H 29 2 H 29 5 H 29 6 H 29 7 H 29 8 H 29 0 0 1 2 3 4 5 6 7 8 9 taken taken taken taken taken taken taken taken taken taken Collision Handling Abstracting it Up H k H k 0 H k 1 H k 2 Linear probing h 29 4 Hlinear 29 4 5 6 7 8 9 0 1 2 3 General properties H 29 3 H 29 1 H 29 4 H 29 9 H 29 2 H 29 5 H 29 6 H 29 7 H 29 8 H 29 0 0 1 2 3 4 5 6 7 8 9 taken taken taken taken taken taken taken taken taken taken Collision Handling Abstracting it Up Any collision handling strategy comes to for key k probe H k 0 then H k 1 etc No point in trying the same place twice Probes should cover the whole table otherwise we raise table full prematurely Conclusion H k 0 H k 1 H k m 1 are a permutation of 1 2 3 m Linear Probing and Permutations h 29 4 H 29 4 5 6 7 8 9 0 1 2 3 h k h0 mod m H k h0 mod m h0 1 mod m h0 2 mod m h0 m 1 mod m m permutations max m h 29 h 29 1 h 29 2 h 29 3 0 1 2 3 4 5 6 7 8 9 taken taken taken taken taken here taken Ideal Collision Handling Simple Hashing collision by chaining Ideal hashing function uniformly distributes keys across hash values Open Addressing Ideal hashing function uniformly distributes keys across permutations a k a uniform hashing Uniform Hashing Achievable Simple mapping between permutations of m and numbers 1 m Convert key to big number then use permutation number bignum mod m right k mod 6 Permutation 0 1 2 3 1 1 3 2 2 2 1 3 3 2 3 1 4 3 1 2 5 3 2 1 Uniform Hashing Achievable Number of digits in m O log m O m log m Working mod m is slow check your Python cost model k mod 6 Permutation 0 1 2 3 1 1 3 2 2 2 1 3 3 2 3 1 4 3 1 2 5 3 2 1 Working Compromise Why does linear probing suck We jump in the table once then walk Improvement Keep jumping after the initial jump Jumping distance 2 hash function Name double hashing nd Double Hashing Math h1 k and h2 k are hashing functions 0 1 2 3 4 5 6 7 8 9 taken taken taken taken taken taken taken Double Hashing Math h1 k and h2 k are hashing functions H k 0 h1 k 0 1 2 3 h1 29 4 5 6 7 8 9 taken taken taken taken taken taken taken Double Hashing Math h1 k and h2 k are hashing functions H k 0 h1 k H k 1 h1 k h2 k 0 1 2 3 h1 29 4 5 6 h1 29 h2 29 7 8 9 taken taken taken taken taken taken taken Double Hashing Math h1 k and h2 k are hashing functions H k 0 h1 k H k 1 h1 k h2 k h1 29 2 h2 29 0 1 2 3 h1 29 4 5 6 h1 29 h2 29 7 8 9 taken taken taken taken taken taken taken Double Hashing Math h1 k and h2 k are hashing functions H k 0 h1 k H k 1 h1 k h2 k h1 29 2 h2 29 0 1 2 h1 29 3 h2 29 3 h1 29 4 5 6 h1 29 h2 29 7 8 9 taken taken here taken taken taken taken taken Double Hashing Math h1 k and h2 k are hashing functions h1 29 2 h2 29 0 1 2 H k 0 h1 k h1 29 3 h2 29 3 H k 1 h1 k h2 k h1 29 4 5 H k i h1 k i h2 k 6 h1 29 h2 29 7 mod m 8 9 you knew that right taken taken here taken taken taken taken taken Double Hashing Trap gcd h2 k m must be 1 h1 29 2 h2 29 0 1 solution 1 easy to get 2 m prime h2 k k h1 29 3 h2 29 3 mod q where q m h1 29 4 5 solution 2 faster better 6 h 1 29 h2 29 7 r m 2 table can grow 8 9 h2 k is odd not even taken taken here taken taken taken taken taken Open Addressing Deleting Keys Suppose we want to delete kd stored at 7 Can t simply wipe the entry because key 29 wouldn t be found anymore rember H 29 4 7 0 3 h1 29 2 h2 29 0 1 2 h1 29 3 h2 29 3 h1 29 4 5 …
View Full Document
Unlocking...