Good Hash Tables & Multiple Hash Functions

Hash Function Performance

Let x_k(t) be the fraction of the m buckets that hold at least k keys when there are tm keys in the hash table. Note that x₀(t) always equals 1. Consider now what happens when you add one more key. The "time" t increases to t+1/m. The value of x_k(t) increases by 1/m if the new key lands in a bin with exactly k-1 keys already there. Specifically, x_k(t) increases if and only if both choices have at least k-1 keys but both choices do not have at least k keys. The probability that both choices have at least j keys is (x_j(t))², so the probability that x_k(t) increases is (x_k-1(t))²-(x_k(t))². You can express this result as in Figure 3(a): that is, the expected change in x_k when a new key arrives is just ((x_k-1(t))²- (x_k(t))²)/m. You can rewrite the equation, as in Figure 3(b). The left side looks much like the equation for a derivative, and if m is large, a good approximation for the aforementioned equation is in Figure 3(c).

The analysis therefore yields a family of differential equations that accurately describe the behavior of the x_k(t) when the number of buckets m and the number of keys n are reasonably large, and n=mt for some constant t. By calculating the solution to the family numerically, you obtain Table 2. Using similar methods, you can develop families of differential equations that lead to Tables 3 and 4.