50000个随机生成的7位十六进制字符串之间为什么没有发生碰撞？（生日悖论问题）

Question

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

我想知道碰撞的概率是多少。我记得生日问题。这就是那个问题的一个实例，不是吗？一年有365天，而这里有16^7个可能的字符串。根据维基百科上的说法，给定n个字符串的碰撞概率为

其中d为16的7次方。

一位同事声称他们能够无问题地插入50000行数据。我对此表示怀疑，因为在n=50000和d=16的7次方条件下发生碰撞的概率是

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

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

这怎么可能呢？（除了他们真的很幸运之外。）我是不是误用了生日悖论？

---

编辑

这是一个最简化的测试，展示了该程序本应该会有碰撞。

import java.util.UUID;
import java.util.HashSet;

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

对于N=50,000，10次尝试中有10次发生冲突-这符合99%的冲突率的预期。对于N=10,000，我看到0、1、2或3次尝试中出现冲突，这都在17%的冲突率的范围内，符合预期。

- Andrew Cheong

---

没有头绪。一个有趣的测试是尝试通过一个快速的代码示例使用 UUID.randomUUID() 来生成 50,000 个7位数字 ID。每次运行这个程序时，你是否会发现99%的冲突？也许在 UUID.randomUUID() 背后的伪随机数生成器在某种程度上扭曲了概率。 - Scotty Jamison

假设你的算术是正确的，那么有四种合理的解释：（1）你很幸运，（2）ID实际上没有被截断为7位数字，（3）唯一性约束没有被正确地应用，（4）进行插入的代码具有检查和重试逻辑，当它生成重复时。仅凭你的问题中提供的信息，我们无法确切知道发生了什么事情。 - kaya3

99%是相当高的概率，但1/100的机会仍然相当可信。考虑到似乎没有其他解释（特别是因为进行了产生类似概率的示例运行），并且假设您已经正确阅读了代码并且没有其他奇怪的事情发生，您可能只需要说这是疯狂的运气。但是，如果您不尽快解决问题，您很快就会遇到一个集合 - 碰撞的几率随着您放入更多内容而变得越来越高！ - Scotty Jamison

在Python中复制：from uuid import uuid4; [len({uuid4().hex[:7] for i in range(50000)}) for i in range(100)]。我在200次尝试中得到了一个无冲突的集合。 - BoppreH

@Jorn - 哦，谢谢你指出来。我直接从维基百科复制了这张图片。它一定是一个透明的PNG。我已经用截图替换了它。 - Andrew Cheong

Answer 1

终于我有了一个解释。感谢大家提供的有用想法。

简短概述 - 我认为在插入时必须有唯一约束条件，因为数据库中确实有50,000个不同的代码。但事实证明，当时并没有这样的约束条件。最初的50,000个代码中确实存在重复，一个月后通过一次SQL语句（附加“1”）找到并修改了这些重复的代码。

详细解释：

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

这张表没有时间戳字段（例如 last_modified），否则我可能早就有了提示。我只知道这50,000个促销代码的批次是在2023年1月6日插入的——已经3个月了。

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

我认为，由于调用了.rollback()，插入50,000行是原子性完成的。换句话说，如果单个插入失败，那么在此之前的所有插入都应该被回滚。

（因此，一种可能性是我的同事们一直重试，直到他们命中1%的大奖。但当我问他们时，似乎并非如此。他们不记得必须重试。）

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

我希望能找到这个约束创建的时间戳，但并没有立即看到。我应该进一步追究，但我没有这样做，因为：我已经查询了不同 promo_code_ids 的计数，并获得了 50,000（请参见上面的第一个截图）。无论有没有约束，最终得到 50,000 个不同代码的概率仍然小于 1%。这就是我犯了错误的地方：认为代码在此之后没有被篡改。

今天我发现了一个 Liquibase XML 更改，它是在“成功”插入 50,000 条记录后的一个月添加的约束：

但是请注意，除了添加唯一约束条件之外，还有随之而来的SQL更改。我们实际上运行了一个脚本，在所有重复代码的末尾添加了“1”。因此，“插入50000个没有重复的代码”的成功是通过这种方式实现的：它并没有——首先没有约束条件，然后进行了更正。

- Andrew Cheong

---

请使用文本而不是图像来提供可以用文本表示的内容。评论是短暂的，请将评论中相关的内容放入帖子中。 - philipxy

Answer 2

运行您粘贴的确切代码，我得到了10次false。这意味着：是的，碰撞发生得相当可靠。继续运行直到返回“true”，我得到：

7685
27479
15262
46177
18297
17230
14050
12091
39249
8921

这似乎与数学相符，这是您所期望的（这些数字表示：我添加的第39249个ID与已经存在的ID发生了冲突）。

我假设您之所以提出这个问题，是因为您没有在自己的计算机上运行此代码或者误解了“false”的含义。

如果您确实运行了您粘贴的完全相同的代码，并且得到的不是10次false（也许有1次在120次左右会因为巧合而是true），那么可能是某些非常奇怪的事情发生了，很可能与您的奇怪JVM上的随机数生成方式有关。但是，这听起来非常牵强。

这里是稍微调整过的代码，以打印重复点：

        final int N = 20000;
        for (int trial = 0; trial < 10; trial++) {
            HashSet<String> strings = new HashSet<>();
            int i = 0;
            while (true) {
                i++;
                String uuid = UUID.randomUUID().toString();
                String id = uuid.substring(uuid.length() - 7);
                if (strings.contains(id)) {
                    success = false;
                    System.out.println(i);
                    break;
                }
                strings.add(id);
            }
//            System.out.println(success);
        }

以下是对你的朋友所观察到的情况的一些解释。这些只是猜测：

• 他们确实发生了碰撞，误解了情况：无论他们采取什么样的检查来确保没有碰撞，都是错误的。
• 他们的代码会检测到碰撞并“重新投掷骰子”。在这种情况下，随着你越来越接近数据库中16^7个条目，直到你运气好地避免碰撞的随机UUID的重新投掷次数呈指数增长，你的应用程序将随着时间的推移而变得越来越慢。你的朋友可能没有告诉你这一点，或者忘记了他们的代码会这样做。
• 按设计的查询实际上并没有插入UUID的最后7个字符，而是插入了整个UUID。
• 按设计的查询实际上并没有插入UUID的最后7个字符，而是插入了数据库默认值，例如自动递增（数据库序列）。
• 你的朋友使用的UUID生成器不是“正常”的（随机生成），而是修改过的变体；有各种各样的变体存在；例如，他们可能有自己的UUID生成器，只生成000001、000002等。在这种情况下，直到添加了16^7条记录，你才会遇到碰撞。

- rzwitserloot

---

嗯，我为什么要写那段代码然后不运行它呢？我的最后一段描述了我看到的输出。我在问题下的评论中也分享了更多细节。此时，我不仅在我的机器上运行它，还在生产服务运行的 Kubernetes 实例上运行了它。（我想知道 UUID 生成是否对硬件 / MAC 地址 / # of CPUs 等敏感）。我在这里恰好是因为情况很奇怪，我知道我肯定有哪里出错了。虽然感谢所有的建议 - 它们给了我一些更多的测试想法。 - Andrew Cheong

你的第一次“尝试”就命中了要害。我已经自问自答这个问题。感谢你的想法。 - Andrew Cheong

我想我误读了你的问题，并认为你将自己的代码实验解释为没有发生碰撞; 你添加它是为了表明在你的代码中确实发生了碰撞，而你想知道为什么DB（在你写问题时）似乎没有任何碰撞。对于没有正确阅读最后一段，我感到抱歉！ - rzwitserloot

啊，我明白了，是的，我能看出来它可能被解读为展示负面而不是正面的示例代码。我已经添加了一个标题来澄清这一点。谢谢你的解释！ - Andrew Cheong

Answer 3

有趣的统计数据 - 我在这个讨论中缺少"商业角度"。假设有2%-5%的目标客户有效使用促销代码：对于一个获得消息"您的促销代码已被使用"并转向竞争对手的客户来说，机会是多少？ 客户流失率可能不值得所有这些复杂的双平台独特性增强的努力。从统计学的角度来看：在数据库级别添加"1"不能修复三次出现，但如上所述：这无关紧要。

- OldFrank

---

是的，这些都是现实世界中的实际考虑因素。事实证明，添加一个“1”就足够有效了，因为这将生成一个8位代码，而所有其他代码都是7位数。由于它不能与任何7位数代码发生冲突，所以它有非常非常好的成功机会，而它确实成功了，但你的谨慎是正确的。有趣的是，在这种情况下，不是客户报告问题，而是账户经理试图一次创建成千上万个代码，并收到状态码500。我现在正在与产品经理商讨将其增加到10位数。就是这样。 - Andrew Cheong