平成22年度 春期 午前 問6

✓ これが正解イ一様分布

解説

散らばりに偏りが無いほど値の重なりが減ります。

ハッシュ表探索では、鍵から計算した値を表の位置として使います。同じ位置に2つ以上の鍵が来てしまうことを衝突と呼び、これが増えるほど探索は遅くなります。ですから衝突が起きにくいのは、どの位置にも同じ確からしさで鍵が散らばるときです。逆に、ある範囲の値が出やすい山のある散らばり方をすると、その山の付近に鍵が集まり、重なりが増えてしまいます。表のどの位置も同じ確率で選ばれる散らばり方が一様分布ですから、これで近似できるときに重なりがいちばん起きにくくなります。判定の軸は、値の出やすさに山があるかどうかの一点です。

ほかの選択肢はなぜ違うのか

• ア2項分布：決まった回数の試行で何回当たるかを表す散らばり方で、中ほどの回数がいちばん出やすくなります。出やすさに山ができる以上、表の位置は均等には埋まりません。
• ウ正規分布：平均のまわりがいちばん出やすく、そこから離れるほど出にくくなる釣り鐘の形をした散らばり方です。中央付近に鍵が集まるので、同じ位置が選ばれる機会が増えます。
• エポアソン分布：まれにしか起きない出来事が一定の間に何回起きるかを表す散らばり方で、回数の少ない側が出やすくなります。やはり偏りがあるため、鍵を均等に配ることができません。