6.046J Lecture 10: Hashing and Amortization

Lecture 10 Hashing and Amortization Supplemental reading in CLRS: Chapter 11; Chapter 17 intro; Section 17.1 10.1 Arrays and Hashing Arrays are very useful. The items in an array are statically addressed, so that inserting, deleting, and looking up an element each take O(1) time. Thus, arrays are a terrific way to encode functions © ª 1, . . . , n → T, where T is some range of values and n is known ahead of time. For example, taking T = {0, 1}, we find that an array A of n bits is a great way to store a subset of {1, . . . , n}: we set A[i] = 1 if and only if i is in the set (see Figure 10.1). Or, interpreting the bits as binary digits, we can use an n-bit array to store an integer between 0 and 2n − 1. In this way, we will often identify the set {0, 1}n with the set {0, . . . , 2n − 1}. What if we wanted to encode subsets of an arbitrary domain U, rather than just {1, . . . , n}? Or to put things differently, what if we wanted a keyed (or associative) array, where the keys could be arbitrary strings? While the workings of such data structures (such as dictionaries in Python) are abstracted away in many programming languages, there is usually an array-based solution working behind the scenes. Implementing associative arrays amounts to finding a way to turn a key into an array index. Thus, we are looking for a suitable function U → {1, . . . , n}, called a hash function. Equipped with this function, we can perform key lookup: ª array lookup hash function © U −−−−−−−−−→ 1, . . . , n −−−−−−−−−→ T (see Figure 10.2). This particular implementation of associative arrays is called a hash table. There is a problem, however. Typically, the domain U is much larger than {1, . . . , n}. For any hash function h : U → {1, . . . , n}, there is some i such that at least |Un | elements are mapped to i. The set A: 0 1 0 1 1 0 0 1 0 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 © ª © ª Figure 10.1. This 12-bit array encodes the set 2, 4, 5, 8, 11 ⊆ 1, . . . 12 . 1 2 ­ key3 , val3 ® h key1 = 5 ­ key1 , val1 ® ¡ ¢ h key2 = 6 ­ key2 , val2 ® ¡ ¢ h key3 = 3 4 ¡ ¢ 7 Figure 10.2. An associative array with keys in U and values in T can be implemented as a (U × T)-valued array equipped with a hash function h : U → {1, . . . , n}. h−1 (i) of all elements mapped to i is called the load on i, and when this load contains more than one of the keys we are trying to store in our hash table we say there is a collision at i. Collisions are problem for us—if two keys map to the same index, then what should we store at that index? We have to store both values somehow. For now let’s say we do this in the simplest way possible: storing at each index i in the array a linked list (or more abstractly, some sort of bucket-like object) ¡ ¢ consisting of all values whose keys are mapped to i. Thus, lookup takes O h−1 (i) time, which may be poor if there are collisions at i. Rather than thinking about efficient ways to handle collisions,1 let’s try to reason about the probability of having collisions if we choose our hash functions well. 10.2 Hash Families Without any prior information about which elements of U will occur as keys, the best we can do is to choose our hash function h at random from a suitable hash family. A hash family on U is a set H of functions U → {1, . . . , n}. Technically speaking, H should come equipped with a probability distribution, but usually we just take the uniform distribution on H , so that each hash function is equally likely to be chosen. If we want to avoid collisions, it is reasonable to hope that, for any fixed x1 , x2 ∈ U (x1 6= x2 ), the values h(x1 ) and h(x2 ) are completely uncorrelated as h ranges through the sample space H . This leads to the following definition: Definition. A hash family H on U is said to be universal if, for any x1 , x2 ∈ U (x1 6= x2 ), we have £ ¤ Pr h(x1 ) = h(x2 ) ≤ n1 . h∈H 1 If you are expecting lots of collisions, a more efficient way to handle things is to create a two-layered hash table, where each element of A is itself a hash table with its own, different hash function. In order to have collisions in a two-layer hash table, the same pair of keys must collide under two different hash functions. If the hash functions are chosen well (e.g., if the hash functions are chosen randomly), then this is extremely unlikely. Of course, if you want to be even more sure that collisions won’t occur, you can make a three-layer hash table, and so on. There is a trade-off, though: introducing unnecessary layers of hashing comes with a time and space overhead which, while it may not show up in the big-O analysis, makes a difference in practical applications. Lec 10 – pg. 2 of 7 Similarly, H is said to be ²-universal if for any x1 6= x2 we have £ ¤ Pr h(x1 ) = h(x2 ) ≤ ². h∈H The consequences of the above hypotheses with regard to collisions are as follows: Proposition 10.1. Let H be a universal hash family on U. Fix some subset S ⊆ U and some element x ∈ U. Pick h ∈ H at random. The expected number of elements of S that map to h(x) is at most 1 + |Sn | . In symbols, h¯ ¡ ¢¯i |S | E ¯ h−1 h(x) ¯ ≤ 1 + . h∈H n If H is ²-universal rather than universal, then the same holds when 1 + |Sn | is replaced by 1 + ² |S |. Proof. For a proposition ϕ with random parameters, let I ϕ be the indicator random variable which equals 1 if ϕ is true and equals 0 otherwise. The fact that H is universal means that for each x0 ∈ U \ { x} we have £ ¤ 1 E I h(x)=h(x0 ) ≤ . h∈H n Thus by the linearity of expectation, we have   h¯ i X ¯ ¡ ¢   E ¯ h−1 h(x) ∩ S ¯ = I x∈S + E  I h(x)=h(x0 )  h∈H = I x∈ S + X x0 ∈ S x0 6= x x0 ∈ S x0 6= x E h∈H £ I h(x)=h(x0 ) ¤ ≤ 1 + |S | · n1 . The reasoning is almost identical when H is ²-universal rather than universal. Corollary 10.2. For a hash table in which the hash function from a universal family, ³ is chosen ´ |S | insertion, deletion, and lookup have expected running time O 1 + n , where S ⊆ U is the set of keys which actually occur. If instead the hash family is ²-universal, then the operations have expected ¡ ¢ running time O 1 + ² |S | . Corollary 10.3. Consider a hash table of size n with keys in U, whose hash function is chosen from a universal hash family. Let S ⊆ U be the set of keys which actually occur. If |S | = O(n), then insertion, deletion, and lookup have expected running time O(1). Let H be a universal hash family on U. If |S | = O(n), then the expected load on each index is O(1). Does this mean that a typical hash table has O(1) load at each index? Surprisingly, the answer is no, even when the hash function is chosen well. We’ll see this below when we look at examples of universal hash families. Examples 10.4. © ª 1. The set of all functions h : U → 1, . . . , n is certainly universal. In fact, we could not hope to get any more balanced than this: Lec 10 – pg. 3 of 7 • For any x ∈ U, the random variable h(x) (where h is chosen at random) is uniformly dis© ª tributed on the set 1, . . . , n . • For any pair x1 6= x2 , the random variables h(x1 ), h(x2 ) are independent. In fact, for ¡ ¢ any finite subset { x1 , . . . , xk } ⊆ U, the tuple h(x1 ), . . . , h(xk ) is uniformly distributed on © ªk 1, . . . , n . ¢ ¡ The load on each index i is a binomial random variable with parameters |S | , n1 . Fact. When p is small and N is large enough that N p is moderately sized, the binomial distribution with parameters (N, p) is approximated by the Poisson distribution with parameter N p. That is, if X is a binomial random variable with parameters (N, p), then £ ¤ (N p)k − N p Pr X = k ≈ e k! (k ≥ 0). In our case, N = |S | and p = n1 . Thus, if L i is the load on index i, then ³ £ ¤ Pr L i = k ≈ ´ |S | k n −|S |/n k! e . For example, if |S | = n, then £ ¤ Pr L i = 0 ≈ e−1 ≈ 0.3679, £ ¤ Pr L i = 1 ≈ e−1 ≈ 0.3679, £ ¤ Pr L i = 2 ≈ 21 e−1 ≈ 0.1839, .. . Further calculation shows that, when |S | = n, we have · ¸ µ ¶ lg n E max L i = Θ . 1≤ i ≤ n lg lg n ³ ´ lg n Moreover, with high probability, max L i does not exceed O lg lg n . Thus, a typical hash table with |S | = n and h chosen uniformly from the set of all functions looks like Figure 10.3: about 37% of the buckets empty, about 37% of the buckets having one element, ³ and´ about 26% of the lg n buckets having more than one element, incuding some buckets with Θ lg lg n elements. 2. In Problem Set 4 we considered the hash family © ª H = h p : p ≤ k and p is prime , © ª © ª where h p : 0, . . . , 2m − 1 → 0, . . . , k − 1 is the function h p (x) = x mod p. In Problem 4(a) you proved that, for each x 6= y, we have £ ¤ m ln k Pr h p (x) = h p (y) ≤ . p k Lec 10 – pg. 4 of 7 1 2 3 4 . . . Maximum load = Θ ³ lg n lg lg n ´ . . . n Figure 10.3. A typical hash table with |S | = n and h chosen uniformly from the family of all functions U → {1, . . . , n}. 3. In Problem Set 5, we fixed a prime p and considered the hash family o n a ∈ Zm H = h~a : ~ p , where h~a : Zm p → Z p is the dot product h~a (~x) = ~x · ~ a= X xi a i (mod p). 4. In Problem Set 6, we fixed a prime p and positive integers m and k and considered the hash family n o H = h A : A ∈ Zkp×m , k where h A : Zm p → Z p is the function h A (~x) = A~x. 5. If H 1 is an ²1 -universal hash family of functions {0, 1}m → {0, 1}k and H 2 is an ²2 -universal hash family of functions {0, 1}k → {0, 1}` , then2 © ª H = H 2 ◦ H 1 = h2 ◦ h1 : h1 ∈ H 1 , h2 ∈ H 2 is an (²1 + ²2 )-universal hash family of functions {0, 1}m → {0, 1}` . To see this, note that for any x 6= x0 , the union bound gives £ ¤ Pr h 2 ◦ h 1 (x) = h 2 ◦ h 1 (x0 ) h 1 ∈H 1 h 2 ∈H 2 2 To fully specify H , we have to give not just a set but also a probability distribution. The hash families H and H 1 2 come with probability distributions, so there is an induced distribution on H 1 ×H 2 . We then equip H with the distribution induced by the map H 1 × H 2 → H , (h 1 , h 2 ) 7→ h 2 ◦ h 1 . You could consider this a mathematical technicality if you wish: if H 1 and H 2 are given uniform distributions (as they typically are), then the distribution on H 1 × H 2 is also uniform. The distribution on H need not be uniform, however: an element of H is more likely to be chosen if it can be expressed in multiple ways as the composition of an element of H 2 with an element of H 1 . Lec 10 – pg. 5 of 7 h ³ ´i = Pr h 1 (x) = h 1 (x0 ) or h 1 (x) 6= h 1 (x0 ) and h 2 ◦ h 1 (x) = h 2 ◦ h 1 (x0 ) h i h i ≤ Pr h 1 (x) = h 1 (x0 ) + Pr h 1 (x) 6= h 1 (x0 ) and h 2 ◦ h 1 (x) = h 2 ◦ h 1 (x0 ) ≤ ²1 + ²2 . In choosing the parameters to build a hash table, there is a tradeoff. Making n larger decreases the likelihood of collisions, and thus decreases the expected running time of operations on the table, but also requires the allocation of more memory, much of which is not even used to store data. In situations where avoiding collisions is worth the memory cost (or in applications other than hash tables, when the corresponding tradeoff is worth it), we can make n much larger than S. Proposition 10.5. Let H be a universal hash family U → {1, . . . , n}. Let S ⊆ U be the the set of keys ¡ ¢ that occur. Then the expected number of collisions is at most |S2 | · n1 . In symbols, " E h∈H # X x6= x0 ∈U I h(x)=h(x0 ) à ! |S | 1 ≤ · . 2 n ¡ ¢ Proof. There are |S2 | pairs of distinct elements in S, and each pair has probability at most causing a collision. The result follows from linearity of expectation. 1 n of Corollary 10.6. If n ≥ 100 |S |2 , then the expected number of collisions is less than 1/200, and the probability that a collision exists is less than 1/200. Proof. Apply the Markov bound. Thus, if n is sufficiently large compared to S, a typical hash table consists mostly of empty buckets, and with high probability, there is at most one element in each bucket. As we mentioned above, choosing a large n for a hash table is expensive in terms of space. While the competing goals of fast table operations and low storage cost are a fact of life if nothing is known about S in advance, we will see in recitation that, if S is known in advance, it is feasible to construct a perfect hash table, i.e., a hash table in which there are no collisions. Of course, the smallest value of n for which this is possible is n = |S |. As we will see in recitation, there are reasonably efficient algorithms to construct a perfect hash table with n = O (|S |). 10.3 Amortization What if the size of S is not known in advance? In order to allocate the array for a hash table, we must choose the size n at creation time, and may not change it later. If |S | turns out to be significantly greater than n, then there will always be lots of collisions, no matter which hash function we choose. Luckily, there is a simple and elegant solution to this problem: table doubling. The idea is to start with some particular table size n = O(1). If the table gets filled, simply create a new table of size 2n and migrate all the old elements to it. While this migration operation is costly, it happens infrequently enough that, on the whole, the strategy of table doubling is efficient. Let’s take a closer look. To simplify matters, let’s assume that only insertions and lookups occur, with no deletions. What is the worst-case cost of a single operation on the hash table? Lec 10 – pg. 6 of 7 • Lookup: O(1), as usual. • Insertion: O(n), if we have to double the table. Thus, the worst-case total running time of k operations (k = |S |) on the hash table is ¡ ¢ O (1 + · · · + k) = O k2 . The crucial observation is that this bound is not tight. Table doubling only happens after the second, fourth, eighth, etc., insertions. Thus, the total cost of k insertions is à ! lg Xk j k · O(1) + O 2 = O (k) + O (2k) = O (k) . j =0 Thus, in any sequence of insertion and lookup operations on a dynamically doubled hash table, the average, or amortized, cost per operation is O(1). This sort of analysis, in which we consider the total cost of a sequence of operations rather than the cost of a single step, is called amortized analysis. In the next lecture we will introduce methods of analyzing amortized running time. Lec 10 – pg. 7 of 7