Modern perfect hashing
55 points by gioele
55 points by gioele
Looks like this is essentially Knuth's multiplicative hash (multiply by a constant and take the high bits), where you try to find a constant that happens to give distinct values for each of your input strings?
This article cites and discusses an implementation of [the method proposed by Wojciech Muła] which uses the PEXT instruction. Impressive results...
I wonder if this could be turned into a Zig comptime API. Would be much nicer than external tools like gperf.
It is with a slightly different strategy, but andrewk blogged about a perfect string matching comptime solution and its API in Zig here: https://andrewkelley.me/post/string-matching-comptime-perfect-hashing-zig.html