3 ms·
The optimal algorithm is the CHD algorithm - the function can use as little as 1.6bits per key. http://cmph.sourceforge.net/papers/esa09.pdf http://cmph.sourcef
by innagadadavida 8y ago
The optimal algorithm is the CHD algorithm - the function can use as little as 1.6bits per key. http://cmph.sourceforge.net/papers/esa09.pdf http://cmph.sourceforge.net/papers/esa09.pdf
There are implementations in Python: python chd perfect hashing
and in go: https://github.com/alecthomas/mph https://github.com/alecthomas/mph
In addition to the author's C code.
- alnsn 8y agoSpace optimal isn’t necessarily the fastest. Note that PostgreSQL code uses 2-graph instead of a more compact 3-graph version. The latter is noticeably more compact: 1.25 vs 2.1 factor.