2 ms·
If the lists are immutable, could you not just construct a special hash function a priori that will guarantee no collisions?
by kccqzy 4y ago
If the lists are immutable, could you not just construct a special hash function a priori that will guarantee no collisions?
- jnwatson 4y agoYes. The term of art is “perfect hash”.
- yencabulator 4y agoPerfect Hash Functions are possible, but in my limited experience they rarely out-perform the naive thing where you pre-size the hash table to fit all your data (avoid grow-on-insert overhead). PHFs have two downsides: Finding a PHF for your data can take a bunch of CPU time so it's frustrating to have in your build, and the resulting hash function can be much more costly than a simpler hash function. That is, the cost of hashing can more than dominate an extra lookup in a tiny fraction of cases. I'd say the use case for PHF is more when you're absolutely memory-bound, e.g. in an embedded ROM. For anything else, just bump up your hash table size a little, to not have those collisions.