基本情報技術者 2010年 春期 午前（科目A） 問06

ハッシュ値の分布特性【午前解説】

正解の理由

解法ステップ

1. 各バケットに入る確率を$p_i$と定義する（${\sum }_i{p}_i=1$）。
2. 異なる2要素が同じバケットに入る確率を${\sum }_i{p}_i^2$と導出する。
3. 制約下で${\sum }_i{p}_i^2$を最小化する問題を考える（凸性またはラグランジュ乗数法）。
4. 解として$p_i=1/m$（一様）が得られ、衝突確率は最小であると結論付ける。

選択肢別の誤答解説

• ア: 2項分布 — 2項分布は成功確率に依存して質量が特定の値に集中するため、バケット割当が均一になるとは限らず衝突を最小にしません。
• イ: 一様分布 — 各バケット確率が等しくなり${\sum }_i{p}_i^2$が最小化されるため正解です。
• ウ: 正規分布 — 連続的に中心付近へ集中する性質があり、有限のバケットに割り当てると中心バケットに偏り衝突が増えます。
• エ: ポアソン分布 — イベント数の散発的発生を表す分布で、特に低平均や高平均で偏りが生じ得るため均一とは言えません。

よくある誤解

• 「正規分布やポアソン分布なら散らばるから衝突が減る」は誤り。これらは中心付近に質量が集中する場合が多く、バケットへの割当は偏りが出やすいです。
• 「ランダムに振れば必ず一様になる」は誤り。ランダム性の定義やハッシュ関数の性質次第で偏りが残ることがあります。
• 「入力データの分布は無視できる」と考えるのは危険。入力分布が偏っていれば、ハッシュ関数で均一化できなければ衝突が増えます。

補足コラム

• 実装面では「一様分布に近づける」ことが重要であり、良いハッシュ関数（例えば汎用の乱数似た混ぜ合わせを行うもの）やリハッシュ／チェイニング戦略が有効です。
• 誕生日のパラドックス的観点では、バケット数$m$に対して要素数$n$が約$\sqrt{m}$程度になると衝突が急増します。均一でもこのスケールは変わりません。
• 一様分布での期待衝突ペア数は約$n(n-1)/(2m)$。従って負荷係数$\alpha =n/m$を管理することが衝突回避につながります。

FAQ