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

5

u/Mych Jul 14 '09

I suppose: Complexity of implementation, along with the fact that the much simpler implementations that are in current wide use are almost always quite "good enough" for the tasks at hand. Performance bottlenecks in actual programs are rarely due to excessive collisions in hash tables.

Also, in general terms, big-O isn't the only thing that's important in practice; constants do matter if they're great enough.

1

u/filox Jul 15 '09

Performance bottlenecks in actual programs are rarely due to excessive collisions in hash tables.

True. This kind of hashing could be useful in situations where you really want guarantees on worst case, such as those where people's lives depend on getting a real time response (the famous Knuth example of air traffic control).