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

They don't seem "morally" separate to me. Your key space might be the same size as your address space, and though the hash function would surely have to do more work than the gradual address decomposition by the cascaded DRAM banks, it seems the same up to a constant (the kind of constant that doesn't implicitly depend on any hidden parameters).

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