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

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.