Dynamical system representation of open address hash functions

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

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 conference › Paper › peer-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 language	English (US)
Pages	S919-S920
State	Published - 1999
Externally published	Yes
Event	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999

Other

Other	Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
City	Baltimore, MD, USA
Period	1/17/99 → 1/19/99

ASJC Scopus subject areas

Software
General Mathematics

Cite this

@conference{66d3245e1d094c93ac476d9e3a592bf3,

title = "Dynamical system representation of open address hash functions",

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.",

author = "Heileman, {Gregory L.} and Abdallah, {Chaouki T.} and Moret, {Bernard M.E.} and Smith, {Bradley J.}",

year = "1999",

language = "English (US)",

pages = "S919--S920",

note = "Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 17-01-1999 Through 19-01-1999",

}

TY - CONF

T1 - Dynamical system representation of open address hash functions

AU - Heileman, Gregory L.

AU - Abdallah, Chaouki T.

AU - Moret, Bernard M.E.

AU - Smith, Bradley J.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032805116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032805116&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032805116

SP - S919-S920

T2 - Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 1999 through 19 January 1999

ER -

Dynamical system representation of open address hash functions

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this