Lecture 8: Hashing

Lecture 8 Hashing 6.046J Spring 2015 Lecture 8: Hashing Course Overview This course covers several modules: 1. Review: dictionaries, chaining, simple uniform 2. Universal hashing 3. Perfect hashing Review Dictionary Problem A dictionary is an Abstract Data Type (ADT) that maintains a set of items. Each item has a key. The dictionary supports the following operations: • insert(item): add item to set • delete(item): remove item from set • search(key): return item with key if it exists We assume that items have distinct keys (or that inserting new ones clobbers old ones). This problem is easier than predecessor/successor problems solved in previous lecture (by van Emde Boas trees, or by AVL/2-3 trees/skip lists). Hashing from 6.006 Goal: O(1) time per operation and O(n) space complexity. Definitions: • u = number of keys over all possible items • n = number of keys/items currently in the table • m = number of slots in the table 1 Lecture 8 6.046J Spring 2015 Hashing Solution: hashing with chaining Assuming simple uniform hashing, Pr {h(k1 ) = h(k2 )} = k1 =k2 1 m n is called load factor. The we achieve Θ(1 + α) time per operation, where α = m downside of the algorithm is that it requires assuming input keys are random, and it only works in average case, like basic quicksort. Today we are going to remove the unreasonable simple uniform hashing assumption. Etymology The English ‘hash’ (1650s) means “cut into small pieces”, which comes from the French ‘hacher‘ which means “chop up”, which comes from the Old French ‘hache’ which means “axe” (cf. English ‘hatchet’). Alternatively, perhaps they come from Vulcan ‘la’ash’, which means “axe”. (R.I.P. Leonard Nimoy.) Universal Hashing The idea of universal hashing is listed as following: • choose a random hash function h from H • require H to be a universal hashing family such that Pr {h(k) = h(k' )} ≤ h∈H . 2 1 for all k = k ' m Lecture 8 6.046J Spring 2015 Hashing • now we just assume h is random, and make no assumption about input keys. (like Randomized Quicksort) Theorem: For n arbitrary distinct keys and random h ∈ H, where H is a universal hashing family, E[ number of keys colliding in a slot ] ≤ 1 + α where α = 1 if h(ki ) = h(kj ) Proof : Consider keys k1 , k2 , . . . , kn . Let Ii,j = 0 otherwise n m . Then we have E[Ii,j ] = Pr{Ii,j = 1} = Pr{h(ki ) = h(kj )} 1 ≤ for any j 6= i m � E[# keys hashing to the same slot as ki ] = E n L (1) � Ii,j j=1 = n L E[Ii,j ] (linearity of expectation) j=1 = L E[Ii,j ] + E[Ii,i ] 6 j=i ≤ n +1 m (2) D From the above theorem, we know that Insert, Delete, and Search all take O(1+α) expected time. Here we give some examples of universal hash functions. All hash functions: H = {all hash functions h : {0, 1, . . . , u − 1} → {0, 1, . . . , m − 1}}. Apparently, H is universal, but it is useless. On one hand, storing a single hashing function h takes log(mu ) = u log(m) bits » n bits. On the other hand, we would need to precompute u values, which takes Ω(u) time. Dot-product hash family: Assumptions • m is a prime 3 Lecture 8 6.046J Spring 2015 Hashing • u = mr where r is an integer In real cases, we can always round up m and u to satisfy the above assumptions. Now let’s view keys in base m: k = hk0 , k1 , . . . , kr−1 i. For key a = ha0 , a1 , a2 , . . . , ar−1 i, define ha (k) = a · k mod m (dot product) = r−1 X (3) ai ki mod m i=0 Then our hash family is H = {ha | a ∈ {0, 1, . . . , u − 1}} Storing ha ∈ H requires just storing one key, which is a. In the word RAM model, manipulating O(1) machine words takes O(1) time and “objects of interest” (here, keys) fit into a machine word. Thus computing ha (k) takes O(1) time. Theorem: Dot-product hash family H is universal. 6 k 0 . They must differ in some digits. Say kd = 6 kd0 . Proof : Take any two keys k = Define not d = {0, 1, . . . , r − 1} \ {d}. Now we have ( r−1 ) r−1 X X Pr{ha (k) = ha (k 0 )} = Pr ai ki = ai ki0 (mod m) a a = Pr ( i=0 X a i=0 ) ai ki + ad kd = i=d 6 X ai ki0 + ad kd0 (mod m) i=d 6 ( ) X = Pr a ai (ki − ki0 ) + ad (kd − kd0 ) = 0 (mod m) i=d 6 ( ) = Pr ad = −(kd − kd0 )−1 a X ai (ki − ki0 ) (mod m) i=d 6 (4) (m is prime ⇒ Zm has multiplicative inverses) = E [Pr{ad = f (k, k 0 , anot d )}] anot d ad X (= Pr{anot d = x}Pr{ad = f (k, k 0 , x)}) ad x  = E anot = d 1 m  1 m  4 Lecture 8 Hashing 6.046J Spring 2015 Another universal hash family from CLRS: Choose prime p ≥ u (once). Define hab (k) = [(ak + b) mod p)] mod m. Let H = {hab | a, b ∈ {0, 1, . . . , u − 1}}. Perfect Hashing Static dictionary problem: Given n keys to store in table, only need to support search(k). No insertion or deletion will happen. Perfect hashing: [Fredman, Komlós, Szemerédi 1984] • polynomial build time with high probability (w.h.p.) • O(1) time for search in worst case • O(n) space in worst case Idea: 2-level hashing The algorithm contains the following two major steps: Step 1: Pick h1 : {0, 1, . . . , u − 1} → {0, 1, . . . , m − 1} from a universal hash family for m = Θ(n) (e.g., nearby prime). Hash all items with chaining using h1 . 5 Lecture 8 Hashing 6.046J Spring 2015 Step 2: For each slot j ∈ {0, 1, . . . , m − 1}, let lj be the number of items in slot j. lj = |{i | h(ki ) = j}|. Pick h2,j : {0, 1, . . . , u − 1} → {0, 1, . . . , mj } from a universal hash family for lj2 ≤ mj ≤ O(lj2 ) (e.g., nearby prime). Replace chain in slot j with hashing-with-chaining using h2,j . The space complexity is O(n + to add two more steps: Step 1.5: If Lm−1 j=0 Lm−1 j=0 lj2 ). In order to reduce it to O(n), we need lj2 > cn where c is a chose constant, then redo Step 1. Step 2.5: While h2,j (ki ) = h2,j (ki' ) for any i 6= i' , j, repick h2,j and rehash those lj . The above two steps guarantee that there are no collisions at second level, and the space complexity is O(n). As a result, search time is O(1). Now let’s look at the build time of the algorithm. Both Step 1 and Step 2 are O(n). How about Step 1.5 and Step 2.5? For Step 2.5, L Pr{h2,j (ki ) = h2,j (ki' ) for some i = 6 i' } ≤ Pr{h2,j (ki ) = h2,j (ki' )} (union bound) h2,j i=i 6 , h2,j � � 1 lj ≤ · 2 2 lj 1 < 2 (5) As a result, each trial is like a coin flip. If the outcome is “tail”, we move to the next step. By Lecture 7, we have E[#trials] ≤ 2 and #trials = O(log n) w.h.p. By a Chernoff bound, lj = O(log n) w.h.p., so each trial takes O(log n) time. Because we have to do this for each j, the total time complexity is O(log n) · O(log n) · O(n) = O(n log2 n) w.h.p. 6 Lecture 8 6.046J Spring 2015 Hashing ( For Step 1.5, we define Ii,i0 = 1 if h(ki ) = h(ki0 ) 0 otherwise . Then we have "m−1 # " n n # X XX E lj2 = E Ii,i0 j=0 = i=1 i0 =1 n n XX E[Ii,i0 ] (linearity of expectation) i=1 i0 =1 (6)   n 1 ≤n+2 · 2 m = O(n) because m = Θ(n) By Markov inequality, we have (m−1 ) Pm−1 2 X 1 j=0 lj Pr lj2 ≤ cn ≤ ≤ h1 cn 2 j=0 for a sufficiently large constant c. By Lecture 7, we have E[#trials] ≤ 2 and #trials = O(log n) w.h.p. As a result, Step 1 and Step 1.5 combined takes O(n log n) time w.h.p. 7