基本情報技術者 2013年 秋期 午前（科目A） 問19

直接編成ファイルにおけるハッシュ値の分布はどれか【午前2 解説】

要点まとめ

• 結論: 直接編成ファイルで理想的なのはハッシュ値がアドレス空間に偏りなく分散する一様分布で、衝突や偏りが最小化されアクセス効率が向上します。
• 根拠: 一様分布なら各格納アドレスに割り当てられるレコードの期待値が等しくなり、探索や挿入の平均コストが均一化され性能が安定します。
• 差がつくポイント: ハッシュ関数選定では一様性（分散の小ささ）を重視し、サンプルでカイ二乗検定や負荷分散の確認を行うことが得点差につながります。

正解の理由

よくある誤解

• 「ポアソン分布が理想」は誤り：個々のアドレスに入るレコード数の近似分布としてポアソンが現れる場合はあるが、理想のハッシュ値の分布そのものは一様である点を混同しやすいです。
• 「幾何分布・二項分布でもよい」は誤り：幾何分布は成功までの試行回数、二項分布は成功回数の分布であり、格納アドレスへの値の“偏りがないこと”を表す一様性とは本質的に異なります。

解法ステップ

1. 「直接編成ファイル」の意味を確認する（キー→アドレスの直接変換で格納）。
2. 理想状態の要件を定義する（偏りなくアドレス空間に分散すること＝アクセス効率の均一化）。
3. 各選択肢が「アドレスへの分布のどの性質」を示すかを比較する（一様＝均等、ポアソン/二項/幾何＝別の確率論的性質）。
4. 要件に一致するのは「一様分布」であるため、これを正解とする。

選択肢別の誤答解説

• ア: 一様分布 — 正解。ハッシュ値がアドレス空間に偏りなく分散すれば衝突が減り性能が安定します。
• イ: 幾何分布 — 誤り。試行回数に関する分布であり、アドレス空間への均等分散を意味しません。
• ウ: 二項分布 — 誤り。固定試行回数における成功回数の分布で、ハッシュ値が均等に広がる性質を直接表しません。
• エ: ポアソン分布 — 誤り（状況依存で似た振る舞いをすることはある）。多数のキーを多くのバケットにランダムに割り当てると各バケットの個数分布は近似的にポアソンとなる場合がありますが、ハッシュ値自体の理想的な分布はやはり一様です。

補足コラム

• 理論的には、n 個のキーを m 個のバケット（アドレス）に独立に一様に割り当てると、ある特定バケットに入るキー数は二項分布 Bin(n, 1/m) になります。n と m が大きく $p=1/m$ が小さい場合、これはポアソン分布 $Poisson(\lambda =n/m)$ に近似できます。すなわち「各バケットの個数分布がポアソンに近い」という話と「ハッシュ値が一様分布であるべき」という設計要件は混同しないようにしてください。
• 実装上のポイント：良いハッシュ関数は入力の統計的偏りを打ち消して出力を一様化します。チェイニングやオープンアドレッシングといった衝突処理も併せて設計することが重要です。
• 検証方法：実装後はサンプルデータでヒストグラムを作成し、カイ二乗適合度検定などで一様性をチェックします。

FAQ