The Power of Two Choices with Simple Tabulation

The power of two choices is a classic paradigm used for assigning m balls to n bins. When placing a ball we pick two bins according to some hash functions h0 and h1, and place the ball in the least full bin. It was shown by Azar et al. [STOC’94] that for m “ Opnq with perfectly random hash functions this scheme yields a maximum load of lg lg n ` Op1q with high probability. The two-choice paradigm has many applications in e.g. hash tables and on-line assignment of tasks to servers. In this paper we investigate the two-choice paradigm using the very efficient simple tabulation hashing scheme. This scheme dates back to Zobrist in 1970, and has since been studied by Pǎtraşcu and Thorup [STOC’11]. Pǎtraşcu and Thorup claimed without proof that simple tabulation gives an expected maximum load of Oplog log nq. We im-prove their result in two ways. We show that the expected maximum load, when placing m “ Opnq balls into two tables of n bins, is at most lg lg n ` Op1q. Furthermore, unlike with fully random hashing, we show that with simple tabulation hashing, the maximum load is not bounded by lg lg n`Op1q, or even p1 ` op1qq lg lg n with high probabil-ity. However, we do show that it is bounded by Oplog log nq with high probability, which is only a constant factor worse than the fully ran-dom case. Previously, such bounds have required Ωplog nq-independent hashing, or other methods that require ωp1q computation time. Our analysis relies on classifying the dependencies between keys when using simple tabulation. We show, as a corollary, that these methods can be used to give good bounds for any constant moment