Lower bound time complexity for obtaining an arbitrary entry in a hashtable
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.