做一份能重放的随机抽样：水塘算法、种子与输入摘要

“种子已经记下来了，为什么这次抽到的名单还是不同？”先别怀疑Random。输入行顺序、过滤规则、重复记录和算法调用次数，都可能改变同一条伪随机序列被用在什么位置。

可复现抽样不只是给new Random传一个固定数字。需要把输入身份、遍历顺序、抽样算法和参数一起固定。尤其是从大清单中抽k行时，先全量shuffle既要保存全部输入，也会把算法实现与容器顺序带进结果。

这次实现一个可直接运行的水塘抽样工具：输入UTF-8逐行ID，保留至多k条，最终按原始行号展示。结果带种子、总行数、原始字节SHA-256和算法名reservoir-r1。它抽的是行，不承诺相同ID只出现一次。

不知道总行数，也能维护一个大小为 k 的样本

前k行直接进入水塘。读到第i行时，在0到i-1中均匀选择一个位置；若位置小于k，就替换水塘相应槽位，否则不选当前行。

这让第i行被选中的概率为k除以i，已入选的旧行继续保留到结束的概率也按同样关系调整。它不是给每条记录独立掷一个固定概率的硬币：后者只能得到随机样本数量，不能保证至多k条的固定容量结果。

代码使用Java 17的受限long随机入口，避免自己取模引入偏差。总行数虽然在样本预算内很小，仍用long表示并明确检查，算法不依赖int行号回绕。

完整工具和可复现输入

需要完整JDK 17，保存为 ReplayableSample.java。无参数会创建八行固定输入跑回归；也可以传入文件、k和种子执行自己的受控清单。源码命令为java ReplayableSample.java，或java ReplayableSample.java ids.txt 3 123。

import java.io.*;
import java.nio.charset.*;
import java.nio.file.*;
import java.security.*;
import java.util.*;
public class ReplayableSample {
    record Pick(long row, String id) { }
    record Sample(long seed, long rows, String sha256, List<Pick> picks) { }
    static final class Limited extends FilterInputStream {
        long count; final long limit;
        Limited(InputStream in, long limit) { super(in); this.limit = limit; }
        int checked(int n) throws IOException {
            if (n > 0 && (count += n) > limit) throw new IOException("BYTE_LIMIT");
            return n;
        }
        public int read() throws IOException { int n = in.read(); checked(n < 0 ? 0 : 1); return n; }
        public int read(byte[] b, int off, int len) throws IOException {
            if (len == 0) return 0;
            return checked(in.read(b, off, (int)Math.min(len, limit - count + 1)));
        }
    }
    static Sample sample(Path path, int k, long seed) throws Exception {
        if (k < 0 || k > 1000) throw new IllegalArgumentException("k must be 0..1000");
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        Random random = new Random(seed); List<Pick> reservoir = new ArrayList<>(k); long seen = 0;
        CharsetDecoder decoder = StandardCharsets.UTF_8.newDecoder()
                .onMalformedInput(CodingErrorAction.REPORT).onUnmappableCharacter(CodingErrorAction.REPORT);
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(
                new DigestInputStream(new Limited(Files.newInputStream(path), 1024 * 1024), digest), decoder))) {
            for (String line; (line = reader.readLine()) != null; ) {
                if (line.isBlank() || line.length() > 128) throw new IOException("INVALID_LINE");
                if (++seen > 10000) throw new IOException("ROW_LIMIT");
                if (k == 0) continue;
                if (reservoir.size() < k) reservoir.add(new Pick(seen, line));
                else {
                    long slot = random.nextLong(seen);
                    if (slot < k) reservoir.set((int)slot, new Pick(seen, line));
                }
            }
        }
        reservoir.sort(Comparator.comparingLong(Pick::row));
        return new Sample(seed, seen, HexFormat.of().formatHex(digest.digest()), List.copyOf(reservoir));
    }
    public static void main(String[] args) throws Exception {
        if (args.length == 3) {
            Sample s = sample(Path.of(args[0]), Integer.parseInt(args[1]), Long.parseLong(args[2]));
            System.out.println("algorithm=reservoir-r1"); System.out.println(s); return;
        }
        if (args.length != 0) throw new IllegalArgumentException("file k seed expected");
        Path file = Files.createTempFile("sample-input-", ".txt");
        try {
            List<String> ids = List.of("A", "B", "C", "D", "E", "F", "G", "H");
            Files.write(file, ids, StandardCharsets.UTF_8);
            Sample one = sample(file, 3, 123), two = sample(file, 3, 123);
            System.out.println("same_result=" + one.equals(two));
            System.out.println("selected=" + one.picks());
            System.out.println("zero_size=" + sample(file, 0, 123).picks().size());
            System.out.println("larger_k=" + sample(file, 20, 123).picks().size());
            List<String> reverse = new ArrayList<>(ids); Collections.reverse(reverse);
            Files.write(file, reverse, StandardCharsets.UTF_8);
            System.out.println("order_digest_changed=" + !one.sha256().equals(sample(file, 3, 123).sha256()));
            Files.writeString(file, "A\n\nB\n");
            try { sample(file, 3, 123); throw new AssertionError(); }
            catch (IOException expected) { System.out.println("blank=" + expected.getMessage()); }
        } finally { Files.deleteIfExists(file); }
    }
}

无参数核对输出：

same_result=true
selected=[Pick[row=1, id=A], Pick[row=7, id=G], Pick[row=8, id=H]]
zero_size=0
larger_k=8
order_digest_changed=true
blank=INVALID_LINE

same_result为true，证明同一份字节、顺序、参数和程序重复运行得到同样选择。修改输入顺序以后摘要不同，工具不会把它悄悄当成同一次实验。k大于输入行数时返回所有可用行，k为0则不保留任何行，但仍读完并记录输入身份。

输入摘要记录的是哪一份数据

SHA-256在读取原始字节时更新，而不是对去空白或重新编码后的ID计算。LF与CRLF、BOM和末尾换行差异，都可能使摘要不同。这样记录保守但清楚：只要输入文件字节变化，就不轻率宣称它还是同一份输入。

如果业务想按规范化后的逻辑记录识别输入，需要另设规范格式并记录版本，再计算相应摘要。不要在一次重构中无声把原始摘要改成逻辑摘要，然后沿用同一字段名，历史重放会失去可比性。

摘要也不是来源认证。它帮助确认两次输入是否相同，不证明文件由谁提供或没有被有权限的人替换。需要可信交付时，应由存储权限、签名或其他流程保证，抽样算法不替它们背书。

行顺序属于实验参数

同一组ID换顺序，会让每行遇到不同i，也会把随机选择映射到不同记录。若输入来自数据库，必须有确定ORDER BY及平局规则；若来自多个文件，文件合并次序也要写进协议。

在程序里先sort再抽样当然可以，但它改变了算法输入。排序会消耗额外时间与内存，大规模场景还可能需要外部排序。更直接的办法是让输入生产者交付一份固定有序快照，并把这份快照与元数据一起保存。

相同行ID出现两次时，本工具按两条行处理，因此这个ID可能有更大入选机会，也可能在结果出现两次。这不是水塘算法失衡，而是抽样单位定义不同。需要均匀抽独立用户时，应先生成每用户一条的清单；在线去重通常需要保存已见集合，内存成本就不再只是k条水塘。

结果按行号展示，不改变抽中身份

水塘槽位的顺序由替换历史决定，不等于原输入顺序。程序在抽样结束以后按原行号排序，方便人工核对和后续提取。这个排序只改变输出呈现，不重新挑选样本。

如果调用方希望随机顺序展示，可以在选定后使用单独、明确的随机过程，并记录其种子或从主种子派生规则。不能为了排序再消费同一个Random，随后又继续抽其他批次，却期望结果不受影响。

同一Random连续处理两个文件与分别以同种子处理两个文件，也不是同一实验。把随机生成器作用域固定在一次sample调用内，可以让每份输入独立重放；需要跨批次连续序列时，则应显式保存算法状态与边界。

资源预算与错误记录

示例只接收一兆字节以内、最多一万行、每行最多128个UTF-16码元，k最多1000。字节限额在解码器下方，错误编码按REPORT拒绝；空白行也是错误，不会悄悄跳过并改变后续行号。

行长在BufferedReader交付字符串后检查，因此它不是任意大输入的低内存逐字符行解析器；外层一兆字节预算给这一实现提供明确上界。需要更大或不可信连续输入时，应改成有界分行器，而不是只把MAX_BYTES放大几个数量级。

读取中途失败就不返回部分样本。否则同一份坏文件在不同失败时点可能交出不同规模结果，却都带着相同种子。调用方应记录失败类别，不把它当一次有效抽样报告。

源文件读取期间如果还能被写入，得到的摘要和样本对应的是实际观察到的字节流，不一定是某个历史版本的完整文件。真正要求重放时，应使用已封存快照或版本化对象，不能靠计算摘要把变化文件自动变成稳定输入。

版本升级时保留一份黄金样本

固定种子不意味着所有语言、所有Random算法和所有JDK未来实现细节都可互换。这里明确采用Java 17、java.util.Random和reservoir-r1的调用顺序；迁移随机API或改变筛选步骤时，先用固定输入核对预期结果，再决定升级算法版本。

回归应分别覆盖重复运行、k为0、k大于行数、非法k、空文件、空白行和坏UTF-8。频率检验可在算法验证层补充，但普通测试不应要求每一次抽样都覆盖每个类别，那恰好会误解随机波动。

一次可交付的抽样结果，应该能回答抽了哪份输入、按什么顺序、用了什么规则，以及为何只有这些行。把这些记录与选中行号一起保存，种子才有机会成为真正可用的重放线索，而不是一个看起来专业却无法还原过程的数字。