Linear hash functions.
Consider the set   H   of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good   H is as a class of hash functions, namely we consider hashing a set S of size n into a range having the same cardinality n by a randomly chosen function from   H and look at the expected size of the largest hash bucket.   H is a universal class of hash functions for any finite field, but with respect to our measure different fields behave differently.If the finite  field   F has n elements, then there is a bad set S    F2 of size n with expected maximal bucket size   H(n1/3). If n is a perfect square, then there is even a bad set with largest bucket size always at least    n. (This is worst possible, since with respect to a universal class of hash functions every set of size n has expected largest bucket size below    n however, we consider the field of  two  elements, then we get much better bounds. The best previously known upper bound on the  expected size of the largest bucket for this class was  O(2   log n). We reduce this upper bound to O(log n log logn). Note that this is not far from the guarantee for a random function. There, the average largest bucket would be &THgr;(log n/ log log n).In the course of our proof we develop a tool which may be of independent interest. Suppose we have a subset S of a vector space D over   Z2, and consider a random linear mapping of  D to a smaller vector space R. If the cardinality of S is larger than   c&egr;|R|log|R|, then with probability 1 - &egr;, the image of S will cover all elements in the range.
Introduction
Consider distributing n balls in s buckets, randomly and independently. The resulting distribution
of the balls in the buckets is the object of occupancy theory.
Dep. of Math., Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel and Institute for Advanced
Study, Princeton, NJ 08540. Research supported in part by a USA-Israeli BSF grant, by the Sloan Foundation grant
No. 96-6-2, by an NEC Research Institute grant and by the Hermann Minkowski Minerva Center for Geometry at
Tel Aviv University. E-mail: noga@math.tau.ac.il.
y Fakultat fur Informatik und Automatisierung, Technische Universitat Ilmenau, Postfach 100565, 98684 Ilmenau,
Germany. This work was done while the author was a-liated with the University of Dortmund. Partially supported
by DFG grant Di 412/5-1. E-mail: Martin.Dietzfelbinger@theoinf.tu-ilmenau.de.
z BRICS, Centre of the Danish National Research Foundation, University of Aarhus, Ny Munkegade, Aarhus,
Denmark. Supported by the ESPRIT Long Term Research Programme of the EU under project number 20244
(ALCOM-IT). E-mail: bromille@brics.dk. Part of this work was done while the author was at the University of
Toronto.
x IBM Haifa Research Lab, MATAM, Haifa 31905, Israel. E-mail: erezp@haifa.vnet.ibm.com. Most of this work
was done while the author was visiting the University of Toronto.
{ Renyi Institute of the Hungarian Academy of Sciences, Pf. 127, Budapest, H-1364 Hungary. Partially supported
by DIMACS Center and the grants OTKA T-020914, T-030059 and FKFP 0607/1999. E-mail: tardos@cs.elte.hu.
Part of this work was done while the author was visiting the University of Toronto and the Institute for Advanced
Study, Princeton.
In the theory of algorithms and in complexity theory, it is often necessary and useful to consider
putting balls in buckets without complete independence. More precisely, the following setting is
studied: A class H of hash functions, each mapping a universe U to f1; xed. A set
U to be hashed is given by an adversary, a member h 2 H is chosen uniformly at random, S is
hashed using h, and the distribution of the multi-set fh(x)jx 2 Sg is studied. If the class H is the
class of all functions between U and f1; we get the classical occupancy problems. Carter
and Wegman dened a class H to be universal if
1=s:
We remark that a stricter denition is often used in the complexity theory literature.
For universal families, the following properties are well known; variations of them have been
used extensively in various settings:
1. If S of size n is hashed to n 2 buckets, with probability more than 1=2, no collision occurs.
2. If S of size 2n 2 is hashed to n buckets, with probability more than 1=2, every bucket receives
an element.
3. If S of size n is hashed to n buckets, the expected size of the largest bucket is less than p
n+ 1The intuition behind universal hashing is that we often lose relatively little compared to using a
completely random map. Note that for the property 1, this is true in a very strong sense; even with
complete randomness, we do not expect o(n 2 ) buckets to su-ce (the birthday paradox), so nothing
is lost by using a universal family instead. The bounds in the second and third properties, however,
are rather coarse compared to what one would get with complete randomness. For property 2, with
complete randomness, (n log n) balls would su-ce to cover the buckets with good probability
(the coupon collector's theorem), i.e. a polynomial improvement over n 2 , and for property 3,
with complete randomness, we expect the largest bucket to have size (log n= log log n), i.e. an
exponential improvement over p n. In these last cases we do seem to lose quite a lot compared to
using a completely random map and better bounds would seem desirable. However, it is rather
easy to construct (unnatural) examples of universal families and sets to be hashed showing that
size (n 2 ) is necessary to cover n buckets with non-zero probability, and that buckets of size
are in general unavoidable, when a set of size n is hashed to n buckets. This shows that the abstract
property of universality does not allow for stronger statements. Now x a concrete universal family
of hash functions. We ask the following question: To which extent are the ner occupancy properties
of completely random maps preserved?
We provide answers to these questions for the case of linear maps between two vector spaces
over a nite eld, a natural and well known class of universal (in the sense of Carter and Wegmen)
hash functions. The general
avor of our results is that \large elds are bad", in the sense that the
bounds become the worst possible for universal families, while \small elds are good" in the sense
that the bounds become as good or almost as good as the ones for independently distributed balls.
More precisely, for the covering problem, we show the following (easy) theorem.
Theorem 1 Let F be a eld of size n and let H be the class of linear maps between F 2 and F .
There is a subset S of F 2 of size (jF j 2 ), so that for no h
On the other hand, we prove the following harder theorem.
Theorem 2 Let S be a subset of a vector space over Z 2 and choose a random linear map to a
smaller vector space R. If jSj  c  jRj log jRj then with probability at least 1  the image of S
covers the entire range R.
For the \largest bucket problem", let us rst introduce some notation: Let U be the universe
from which the keys are chosen. We x a class H of functions mapping U to sg. Then, a
set S  U of size n is chosen by an adversary, and we uniformly at random pick a hash function
using h and look at the size of the largest resulting hash bucket. We denote the
expectation of this size by L s
n . Formally,
SU;jSj=n
Usually we think of s being of size close to n. Note that if
universal class yields
The class H we will consider is the set of linear maps between F m ! F k for m > k. Here F is
a nite eld and This class is universal for all values of the parameters.
s the expected largest bucket can be large.
Theorem 3 Let F be a nite eld with jF s. For the class H of all linear transformations
s
s 1=3
Furthermore if jF j is a perfect square we have
s (H) >
s:
Note how close our lower bound for quadratic elds is to the upper bound of
that holds
for every universal class. We also mention that for the bad set we construct in Theorem 8 for a
quadratic eld there is no good linear hash function, since there always exists a bucket of size at
least p s.
When the eld is the eld of two elements, the situation is completely dierent. Markowsky,
Carter and Wegman [MCW78] showed that for this case L s
s
[MV84] improved on this result (although this is implicit in their paper) and showed that L s
s
O(2
log s ). We further improve the bound and show that:
Theorem 4 For the class H of all linear transformations between two vector spaces over Z 2 ,
s
Furthermore, we also show that even if the range is smaller than jSj by a logarithmic factor, the
same still holds:
Theorem 5 For the class H of all linear transformations between two vector spaces over Z 2 ,
log s
Note that even if one uses the class R of all functions one obtains only a slightly better result:
the expected size of the largest bucket in this case is L s
log s) and L s
s log s
(log s), which is the best possible bound for any class. Interestingly, our upper bound is based on
our upper bound for the covering property.
We do not have any non-trivial lower bounds on L s
s for the class of linear maps over Z 2 , i.e., it
might be as good as O(log s= log log s). We leave this as an open question.
1.1 Motivation
There is no doubt that the method of implementing a dictionary by hashing with chaining, recommended
in textbooks [CLR90, GBY90] especially for situations with many update operations, is a
practically important scheme.
In situations in which a good bound on the cost of single operations is important, e. g., in
real-time applications, the expected maximal bucket size as formed by all keys ever present in the
dictionary during a time interval plays a crucial role. Our results show that, at least as long as the
size of the hash table can be determined right at the start, using a hash family of linear functions
over Z 2 will perform very well in this respect. For other simple hash classes such bounds on the
worst case bucket size are not available, or even fail to hold (see example in Section 4); other, more
sophisticated hash families [S89, DM90, DGMP92] that do guarantee small maximal bucket sizes
consist of functions with higher evaluation time. Of course, if worst case constant time for certain
operations is absolutely necessary, the known two-level hashing schemes can be used, e. g., the FKS
scheme [FKS84] for static dictionaries; dynamic perfect hashing [DKMHRT94] for the dynamic case
with constant time lookups and expected time O(n) for n update operations; and the \real-time
dictionaries" from [DM90] that perform each operation in constant time, with high probability. It
should be noted, however, that a price is to be paid for the guaranteed constant lookup time in
the dynamic schemes: the (average) cost of insertions is signicantly higher than in simple schemes
like chained hashing; the overall storage requirements are higher as well.
1.2 Related work
Another direction in trying to show that a specic class has a good bound on the expected size of
the largest bucket is to build a class specically designed to have such good property.
One immediate such result is obtained by looking at the class H of d-degree polynomials over
nite elds, where log n= log log n (see, e.g., [ABI86].) It is easy to see that this class maps
each d elements of the domain independently to the range, and thus, the bound that applies to the
class of all functions also applies to this class. We can combine this with the following well known
construction, found in, e.g., [FKS84], and sometimes called \collapsing the universe": There is a
class C of size 2 (log n+log log jU containing functions mapping U to g, so that, for any
set S of size n, a randomly chosen map from C will be one-to-one with probability 1 O(1=n k ).
The class consisting of functions obtained by rst applying a member of C, then a member of H
is then a class with L n
log log n) and size 2 O(log log jU j+log 2 n= log log n) and with evaluation
time O(log n= log log n) in a reasonable model of computation, say, a RAM with unit cost operations
on members of the universe to be hashed.
More e-cient (but much larger) families were given by Siegel [S89] and by Dietzfelbinger and
Meyer auf der Heide [DM90]. Both provide families of size jU j n
such that the functions can be
evaluated in O(1) time on a RAM and with L n
log log n). The families from [S89] and
[DM90] are somewhat complex to implement while the class of linear maps requires only very basic
bit operations (as discussed already in [CW79]). It is therefore desirable to study this class, and
this is the main purpose of the present paper.
1.3 Notation
If S is a subset of the domain D of a function h we use h(S) to denote Sg. If x is
an element of the range we use h 1 (x) to denote fs 2 D j xg. If A and B are subsets
of a vector space V and x 2 V we use the notations A
Ag. We use Z 2 to denote the eld with 2 elements. All logarithms in this
paper are base two.
2 The covering property
2.1 Lower bounds for covering with a large eld
We prove Theorem 1. Take any set A  F of size
Ag. S has density around one quarter. To see this, note that if x
and y are picked randomly and independently in F  , (x=y; (x 1)=y) has the same distribution as
linear To see this take a nonzero linear
by and note that if 0 2 g(S) then a 6= 0 and b=a 2 A but in this case
a 62 g(S).
2.2 Upper bounds for covering with a small eld - the existential case
We start by showing that if we have a subset A of a vector space over Z 2 and jAj is su-ciently
larger than another space W then there exists a linear transformation T mapping A to the entire
range . The constant e below is the base of the natural logarithm.
Theorem 6 Let A be a nite set of vectors in a vector space V of an arbitrary dimension over Z 2
and let t > 0 be an integer. If jAj > t2 log e then there exists a linear
, so that
maps A onto Z t
.
For the proof of this theorem we need the following simple lemma. Note that although we state
the lemma for vector spaces, it holds for any nite group.
Lemma 2.1 Let V be a nite vector space, A  V ,
Proof. If v and u are both chosen uniformly independently at random from V then both events
and u 62 v +A have probability  and they are independent. 2
Proof of Theorem 6. Let m be the dimension of V ,
Starting with A choose a vector so that for A
Such a choice for v 1 exists by Lemma 2.1. Then, by the same procedure, we choose a v 2 so that for
and so on up to A
Note that one can assume that the vectors v are linearly independent since choosing a
vector v i which linearly depends on the vectors formerly chosen makes A
g. We have A
and A were disjoint, a contradiction as jx
We choose an onto linear
2 such that its kernel T 1 (0) equals W . As T (W
we have
2 as claimed. 2
The bound in Theorem 6 is asymptotically tight as shown by the following proposition.
Proposition 2.2 For every large enough integer t there is a set A of at least (t 3 log t)2
vectors in a vector space V over Z 2 so that for any linear map
does not map A
.
let A be chosen at random by picking each element
of V independently and with probability into the set with
From Chebyshev's inequality we know that with probability at least 3=4, A has cardinality at
least pN 2
pN for Using p > x= log e x 2 =(2 log 2 e) one can show that this is as
many as claimed in the proposition. Let us compute the probability that there exists a linear map
2 such that T maps A onto Z t
. There are 2 t(t+s) possible maps T and each of them
with probability at most 1 (1 p) 2 s  2 t
So with probability almost 3=4, A is not small and still no T maps A onto Z t
2.3 Choosing the linear map at random
In this subsection we strengthen Theorem 6 and prove that if A is bigger than what is required
there by only a constant factor, then almost all choices of the linear transformation T work. This
may seem immediate at rst glance since Lemma 2.1 tells us that a random choice for the next
vector is good on average. In particular, it might seem that for a random choice of v 1 and v 2 in the
proof of Theorem 6,
. Unfortunately this is not the case:
For example, think of A being a linear subspace containing half of V . In this case, the ratio  of
points that are not covered is 1=2. As random vectors v i are chosen to be added to A, vectors in
A are chosen with probability 1=2. Thus, after i steps,  remains 1=2 with probability 1=2 i and
becomes 0 otherwise. Thus, the expected value of  i is 2 i 1 which is much bigger than
Our rst lemma is technical in nature.
Lemma 2.3 Let  i for 1  i  k be random variables and let 0 <  0 < 1 be a constant. Suppose
that for 0  i < k we have 0   i+1   i and conditioned on any set of values for
have
. Then for any threshold 0 < t < 1 we have
Proof: The proof is by induction on k. The base case is trivial.
We assume the statement of the lemma for k and prove it for k + 1. Let log log(1=t).
We may suppose c since otherwise the bound in the lemma is greater than
1.
After the choice of  1 , the rest of the random variables form a random process of length k
satisfying the conditions of the lemma (unless  thus we can apply the inductive hypothesis
to get
where we dene f in the same
interval and clearly an upper bound on Prob[ k+1  t j  1 ].
We claim that in the interval 0  x   0 we have f(x)  f 0 ( 0 )x= 0 . To prove this simply
observe that f 0 (x)=x is rst increasing then decreasing on (0; 1). To see this compute the derivative
. If  0 is still in the increasing phase then we have
Suppose now that  0 is already in the decreasing
phase and dene x
. Notice that we assumed  0  x 0 in the beginning of the proof, so
we have f us dene x
and notice that we have
and only if x  x 00 . It is easy to check that x 00 must still be in the increasing phase of f 0 (x)=x thus
we have . For x 00  x < 1 we simply have
. Thus we must have f(x)=x  1=x
We have thus proved the claim in all cases for 0 < x   0 . The claim is trivial for
Using the claim we can nish the proof writing:
remark that the bound in the lemma is achievable for
0 with an integer 0  j  k.
The optimal process has
Theorem 7 a) For every  > 0 there is a constant c  > 0 such that the following holds. Let A be a
nite set of vectors in a vector space V of an arbitrary dimension over Z 2 , let t > 0 be an integer.
If jAj  c  t2 t then for a uniform random linear transformation
b) If A is a subset of the vector space Z u
2 of density jAj=2 is an integer
then for a uniform random onto linear transformation
Proof: We start with proving part b) of the theorem. In order to pick the onto map T we use
the following process (similar to the one in the proof of Theorem 6). Pick vectors
s uniformly at random from the vectors in Z u
2 and choose T to be a random onto linear
2 with the constraints T (v i.e. the vectors v
are in the kernel of T . Note that the v i 's are not necessarily linearly independent and that they
do not necessarily span the kernel. Still, the transformation T is indeed distributed uniformly at
random amongst all onto linear maps of Z u
.
Using notations similar to the ones used in the proof of Theorem 6, let A
nonnegative and monotone
decreasing in i with  . The equation E[
i is guaranteed by Lemma 2.1
since A independent of  j for j  i. Thus all the conditions of
Lemma 2.3 are satised and we have
By the denition of s the right hand side here is equal to the estimate in the theorem. Finally note
that (as in the proof of Theorem
2 since for x 2 Z t
the sets
were disjoint with sizes 2 u t and (1  s )2 u > 2 u 2u t, a contradiction. Thus
we have the claimed upper bound for the probability that T (A) 6= Z t
.
Now we turn to part a) of the theorem and prove it using part b). Part a) is about a random
linear transformation, not necessarily onto, but this dierence from the claim just proved poses
less of a problem, the di-culty is that we do not have an a priori bound on 1 jAj=jV j. In fact,
this ratio can be arbitrarily small. To solve this, we choose the transformation T in two steps, the
rst step ensuring that the density of the covered set is substantial, then applying part b) for the
second step.
. First, we pick uniformly at
random a linear transformation we pick a random onto linear map
2 , and set This results in a uniformly chosen linear
2 . This is
true even for a xed onto T 1 and a random T 0 , since the values T 0
are independent and uniformly distributed in W , thus the values T (e i ) are also independent and
uniformly distributed in Z t
.
Any pair of vectors v 6= w 2 A collide (due to T 0 ) with probability Prob[T 0
Thus the expected number of collisions is jAj
=jW j. Since jT 0 (A)j  jAj=2 implies at least jAj=2
such collisions, Markov's inequality gives Prob[jT 0 (A)j  jAj=2]  2 jAj
For any xed T 0 , part b) of the theorem gives
In case jT 0 (A)j > jAj=2 we have  < 1 jAj=(2jW
using the monotonicity of the bound above we get
Choosing c we have that jAj  c  t2 t implies
(4=) log(2=). This implies that the bound in Equation 1 is less than =2, thus we get Prob[T (A) 6=
We remark that a more careful analysis gives c  that is a small polynomial of 1=.
3 The largest bucket
3.1 Lower bound for the largest bucket with a large eld
We start by showing why linear hashing over a large nite eld is bad with respect to the expected
largest bucket size measure. This natural example shows that universality of the class is not enough
to assure small buckets. For a nite eld F we prove the existence of a bad set S  F 2 of size
such that the expected largest bucket in S with respect to a random linear
is big. We prove the results in Theorem 3 separately for quadratic and non-quadratic elds.
We start with an intuitive description of the constructions. Linear hashing of the plane collapses
all straight lines of a random direction. Thus, a bad set in the plane must contain many points on
at least one line in many dierent directions. It is not hard to come up with bad sets that contain
many points of many dierent lines, however the obvious constructions (subplane or grid) yield sets
where many of the \popular lines" tend to be parallel and thus they only cover a few directions.
This problem can be solved by a projective transformation: the transformed set has many popular
lines, but they are no longer parallel.
For the non-quadratic case, it is convenient to explicitly use the concept of the projective
plane over a eld F . Recall that the projective plane P over F is dened as
where  is the equivalence relation (x; The a-ne plane F 2 is
embedded in P by the one-to-one map (x; y) 7! (x; 1). A line in P is given by an equation
projective line corresponds to a plane in F 3 containing the origin.
All projective lines are extensions (by one new point) of lines in the a-ne plane F 2 , except for
the ideal line, given by f(x; 0g. A projective transformation mapping the ideal line to
another projective line L is a map ~
obtained as the -quotient of a nonsingular linear
mapping the plane corresponding to the ideal line into the plane corresponding
to L.
Projective geometry is useful for understanding the behavior of linear hash functions due to the
following fact which is easily veried: Picking a random non-trivial linear map F 2 ! F as a hash
function and partitioning a subset S  F 2 into hash buckets accordingly, corresponds exactly to
picking a random point p on the ideal line and partitioning the points of S according to which line
through p they are on. This observation will be used explicitly in the proof of Theorem 9.
Theorem 8 Let F be a nite eld with jF j being a perfect square. There exists a set S  F 2 of
size such that for every linear has a large bucket, i.e. there exists a
value y 2 F with jh 1 (y)j
jF j.
Proof. We have a nite eld F 0 of which F is a quadratic extension. Let jF
a be an arbitrary element in F n F 0 and dene
g.
Note that also, that S is the image of the subplane F 2
0 under the projective
transformation (x; y) 7! ( 1
Fix F and consider the function h dened by h(x; By. We must
show that there is some C 2 F such that jh 1 (C) \ Sj  m. If maps all the m
elements of S to needed. Otherwise, we claim that there
is a C 2 F such that both C
B and aC A
are in F 0 . To see this observe that if g 1 and g 2 are two
distinct members of F 0 , then ag 1 and ag 2 lie in distinct additive cosets of F 0 in F , since otherwise
their dierence, a(g 1 would have to be in F 0 , contradicting the fact that a 62 F 0 . Thus, as
ranges over all members of F 0 , ag intersects distinct additive cosets of F 0 in F , and hence aF 0
intersects all those cosets. In particular, there is some g 2 F 0 so that ag 2 F
implying that
the assertion of the claim. For the above C, dene
it follows that y(x) 2 F 0 for every x 2 F 0 . We have now A 1
a+x +B y(x)
showing that h maps
all the m elements of S
Theorem 9 Let F be a nite eld. There exists a set S  F 2 of size such that for more
than half of the linear maps has a large bucket, i.e. there exists a value y 2 F with
Proof. First we construct a set S 0  F 2 such that jS 0 j  jF and there are n distinct lines
in the plane F 2 each containing at least m  n 1=3 =3 points of S 0 .
Let us rst consider the case when n is a prime, so F consists of the integers modulo n. We
ng and consider the square grid S A. Clearly jS 0 j < n. It is well
known that each of the n most popular lines contains at least m  n 1=3 =3 points of S 0 . This is
usually proved for the same grid in the Euclidean plane (see e.g. [PA95], pp. 178{179) but that
result implies the same for our grid in F 2 .
Now let be the subeld in F of p elements. Let x 2 F be a primitive element,
then every element of F can be uniquely expressed as a polynomial of x of degree below k with
coe-cients from F 0 . Let k
and let A
where the polynomials f have coe-cients from F 0 . Finally we take
n. For a 2 A 1 and b 2 A 2 we consider the line L ay
. Notice that there are n such lines and we have ay
we have n distinct lines each containing points of S 0 . We have m  n 1=3 as claimed
unless k  1 (mod 3). Notice that for k  2 (mod our m is much higher than n 1=3 . For the
bad case k  1 (mod 3) we apply the construction below instead.
Finally suppose is a prime and k  1 (mod 3). To get our set S 0 in this case we
have to merge the two constructions above. Let F 0 be the p element subeld of F , then F 0 consists
of the integers modulo p. We set
pg. Let k
and let x 2 F be a primitive element, so we can express any element of F uniquely as a polynomial
of x of degree less then k with coe-cients from F 0 . We set A
Ag where the polynomials f have coe-cients from F 0 . Finally
we set S g. Let
a and b be polynomials with coe-cients from F 0 with deg(a) < k 1 and deg(b) < k 2 . Consider
the line L Fg. We now compute the value of jL a;b \ S 0 j. Note that
a point (y; a(x)y + b(x)) of L a;b is in S 0 if and only if polynomial f so that
A. The number of such polynomials f is exactly
exactly p k1 1 jL a(0);b(0) \(AA)j. Thus, from knowing
that the p most popular lines in F 2
0 contain at least m 0  p 1=3 =3 points from A  A we conclude
that there exist n distinct lines each containing at least points of S namely,
the lines L a;b for those choices of a and b for which L a(0);b(0) is a popular line in F 2
In all cases we have constructed our set S 0  F 2 of size jS 0 j  n with n distinct popular lines
each containing at least m > n 1=3 =3 points of S 0 . Let P be the projective plane containing F 2 .
Out of the n 2 +n+ 1 points in P every popular line covers n+ 1. The ith popular line (1  i  n)
can only have i 1 intersections with earlier lines, thus it covers at least n+ 2 i points previously
uncovered. Therefore a total of at least n+2
1 points are covered by popular lines. Simple
counting gives the existence of a line L in P not among the popular lines, such that more than
half of the points on L are covered by popular lines. Let f be a projective transformation taking
the ideal line L to L. We dene
One linear hash function h : F 2 ! F is constant zero (and thus all of S is a single bucket), for
the rest there is a point x h 2 L 0 such that h collapses the points of F 2 of each single line going
through x h , as we observed at the beginning of the section. Furthermore, if the linear non-zero
map is picked at random, all such points x h are equally likely. Thus, the statement of the theorem
follows, if we show that for at least half the points x h on the ideal line, it holds that some line
through x h intersects S in at least n 1=3 =3 1 points. But some line through x h intersects S in at
least n 1=3 =3 1 points if and only if some line through f(x h ) intersects f(S) in at least n 1=3 =3 1
(projective) points. For this, it is su-cient that some line through f(x h ) intersects S 0 in at least
(n 1=3 =3 points (the +1 comes from the possibility of f(x h
line through f(x h ) is popular, in the sense we used above. But by denition of f , this is true for
at least half of the points x h on the ideal line, and we are done. 2
3.2 Upper bound for the largest bucket with a small eld
Let us now recall and prove our main result.
For convenience here we speak about hashing n log n keys to n values. Also, we assume that n
is a power of 2.
Theorem 5: Let H be the class of linear transformations between two vector spaces over Z 2 , then
log n log log n):
This theorem implies Theorem 4.
We have to bound the probability of the event that many elements in the set S are mapped to
a single element in the range. Denote this bad event by E 1 . The overall idea is to present another
(less natural) event E 2 and show that the probability of E 2 is small, yet the probability of E 2 given
big. Thus, the probability of E 1 must be small. We remark here that a somewhat similar line
of reasoning was used in the seminal paper of Vapnik and Chervonenkis [VC71].
For the proof we x the domain to be
2 , the range (the buckets) to be
S  D of size
Let us choose arbitrary '  log n and consider the space
2 . We construct the linear
through the intermediate range A in the following way. We choose
uniformly at random a linear transformation and uniformly at random an onto linear
transformation . Note that as mentioned in the proof of part
a) of Theorem 7 this yields an h which is uniformly chosen from among all linear transformations
from D to B.
Let us x a threshold t. We dene two events. E 1 is the existence of a bucket of size at least t:
There exists an element  2 B such that
> t:
We are going to limit the probability of E 1 through the seemingly unrelated event
There exists an element  2 B such that
Consider the distribution space in which h 1 and h 2 are uniformly chosen as above. We shall
show that
Proposition 3.1 If
log d log log d :
Proposition 3.2 If t > c 1=2 (2 ' =n) log(2 ' =n) (with c 1=2 from Theorem 7a)) then
From Propositions 3.1 and 3.2 we deduce that the probability of E 1 must be small:
Corollary 3.3 There is a constant C, so that for all r > 4 and every power of two n, the following
holds: If a subset S of size log n of a vector space over Z 2 is hashed by a random linear
transformation to Z log n
2 , we have
Prob[maximum bucket size > rC log n log log n]  2(r= log r) log(r= log r) log log(r= log r) :
Proof: Given r > 4, let l = blog n+log log n+log r log log r +1c and let log log n:
Letting log n), we have log n+log log n+log r log log r =(n log n) = r= log r >
1 and 2 l =n  2 log n+log log n+log r log log r+1 log n(r= log r), so
c 1=2 (2 l =n) log(2 l =n) < c 1=2 (2 log n(r= log r))(1 log log n log r)
log n(r= log r)(2 log log n log r)
log log n
so the conditions of Proposition 3.1 and 3.2 are satised, and, combining their conclusions, we get
log d log log d :
But the event E 1 is the event that the biggest bucket is bigger than log log n and
since d  r= log r, the statement of the corollary follows, by putting
Let us now prove the propositions above.
Proof of Proposition 3.1: Note rst that an alternative way to describe E 2 is
We will prove that Proposition 3.1 holds for any specic h 1 , and thus it also holds for a randomly
chosen h 1 . So x h 1 and consider the distribution in which h 2 is chosen uniformly amongst all full
rank linear transformation from A to B.
We use part b) of Theorem 7 for the set A n h 1 (S)  A. Its density is clearly 1  for
1=d. Thus the theorem gives log log n+log log(1=)
d log d log log d as claimed. 2
Proof of Proposition 3.2: Fix h for which E 1 holds, and x any full rank h 2 . We will show that
the probability of event E 2 is at least 1=2 even when these two are xed and thus the conditional
probability is also at least 1=2.
Now since E 1 holds there is a subset S 0  S of cardinality at least t mapped by h to a single
element  2 Z log n
. Fix this  and dene
(). Consider the distribution
of h 1 satisfying . When we restrict h 1 to D 0 , we get that the distribution implied by
such h 1 is a uniform choice of an a-ne or linear map from D 0 into A 0 (we show this in Proposition
3.4 below). For event E 2 to hold it is enough to have A 0  h 1 (S). We will show that h 1 (S 0 ) covers
all the points in A 0 with probability at least 1=2 and thus we get that event E 2 happens with
probability 1=2. Since h 2 is onto we have jA On the other hand, D 0 \S has cardinality at
least a) of Theorem 7, the probability that a set of cardinality
t mapped by a random linear transformation will cover a range of cardinality 2 ' =n is at least 1=2.
(Note that Theorem 7, part a) clearly applies to a random a-ne transformation too.) 2
At this point, we have proven Corollary 3.3. This limits the probability of large buckets with
linear hashing. It is straightforward to deduce Theorem 5 from that corollary:
Proof of Theorem 5: L n
log n is the expectation of the distribution of the largest bucket size.
Corollary 3.3 limits the probability of the tail of this distribution, thus yielding the desired bound
on the expectation. The constant C is from Corollary 3.3 and we set log log n.
4K +Z
4K +KZ2(r= log r) log(r= log r) log log(r= log r) dr
log log n):In order for the paper to be self-contained we include a proof of the simple statement about
random linear transformations used above.
Proposition 3.4 Let D, A and B be vector spaces over Z 2 . Let h : be an arbitrary linear
map, and let be an arbitrary onto linear map. Let  be any point in B and denote
choosing a uniform linear map A such that
restricting the domain to D 0 we get a uniformly chosen linear map from D 0 to A 0
uniformly chosen a-ne map from D 0 to A 0 otherwise.
Proof: Consider D 0
(0). Let us choose a complement space D 1 to
us call x the unique vector in D 0 \ D 1 .
We have linear transformation A is determined by its two restrictions
A. Clearly the uniform random choice of h 1 corresponds to uniform
and independent choices for h 0 and h 00 . The restriction means that h 0 (D 0 )  A 0 and
is the restriction of h to D 1 . Thus, after the restriction the random choices of h 0 and h 00
are still independent. Note now that if then the restriction of h 1 in question is exactly
to note that the restriction
in question is again h 0 , this time translated by the random value h 00 (x) 2 A 0 . 2
4 Remarks and open questions
We have discussed the case of a very small eld (size 2) and a very large eld (size n). What
happens with intermediate sized elds? Some immediate rough generalizations of our bounds are
the following: If we hash an adversely chosen subset of F m of size by a randomly
chosen linear map, the expected size of the largest bucket is at most O((log n log log n) log jF j ) and
at
least
bounds should be possible.
Another question is which properties other well known hash families have. Examples of
the families we have in mind include: Arithmetic over Z p [CW79, FKS84] (with h a;b
b mod p) mod n), integer multiplication [DHKP97, AHNR95] (with h a
Boolean convolution [MNT93] (with h a projected to some subspace).
An example of a natural non-linear scheme for which the assertion of Theorem 6 fails is the
scheme that maps integers between 1 and p, for some large prime p, to integers between 0 and n 1
mapping x 2 Z p to (ax are two randomly chosen
elements of Z p . For this scheme, there are primes p and choices of n and a subset S of cardinality
log n log log log n) of Z p , which is not mapped by the above mapping onto [0; n 1] under any
choice of a and b.
To see this, let p be a prime satisfying p  3 (mod 4) and consider the set
of all quadratic residues modulo p. Note that for every nonzero element a 2 Z p , the set aS ( mod p)
is either the set of all quadratic residues or the set of all quadratic non-residues modulo p. The
main result of Graham and Ringrose [GR90] asserts that for innitely many primes p, the smallest
quadratic nonresidue modulo p is at least
ast p log log log p) (this result holds for primes p
as well, as follows from the remark at the end of [GR90]). Since for such primes p,
1 is a quadratic nonresidue, it follows that for the above S and for any choice of a; b 2 Z p ,
the set aS (computed in Z p ) avoids intervals of length at least
ast p log log log p). Choosing
log log log p for an appropriate (small) constant c, and dening
that
log n log log log n) is not mapped onto [0; n 1] under any choice of a
and b.
A nal question is whether there exists a class H of size only 2 O(log log jU j+log n) and with L n
O(log n= log log n). Note that linear maps over Z 2 , even combined with collapsing the universe, use
O(log log bits while the simple scheme using higher degree polynomials uses
O(log log log log n).

Acknowledgment

We thank Sanjeev Arora for helpful remarks.



--R

A fast and simple randomized parallel algorithm for the maximal independent set problem.
Sorting in linear time?
Universal classes of hash functions
Introduction to Algorithms
A reliable randomized algorithm for the closest-pair problem


Polynomial hash functions are reliable

Handbook of Algorithms and Data Structures
Lower bounds for least quadratic nonresidues
Analysis of a universal class of hash functions
Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories.
The computational complexity of universal hashing.
Combinatorial Geometry
On universal classes of fast high performance hash functions
On the uniform convergence of relative frequencies of events to their probabilities
--TR
Storing a Sparse Table with <italic>0</italic>(1) Worst Case Access Time
Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
A fast and simple randomized parallel algorithm for the maximal independent set problem
Introduction to algorithms
The computational complexity of universal hashing
Dynamic Perfect Hashing
Sorting in linear time?
A reliable randomized algorithm for the closest-pair problem
Polynomial Hash Functions Are Reliable (Extended Abstract)

--CTR
Dahlia Malkhi , Moni Naor , David Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Beate Bollig , Stephan Waack , Philipp Woelfel, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, Theoretical Computer Science, v.362 n.1, p.86-99, 11 October 2006
Beate Bollig , Philipp Woelfel, A read-once branching program lower bound of (2n/4) for integer multiplication using universal hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.419-424, July 2001, Hersonissos, Greece
universal hashing;hashing via linear maps