平成22年度秋期問6テクノロジ系

基本情報平成22年度秋期問6：テクノロジ系に関する問題

ハッシュ表探索において, 同一のハッシュ値となる確率が最も低くなるのは, ハッシュ値がどの分布で近似されるときか。

a2項分布
b一様分布正答
c正規分布
dボアソン分布

正答：B一様分布

AI解説（初心者・標準・上級）

理解度に合わせて3レベルの解説を無料で読めます。

初心者向けまずはここから。やさしく要点を解説

答えは b「一様分布」 です。

ハッシュ表は「鍵（key）からハッシュ値（=保管箱の番号）を計算して、データを箱に入れる」仕組み。

もし箱が10個あって、ハッシュ値が偏らずにバラけている（一様）なら、各箱に均等にデータが入り、同じ箱に複数入る（=衝突）確率が一番低くなります。

逆に正規分布など偏ったハッシュ関数だと、特定の箱に集中して衝突だらけに。

👉 覚え方：「ハッシュ値はバラけていてほしい=一様分布」。

ほかの選択肢：a 2項分布／c 正規分布（山型に集中）／d ポアソン分布（裾が長い）。どれも偏りがあって衝突しやすい。

標準試験対策の基準レベル

なぜこれが正解か

正解は b。ハッシュ表（ハッシュテーブル）はキーをハッシュ関数で配列インデックスに変換しデータを格納する。ハッシュ値が一様分布（uniform distribution、全インデックスが等確率）に従えば、データが配列全体に均等に分散し衝突（コリジョン）確率が最小化される。

各選択肢の解説

a 2項分布：成功/失敗の試行回数分布。連続的データ分散用ではない。
b 一様分布：すべての値が等しい確率。ハッシュの理想（正解）。
c 正規分布：平均値付近に集中する釣鐘型分布。一部のインデックスに偏り衝突多発。
d ポアソン分布：稀な事象の発生回数分布。偏りあり。

覚え方・ひっかけ注意

ハッシュ関数の理想3条件：(1) 計算が高速、(2) 値が一様分布、(3) 入力の小変化で出力が大きく変わる（雪崩効果）。一様分布以外は何らかの偏りがあり、衝突が増えて性能劣化を招く。「ハッシュは均等にばらまけ」のスローガンで覚える。

上級誤答論破・背景理論まで深掘り

理論的背景

ハッシュ表の平均探索時間はO(1)、最悪はO(n)（全要素が同一バケットに集中する病的ケース）。ハッシュ関数h(k)がSUHA（Simple Uniform Hashing Assumption、各キーが等確率で全バケットに分散）を満たせば、負荷率α=n/m（要素数n／バケット数m）に対し、衝突解決法：(1) チェイン法（連結リスト）で平均探索 1+α/2、(2) オープンアドレス法（線形/2次/ダブルハッシュ）で 1/(1-α) と評価される。バースデーパラドックスから、m個のバケットに√m個のキーで衝突確率が50%を超える性質も重要。ユニバーサルハッシュ（Carter-Wegman）はランダム選択でSUHAを保証する理論的手法。

実務での使われ方

暗号学的ハッシュ関数（SHA-256、SHA-3、BLAKE3）は雪崩効果＋衝突困難性＋第二原像困難性を満たし、デジタル署名・パスワード保存（bcrypt/scrypt/Argon2はストレッチング付き）・ブロックチェーン（Merkle Tree、Proof of Work）・コードハッシュ（Git、IPFS、Sigstore）で活用。非暗号学的高速ハッシュはxxHash（最速級）、MurmurHash、CityHash、MetroHash、SipHash（DoS耐性付き、Python/Rustデフォルト）。Locality-Sensitive Hashing（LSH）は類似データを同バケットに集める性質を活用した近似最近傍探索の基盤（MinHash、SimHash）。

試験での位置づけ

FE科目Aでハッシュ表の基本性質、衝突確率、分布の選択問題が頻出。応用情報・データベーススペシャリストではハッシュインデックス、ハッシュ結合（Hash Join）、ハッシュ分割、ダイナミックハッシング（拡張可能ハッシング、線形ハッシング）が問われる。情報処理安全確保支援士ではパスワードハッシング、レインボーテーブル攻撃、ソルト付きストレッチング、HMAC（Hash-based Message Authentication Code）、HKDF（鍵導出）が深く扱われる。

選択肢の発展補足

ハッシュ表の現代実装：Open Addressing系＝Linear Probing（CPU cache friendly、現代ハードに最適）、Cuckoo Hashing（最悪O(1)保証、2ハッシュ関数）、Robin Hood Hashing（探索距離均等化）、Hopscotch Hashing（局所性保持）／Chaining系＝Java HashMap（負荷率0.75、ツリー化閾値8）、Linux Kernelのdcache。Concurrent Hash Table＝Lock-Free（Java ConcurrentHashMap）、Per-Segment Lock。ハッシュ表攻撃：Algorithmic Complexity Attack（意図的衝突注入によるDoS、SipHash対策が標準化）。Bloom Filterは確率的データ構造で、ハッシュ表の代替/補完として大規模システムで活用（Cassandra、HBase、CDN、データベース）、メンバシップ判定にO(k)（kはハッシュ関数数）と低コスト。HyperLogLogは集合濃度（cardinality）の確率的推定でRedis等が実装。Counting Bloom Filter、Cuckoo Filter、XOR Filterなどの発展形もあり、近年データ集約系で頻出。FE午後ではハッシュ表の具体実装問題、衝突解決アルゴリズムの比較問題が定番。