Java 50,000 个随机的 7 位十六进制字符串之间如何不发生碰撞 (生日问题)

发布于04月25日

我遇到过一些代码，它们通过UUID.randomUUID()生成许多UUID，取每个UUID的最后7位(最新版本的UUID按照熵均匀分布)，并将其用作向数据库中插入行的键.

我想知道相撞的可能性有多大.我记得有the Birthday Problem个.这就是那个问题的一个例子，不是吗？一年中不是365天，而是16^7个可能的字符串.然后根据维基百科的页面，给定n个字符串，冲突的概率为

其中d是16^7.

一位同事声称，他们能够插入50,000行，没有任何问题.我对此表示怀疑，因为与n=50,000和d=16^7相撞的可能性是

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

但后来我查了我们的数据库.事实上，5万个插入物成功了.

这怎么可能？(除此之外，他们真的很幸运.)我是不是错用了生日问题？

Edit个

这是一个最低限度的测试，显示有should起碰撞事件.

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次try 中有10次发生冲突-预计碰撞率为99%.对于N=10,000，我看到10次try 中有0次、1次、2次或3次发生冲突，这都在17%的冲突率的预期范围内.