@aparrish I'm pretty sure sampling at random until you get a hit is the optimal algorithm for this. Bad worst-case performance that you will almost certainly never see, constant time average-case performance.

You'll probably want to add checks for low fill ratios if those can happen, like when you're first populating the table, but you could also implement a linear congruential PRNG to use as a secondary PRNG since it's guaranteed to hit every slot without repeats. Or if you only have low fill ratios at small array sizes, like with a growable hash table, and if you know the number of stored items, you can choose the nth item at random and scan the array linearly, counting until you hit it. Slow but potentially faster than calling the PRNG over and over at low fill ratios.