50,000 个随机的 7 位十六进制字符串如何不发生碰撞？（生日问题）

Question

我遇到过一些代码，通过 生成多个 UUID UUID.randomUUID()，获取每个 UUID 的最后 7 位数字（最新版本的 UUID 在熵方面是均匀分布的），并使用它作为将行插入数据库的键。

\n

我想知道碰撞的概率是多少。我想起了生日问题。这是这个问题的一个例子，不是吗？一年不是 365 天，而是 16^7 种可能的字符串。然后根据维基百科页面，给定n 个字符串的碰撞概率为

\n

\n

其中d是 16^7。

\n

一位同事声称他们能够毫无问题地插入 50,000 行。我对此表示怀疑，因为与n=50,000和d=16^7发生碰撞的可能性是

\n

1-((16^7-1)/16^7)^(50000*(50000-1)/2) = 99.05%\n

\n

但后来我检查了我们的数据库。确实，50,000 次插入成功了。

\n

这怎么可能？（除此之外，他们真的很幸运。）我是否误用了生日问题？

\n

---

\n

编辑

\n

这是一个最小的测试，表明应该存在碰撞。

\n

import java.util.UUID;\nimport java.util.HashSet;\n\npublic class MyClass {\n    public static void main(String args[]) {\n        final int N = 50000;\n        for (int trial = 0; trial < 10; trial++) {\n            HashSet<String> strings = new HashSet<>();\n            Boolean success = true;\n            for (int i = 0; i < N; i++) {\n                String uuid = UUID.randomUUID().toString();\n                String id = uuid.substring(uuid.length() - 7);\n                if (strings.contains(id)) {\n                    success = false;\n                    // System.out.println(id);\n                    break;\n                }\n                strings.add(id);\n            }\n            System.out.println(success);\n        }\n    }\n}\n

\n

对于 N=50,000，10 次尝试中有 10 次发生碰撞\xe2\x80\x94，预计碰撞率为 99%。对于 N=10,000，我发现 10 次尝试中有 0、1、2 或 3 次发生碰撞，所有这些都在 17% 碰撞率的预期范围内。

\n

Answer 1

最后我有一个解释。感谢大家提供有用的想法。

\n

tl;dr - 我认为在插入时必须有一个唯一的约束，因为数据库中确实有 50,000 个不同的代码。但事实证明，当时并没有限制。原来的5万条确实有重复，一个月后通过一次性SQL语句发现并修改（通过追加“1”修改）。

\n

完整解释：

\n

该代码用于生成一次性使用促销代码，例如 SUMMER23-65ACFF9。这就是我推断数据库中确实插入了50,000 个不同代码的原因：

\n

\n

该表没有时间戳字段（例如last_modified），否则我可能会更早得到提示。我只知道这批50,000个促销代码是在2023年1月6日\xe2\x80\x943个月前插入的。

\n

\n

我浏览了 2023 年 1 月 6 日之前最后一次提交的存储库，看看当时的代码是否有某些内容可能允许 50,000 个代码成功。相关代码是这样的：

\n

\n

我相信，由于调用了 .rollback()，50,000 行的插入是自动完成的。换句话说，如果单个插入失败，则在此之前的所有插入都应该回滚。

\n

（所以一种可能是我的同事不断重试，直到中了 1% 的大奖。但当我问他们时，情况似乎并非如此。他们根本不记得必须重试.)

\n

我确实想知道插入时是否存在唯一 promo_code_id 的约束。我检查它确实存在：

\n

\n

我希望找到创建此约束的时间戳，但没有立即看到。我应该进一步追求这一点，但我没有，因为：我已经查询了不同promo_code_ids 的计数并获得了 50,000 个（请参见上面的第一个屏幕截图）。无论有没有约束，最终得到 50,000 个不同代码的概率仍然低于 1%。这就是我做出错误假设的地方：自 以来代码没有被篡改过。

\n

今天，我在 2 月份（“成功”50,000 次插入后一个月）遇到了 Liquibase XML 更改，我们显然在其中添加了约束：

\n

\n

但除了添加唯一约束之外，请注意随该更改而来的 SQL。我们实际上运行了一个脚本，在所有重复代码的末尾添加“1”。于是“插入50000条不重复的代码”就成功了：它没有\xe2\x80\x94，它一开始就没有约束，后来又纠正了。

\n