The power of simple tabulation hashing

Mihai Patrascu; Mikkel Thorup

doi:10.1145/1993636.1993638

The power of simple tabulation hashing

26 Citations (Scopus)

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_c) is hashed to T₁[x₁] ⊕ ... ⊕ T_c[x_c], where ⊕ denotes xor. 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.

Original language	English
Title of host publication	Proceedings of the 43rd annual ACM symposium on Theory of computing
Number of pages	10
Publisher	Association for Computing Machinery
Publication date	2011
Pages	1-10
ISBN (Print)	978-1-4503-0691-1
DOIs	https://doi.org/10.1145/1993636.1993638
Publication status	Published - 2011
Externally published	Yes
Event	43rd ACM Symposium on Theory of Computing - San Jose, California, United States Duration: 6 Jun 2011 → 8 Jun 2011 Conference number: 43

Conference

Conference	43rd ACM Symposium on Theory of Computing
Number	43
Country/Territory	United States
City	San Jose, California
Period	06/06/2011 → 08/06/2011

Access to Document

10.1145/1993636.1993638

https://dl.acm.org/doi/pdf/10.1145/1993636.1993638

Cite this

@inproceedings{86d4ddc3f57a447192d6ab04d398de99,

title = "The power of simple tabulation hashing",

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 T1, ..., Tc mapping characters to random hash codes. A key x = (x1, ..., xc) is hashed to T1[x1] ⊕ ... ⊕ Tc[xc], where ⊕ denotes xor. 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.",

author = "Mihai Patrascu and Mikkel Thorup",

year = "2011",

doi = "10.1145/1993636.1993638",

language = "English",

isbn = "978-1-4503-0691-1",

pages = "1--10",

booktitle = "Proceedings of the 43rd annual ACM symposium on Theory of computing",

publisher = "Association for Computing Machinery",

note = "43rd ACM Symposium on Theory of Computing ; Conference date: 06-06-2011 Through 08-06-2011",

}

TY - GEN

T1 - The power of simple tabulation hashing

AU - Patrascu, Mihai

AU - Thorup, Mikkel

N1 - Conference code: 43

PY - 2011

Y1 - 2011

N2 - 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 T1, ..., Tc mapping characters to random hash codes. A key x = (x1, ..., xc) is hashed to T1[x1] ⊕ ... ⊕ Tc[xc], where ⊕ denotes xor. 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.

AB - 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 T1, ..., Tc mapping characters to random hash codes. A key x = (x1, ..., xc) is hashed to T1[x1] ⊕ ... ⊕ Tc[xc], where ⊕ denotes xor. 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.

U2 - 10.1145/1993636.1993638

DO - 10.1145/1993636.1993638

M3 - Article in proceedings

SN - 978-1-4503-0691-1

SP - 1

EP - 10

BT - Proceedings of the 43rd annual ACM symposium on Theory of computing

PB - Association for Computing Machinery

T2 - 43rd ACM Symposium on Theory of Computing

Y2 - 6 June 2011 through 8 June 2011

ER -

The power of simple tabulation hashing

Abstract

Conference

Access to Document

Fingerprint

Cite this