Linear Hashing is Awesome
Mathias Bæk Tejs Knudsen∗

arXiv:1706.02783v1 [] 8 Jun 2017

University of Copenhagen,
mathias@tejs.dk

Abstract
We consider the hash function hpxq “ ppax ` bq mod pq mod n where a, b are chosen uniformly at
random from t0, 1, . . . , p ´ 1u. We prove that when we use hpxq in hashing with
to insert n
` chaining
˘
elements into a table of size n the expected length of the longest chain is Õ n1{3 . The proof also
generalises to give the same bound when we use the multiply-shift hash function by Dietzfelbinger
et al. [Journal of Algorithms 1997].

∗

Research partly supported by Advanced Grant DFF-0602-02499B from the Danish Council for Independent Research
under the Sapere Aude research career programme and by the FNU project AlgoDisc - Discrete Mathematics, Algorithms,
and Data Structures

1

Introduction

In this paper we study the hash function h : rps Ñ rms (where rms “ t0, 1, . . . , m ´ 1u) defined by
hpxq “ ppax ` bq mod pq mod m, where a, b P rps are chosen uniformly at random from rps. Here, p is a
prime and p ě m. We assume that we have a set X Ď rps of n keys with n ď m and use h to assign a
hash value hpxq to each key x P X. We are interested in the frequency of the most popular hash value,
i.e. we study the random variable M ph, Xq defined by
M ph, Xq “ max |tx P X | hpxq “ yu| .

(1)

yPrms

`?
˘
In Theorem 1 we proveY that ErM]ph, Xqs “ O 3 n log n . We also consider the hash function h̄ : rqs Ñ
mod q
, where q, m are powers of 2, q ě m ě n and a is chosen uniformly at
rms defined by h̄pxq “ paxqq{m
random among the odd numbers from rqs. The function“ h̄pxq was‰ first `introduced
˘ by Dietzfelbinger et
?
3
al. [3]. In Theorem 2 we prove that it also holds that E M ph̄, Xq “ O n log n .
We note that when we use hpxq “ ppax ` bq mod pq mod m in hashing with chaining, M is the size
of the largest chain. When scanning the hash table for an element the expected time used is Op1q and
the worst case time is at most OpM ph, Xqq.

1.1

Related work

?
It is folklore that the size of the largest chain is Op nq and this bounds hold for any 2-independent hash
function.
Alon et al. [1] considers the linear hash function hm,k : F m Ñ F k , where F is a finite field and
ř
n “ |F|k . The function is defined by hm,k px1 , . . . , xm q “ i xi ai , where ai P F k is chosen uniformly at
random. For m “ 2, k “ 1 the hash function is h2,1 px, yq “ ax ` by where a, b P F are chosen uniformly
?
at random. It is shown in [1] that there exists a set X Ď F 2 such that ErM ph2,1 , Xqs ą n if n is a
?
square and ErM ph2,1 , Xqs “ Ωp 3 nq if n is a prime power that is not a square. In [1] it is also shown
that when F is the field of two elements the expected length of the longest chain is Oplog n log log nq
improving the results in [4, 5].
Broder et al. [2] considered hpxq “ pax ` bq mod p in the context of min-wise hashing.

2

Preliminaries

Z denotes the integers, and Zn “ Z{nZ denotes the integers mod n. Z˚n is the set of elements of Zn
having a multiplicative inverse. rns is the set of integers from 0 to n ´ 1, that is rns “ t0, 1, 2, . . . , n ´ 1u.
For a pair of integers n, m P Z such that pn, mq ‰ p0, 0q we let gcdpn, mq denote the greatest common
divisor of n and m. If gcdpn, mq “ 1 then n and m are said to be coprime.
For integers x, r P Z we let rxsr P Zr denote the residue class of x mod r. We let ιr : Zr Ñ rrs be the
unique mapping that satisfies rιr pxqsr “ x. For x P Zr we let ||x||r “ min tιr pxq , ιr p´xqu.
For a set S and an element x the sets S ` x and xS are defined as ts ` x | s P Su and txs | s P Su,
respectively.
For integers r, s, m, let Im pr, sq Ď Zm denote the set
Im pr, sq “ trrsm , rr ` 1sm , . . . , rr ` s ´ 1sm u .
The set Im pr, sq is called an interval. A non-empty set X Ď Zm is an interval if there exists r, s such
that X “ Im pr, sq.

1

3

Main Result

In this section we prove the main results of this paper, namely Theorem 1 and Theorem 2. The proofs
of the two theorems are very similar and both rely on Lemma 1 below.
Lemma 1. Let n, M, r be integers satisfying 4M ď n ď r and let A Ď Zr be a set of size n. Let B Ď Z˚p
be a set of size ď M satisfying the following conditions:
1 ιpbq P pM, 2M q for all b P B.
2 ιpbq, ιpb1 q, and r are pairwise coprime for every b, b1 P B with b ‰ b1 .
P T
Assume that for every b P B there exists an interval Ib of size nr such that Ib X bA contains at least
4M elements. Then there exists at least M |B| ordered pairs of different elements a, a1 P A such that
r
|a ´ a1 | ă nM
.
Q
U
r
Proof. We note that for every b the set b´1 Ib is the union of ιpbq disjoint intervals of size ď nιpbq
, and
Ť
ιpbq´1
´1
we write it as such a union b´1 Ib “ j“0 Ib,j . For any b, b1 P B, b ‰ b1 the set b´1 Ib X b1 Ib1 is either
empty or an interval. So for each b, b1 P B, b ‰ b1 there is at most one index j P rιpbqs such that the
intersection Ib,j X b1 ´1 Ib1 is non-empty. For every b P B and j P rιpbqs, let δpb, jq denote the number of
elements b1 P B such that Ib,j X b1 ´1 Ib1 is non-empty. Note that δpb, jq ě 1 since b P B. Furthermore
řιpbq´1
1 ´1 I 1 has a non-empty intersection with at most one of
b
j“0 δpb, jq ă |B| ` ιpbq ď 3M since each b
the sets Ib,j , j P rιpbqs.
r
is
The number of ordered pairs of different elements pa, a1 q P AQX Ib,jU such that |a ´ a1 | ă nM
exactly |A X Ib,j | ¨ p|A X Ib,j | ´ 1q since Ib,j is an interval of size ď

r
nιpbq

and ιpbq ą M . Let τ pb, jq “

max t0, |A X Ib,j | ´ 1u, then the number of pairs is at least pτ pb, jqq2 . We can lower bound the number
of such pairs in A by considering the pairs in A X Ib,j for each b P B and j P rιpbqs and note that each
pair we count is counted at most δpb, jq times. This gives that the number of ordered pairs pa, a1 q P A
r
such that |a ´ a1 | ă nM
is at least:
ÿ ÿ pτ pb, jqq2
δpb, jq
bPB

(2)

jPrιpbqs

For any b P B, by the Cauchy-Schwartz inequality we have that:
¨
˛¨
˛ ¨
˛2
ÿ
ÿ pτ pb, jqq2
ÿ
˝
‚ě ˝
δpb, jq‚˝
τ pb, jq‚
δpb, jq
jPrιpbqs

We clearly have that

ř

jPrιpbqs τ pb, jq

jPrιpbqs

(3)

jPrιpbqs

ě 4M ´ ιpbq ě 2M . Also recall, that we have that

3M . Combining this with (2) and (3) gives that A contains at least
pairs.

4M |B|
3

ř

jPrιpbqs δpb, jq

ď

ě M |B| of the desired

Below is a proof of Theorem 1.
Theorem 1. Let n, m, p be integers with p a prime and p ě m ě n. Let X Ď Zp be a set of n elements.
Let h : Zp Ñ Zm be defined by hpxq “ rιp pax ` bqsm where a, b P Zp are chosen uniformly at random.
Let M “ M pXq be the random variable counting the number of elements x P X that hash to the most
popular hash value, that is
M “ M pXq “ max |tx P X | hpxq “ yu| .
yPZm

Then
ErM s “ O

´a
¯
3
n log n .
2

(4)

Proof. We note that ErM | a “ 0s “ n since h is constant when a “ 0. Therefore:
ErM s “

p´1
1
ErM | a ‰ 0s ` ErM | a “ 0s ă ErM | a ‰ 0s ` 1 .
p
p

Therefore it suffices to bound the expected value of M when a is chosen uniformly at random from
Zp z t0u “ Z˚p and not from Zp . So from now on, assume that a is chosen uniformly at random from Z˚p .
´1
“ `The random
˘‰variables a and a b are independent. Note, that hpxq can be rewritten as hpxq “
´1
ιp apx ` a bq m . It clearly suffices to bound the expected value of M conditioned on all possible
values a´1 b. For any fixed value of a´1 b “ c, the expected value of M conditioned on a´1 b “ c is the
same as the expected value of M pX ` cq conditioned on b “ 0. Therefore it suffices to give the proof
under the assumption that b “ 0. So we assume that b “ 0.
PpT
Let A “ m´1 aX, then there exists an interval Ia of size at most m
that contains M elements of
A for the following reason: Let f ˇ: Zp Ñ Zm beˇ defined by x Ñ rιp pxqsm . By definition, there exists a
random variable y P Zp such that ˇf ´1 pyq X aX ˇ ě M . And there exists a i P rms such that
*
"
p´i
´1
,
f pyq “ ri ` kmsp | k P Z, 0 ď k ă
m
P T
´1 f ´1 pyq is an interval of size ď p that contains M elements of A.
and hence I“a “ m
m
‰
Let α P 1, n4 . We are now going to bound the probability that M ě 4α. Let δ “ PrrM ě 4αs and
let A be the set of all elements a0 P Z˚p such that M ě 4α if a “ a0 .
Let S Ď Z˚p be the set of all elements s P Z˚p that satisfies that ιp psq is a prime in the interval pα, 2αq.
Let B Ď S be the set of all elements s P S such that as P A. Note, that B is a random variable. By
´1
linearity of expectation, we have that Er|B|s “ |S| δ. Recall,
P r T that A “ m aX. For any b P B we have
that ab P A and therefore there exists an interval of size n that contains at least 4α elements of bA.
By Lemma 1, this implies that there are α |B| ordered pairs of different elements x, x1 P X such that
p
p
||ax ´ ax1 ||p ă mα
. So the expected number of elements x, x1 P X such that ||apx ´ x1 q||p ă mα
is at
least α Er|B|s “ αδ |S|. On the other hand, for each ordered pair of different elements x, x1 P X the
p
2p
probability that ||apx ´ x1 q||p ă mα
, and by linearity of expectation the expected
is at most mαpp´1q
number of such ordered pairs is at most
npn ´ 1q ¨
We conclude that αδ |S| ď
gives us that:

2n
α.

2p
2n
ď
.
mαpp ´ 1q
α

´
¯
´
¯
By the prime number theorem, |S| “ Θ logα α “ Ω logα n . Reordering
ˆ

n log n
PrrM ě 4αs “ δ “ O
α3

˙
.

The expected value of M can now be bounded in the following manner:
ErM s “

8
ÿ

PrrM ě ks

k“1
?
t 3 n log nu

ÿ
“

n
ÿ

PrrM ě ks `

]
Ya
ď 3 n log n `

n
ÿ
?
k“t 3 n log nu`1

“O

PrrM ě ks

?
k“t 3 n log nu`1

k“1

´a
¯
3
n log n

which was what we wanted.
3

ˆ

n log n
O
k3

˙

The proof of Theorem 2 is very similar to the proof of Theorem 1 but we include it for completeness.
Theorem 2. Let n, `, r, q, m be integers with q “ 2Xr , m “ 2` and
\ q ě m ě n. ˚Let X Ď Zq be a set of n
`´r
elements. Let h : Zq Ñ rms be defined by hpxq “ ιq paxq ¨ 2
where a P Zq are chosen uniformly at
random. Let M “ M pXq “ maxyPrms |tx P X | hpxq “ yu|. Then
ErM s “ O

´a
¯
3
n log n .

(5)

ˇ
ˇ
Proof. Let y be a random variable such that ˇh´1 pyq X X ˇ “ M , and let A “ aX. The set ah´1 pyq is
q
an interval of
“ size
‰ m that contains exactly M elements of A.
n
Let α P 1, 4 . We are now going to bound the probability that M ě 4α. Let δ “ PrrM ě 4αs, and
let A be the set of all elements a0 P Z˚p such that M ě 4α if a “ a0 .
Let S Ď Z˚q be the set of all elements s P Z˚q that satisfies that ιq psq is a prime in the interval pα, 2αq.
Let B Ď S be the set of all elements s P S such that as P A. Note, that B is a random variable. By
linearity of expectation, we have that Er|B|s “ |S| δ. Recall, that A “ m´1 aX. For any b P B we have
q
that ab P A and therefore there exists an interval of size m
that contains at least 4α elements of bA.
By Lemma 1, this implies that there are α |B| ordered pairs of different elements x, x1 P X such that
q
q
||ax ´ ax1 ||q ă mα
. So the expected number of elements x, x1 P X such that ||apx ´ x1 q||q ă mα
is at
1
least α Er|B|s “ αδ |S|. On the other hand, for each ordered pair of different elements x, x P X the
q
4
probability that ||apx ´ x1 q||q ă mα
is at most mα
, and by linearity of expectation the expected number
of such ordered pairs is at most
npn ´ 1q ¨
We conclude that αδ |S| ď

4n
α,

4
4n
ď
.
mα
α

and now we can bound the expected value exactly as in Theorem 1.

4

References
[1] Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and Gábor Tardos. Linear
hash functions. Journal of the ACM (JACM), 46(5):667–683, 1999.
[2] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent
permutations. J. Comput. Syst. Sci., 60(3):630–659, 2000.
[3] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19–51, 1997.
[4] George Markowsky, Larry Carter, and Mark N. Wegman. Analysis of a universal class of hash
functions. In Mathematical Foundations of Computer Science 1978, Proceedings, 7th Symposium,
Zakopane, Poland, September 4-8, 1978, pages 345–354, 1978.
[5] Kurt Mehlhorn and Uzi Vishkin. Randomized and deterministic simulations of prams by parallel
machines with restricted granularity of parallel memories. Acta Inf., 21:339–374, 1984.

5

