▲コンピュータ将棋スレッド132

▲コンピュータ将棋ス ..

159:名無し名人
18/02/04 01:48:05.06 23gFbzJ50.net
で、衝突を避けるために1ビンの中に3エントリ設けているわけだが
ビンの中が満杯のとき、たまたまどれかのエントリの記憶する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で衝突を起こす
、、、

次ページ

続きを表示

1を表示