But it's easy to download & run.
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.
To be pedantic: some individual insertions can take more the O(1), namely when you have to rehash it can take O(n) time. So the tight upper bound on each insertion is O(n). So doing n of them seems like it might take O(n^2).
Except you can't rehash on every insertion. So even though the time to insert one is O(n), the time to insert n is also O(n). If you amortize that time over all n insertions, you get O(n) / n == O(1).
EPH seems to be better than BDZ, CHM and FCH, but only for really huge tables, like >100.000 entries. For smaller hash tables a simple perfect hash or even an optimized memcmp switch table is still faster. https://github.com/rurban/Perfect-Hash#benchmarks cmph is usually 2-3x slower than a trivial PH, and much slower for small tables.
