生日悖论与Hash需要位数

m个数字随机选取n次,各不相同的概率P=((m-1)/m)^(n*(n-1)/2)

m、n很大时取最高次项公式近似为P=((m-1)/m)^(n^2/2)

lim(m->+…)((m-1)/m)^m=1/e

有P=(1/e)^(n^2/2/m)

n=(log(1/e)(P)*2*m)^(1/2)

当P=0.5时,代入上式n=(1.386*m)^(1/2)=1.177*m^(1/2)

在生日悖论原题中,m=365,得n=22.49,即班上有23人时生日出现重复的概率就超过0.5了(虽然是近似计算,但这个误差已经很小了)。

选取hash的话,考虑简单用32数表示hash,看上去能表示的数字有40多亿,但从上式中可以看出,出现碰撞的概率其实是其能表示的数字开平方的级别,也就是数万条数据就可能出现碰撞,这是很可怕的。

为了使crc32不容易碰撞,我们取P=0.95,可求得n=20991。若要求更高取P=0.99,求得n=9291。

(鉴于博主的高中数学已经还给老师,高数又都喂狗了,windows的计算器没法对亿级别的数做指数运算所以没法用最开始的公式验证,所以上面的计算如有疏漏还请读者指正)

Leave a Reply

Your email address will not be published. Required fields are marked *