A Practical Minimal Perfect Hashing Method | Zendy

Fabiano C. Botelho | Zendy; Yoshiharu Kohayakawa | Zendy; Nívio Ziviani | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Practical Minimal Perfect Hashing Method

Author(s) -

Fabiano C. Botelho,

Yoshiharu Kohayakawa,

Nívio Ziviani

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-25920-1

DOI - 10.1007/11427186_42

Subject(s) - perfect hash function , hash function , computer science , dynamic perfect hashing , universal hashing , heuristic , k independent hashing , simple (philosophy) , set (abstract data type) , algorithm , constant (computer programming) , theoretical computer science , construct (python library) , hash table , discrete mathematics , mathematics , double hashing , artificial intelligence , philosophy , computer security , epistemology , programming language

We propose a novel algorithm based on random graphs to construct minimal perfect hash functions h. For a set of n keys, our algorithm outputs h in expected time O(n). The evaluation of h(x) requires two memory accesses for any key x and the description of h takes up 1.15n words. This improves the space requirement to 55% of a previous minimal perfect hashing scheme due to Czech, Havas and Majewski. A simple heuristic further reduces the space requirement to 0.93n words, at the expense of a slightly worse constant in the time complexity. Large scale experimental results are presented.

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