Practice Problem Set 2 Solutions
Suppose that we use hash chaining for a hash table with \(n\) keys, but with a hash table that is too small, so that the load factor \(\alpha\) is \(3\ln n\). (This will cause operations on the hash table to take logarithmic time rather than constant time.) Prove that, for a random hash function and for this load factor, there is only \(o(1)\) probability of a hash chain existing with size at least \(6\ln n\).
Hint: Use the Chernoff bound for the probability of having at least \(6\ln n\) elements in a single cell. Then, use the union bound to combine the Chernoff bounds from all the cells.
Solution: We first analyze the probability that a fixed cell \(C\) of the table has a big hash chain of size at least \(6\ln n\). To apply Chernoff, we define \(n\) random variables, one per key, that are 1 if the key maps to \(C\) and 0 if it does not. Then the sum of these 0–1 variables, \(X\), is the size of the hash chain in cell \(C\), and \(E[X]=3\ln n\). We want to bound the probability that \(X\) is at least twice as large as its expected value, so the factor \(c\) in the Chernoff bound is two. By the Chernoff bound, the probability that \(X\) is at least twice as large as its expectation is at most \[\left(\frac{e^{c-1}}{c^c}\right)^{E[X]}=\left(\frac{e}{4}\right)^{3\ln n}.\] Here it's helpful to remember that \(a^{b\ln c}=c^{b\ln a}\). (To see why, take the logarithm of both sides.) So the probability is at most \[n^{3\log\tfrac{e}{4}}\approx n^{-1.159}.\] This was the probability that a single cell is too big; there are \(n/(3\ln n)\) cells, so when we take the union bound, we multiply this probability by \(n/(3\ln n)\). Let's be a little sloppy and multiply by the bigger number \(n\); the result will still be a valid upper bound on the probability. This gives a probability of a too-big cell existing of at most \(n^{-0.159}=o(1)\).
Suppose that we want a very small 2-independent hash function, one that maps three different inputs \(x\), \(y\), and \(z\) to two outputs \(0\) or \(1\).
One possible choice for a 2-independent family \(H\) would be the family of all functions from these three inputs to these two outputs. How many functions are in \(H\), for this choice?
Solution: \(2^3=8\).
Find a different choice of \(H\) that is also 2-independent, but has fewer functions than the family of all functions. Express your choice as a table, where the rows are the functions in \(H\) and each column lists the values of each function for one of the three inputs. How many functions are in your family?
Solution: Four functions: the set of all functions from \(x\) and \(y\) to the two outputs, with \(f(z)=f(x)+ f(y)\pmod{2}\).
\(f(x)\) \(f(y)\) \(f(z)\) Function 1: 0 0 0 Function 2: 0 1 1 Function 3: 1 0 1 Function 4: 1 1 0
In Python, there is a function hash() built into the language that can map most types of object to an integer. For an integer \(x\), the value of hash(\(x\)) is just \(x\) mod \(2^{31}-1\), so for all integers smaller than \(2^{31}-1\), the hash of \(x\) is just \(x\) itself. Other types of objects have less-predictable hash values. The hash value, computed in this way, is used as the hash function for dictionaries by taking the result modulo the dictionary size. Python uses open addressing, but not linear probing, for its dictionaries.
If you know or can predict the size \(s\) of a hash table, describe how to choose \(s/2\) numbers that will all collide with each other.
Solution: choose the numbers \(i\cdot s\) for \(i=0,1,\dots,s/2-1\).
What is the average time per operation to insert all these numbers into a linear-probing hash table, with this hash function? (Calculate the total time, using \(O\)-notation, and then divide by the number of insertions. Do not use the analysis of linear probing with random hash functions. You can assume that the size of the table is \(s\) throughout the sequence of insertions.)
Solution: \(O(s)\), or really better using theta-notation \(\Theta(s)\).
Starting from the cuckoo hash table shown on the lecture note slide “Graph view of cuckoo state”, describe the sequence of operations that would be performed if we insert a new key \(K\) with value \(5\), \(h_1(K)=3\), and \(h_2(K)=1\), and show what the graph view of the hash table looks like after the insertion is complete. Which of the cases listed in the slide “Graph view of key insertion” describes this insertion?
Solution: Inserting \(K\) with hash values 3 and 1 performs the following steps:
- Place \(K\) in cell A[3], evicting \(Z\)
- Place \(Z\) in cell A[2], evicting \(X\)
- Place \(X\) in cell A[4], evicting \(Y\)
- Place \(Y\) in cell A[3], evicting \(K\)
- Place \(K\) in cell A[1]
The updated graph reverses the arrows in the triangle of cells A[2], A[3], and A[4], and adds an edge from A[1] to A[3]:
This is the case that \(h_1(K)\) was in a pseudotree (the one shown on the graph view slide) and \(h_2(K)\) was in a tree (a single-vertex tree containing cell A[1]).