Dynamical system representation of open address hash functions

Gregory L. Heileman, Chaouki T. Abdallah, Bernard M.E. Moret, Bradley J. Smith

Research output: Contribution to conferencePaperpeer-review

Abstract

This paper demonstrates how a broad collection of hash function families can be expressed as dynamical systems. We then show that this representation can be useful for analysis. In particular, we provide an analysis which proves that a widely-used family of double hash functions will transform any initial distribution of keys into the uniform distribution over the table space.

Original languageEnglish (US)
PagesS919-S920
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Dynamical system representation of open address hash functions'. Together they form a unique fingerprint.

Cite this