Abstract
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.
| Original language | English |
|---|---|
| Article number | 14 |
| Journal | Association for Computing Machinery. Journal |
| Volume | 59 |
| Issue number | 3 |
| Number of pages | 50 |
| ISSN | 0004-5411 |
| DOIs | |
| Publication status | Published - Jun 2012 |