与6位随机字母数字代码发生冲突的概率是多少？

Question

我使用以下perl代码生成随机字母数字字符串(仅限大写字母和数字),以用作MySQL数据库中记录的唯一标识符.该数据库可能会保持在1,000,000行以下,但绝对现实最大值约为3,000,000.我有2个记录具有相同随机码的危险机会,或者它可能发生的次数非常少吗？我对概率知之甚少(如果从这个问题的性质来看还不是很清楚)并且会喜欢某人的意见.

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

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

Answer 2

好吧,你有36**6个可能的代码,大约20亿.叫这个d.使用此处的公式,我们发现对于n个代码,碰撞的概率是近似的

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

对于超过50,000左右的任何n,这都是相当高的.

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

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')

这使

如您所见，碰撞次数随着试验次数/行数的增加而迅速增加

Answer 4

根据http://en.wikipedia.org/wiki/Birthday_paradox#Approximation_of_number_of_people中给出的等式,在将大约55,000条记录插入此大小的Universe后,有50%的机会遇到至少一次碰撞:

http://wolfr.am/niaHIF

试图插入两到六倍的记录几乎肯定会导致碰撞.您需要非随机分配代码,或使用更大的代码.