0154名無し名人 (ワッチョイ 9fbd-CNA0)
2018/02/04(日) 01:35:12.92ID:23gFbzJ50ハッシュキーの有効ビット数が32 bitというのは見積もりが甘すぐる…
ビンの数が64 K個で、ハッシュは理想的
(現実に現れる局面が、64 bit(96 bitでも良いが)のハッシュキー空間に一様に分布 && 下位16 bitと上位に相関が無い
とすると、1個のビンは平均64 K回に1回参照される。
置換表サイズを大きくすることでビンの参照周期が伸びれば確かに参照回数(≒時間)当たりの衝突頻度は下がるが、
1個のビン特定後の事後確率としての衝突確率はなんら下がらない
そいつはハッシュキーの上位16 bitでしか比較しないのだから、やっぱ1/64 K程度になるであろう