基于secrets.choice的固定词表密码短语生成器重复概率异常

我开发了一个基于固定词表的密码短语生成器，每个位置对应特定词表，核心生成逻辑如下：

def generate(self) -> str:
    passphrase = "%s-%s-%s-%s-%s%s%s" % (
        self.choose_word(self.verbs),
        self.choose_word(self.determiners),
        self.choose_word(self.adjectives),
        self.choose_word(self.nouns),
        self.choose_word(self.numbers),
        self.choose_word(self.numbers),
        self.choose_word(self.numbers),
    )

词表规模：

• 形容词：100个
• 限定词：9个
• 名词：217个
• 动词：67个
• 数字：1-9（共9个）

选词逻辑使用secrets.choice实现：

def choose_word(cls, word_list: List[str]) -> str:
    return secrets.choice(word_list)

理论上总唯一组合数约130亿，但我编写的测试用例（单次生成10000个短语并检查唯一性）在通过pytest-repeat运行4145次后，出现了24次重复碰撞。测试代码如下：

def test_can_generate_10000_passphrases_without_collision(passphrase: Passphrase):
    generated_passphrases = []
    for i in range(10000):
        generated_passphrase = passphrase.generate()
        assert generated_passphrase is not None and len(generated_passphrase) > 10
        assert generated_passphrase not in generated_passphrases
        generated_passphrases.append(generated_passphrase)

    assert len(generated_passphrases) == 10000

我已经尝试切换到secrets.choice（原本用random.choice）、每次运行重新实例化生成器类、增加非空检查、在Docker内外运行等操作，但问题依然存在。想知道重复概率异常的原因，是概率计算有误、测试逻辑有问题还是其他因素？

1. 概率计算的认知误区 #

你觉得130亿总空间下生成10000个短语不会碰撞，这是直觉错误，生日悖论会让碰撞概率远高于预期：
根据生日悖论近似公式，碰撞概率为：
P ≈ 1 - e^(-n²/(2N))
其中n=10000（单次生成数量），N=1.3×10^10（总组合数）

代入计算：
n²/(2N) = (10^8)/(2.6×10^10) ≈ 0.0038
e^-0.0038 ≈ 0.9962
碰撞概率P ≈ 1 - 0.9962 = 0.38%

按此概率，4145次测试的期望碰撞次数约为15.7次，实际出现24次属于统计波动范围内的正常情况，并非概率计算错误或生成器故障。

2. 词表可能存在重复条目 #

如果某个词表内部有重复条目（比如形容词列表里同一个词出现多次），会导致实际唯一组合数远低于理论值，进而提升碰撞概率。比如若形容词列表有10个重复词，实际唯一形容词数量为90，总组合数会降到117亿，碰撞概率随之升高。

3. 测试逻辑的潜在问题 #

• 用列表存储已生成短语时，generated_passphrase not in generated_passphrases是线性查找，虽逻辑正确，但极端情况下可能出现比较错误（概率极低）；
• 需确认测试用例的passphrase fixture作用域，若为全局复用（如session级），即使手动实例化也可能因状态异常导致重复。

1. 验证词表唯一性
   检查所有词表（verbs、determiners、adjectives、nouns）内部是否存在重复条目，确保每个词表元素唯一，保证理论组合数的准确性。

2. 调整测试预期
   不要把“生成10000个无重复短语”作为必过测试，可选择：

• 降低单次生成数量（如改为1000个），此时碰撞概率降至≈0.0038%，几乎不会出现碰撞；
• 将测试改为统计碰撞频率，验证其是否符合理论概率范围。

3. 优化碰撞检测效率与可靠性
   用集合（set）代替列表存储已生成短语，in操作时间复杂度从O(n)降到O(1)，避免线性查找的极端问题：

def test_can_generate_10000_passphrases_without_collision(passphrase: Passphrase):
    generated_passphrases = set()
    for i in range(10000):
        generated_passphrase = passphrase.generate()
        assert generated_passphrase is not None and len(generated_passphrase) > 10
        assert generated_passphrase not in generated_passphrases
        generated_passphrases.add(generated_passphrase)

    assert len(generated_passphrases) == 10000

4. 确认随机源有效性
   临时添加日志输出几次choose_word的结果，确认secrets.choice无重复选择的异常模式；同时检查运行环境熵池是否充足（嵌入式/容器环境可能熵不足，但桌面/服务器环境一般无此问题）。

内容的提问来源于stack exchange，提问作者Alec Joy