Yes, you can replace any key by other key.
A logical speedup is to ignore the rest of the elements in the range/set, and choose a new range/set, to maximize chances to find another new element.
Then the new set has exactly the same odds to find a match as the set you were about to run when finishing the range.
It feels counter intuitive, I know. If you want to be convinced just run the odds of both cases by taking a range of size 1000 with 5% probability.