The power of two choices with simple tabulation

The power of two choices is a classic paradigm for load balancing when assigning m balls to n bins. When placing a ball, we pick two bins according to two hash functions ho and h1, and place the ball in the least loaded bin. Assuming fully random hash functions, when m = O(n), Azar et al. [STOC'94] proved that the maximum load is lglgn + 0(1) with high probability.

No such bound was known with a hash function implementable in constant time. In this paper, we investigate the power of two choices when the hash functions ho and h1 are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM'12], PǍtraşcu and Thorup claimed that the expected maximum load with simple tabulation is O(lglgn).

This did not include any high probability guarantee, so the load balancing was not yet to be trusted. Here, we show that with simple tabulation, the maximum load is O(lglgn) with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by lglgn + 0(l), or even (1 + o(l)) lglgn with high probability.

Finally, we show that the expected maximum load is lglgn + 0(1), just like with fully random hashing.