[ANN] BDZ perfect hash

[Alexander Nasonov <alnsn@...>]

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