from Hacker News

Minimal Perfect Hash-Tables in Common Lisp

by vseloved on 2/1/18, 10:56 AM with 13 comments

  • by zokier on 2/2/18, 5:49 PM

    The algorithm used (EPH) seems bit curious. The paper says "The EPH algorithm was implemented in the C language and is available at http://cmph.sf.net", but that page has no mention of EPH and I even checked archive.org. I wonder why they ended up never actually releasing a version of cmph with that algorithm. Two years later they seem to have come up with another algorithm, CHD, which was actually released in cmph. Interestingly enough the CHD paper has no comparisons to EPH either.

  • by taeric on 2/2/18, 4:08 PM

    I love the reference to static structures. Indeed, I have a pet theory that most love of immutable lists is actually a love of static ones. Though, I typically expand that to measure statically visible in the code.

  • by resource0x on 2/2/18, 3:12 PM

  • by kruhft on 2/2/18, 2:57 PM

    Relevant, alternate implementation for C and C++:

    https://www.gnu.org/software/gperf/

  • by justinhj on 2/2/18, 5:35 PM

    “(although, for many methods, it can still be bounded by amortized O(1) time)”

    I don’t follow this. Does it mean that you can build the perfect hash table in constant time? Surely you can’t beat linear.