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

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

• The expected number of entries to probe in a $\frac15$ full hashtable is not "five or so", but $\frac n5$. So the time to find an arbitrary entry is still $O(n)$. – SOFe May 2 at 12:42
• How do you maintain a linked list of used slots in the remove() operation? Accessing the $n$th element in a linked list is $O(n)$ as well. – SOFe May 2 at 12:45