Linear time algorithm for finding minimal perfect hash functions

Zbigniew J. Czech; Bohdan S. Majewski

doi:10.1093/comjnl/36.6.579

Linear time algorithm for finding minimal perfect hash functions

Zbigniew J. Czech
, Bohdan S. Majewski

Department of Algorithmics and Software (RAU/RAU5)

Silesian University of Technology

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

Abstract

A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h₀, h₁ and h₂, searches for a function g such that F(w) = (h₀(w) + g(h₁(w)) + g(h₂(w))) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m + O(1) memory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.

Original language	English
Pages (from-to)	579-587
Number of pages	9
Journal	Computer Journal
Volume	36
Issue number	6
DOIs	https://doi.org/10.1093/comjnl/36.6.579
Publication status	Published - 1993

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1093/comjnl/36.6.579

Cite this

@article{ec9fef873bed48f78efaac926a06f334,

title = "Linear time algorithm for finding minimal perfect hash functions",

abstract = "A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h0, h1 and h2, searches for a function g such that F(w) = (h0(w) + g(h1(w)) + g(h2(w))) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m + O(1) memory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.",

author = "Czech, \{Zbigniew J.\} and Majewski, \{Bohdan S.\}",

year = "1993",

doi = "10.1093/comjnl/36.6.579",

language = "English",

volume = "36",

pages = "579--587",

journal = "Computer Journal",

issn = "0010-4620",

publisher = "Oxford University Press",

number = "6",

}

TY - JOUR

T1 - Linear time algorithm for finding minimal perfect hash functions

AU - Czech, Zbigniew J.

AU - Majewski, Bohdan S.

PY - 1993

Y1 - 1993

N2 - A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h0, h1 and h2, searches for a function g such that F(w) = (h0(w) + g(h1(w)) + g(h2(w))) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m + O(1) memory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.

AB - A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h0, h1 and h2, searches for a function g such that F(w) = (h0(w) + g(h1(w)) + g(h2(w))) mod m is a MPHF, where m is a number of input words. The algorithm involves generation of random bipartite graphs and runs in linear time. The hash function generated is represented by using 2m + O(1) memory words of log m bits each. The empirical observations show that the algorithm runs very fast in practice.

UR - https://www.scopus.com/pages/publications/0027884335

U2 - 10.1093/comjnl/36.6.579

DO - 10.1093/comjnl/36.6.579

M3 - Article

AN - SCOPUS:0027884335

SN - 0010-4620

VL - 36

SP - 579

EP - 587

JO - Computer Journal

JF - Computer Journal

IS - 6

ER -

Linear time algorithm for finding minimal perfect hash functions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this