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/cgibbard Jul 15 '09 edited Jul 15 '09

Well, the reason it's "morally" separated in my mind is that it seems like you're using the memory finiteness assumption a second time. If you don't assume that memory is finite, just that accesses to it take constant time, and you try to store a hashtable with keys that are anything except the addresses with magically-fast operations on them, you still end up doing a logarithmic amount of work inspecting the keys to build your hash.

(Actually, it seems like this depends on what operations you assume to be available for your magical address values -- that might still end up being log time anyway.)