Lecture Notes on

arXiv:1509.04549v3 [] 11 May 2017

Linear Probing with 5-Independent Hashing
Mikkel Thorup
May 12, 2017

Abstract
These lecture notes show that linear probing takes expected constant time if the hash function
is 5-independent. This result was first proved by Pagh et al. [STOC’07,SICOMP’09]. The simple
proof here is essentially taken from [Pǎtraşcu and Thorup ICALP’10]. We will also consider a
smaller space version of linear probing that may have false positives like Bloom filters.
These lecture notes illustrate the use of higher moments in data structures, and could be
used in a course on randomized algorithms.

1

k-independence

The concept of k-independence was introduced by Wegman and Carter [21] in FOCS’79 and has
been the cornerstone of our understanding of hash functions ever since. A hash function is a
random function h : [u] → [t] mapping keys to hash values. Here [s] = {0, . . . , s − 1}. We can also
think of a h as a random variable distributed over [t][u] . We say that h is k-independent if for any
distinct keys x0 , . . . , xk−1 ∈ [u] and (possibly non-distinct) hash values y0 , . . . , yk−1 ∈ [t], we have
Pr[h(x0 ) = y0 ∧ · · · ∧ h(xk−1 ) = yk−1 ] = 1/tk . Equivalently, we can define k-independence via two
separate conditions; namely,
(a) for any distinct keys x0 , . . . , xk−1 ∈ [u], the hash values h(x0 ), . . . , h(xk−1 ) are independent
random variables, that is, for
non-distinct) hash
i values y0 , . . . , yk−1 ∈ [t] and
h any (possibly
V
i ∈ [k], Pr[h(xi ) = yi ] = Pr h(xi ) = yi | j∈[k]\{i} h(xj ) = yj , and

(b) for any x ∈ [u], h(x) is uniformly distributed in [t].

As the concept of independence is fundamental to probabilistic analysis, k-independent hash functions are both natural and powerful in algorithm analysis. They allow us to replace the heuristic
assumption of truly random hash functions that are uniformly distributed in [t][u] , hence needing
u lg t random bits (lg = log2 ), with real implementable hash functions that are still “independent
enough” to yield provable performance guarantees similar to those proved with true randomness.
We are then left with the natural goal of understanding the independence required by algorithms.
Once we have proved that k-independence suffices for a hashing-based randomized algorithm,
we are free to use any k-independent hash function. The canonical construction of a k-independent

1

hash function is based on polynomials of degree k − 1. Let p ≥ u be prime. Picking random
a0 , . . . , ak−1 ∈ [p] = {0, . . . , p − 1}, the hash function is defined by:

(1)
h(x) = ak−1 xk−1 + · · · + a1 x + a0 mod p

If we want to limit the range of hash values to [t], we use h′ (x) = h(x) mod t. This preserves
requirement (a) of independence among k hash values. Requirement (b) of uniformity is close to
satisfied if p ≫ t. More precisely, for any key x ∈ [p] and hash value y ∈ [t], we get 1/t − 1/p <
Pr[h′ (x) = y] < 1/t + 1/p.
Sometimes 2-independence suffices. For example, 2-independence implies so-called universality
[5]; namely that the probability of two keys x and y colliding with h(x) = h(y) is 1/t; or close
to 1/t if the uniformity of (b) is only approximate. Universality implies expected constant time
performance of hash tables implemented with chaining. Universality also suffices for the 2-level
hashing of Fredman et al. [7], yielding static hash tables with constant query time.
At the other end of the spectrum, when dealing with problems involving n objects, O(lg n)independence suffices in a vast majority of applications. One reason for this is the Chernoff bounds
of [18] for k-independent events, whose probability bounds differ from the full-independence Chernoff bound by 2−Ω(k) . Another reason is that random graphs with O(lg n)-independent edges [2]
share many of the properties of truly random graphs.
The independence measure has long been central to the study of randomized algorithms. It
applies not only to hash functions, but also to pseudo-random number generators viewed as assigning hash values to 0, 1, 2, . . .. For example, [10] considers variants of QuickSort, [1] consider
the maximal bucket size for hashing with chaining, and [9, 6] consider Cuckoo hashing. In several
cases [1, 6, 10], it is proved that linear transformations x 7→ (ax + b) mod p do not suffice for
good performance, hence that 2-independence is not in itself sufficient.
Our focus in these notes is linear probing described below.

2

Linear probing

Linear probing is a classic implementation of hash tables. It uses a hash function h to map a
dynamic set S of keys into an array T of size t > |S|. The entries of T are keys, but we can also see
if an entry is “empty”. This could be coded, either via an extra bit, or via a distinguished nil-key.
We start with an empty set S and all empty locations. When inserting x, if the desired location
h(x) ∈ [t] is already occupied, the algorithm scans h(x) + 1, h(x) + 2, . . . , t − 1, 0, 1, . . . until an
empty location is found, and places x there. Below, for simplicity, we ignore the wrap-around from
t − 1 to 0, so a key x is always placed in a location i ≥ h(x).
To search a key x, the query algorithm starts at h(x) and scans either until it 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.
Deletions are slightly more complicated. The invariant we want to preserve is that if a key x is
stored at some location i ∈ [t], then all locations from h(x) to i are filled; for otherwise the above
search would not get to x. Suppose now that x is deleted from location i. We then scan locations
j = i + 1, i + 2, . . . for a key y with h(y) ≤ i. If such a y is found at location j, we move y to
location i, but then, recursively, we have to try refilling j, looking for a later key z with h(z) ≤ j.
The deletion process terminates when we reach an empty location d, for then the invariant says
2

that there cannot be a key y at a location j > d with h(y) ≤ d. The recursive refillings always
visit successive locations, so the total time spent on deleting x is proportional to the number of
locations from that of x and to the first empty location. Summing up, we have
Theorem 1 With linear probing, the time it takes to search, insert, or delete a key x is at most
proportional to the number of locations from h(x) to the first empty location.
With n the nunber of keys and t the size of the table, we call n/t the load of our table. We
generally assume that the load is bounded from 1, e.g., that the number of keys is n ≤ 23 t. With a
good distribution of keys, we would then hope that the number of locations from h(x) to an empty
location is O(1).
This classic data structure is one of the most popular implementations of hash tables, due to
its unmatched simplicity and efficiency. The practical use of linear probing dates back at least to
1954 to an assembly program by Samuel, Amdahl, Boehme (c.f. [12]). On modern architectures,
access to memory is done in cache lines (of much more than a word), so inspecting a few consecutive
values is typically only slightly worse that a single memory access. Even if the scan straddles a cache
line, the behavior will still be better than a second random memory access on architectures with
prefetching. Empirical evaluations [3, 8, 14] confirm the practical advantage of linear probing over
other known schemes, e.g., chaining, but caution [8, 20] that it behaves quite unreliably with weak
hash functions. Taken together, these findings form a strong motivation for theoretical analysis.
Linear probing was shown to take expected constant time for any operation in 1963 by
Knuth [11], in a report which is now regarded as the birth of algorithm analysis. This analysis, however, assumed a truly random hash function.
A central open question of Wegman and Carter [21] was how linear probing behaves with
k-independence. Siegel and Schmidt [17, 19] showed that O(lg n)-independence suffices for any
operation to take expected constant time. Pagh et al. [13] showed that just 5-independence suffices
for expected constant operation time. They also showed that linear transformations do not suffice,
hence that 2-independence is not in itself sufficient.
Pǎtraşcu and Thorup [16] proved that 4-independence is not in itself sufficient for expected
constant operation time. They display a concrete combination of keys and a 4-independent random
hash function where searching certain keys takes super constant expected time. This shows that
the 5-independence result of Pagh et al. [13] is best possible. In fact [16] provided a complete
understanding of linear probing with low independence as summarized in Table 1.
Considering loads close to 1, that is load (1 − ε), Pǎtraşcu and Thorup [15] proved that the
expected operation time is O(1/ε2 ) with 5-independent hashing, matching the bound of Knuth [11]
assuming true randomness. The analysis from [15] also works for something called simple tabulation
hashing that is we shall return to in Section 3.2.

3

Linear probing with 5-independence

Below we present the simplified version of the proof from [15] of the result from [13] that 5independent hashing suffices for expected constant time with linear probing. For simplicity, we
assume that the load is at most 23 . Thus we study a set S of n keys stored in a linear probing table
of size t ≥ 32 n. We assume that t is a power of two.
A crucial concept is a run R which is a maximal interval of filled positions. We have an empty
position before R, which means that all keys x ∈ S landing in R must also hash into R in the sense
3

Independence
Query time
Construction time

2
√
Θ( n)
Θ(n lg n)

3
Θ(lg n)
Θ(n lg n)

4
Θ(lg n)
Θ(n)

≥5
Θ(1)
Θ(n)

Table 1: Expected time bounds for linear probing with a poor k-independent hash function. The
bounds are worst-case expected, e.g., a lower bound for the query means that there is a concrete
combination of stored set, query key, and k-independent hash function with this expected search
time while the upper-bound means that this is the worst expected time for any such combination.
Construction time refers to the worst-case expected total time for inserting n keys starting from
an empty table.
that h(x) ∈ R. Also, we must have exactly r = |R| keys hashing to R since the position after R is
empty.
By Theorem 1 the time it takes for any operation on a key q is at most proportional to the
number of locations from h(x) to the first empty location. We upper bound this number by r + 1
where r is the length of the run containing h(q). Here r = 0 if the location h(q) is empty. We note
that the query key q might itself be in R, and hence be part of the run, e.g., in the case of deletions.
We want to give an expected upper bound on r. In order to limit the number of different events
leading to a long run, we focus on dyadic intervals: a (dyadic) ℓ-interval is an interval of length 2ℓ
of the form [i2ℓ , (i + 1)2ℓ ) where i ∈ [t/2ℓ ]. Assuming that the hashing maps S uniformly into [t],
we expect n2ℓ /t ≤ 23 2ℓ keys to hash into a given ℓ-interval I. We say that I is “near-full” if at least
3 ℓ
4 2 keys from S \ {q} hash into I. We claim that a long run implies that some dyadic interval of
similar size is near-full. More precisely,
Lemma 2 Consider a run R of length r ≥ 2ℓ+2 . Then one of the first four ℓ-intervals intersecting
R must be near-full.
Proof Let I0 , . . . , I3 be the first four ℓ-intervals intersecting R. Then I0 may only have its last
ℓ
end-point
S in R while I1 , . . . , I3 are contained in R since r ≥ 4 · 2 . In particular, this means that
ℓ
L=
i∈[4] Ii ∩ R has length at least 3 · 2 + 1.
But L is a prefix of R, so all keys landing in L must hash into L. Since L is full, we must have
at least 3 · 2ℓ + 1 keys hashing into L. Even if this includes the query key q, then we conclude that
one of our four intervals Ii must have 3 · 2ℓ /4 ≥ 34 2ℓ keys from S \ {q} hashing into it, implying
that Ii is near-full.
Getting back to our original question, we are considering the run R containing the hash of the
query q.
Lemma 3 If the run containing the hash of the query key q is of length r ∈ [2ℓ+2 , 2ℓ+3 ), then one
of the following 12 consecutive ℓ-intervals is near-full: the ℓ-interval containing h(q), the 8 nearest
ℓ-intervals to its left, and the 3 nearest ℓ-intervals to its right.
Proof Let R be the run containing h(q). To apply Lemma 2, we want to show that the first
four ℓ-intervals intersecting R has to be among the 12 mentioned in Lemma 3. Since the run R
containing h(q) has length less than 8 · 2ℓ , the first ℓ-interval intersecting R can be at most 8 before
the one containing h(q). The 3 following intervals are then trivially contained among the 12.
4

For our analysis, in the random choice of the hash function h, we first fix the hash value h(q) of
the query key q. Conditioned on this value of h(q), for each ℓ, let Pℓ be an upper-bound on the the
probability that any given ℓ-interval is near-full. Then the probability that the run containing h(q)
has length r ∈ [2ℓ+2 , 2ℓ+3 ) is bounded by 12Pℓ . Of course, this only gives us a bound for r ≥ 4.
We thus conclude that the expected length of the run containing the hash of the query key q is
bounded by
Thus, conditioned on the hash of the query key, for each ℓ we are interested in a bound Pℓ on
the probability that any given ℓ-interval is near-full. Then the probability that the run containing
h(q) has length r ∈ [2ℓ+2 , 2ℓ+3 ) is bounded by 12Pℓ . Of course, this only gives us a bound for r ≥ 4.
We thus conclude that the expected length of the run containing the hash of the query key q is
bounded by


log2 t
log2 t
X
X
3+
2ℓ+3 · 12Pℓ = O 1 +
2ℓ Pℓ  .
ℓ=0

ℓ=0

Combined with Theorem 1, we have now proved

Theorem 4 Consider storing a set S of keys in a linear probing table of size t where t is a power
of two. Conditioned on the hash of a key q, let Pℓ bound the probability that 34 2ℓ keys from S \ {q}
hash to any given ℓ-interval. Then the expected time to search, insert, or delete q is bounded by


log2 t
X
O 1 +
2ℓ Pℓ  .
ℓ=0

We note that Theorem 4 does not mention the size of S. However, as mentioned earlier, with a
uniform distribution, the expected number of elements hashing to an ℓ-interval is ≤ 2ℓ |S|/t, so for
Pℓ to be small, we want this expectation to be significantly smaller than 43 2ℓ . Assuming |S| ≤ 23 t,
the expected number is 32 2ℓ .
To get constant expected cost for linear probing, we are going to assume that the hash function
used is 5-independent. This means that no matter the hash value h(q) of q, conditioned on h(q),
the keys from S \ {q} are hashed 4-independently. This means that if Xx is the indicator variable
for a key x ∈ S \ {q} hashing to a given interval I, then the variables Xx , x ∈ S \ {q} are 4-wise
independent.

3.1

Fourth moment bound

The probabilistic tool we shall use here to analyze 4-wise independent variables isP
a 4th moment
bound. For i ∈ [n], let Xi ∈ [2] = {0, 1}, pi = Pr[Xi = 1] = E[Xi ], X =
i∈[n] Xi , and
P
2
2
2
2
µ = E[X] = i∈[n] pi . Also σi = Var[Xi ] = E[(Xi − pi ) ] = pi (1 − pi ) + (1 − pi )pi = pi − p2i . As
long as the Xi are pairwise independent, the variance of the sum is the sum of the variances, so we
define
X
X
σ 2 = Var[X] =
Var[Xi ] =
σi2 ≤ µ.
i∈[n]

i∈[n]

By Chebyshev’s inequality, we have
√
Pr[|X − µ| ≥ d µ] ≤ Pr[|X − µ| ≥ dσ] ≤ 1/d2 .
5

(2)

We are going to prove a stronger bound if the variables are 4-wise independent and µ ≥ 1 (and
which is only stronger if d ≥ 2).
P
Theorem 5 If the variables X0 , . . . , Xn−1 ∈ {0, 1} are 4-wise independent, X = i∈[n] Xi , and
µ = E[X] ≥ 1, then
√
Pr[|X − µ| ≥ d µ] ≤ 4/d4 .
Proof

Note that (X − µ) =
E[(X − µ)4 ] = E[

X
i

P

i∈[n] (Xi

− pi ). By linearity of expectation, the fourth moment is:

4
Xi − pi ] =

X

i,j,k,l∈[n]



E (Xi − pi )(Xj − pj )(Xk − pk )(Xl − pl ) .

Our goal is to get a good
 bound on the fourth moment.

Consider a term E (Xi − pi )(Xj − pj )(Xk − pk )(Xl − pl ) . The at most 4 distinct variables
are
independent. Suppose one of them, say, Xi , appears only
 completely

 once. By definition,
E (Xi − pi ) = 0, and since it is independent of the other factors, we get E (Xi − pi )(Xj − pj )(Xk −
pk )(Xl − pl ) = 0. We can therefore ignore all terms where any variable appears once. We may
therefore assume that each variables appears either twice or 4 times. In terms with variables
appearing twice, we have two indices a < b where a is assigned to two of i, j, k, l, while b is assigned
to the other two, yielding 42 combinations based on a < b. Thus we get
X


E[(X − µ)4 ] =
E (Xi − pi )(Xj − pj )(Xk − pk )(Xl − pl )
i,j,k,l∈[n]

 X
X 


 

4
4
=
E (Xi − pi ) +
E (Xa − pa )2 E (Xb − pb )2 .
2
i

a<b

Considering any multiplicity m = 2, 3, 4, 5, . . ., we have
E[(Xi − pi )m ] ≤ E[(Xi − pi )2 ] = σi2 .

(3)

To see this, note that Xi , pi ∈ [0, 1]. Hence |Xi − pi | ≤ 1, so (Xi − pi )m−2 ≤ 1, and therefore
(Xi − pi )m ≤ (Xi − pi )2 . Continuing our calculation, we get
 X
X 


 

4
4
4
E (Xi − pi ) +
E[(X − µ) ] =
E (Xa − pa )2 E (Xb − pb )2
2
i
a<b


X
X
4
σa2 σb2
≤
σi2 +
2
i
a<b
!2
X
2
2
σi
≤σ +3
i

= σ 2 + 3σ 4 .

(4)

Since σ 2 ≤ µ and µ ≥ 1, we get
E[(X − µ)4 ] ≤ µ + 3µ2 ≤ 4µ2 .
which is our desired bound on the fourth moment.
6

(5)

by Markov’s inequality,
√
√
√
Pr[|X − µ| ≥ d µ] = Pr[(X − µ)4 ≥ (d µ)4 ] ≤ E[(X − µ)4 ]/(d µ)4 ≤ 4/d4 .
This completes the proof of Theorem 5.
We are now ready to prove the 5-independence suffices for linear probing.
Theorem 6 Suppose we use a 5-independent hash function h to store a set S of n keys in a linear
probing table of size t ≥ 23 n where t is a power of two. Then it takes expected constant time to
search, insert, or delete a key.
Proof First we fix the hash of the query key q. To apply Theorem 4, we need to find a bound
Pℓ on the probability that 34 2ℓ keys from S \ {q} hash to any given
P ℓ-interval I. For each key
x ∈ S \ {q}, let Xx be the indicator variable for h(x) ∈ I. Then X = x∈S\{q} Xx is the number of
keys hashing to I, and the expectation of X is µ = E[X] = n2ℓ /t ≤ 32 2ℓ . Our concern is the event
that
3
1
1p ℓ
2 µ.
X ≥ 2ℓ =⇒ X − µ ≥ 2ℓ >
4
12
10
Since h is 5-independent, the Xx are 4-independent, so by Theorem 5, we get


3 ℓ
Pr X ≥ 2 ≤ 40000/22ℓ = O(1/22ℓ ).
4
Thus we can use Pℓ = O(1/22ℓ ) in Theorem 4, and then we get that the expected operation cost is




log2 t
log2 t
X
X
O 1 +
2ℓ Pℓ  = O 1 +
2ℓ /22ℓ  = O(1).
ℓ=0

ℓ=0

Problem 1 Above we assumed that the range of our hash function is [t] where t is a power of two.
As suggested in the introduction, we use a hash function based on a degree 4 polynomial over a
prime field Zp where p ≫ 1, that is, we pick 5 independent random coefficients a0 , . . . , a4 ∈ [p], and
define the hash function h′ : [p] → [t] by



h′ (x) = a4 x4 + · · · + a1 x + a0 mod p mod t.

Then for any distinct x0 , . . . , x4 , the hash values h′ (x0 ), . . . , h′ (x4 ) are independent. Moreover, we
have almost uniformity in the sense that for any x ∈ [p] and y ∈ [t], we have 1/t − 1/p < Pr[h′ (x) =
y] < 1/t + 1/p.
Prove that Theorem 6 still holds with constant operation time if p ≥ 24t.

Problem 2 Assuming full randomness, use Chernoff bounds to prove that the longest run in the
hash table has length O(log n) with probability at least 1 − 1/n10 .
Hint. You can use Lemma 2 to prove that if there is run of length r ≥ 2ℓ+2 , then some ℓ-interval
is near-full. You can then pick ℓ = C ln n for some large enough constant C.
Problem 3 Using Chebyshev’s inequality, show that with 3-independent hashing, the expected operation time is O(log n).
7

3.2

Fourth moment and simple tabulation hashing

In the preceding analysis we use the 5-independence of the hash function as follows. First we fix
the hash of the query key. Conditioned on this fixing, we still have 4-independence in the hashes
of the stored keys, and we use this 4-independence to prove the 4th moment bound (5) on the
number stored keys hashing to any given interval. This was all we needed about the hash function
to conclude that linear probing takes expected constant time per operation.
Pǎtraşcu and Thorup [15] have proved that something called simple tabulation hashing, that
is only 3-independent, within a constant factor provides the same 4th moment bound (5) on the
number of stored keys hashing to any given interval conditioned on a fixed hash of the query key.
Linear probing therefore also works in expected constant time with simple tabulation. This is
important because simple tabulation is 10 times faster than 5-independence implemented with a
polynomial as in (1).
Simple tabulation hashing was invented by Zobrist [22] in 1970 for chess computers. The basic
idea is to view a key x as consisting of c characters for some constant c, e.g., a 32-bit key could
be viewed as consisting of c = 4 characters of 8 bits. We initialize c tables T1 , . . . , Tc mapping
characters to random hash values that are bit-strings of a certain length. A key x = (x1 , ..., xc ) is
then hashed to T1 [x1 ] ⊕ · · · ⊕ Tc [xc ] where ⊕ denotes bit-wise xor.

4

The k-th moment

The 4th moment bound used above generalizes to any even moment. First we need
Theorem 7 Let X0 , . . . , Xn−1 ∈ {0, 1} be k-wise independent variables for
P some (possibly odd)
k ≥ 2. Let pi = Pr[Xi = 1] and σi2 = Var[Xi ] = pi − p2i . Moreover, let X = i∈[n] Xi , µ = E[X] =
P
P
2
2
i∈[n] σi . Then
i∈[n] pi , and σ = Var[X] =
E[(X − µ)k ] ≤ O(σ 2 + σ k ) = O(µ + µk/2 ).

Proof

The proof is a simple generalization of the proof of Theorem 5 up to (4). We have
X

(Xi0 − pi0 )(Xi1 − pi1 ) · · · (Xik−1 − pik−1 )
(X − µ)k =
i0 ,...,ik−1 ∈[n]

By linearity of expectation,
E[(X − µ)k ] =

X

i0 ,...,ik−1 ∈[n]

E




(Xi0 − pi0 )(Xi1 − pi1 ) · · · (Xik−1 − pik−1 )

We now consider a specific term

(Xi0 − pi0 )(Xi1 − pi1 ) · · · (Xik−1 − pik−1 )

Let j0 < j1 < · · · < jc−1 be the distinct indices among i0 , i1 , . . . , in−1 , and let mh be the multiplicity
of jh . Then

(Xi0 − pi0 )(Xi1 − pi1 ) · · · (Xik−1 − pik−1 )

= (Xj0 − pj0 )m0 (Xj1 − pj1 )m1 · · · (Xjc−1 − pjc−1 )mc−1 .
8

The product involves at most k different variables so they are all independent, and therefore


E (Xj0 − pj0 )m0 (Xj1 − pj1 )m1 · · · (Xjc−1 − pjc−1 )mc−1


= E [(Xj0 − pj0 )m0 ] E [(Xj1 − pj1 )m1 ] · · · E (Xjc−1 − pjc−1 )mc−1

Now, for any i ∈ [n], E[Xi − pi ] = 0, so if any multiplicity is 1, the expected value is zero.
We therefore only
P need to count terms where all multiplicities mh are at least 2. The sum of
multiplicities is h∈[c] mh = k, so we conclude that there are c ≤ k/2 distinct indices j0 , . . . , jc−1 .
Now by (3),


E [(Xj0 − pj0 )m0 ] E [(Xj1 − pj1 )m1 ] · · · E (Xjc−1 − pjc−1 )mc−1 ≤ σj20 σj21 · · · σj2c−1 .

We now want to bound the number tuples (i0 , i1 , . . . , ik−1 ) that have the same c distinct indices
j0 < j1 < · · · < jc−1 . A crude upper bound is that we have c choices for each ih , hence ck tuples.
We therefore conclude that
X


E (Xi0 − pi0 )(Xi1 − pi1 ) · · · (Xik−1 − pik−1 )
E[(X − µ)k ] =
i0 ,...,ik−1 ∈[n]

⌊k/2⌋

≤

X
c=1

⌊k/2⌋

≤

X
c=1

⌊k/2⌋

≤
=

X
c=1



ck





0≤j0 <j1 <···<jc−1 <n

ck
c!
k

X

X

j∈[n]

c!

σ

2c





σj20 σj21 · · · σj2c−1 


σj20 σj21 · · · σj2c−1 

j0 ,j1 ,...,jc−1 ∈[n]
c 



c 
c!

⌊k/2⌋  k
X c
c=1

X

σj2  





= O σ 2 + σ k = O µ + µk/2 .
Above we used that c, k = O(1) hence that, e.g., ck = O(1). This completes the proof of Theorem 7.
For even moments, we now get a corresponding error probability bound
Corollary 8 Let X0 , . . . .Xn−1 ∈ {0, 1} be k-wise independent variables for
P some even constant
2
2
k ≥ 2. Let pi = Pr[Xi = 1] and σi = Var[Xi ] = pi − pi . Moreover, let X = i∈[n] Xi , µ = E[X] =
P
P
2
2
i∈[n] pi , and σ = Var[X] =
i∈[n] σi . If µ = Ω(1), then
√
Pr[|X − µ| ≥ d µ] = O(1/dk ).

9

Proof

By Theorem 7 and Markov’s inequality, we get
√
Pr[|X − µ| ≥ d µ] = Pr[(X − µ)k ≥ dk µk/2 ]
E[(X − µ)k ]
dk µk/2

O µ + µ⌊k/2⌋
=
dk µk/2
= O(1/dk ).
≤

Problem 4 In the proofs of this section, where and why do we need that (a) k is a constant and
(b) that k is even.

5

Bloom filters via linear probing

We will now show how we can reduce the space of a linear probing table if we are willing to allow for
a small chance of false positives, that is, the table attemps to answer if a query q is in the current
stored set S. If it answers “no”, then q 6∈ S. If q ∈ S, then it always answers “yes”. However, even
if q 6∈ S, then with some probability ≤ P , the table may answer “yes”. Bloom [4] was the first to
suggest creating such a filter using less space than one giving exact answers. Our implementation
here, using linear probing, is completely different. The author suggested this use of linear probing
to various people in the late 90ties, but it was never written down.
To create a filter, we use a universal hash function s : [u] → [2b ]. We call s(x) the signature of
x. The point is that s(x) should be much smaller than x, that is, b ≪ log2 u. The linear probing
array T is now only an array of t signatures. We still use the hash function h : [u] → [t] to start
the search for a key in the array. Thus, to check if a key q is positive in the filter, we look for
s(q) among the signatures in T from location h(q) and onwards until the first empty locatition. If
s(q) is found, we report “yes”; otherwise “no”. If we want to include q to the filter, we only do
something if s(q) was not found. Then we place s(q) it in the first empty location. Our filter does
not support deletion of keys (c.f. Problem 6).
Theorem 9 Assume that the hash function h and the signature function s are independent, that
h is 5-independent, and that s is universal. Then the probability of a false positive on a given key
q 6∈ S is O(1/2b ).
Proof The keys from S have been inserted in some given order. Let us assume that h is fixed.
Suppose we inserted the keys exactly, that is, not just their signatures, and let X(q) be the set of
keys encountered when searching for q, that is, X(q) is the set of keys from h(q) and till the first
empty location. Note that X(q) depends only on h, not on s.
In Problem 5 you will argue that if q is a false positive, then s(q) = s(x) for some x ∈ X(q).
For every key x ∈ [u] \ {q}, by universality of s, we have Pr[s(x) = s(q)] ≤ 1/2b . Since
q 6∈ S ⊇ X(q), by union, Pr[∃x ∈ X(q) : s(x) = s(q)] ≤ |X(q)|/2b . It follows that the probability
10

that q is a false positive is bounded by
X
Pr[X(q) = Y ] · |Y |/2b = E[|X(q)|]/2b .
Y ⊆S

By Theorem 6, E[|X(q)|] = O(1) when h is 5-independent.

Problem 5 To complete the proof of Theorem 9, consider a sequence x1 , . . . , xn of distinct keys inserted in an exact linear probing table (as defined in Section 2). Also, let xi1 , ..., xim be a subequence
of these keys, that is, 1 ≤ i1 < i2 < · · · < im ≤ n. The task is to prove any fixed h : [u] → [t] and
any fixed j ∈ [t], that when only the subsequence is inserted, then the sequence of keys encountered
from location j and till the first empty location is a subsequence of those encountered when the full
sequence is inserted.
Hint. Using induction on n, show that the above statement is preserved when a new key xn+1
is added. Here xn+1 may or may not be part of the subsequence.
The relation to the proof of Theorem 9 is that when we insert keys in a filter, we skip keys whose
signatures are found as false postives. This means that only a subsequence of the keys have their
signatures inserted. When searching for a key q starting from from location j = h(q), we have thus
proved that we only consider (signatures of ) a subset of the set X(q) of keys that we would have
considered if all keys where inserted. In particular, this means that if we from j encounter a key x
with s(x) = s(q), then x ∈ X(q) as required for the proof of Theorem 9.
Problem 6 Discuss why we canot support deletions.
Problem 7 What would happen if we instead used h(s(x)) as the hash function to place or find x?
What would be the probability of a false positive?
Sometimes it is faster to generate the hash values and signatures together so that the pairs
(h(x), s(x)) are 5-independent while the hash values and signatures are not necessarily independent
of each other. An example is if we generate a larger hash value, using high-order bits for h(x) and
low-order bits for s(x). In this situation we get a somewhat weaker bound than that in Theorem 9.
Theorem 10 Assuming that x 7→ (h(x), s(x)) is 5-independent, the probability of a false positive
on a given key q 6∈ S is O(1/22b/3 ).
Proof Considering the exact insertion of all keys, we consider two cases. Either (a) there is a run
of length at least 2b/3 around h(q), or (b) there is no such run.
For case (a), we use Lemma 3 together with the bound Pℓ = O(1/22ℓ ) from the proof of
Theorem 4. We get that the probability of getting a run of length at least 2b/3 is bounded by
∞
X

12Pℓ = O(1/22b/3 ).

ℓ=b/3−2

We now consider case (b). By the statement proved in Problem 5, we know that any signature s(x)
considered is from a key x from the set X(q) of keys that we would have considered from j = h(q)
if all keys were inserted exactly. With no run of length at least 2b/3 , all keys in X(q) must hash
11

to (h(q) − 2b/3 , h(q) + 2b/3 ]. Thus, if we get a false positive in case (b), it is because there is a key
x ∈ S with s(x) = s(q) and h(x) ∈ (h(q) − 2b/3 , h(q) + 2b/3 ]. Since (h(x), s(x)) and (h(q), s(q)) are
independent, the probability that this happens for x is bounded by 21+b/3 /(t2b ) = O(1/(n22b/3 )),
yeilding O(1/22b/3 ) when we sum over all n keys in S. By union, the probability of a false positive
in case (a) or (b) is bounded by O(1/22b/3 ), as desired.
We note that with the simple tabulation mentioned in Section 3.2, we can put hash-signature pairs as
concatenated bit strings in the character tables T1 , . . . , Tc . Then (h(x), s(x)) = T1 [x1 ] ⊕ · · · ⊕ Tc [xc ].
The nice thing here is that with simple tabulation hashing, the output bits are all completely
independent, which means that Theorem 9 applies even though we generate the hash-signature
pairs together.

References
[1] Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and Gábor Tardos.
Linear hash functions. J. ACM, 46(5):667–683, 1999.
[2] Noga Alon and Asaf Nussboim. k-wise independent random graphs. In Proc. 49th IEEE
Symposium on Foundations of Computer Science (FOCS), pages 813–822, 2008.
[3] John R. Black, Charles U. Martel, and Hongbin Qi. Graph and hashing algorithms for modern
architectures: Design and performance. In Proc. 2nd International Workshop on Algorithm
Engineering (WAE), pages 37–48, 1998.
[4] Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications
of the ACM, 13(7):422–426, 1970.
[5] Larry Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer
and System Sciences, 18(2):143–154, 1979. Announced at STOC’77.
[6] Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes. In Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA),
pages 795–804, 2009.
[7] Michael L. Fredman, János Komlós, and Endre Szemerédi. Storing a sparse table with 0(1)
worst case access time. Journal of the ACM, 31(3):538–544, 1984. Announced at FOCS’82.
[8] Gregory L. Heileman and Wenbin Luo. How caching affects hashing. In Proc. 7th Workshop
on Algorithm Engineering and Experiments (ALENEX), pages 141–154, 2005.
[9] Daniel M. Kane Jeffery S. Cohen. Bounds on the independence required for cuckoo hashing,
2009. Manuscript.
[10] Howard J. Karloff and Prabhakar Raghavan. Randomized algorithms and pseudorandom numbers. Journal of the ACM, 40(3):454–476, 1993.
[11] Donald E. Knuth.
Notes on open addressing.
Unpublished memorandum. See
http://citeseer.ist.psu.edu/knuth63notes.html, 1963.

12

[12] Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley, 1973.
[13] Anna Pagh, Rasmus Pagh, and Milan Ružić. Linear probing with constant independence.
SIAM Journal on Computing, 39(3):1107–1120, 2009. Announced at STOC’07.
[14] Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. Journal of Algorithms, 51(2):122–
144, 2004. Announced at ESA’01.
[15] Mihai Pǎtraşcu and Mikkel Thorup. The power of simple tabulation-based hashing. Journal
of the ACM, 59(3):Article 14, 2012. Announced at STOC’11.
[16] Mihai Pǎtraşcu and Mikkel Thorup. On the k -independence required by linear probing and
minw ise independence. ACM Transactions on Algorithms, 12(1):Article 8, 2016. Announced
at ICALP’10.
[17] Jeanette P. Schmidt and Alan Siegel. The analysis of closed hashing under limited randomness.
In Proc. 22nd ACM Symposium on Theory of Computing (STOC), pages 224–234, 1990.
[18] Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for
applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223–
250, 1995. Announced at SODA’93.
[19] Alan Siegel and Jeanette P. Schmidt. Closed hashing is computable and optimally randomizable with universal hash functions. Technical Report TR1995-687, Courant Institute, New
York University, 1995.
[20] Mikkel Thorup and Yin Zhang. Tabulation-based 5-independent hashing with applications to
linear probing and second moment estimation. SIAM Journal on Computing, 41(2):293–331,
2012. Announced at SODA’04 and ALENEX’10.
[21] Mark N. Wegman and Larry Carter. New classes and applications of hash functions. Journal
of Computer and System Sciences, 22(3):265–279, 1981. Announced at FOCS’79.
[22] Albert Lindsey Zobrist. A new hashing method with application for game playing. Technical
Report 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin,
1970.

13

