[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **[ANN] BDZ perfect hash**
**From**: Alexander Nasonov <alnsn@...>
**Date**: Sun, 19 Feb 2017 01:27:23 +0000

Hi,
I'd like to announce a small (less than 300LOC) module for building
perfect hashes:
https://gist.github.com/alnsn/68f599bc9358fcee122d6175392d779f
For a set of keys and a good primitive hash function (jenkins, xxhash,
etc), the algorithm builds a perfect hash that maps the keys to small
numbers. For instance, 26 keys "a"..."z" can be mapped by the algorithm
to numbers from 0 to 53.
The algorithm is randomized but each iteration runs in linear time
and it usually finishes only after a few iterations.
The module comes with a small demo which I hope will make it easier
to understand the algorithm.
PS I planned to announce a bigger C/C++ library with Lua support [1] but
documenting it will take some time. On the other hand, pure Lua code is
so small and so much simpler that it has a value on its own.
PPS There is a variant of the same algorithm that produces more compact
mapping (e.g. 26 keys are maps to values 0 to 32). I can write it too,
if there is an interest.
[1] https://github.com/alnsn/rgph
[2] http://cmph.sourceforge.net/bdz.html
Alex