96 COMMUNICATIONS OF THE ACM | JULY 2017 | VOL. 60 | NO. 7
in the experiments from Ref., 21 for 32-bit keys, simple tabulation with four character lookups took less than 5 ns, whereas
a single memory lookup in a 4MB table took more than 120 ns.
Character lookups were thus about 100× faster than general
lookups. In fact, simple tabulation is three-independent
and in experiments from Ref., 21 it was found to be more than
three times faster than three-independent hashing implemented as in Equation ( 1) by a degree 2 polynomial tuned
over the Mersenne prime field . Because cache is so critical to computation, most computers are configured with a
very fast cache, and this is unlikely to change.
Usually, it is not a problem to fill the character tables
h0, ..., hc− 1 with random numbers, for example, downloading
them from http://random.org which is based on atmospheric noise. However, for the theory presented here, it
would suffice to fill them with a (lg u)-independent pseudo-random number generator (PRG). The character tables just
need to point to an area in memory with random bits, and
this could be shared across many applications. One could
even imagine computers configured with random bits in
some very fast read-only memory allowing parallel access
from multiple cores.
In Ref., 21 simple tabulation hashing was proved to have
much more po wer than suggested by its three-independence.
This included fourth moment bounds, minwise hashing,
random graph properties necessary in cuckoo hashing, 19
and Chernoff bounds for distributing balls into many bins.
The details are described in the following subsections.
2. 1. Concentration bounds
First, we consider using simple tabulation hashing to distribute n balls into m = 2r bins, that is, assuming that the
balls have keys from [u], we are using a simple tabulation
hash function h : [u] → [m]. In a hash table with chaining,
the balls in a bin would be stored in a linked list.
Consider the number X of balls landing in a given bin.
We have µ = E[X] = n/m. Pa ˇtras˛cu and Thorup21 have proved
that, w.h.p., we get a Chernoff-style concentration on X. First
recall the classic Chernoff bounds16, section 4 for full randomness. On the upper bound side, we have16, Theorem 4. 1
The corresponding probabilistic lower bound16, Proof of Theorem 4. 2
forδ ≤ 1 is
We note that in connection with hash tables, we are often
not just interested in a given bin, but rather we care about
the bin that a specific query ball lands in. This is why the
hash of the query ball is involved in the theorem below with
Chernoff-style bounds for simple tabulation.
Theorem 1 (Pa ˇtras˛cu and Thorup21). Consider hash-
ing n balls into m ≥ n1−1/(2c) bins by simple tabulation (recall
that c = O( 1) is the number of characters). Define X as the
number of regular balls that hash into a given bin or a bin cho-
sen as a function of the bin h(q) of an additional query ball q.
Let . The following probability bounds hold for
any constant γ:
With m ≤ n bins (incl. m < n1−1/(2c)), every bin gets
balls with probability 1 − n−γ.
Contrasting the standard Chernoff bounds, we see
that Equations ( 5) and ( 6) in Theorem 1 can only provide
polynomially small probability, that is, at least m−γ for any
desired constant γ. This corresponds to if we had Θ(log m)-
independence in the Chernoff bound from Ref. 23 In addition,
Theorem 2 (Dahlgaard et al. 7). With the same setup for
simple tabulation as in Theorem 1, for any constant k = O( 1),
Since kth moment bounds is one of the main ways
k-independence is used, it is nice that they are achieved by simple tabulation which is only three-independent. As an example,
the classic AMS sketches1 were first implemented with four-independent hashing, but Braverman et al. 3 noticed that
only a fourth moment bound is needed. They proved that
simple tabulation suffices by proving Theorem 2 for k = 4.
2. 2. Linear probing
Theorem 1 is used in Ref. 21 to get bounds for linear probing.
Linear probing is a classic implementation of hash tables. It
uses a hash function h to map a set of n keys into an array of
size m. When inserting x, if the desired location h(x) ∈ [m] is
already occupied, the algorithm scans h(x) + 1, h(x) + 2, . . ., m − 1,
0, 1, . .. until an empty location is found, and places x there.
The query algorithm starts at h(x) and scans until it either
finds x, or runs into an empty position, which certifies that x is
not in the hash table. When the query search is unsuccessful,
that is, when x is not stored, the query algorithm scans exactly
the same locations as an insert of x. A general bound on the
query time is hence also a bound on the insertion time.
This classic data structure is one of the oldest and
most popular implementations of hash tables, due to its