# DIMACS Discrete Math/Theory of Computing Seminar

## Title:

Is linear hashing good?

## Speaker:

- Gabor Tardos
- Institute for Advanced Study

## Place:

- DIMACS Center, CoRE Building, Seminar Room 431
- Rutgers University

## Time:

- 4:30 PM
- Tuesday, February 11, 1997

Abstract:
Performance of algorithms using hashing is often related to the largest
number of keys mapped by the hash function to the same value. This
motivates the study of the expected size of the largest bucket for the
worst case set of keys of a given size. In this work, we study the
performance of linear transformations as a family of hash functions by
this measure.

Our main result is the linear mappings over GF[2] are excellent hash
functions. They almost match the performance of the best possbile family
of hash functions. (But, of course, are much more efficient.)

A surprising additional result we have implies that linear mappings over
big finite fields (say modulo a prime) are the other way around. They are
almost as bad as possible for any universal family of hash functions.

The main tool in proving the main result may be of independent
interest. We show that a random linear mapping applied on a set
of cardinality $c n\log n$ covers all the element of a size $n$
range with probability at least $1-\epsilon_c$.

This is joint work with Noga Alon, Martin Ditzfelbinger, Peter Bro
Miltersen, and Erez Petrank.

Document last modified on February 7, 1997