[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: [ANN] BDZ perfect hash
- From: Alexander Nasonov <alnsn@...>
- Date: Sun, 19 Feb 2017 01:27:23 +0000
I'd like to announce a small (less than 300LOC) module for building
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  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.