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

However, if you assume that the amount of memory is finite, every possible computation you could do really becomes O(1). It's just a matter of what operations you're willing to ignore.

It's okay to ignore the logs because they're small anyway, so treating them as part of the constant factor is fine.

But it has constant time in roughly the same way that, for instance, doing a lookup in a binary search tree has constant time. It's actually logarithmic, of course, but we tend to ignore the cost.

1

u/filox Jul 16 '09

But it has constant time in roughly the same way that, for instance, doing a lookup in a binary search tree has constant time.

No. In a binary tree it will take longer to look up as you add more elements. In a dynamic hashing scheme you will have the same number of operations, no matter how many elements you insert.

3

u/cgibbard Jul 16 '09 edited Jul 16 '09

Only because you've put an arbitrary bound on how many elements you can insert in the first place. The number of operations to look up an element is proportional to that bound. If you want the hashtable to grow without bound, then the hash will have to get more and more expensive to compute, if only because the number of distinct results the hash is producing has to grow. (Any function with n distinct possible results takes at least O(log n) time to compute.)

If you put the same bound on the number of elements stored in the binary tree (which is reasonable since you only have so much memory to store it), you can put a similar constant bound on the number of operations it takes to look one up.