Lessons from Pick Index

Three key points:

$1.$ Reservoir sampling gives uniform selection without preprocessing or knowing the count.

$2.$ Each element gets replaced with probability $\frac{1}{k}$ where $k$ is its position among matches.

$3.$ This technique works for streaming data where you cannot store all matches.