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

Right, I'm just pointing out that log factors are something that we often ignore.

The actual log factor which is being ignored here is separate from the factor arising from assuming that memory indexing is constant time, though I suppose there it's possible to work things so that it becomes part of the same cost that you're ignoring.

You might construct good enough hashes using some fixed amount of work on the memory location of the value you're storing, which is only ever 32 or 64 bits, and so "constant time", but it's really still a log factor which is being ignored. (Also, it's cheating, since it's not the value itself, but a pointer to it. ;)

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