3 ms·
An optimal algorithm for generating minimal perfect hash functions [pdf]
- icsa 5y agoI discovered this paper in the late 90s. It changed the nature of my work for the next decade or so. An O(n) algorithm for generating MPH functions seemed like a miracle, at the time. Being able to solve "impossible" problems (at the time) gave me access to many opportunities.
- kklisura 5y agoI found out this paper while I was checking out Postgres source code [1]. This is used for generating hash table of postgres keywords, where the hash function is produced on compile time (?) and used in that hash table - if I got everything right. [1] https://github.com/postgres/postgres/blob/master/src/tools/PerfectHash.pm#L8 https://github.com/postgres/postgres/blob/master/src/tools/P...
- dekhn 5y agominimal perfect hash functions are really underrated