一个6位随机字母数字代码发生碰撞的概率是多少？

Question

我正在使用以下Perl代码生成随机的字母数字字符串（仅包括大写字母和数字），用作MySQL数据库记录的唯一标识符。该数据库可能会保持在100万行以下，但绝对的最大值将约为300万行。 我的问题是有没有危险两条记录具有相同的随机代码，或者这种情况只会发生极少次数？由于我对概率知之甚少（如果从这个问题的性质上还不清楚的话），所以希望能得到他人的意见。

perl -le 'print map { ("A".."Z", 0..9)[rand 36] } 1..6'

- Nick

---

为什么不能只使用自动递增字段？ - murgatroid99

如果自动递增无法正常工作，考虑使用UUID代替。它们被设计为随机标识符，并具有最小碰撞几率。https://metacpan.org/module/Data::UUID - Schwern

如果在数据库中创建了唯一索引，当发生冲突时，DBI会抛出异常。您可以捕获异常，生成另一个代码，然后再次尝试插入。当您使用了许多可用代码时，这当然不是特别有效的方法。 - Grant McLean

Answer 1

因为生日悖论的存在，这比你想象的更有可能发生。

有 2,176,782,336 种可能的代码，但即使只插入 50,000 行，发生碰撞的几率已经相当高了。对于 1,000,000 行，很可能会出现许多碰撞（我认为平均约有 250 次）。

我进行了几次测试，以下是在第一次碰撞发生之前我能够生成的代码数量：

• 73366
• 59307
• 79297
• 36909

随着代码数量的增加，碰撞将变得更加频繁。

这是我的测试代码（用 Python 编写）：

>>> import random
>>> codes = set()
>>> while 1:
        code=''.join(random.choice('1234567890qwertyuiopasdfghjklzxcvbnm')for x in range(6))
        if code in codes: break
        codes.add(code)

>>> len(codes)
36909

- Mark Byers

---

如果长度不固定怎么办？比如说它只能返回一个字符，我们能否使用生日悖论的公式来计算呢？ - buncis

Answer 2

你有36**6个可能的代码，大约为20亿。将其称为d。使用在这里找到的公式，我们发现对于n个代码，碰撞的概率大约为

1 - ((d-1)/d)**(n*(n-1)/2)

对于任何超过50,000左右的n值，那就相当高了。

看起来10个字符的代码只有大约1/800的碰撞概率。所以选择10个或更多。

- Tom Zych

Answer 3

如前所述，生日悖论使得这种事件非常可能发生。特别地，当问题被视为碰撞问题时，可以确定一个精确的近似值。设p(n; d)为至少有两个数字相同的概率，d为组合数，n为试验次数，则我们可以证明p(n; d)近似等于：

1 - ((d-1)/d)^(n*(n-1)/2)

我们可以很容易地在R中绘制这个图表：

> d = 2176782336
> n = 1:100000
> plot(n,1 - ((d-1)/d)^(n*(n-1)/2), type='l')

这张图片展示了随着测试/行数的增加，碰撞概率会快速增加。

- csgillespie

Answer 4

根据这个链接给出的公式，在这样一个空间中只需插入约55,000条记录就有50%的概率遇到至少一个冲突：

http://wolfr.am/niaHIF

如果尝试插入两到六倍数量的记录，几乎肯定会导致冲突。您需要非随机地分配代码或使用更大的代码。

- user149341

---

如果长度不固定怎么办？比如说它只能返回一个字符，我们能否使用生日悖论的公式来计算呢？如果不能，那么我们可以使用什么公式来计算呢？ - buncis

Answer 5

虽然我不知道您想如何使用这些伪随机ID的具体细节，但您可能需要考虑生成一个由3000000个整数（从1到3000000）组成的数组，并对其进行随机洗牌。这将确保数字是唯一的。 请参见维基百科上的Fisher-Yates shuffle。

- Alexey Frunze

---

考虑到可能的排列数量，某些序列比其他序列更有可能被选中。 - Sinan Ünür

Answer 6

警告：请注意不要过于依赖内置的 rand，因为伪随机数生成器的质量很重要。我最近了解到 Math::Random::MT::Auto：

Mersenne Twister 是一种快速的伪随机数生成器（PRNG），能够为可能耗尽可用的“真正”随机数据源或系统提供的 PRNG（如 rand）的应用程序提供大量（>10^6004）的“高质量”伪随机数据。

该模块提供了一个方便的 rand 替代品。

您可以使用以下代码生成密钥序列：

#!/usr/bin/env perl

use warnings; use strict;
use Math::Random::MT::Auto qw( rand );

my $SEQUENCE_LENGTH = 1_000_000;
my %dict;
my $picks;

for my $i (1 .. $SEQUENCE_LENGTH) {
    my $pick = pick_one();
    $picks += 1;

    redo if exists $dict{ $pick };

    $dict{ $pick } = undef;
}

printf "Generated %d keys with %d picks\n", scalar keys %dict, $picks;

sub pick_one {
    join '', map { ("A".."Z", 0..9)[rand 36] } 1..6;
}

一段时间前，我写过关于 Windows系统上内置rand的有限范围 的文章。你可能不在使用Windows系统，但是你的系统可能存在其他限制或潜在问题。

- Sinan Ünür