An Optimal Algorithm for Generating Minimal Perfect Hash Functions

by: Zbigniew J Czech, George Havas, Bohdan S Majewski

Information Processing Letters, Vol. 43, No. 5. (1992), pp. 257-264.

View FullText article

CiteSeer (at Penn State), CiteSeer (at MIT), CiteSeer (at Zurich), CiteSeer (at Singapore)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

bigbossman

Find related articles with these CiteULike tags

algorithm, hash

Abstract

A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice. Keywords: Data structures, probabilistic algorithms, analysis of algorithms, hashing, random graphs

@article{citeulike:2064917, abstract = {A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice. Keywords: Data structures, probabilistic algorithms, analysis of algorithms, hashing, random graphs}, author = {Czech, Zbigniew J. and Havas, George and Majewski, Bohdan S. }, citeulike-article-id = {2064917}, journal = {Information Processing Letters}, keywords = {algorithm, hash}, number = {5}, pages = {257--264}, posted-at = {2007-12-06 03:04:59}, priority = {2}, title = {An Optimal Algorithm for Generating Minimal Perfect Hash Functions}, url = {http://citeseer.ist.psu.edu/122364.html}, volume = {43}, year = {1992} }

RIS record

TY - JOUR ID - citeulike:2064917 L3 - citeulike-article-id:2064917 TI - An Optimal Algorithm for Generating Minimal Perfect Hash Functions JF - Information Processing Letters VL - 43 IS - 5 SP - 257 EP - 264 N2 - A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice. Keywords: Data structures, probabilistic algorithms, analysis of algorithms, hashing, random graphs KW - algorithm KW - hash AU - Czech, Zbigniew AU - Havas, George AU - Majewski, Bohdan PY - 1992/// UR - http://citeseer.ist.psu.edu/122364.html ER -

RIS BibTeX