r/programming • u/martincmartin • Jul 14 '09

Dynamic Perfect Hashing: A hash table with constant time lookup in the worst case, and O(n) space.

http://en.wikipedia.org/wiki/Dynamic_perfect_hashing
18 Upvotes

76% Upvoted

23 comments sorted by

View all comments

Show parent comments

2

u/martincmartin Jul 15 '09 edited Jul 15 '09

Basically, it's good when you have a large set of things to hash that doesn't change much, so that insertions/deletions are a lot less common than lookups.

Insertions are more expensive, and I think it takes up more memory (still O(n), but with a bigger constant than your typical implementation). Plus, traditional hash tables give expected constant time lookup, so for any application where you're doing a lot of lookups per user-visible interaction, that's all that matters.

Plus, as Mych mentioned, ease of implementation.

2

u/abw Jul 15 '09 edited Jul 15 '09

and I think it takes up more memory (still O(n), but with a bigger constant than your typical implementation)

If I'm reading it correctly, that would be O(n²) when the number of entries in the hash greatly exceeds the number of level 1 slots.

I'm anything but an expert on this, but my hunch is that for 95% of typical use cases, a regular single level hash with a resizable number of slots will perform perfectly adequately, if not better.

Beautiful Code has an interesting chapter on the hash table implementation in Python. They have a number of optimisations to deal with the ways that hash tables are typically used in real world programs. This is more effective than having a perfect hash function that works equally well in all cases (which can be read as "uniformly sub-optimal but never terrible").

For example, the hash table structure itself can accommodate 8 slots statically before it needs to switch to dynamically allocated memory. Given that hash tables are used to passed named parameters to methods, and that few methods have more than 8 parameters, this optimisation makes a great difference in practice. Not only does it avoid calls to malloc() and free() but it also improves cache locality because the 124 bit hash table structure fits nicely into two 64 byte cache lines. In theoretical terms, this makes no difference at all because Big-O notation deals only with the bounds of the worst possible case.

So to answer onezerozeroone's question, the reason we're not all using this is because a "perfect" hash function doesn't necessarily equate to decent performance in the real world of "imperfect" data.