The algorithm used (EPH) seems bit curious. The paper says "The EPH algorithm was implemented in the C language
and is available at <a href="http://cmph.sf.net"" rel="nofollow">http://cmph.sf.net"</a>, 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.
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.
Relevant, alternate implementation for C and C++:<p><a href="https://www.gnu.org/software/gperf/" rel="nofollow">https://www.gnu.org/software/gperf/</a>
“(although, for many methods, it can still be bounded by amortized O(1) time)”<p>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.