lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


I'd like to announce a small (less than 300LOC) module for building
perfect hashes:

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.