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.
tl;dr: Each insertion is O(n), but n insertions are also O(n). Saying "amortized time is O(1)" just means the time for n operations is O(n).
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).
"Amortized O(1) time" means the time for n operations is O(n), even though individual operations might be more than O(1). Building the hash table means adding n things. So they're saying its linear.
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.
Yes, interesting. Never heard of EPH before.
cmph contains only: BDZ, BDZ_PH, BMZ, BMZ8, BRZ, CHD, CHD_PH, CHM and FCH.
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.
13 comments
[ 4.1 ms ] story [ 33.9 ms ] threadhttps://www.gnu.org/software/gperf/
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.