When the population is much larger than the count you need (say n / max < 0.5), each random draw is almost guaranteed to be new. The expected number of retries to fill the Set is n + small constant, so this is O(n) in practice and the code stays readable. Throw early if the caller asks for more uniques than the range allows, otherwise the loop never terminates. This is the right default for picking 5 of 100, 50 of 10000, or any case where you are sampling sparsely from a large pool.

The retry approach degrades when n approaches max: at n = max - 1, the last draw collides on every value already picked except one, costing roughly max retries on its own. The partial Fisher-Yates fix builds the full [0..max) array once, then shuffles only the first n positions and returns that prefix. Each iteration picks a random index in [i, max) and swaps; the result is a uniform random sample without any retry loop. Memory is O(max), time is O(n), and the algorithm produces every n-permutation with equal probability. Use this when n / max > 0.5 or when you cannot tolerate the variance in retry counts.

Reservoir sampling solves a different problem: pick n uniformly random items from a stream whose total length is not known until you finish iterating. You cannot store everything, you cannot index randomly, and you cannot revisit. Algorithm R fills the first n items into the reservoir, then for each subsequent item at position i (0-indexed) it picks a random slot in [0, i]; if that slot is < n, the new item replaces the reservoir slot. The math works out so every item ends up in the reservoir with probability n / total. Use this for log lines, paginated APIs, or any source where the total count is unknown or huge.