The Power of Simple Tabulation Hashing

2010/11/23 by Patrascu, Mihai, Thorup, Mikkel · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1011.5200

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 Carter and Wegman (STOC'77). Keys are viewed as consisting of c characters. We initialize c tables T₁, ..., T_c mapping characters to random hash codes. A key x=(x₁, ..., x_q) is hashed to T₁[x₁] xor ... xor T_c[x_c]. While this scheme is not even 4-independent, we show that it provides many of the guarantees that are normally obtained via higher independence, e.g., Chernoff-type concentration, min-wise hashing for estimating set intersection, and cuckoo hashing.

Cited by

• Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck

Related

• Fast and Powerful Hashing using Tabulation
• Independence of Tabulation-Based Hash Classes
• Locally Uniform Hashing
• Approximately Minwise Independence with Twisted Tabulation
• A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits