Is linear hashing good?

Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gabor Tardos

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

Abstract

Considering the set H of all linear (or affine) transformations between two vector spaces over a finite field F, the ability of H as a class of hash functions is studied. Hashing a set S of size n into a range, having the same cardinality n by a randomly chosen function from H and looking at the size of the largest hash bucket, is particularly evaluated. If the finite field F has n elements, then there is a bad set S⊂F2 of size n with expected minimal bucket size Ω(n1/3). If n is a perfect square there is a worse set with largest bucket size always at least √n. If however, the considered is the field of two elements then better bounds will be obtained. The best previously known upper bound was O(2√log n). This upper bound is reduced to θ(log n/log log n).

Original languageEnglish (US)
Pages (from-to)465-474
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Is linear hashing good?'. Together they form a unique fingerprint.

Cite this