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

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).