直接回答：场景：数据流长度未知且只能过一遍（日志流、网络包），要等概率抽 k 条。算法：前 k 条直接入池；第 i 条（i>k）以 k/i 的概率入池，入池时等概率替换池中某一条。每条数据的最终入选概率恰为 k/n（n 为流总长），O(k) 空间 O(n) 时间。
展开解析：归纳法证明核心：假设处理完前 i-1 条时，每条在池中的概率是 k/(i-1)。第 i 条以 k/i 入池，概率正确。对已在池中的任一条：它留在池中的概率 = 第 i 条不入池（1-k/i）+ 第 i 条入池但没替换它（k/i × (k-1)/k）= (i-k)/i + (k-1)/i = (i-1)/i，于是它处理后的入选概率为 k/(i-1) × (i-1)/i = k/i，归纳成立。变体与延伸：加权版本（A-ES 算法，按权重 w 取 key=u^(1/w) 排序取前 k，指数跳跃可把跳过过程加速到 O(k log(n/k))）；分布式归并（各机器本地蓄水池后按处理量加权合并）。工程应用：线上请求采样（保留代表性错误样本）、大图采样、A/B 实验分流。实现细节：替换下标用 rand(0, i-1) < k 的形式表述更顺手；随机数质量直接决定抽样无偏性；流可重放时不如直接计数后等距抽样，水塘的价值恰在“不可重放”。
追问方向：k=1 时退化成什么？如何证明加权版本的概率正确性？
（约 470 字）