碰撞即停法抽獎(jiǎng)原理
關(guān)鍵詞：哈希碰撞 碰撞即停 生日悖論變種
一、碰撞即停法的操作步驟
按轉(zhuǎn)發(fā)順序記錄用戶的uid，然后計(jì)算uid對(duì)應(yīng)的md5
(當(dāng)然可以采用其他方式, 要檢查的內(nèi)容也對(duì)應(yīng)改動(dòng))
按轉(zhuǎn)發(fā)順序檢查md5后x位，如果后x位曾經(jīng)出現(xiàn)過，則記發(fā)生一次碰撞，不再繼續(xù)檢查，碰撞的兩人中獎(jiǎng)；未曾出現(xiàn)過，則記錄下后x位以及對(duì)應(yīng)的uid
二、以上次抽獎(jiǎng)為例
按轉(zhuǎn)發(fā)順序排列的數(shù)據(jù)如下:
沖擊鉆突貫龍 17326472 md5后2位是4F
拉特Letter 184982194 md5后2位是FE
納維戈特 483799697?md5后2位是D8
龍祈星吟 232642230 md5后兩位是FE
暝夜丶 21675446 md5后兩位是60
四零七407 87623346 md5后兩位是31
......
則檢查過程是:
沖擊鉆突貫龍 4F 未曾出現(xiàn)
拉特Letter FE 未曾出現(xiàn)
納維戈特?D8 未曾出現(xiàn)
龍祈星吟?FE 和拉特Letter的發(fā)生碰撞，檢查中止
三、概率求算思路
首先，將碰撞對(duì)分為碰撞者（順序靠后的）和被碰撞者（順序靠前的），被碰撞的概率難求，主動(dòng)碰撞的概率易求。記碰撞池總?cè)萘繛镸，對(duì)于md5后兩位而言，M=16種可能^2位=256。假定第一個(gè)轉(zhuǎn)發(fā)者的編號(hào)是0，后面依次編號(hào)，
那么，n號(hào)轉(zhuǎn)發(fā)者成為主動(dòng)碰撞者的條件是(1)前n個(gè)轉(zhuǎn)發(fā)者都未能碰撞(2)自己成功碰撞。所以n號(hào)轉(zhuǎn)發(fā)者主動(dòng)碰撞的概率是
(M/M) * ((M-1)/M) * ((M-2)/M) * ... * ((M-n+1)/M) *?(n/M)
即(M-n+1)!/(M^n) * n/M
由此，被碰撞的概率就是n號(hào)轉(zhuǎn)發(fā)者主動(dòng)碰撞的概率平攤到前n個(gè)轉(zhuǎn)發(fā)者身上
∑(i=1,n) ((M-i+1)!/(M^i) * 1/M)
b站沒有公式編輯器，將就著看吧
由此繪出圖像
