If you want to guarantee it returns, then after N failed operations, just convert the hash table to a list and pick something at random. That will take O(N) tim

If you want to guarantee it returns, then after N failed operations, just convert the hash table to a list and pick something at random. That will take O(N) time, but since you've already spent O(N) time it amortizes out to no additional cost.