0156名無し名人 (ワッチョイ 9fbd-CNA0)
2018/02/04(日) 01:48:05.06ID:23gFbzJ50ビンの中が満杯のとき、たまたまどれかのエントリの記憶する16 bitがハッシュキーの上位16 bit一致する確率は、p=1/(64 K)として
P = 3_C_1 * p * (1-p)^2 + 3_C_2 * p^2 * (1-p) + 3_C_3 * p^3
だけあって、一致したのだけれどそれで正解という(一致後の事後)確率は1/(ハッシュキーの総数)でしかないから
置換表を頻繁にクリアする(結果、ビンの中のエントリに大概空きがある)
という条件でも追加しない限り、
>>133の置換表は毎回だいたい確率Pで衝突を起こす
、、、