HackerPapers

arXiv:1011.5200cs.DS

The Power of Simple Tabulation Hashing

Mihai Patrascu, Mikkel Thorup

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_1, ..., T_c mapping characters to random hash codes. A key x=(x_1, ..., x_q) is hashed to T_1[x_1] 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.

arXiv comments
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jul 2013 to Apr 2023.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Fibonacci Hashing: An optimization that the world forgot (2018) 1 comment

    • So here’s a paper where the author has run the experiment: https://arxiv.org/pdf/1011.5200.pdf And the answer is that the speed is comparable to other functions that however produce worse results.

      tinus_hnView on HNParent context

  2. Reversing Bits in C 1 comment

    • how does it compare to, say, tabulation as in Mihai Patrascu, Mikkel Thorup: The Power of Simple Tabulation Hashing. J. ACM 59(3): 14 (2012) http://doi.acm.org/10.1145/2220357.2220361 (free version: http://arxiv.org/abs/1011.5200) or also Mihai Patrascu, Mikkel Thorup: Twisted…

      csomView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.