A Linear Time Algorithm for Finding Minimal Perfect Hash Functions | Zendy

Zbigniew J. Czech | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Linear Time Algorithm for Finding Minimal Perfect Hash Functions

Author(s) -

Zbigniew J. Czech

Publication year - 1993

Publication title -

the computer journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.319

H-Index - 64

eISSN - 1460-2067

pISSN - 0010-4620

DOI - 10.1093/comjnl/36.6.579

Subject(s) - hash function , perfect hash function , pseudorandom number generator , algorithm , bipartite graph , rolling hash , function (biology) , mathematics , discrete mathematics , computer science , combinatorics , hash table , double hashing , graph , computer security , evolutionary biology , biology

A new algorithm for finding minimal perfect hash functions (MPHF) is proposed. The algorithm given three pseudorandom functions h 0 , h 1 and h 2 , searches for a function g such that F(w)= (h 0 (w)+g(h 1 (w))+g(h 2 (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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research