关键词：哈希碰撞 碰撞即停 生日悖论变种

一、碰撞即停法的操作步骤

1. 按转发顺序记录用户的uid，然后计算uid对应的md5

   (当然可以采用其他方式, 要检查的内容也对应改动)

2. 按转发顺序检查md5后x位，如果后x位曾经出现过，则记发生一次碰撞，不再继续检查，碰撞的两人中奖；未曾出现过，则记录下后x位以及对应的uid

二、以上次抽奖为例

按转发顺序排列的数据如下:

• 冲击钻突贯龙 17326472 md5后2位是4F

• 拉特Letter 184982194 md5后2位是FE

• 纳维戈特 483799697 md5后2位是D8

• 龙祈星吟 232642230 md5后两位是FE

• 暝夜丶 21675446 md5后两位是60

• 四零七407 87623346 md5后两位是31

• ......

则检查过程是:

1. 冲击钻突贯龙 4F 未曾出现

2. 拉特Letter FE 未曾出现

3. 纳维戈特 D8 未曾出现

4. 龙祈星吟 FE 和拉特Letter的发生碰撞，检查中止

三、概率求算思路

首先，将碰撞对分为碰撞者（顺序靠后的）和被碰撞者（顺序靠前的），被碰撞的概率难求，主动碰撞的概率易求。记碰撞池总容量为M，对于md5后两位而言，M=16种可能^2位=256。假定第一个转发者的编号是0，后面依次编号，

那么，n号转发者成为主动碰撞者的条件是(1)前n个转发者都未能碰撞(2)自己成功碰撞。所以n号转发者主动碰撞的概率是

(M/M) * ((M-1)/M) * ((M-2)/M) * ... * ((M-n+1)/M) * (n/M)

即(M-n+1)!/(M^n) * n/M

由此，被碰撞的概率就是n号转发者主动碰撞的概率平摊到前n个转发者身上

∑(i=1,n) ((M-i+1)!/(M^i) * 1/M)

b站没有公式编辑器，将就着看吧

由此绘出图像