Lower bound time complexity for obtaining an arbitrary entry in a hashtable

Question

I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable, the algorithm should return a pointer to an arbitrary nonempty entry in the hashtable. My answer was quite casual and I am not confident if my proof was correct. I am rephrasing the problem statement below:

• We are allowed to extend the insert()/remove() operations of a hashtable
• We need to expose a get_arbitrary() operation that always returns a nonempty entry in the hashtable if it is nonempty, or nil if it is empty.
• We are allowed to store extra data related to hashtable
• Assume hash keys are uniformly distributed.
• Assume insert()/remove() have memorylessly equal probability to be called on any key that exists in the hashtable.

This problem asks if it is possible to draw some relation on the lower bounds of the

• time complexity of insert() $T_i(n)$
• time complexity of remove() $T_r(n)$
• time complexity of get_arbitrary() $T_a(n)$
• space complexixty of any extra data we are storing, in addition to the original hashtable $S(n)$

One of the conjectures I thought of (as mentioned in the linked StackOverflow question) is $T_a(n) = O\left(\frac n{S(n)}\right)$, but I am not sure if this is correct. Also I am interested in knowing something can be said about how $T_a(n)$ relates to $T_r(n)$.

Answer 1

We usually assume that a reasonable proportion of entries in a hash table are used, or we would be wasting memory. If we know that a hash table is at least 20% full then we can just visit random locations until we find a used one , five or so in this case (starting with a random entry and checking consecutive entries wouldn’t work with badly distributed hash keys). You could do this if you re-hash the table with fewer slots if it gets to empty, or if you know that you never delete any hash entry.

You could have a bitmap of unused entries which would make the search faster by a large constant factor. You could create a linked list of the used slots if less than 20% of slots are used and maintain it until usage exceeds 50%, instead of re-hashing.