The Power of Simple Tabulation Hashing

Randomized algorithms are often enjoyed for their simplicity, but the hash functions used to yield the desired theoretical guarantees are often neither simple nor practical. Here we show that the simplest possible tabulation hashing provides unexpectedly strong guarantees. The scheme itself dates back to Zobrist in 1970 who used it for game playing programs. Keys are viewed as consisting of c characters. We initialize c tables H 1, ..., H c mapping characters to random hash codes. A key x = ( x 1 , ..., x c ) is hashed to H 1 x 1 ⊕ ⋯ ⊕ H c x c , where ⊕ denotes bit-wise exclusive-or. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, for example, Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.