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

インデックス方式のうち、キー値を基にして格納位置を算出するとき、異なったキー値でも同一の算出結果となる可能性があるものはどれか。【午前2 解説】

要点まとめ

• 結論：ハッシュインデックスはキーからハッシュ値で格納位置を算出するため、異なるキーが同一の算出結果（衝突）となる可能性がある。
• 根拠：ハッシュ関数は有限のバケット空間へ写像するため、異なる入力が同じハッシュ値に写る（ハッシュ衝突）が理論的に発生し得る。
• 差がつくポイント：B+木は順序を保ちポインタで管理、転置インデックスは語→出現リスト、ビットマップは値ごとのビット列で「衝突」の扱いが根本的に異なる点を押さえる。

正解の理由

よくある誤解

• 「B+木でも衝突が起きる」と考える誤解：B+木はキーの大小関係でノードを分岐していく構造で、同じ葉に重複キーが存在しても格納位置はポインタ（レコード参照）で管理され、ハッシュ的な衝突とは意味が異なります。
• 「転置インデックス＝ハッシュを使う」との混同：転置（インバーテッド）インデックスは単語やトークンをキーにして出現リストを保持するもので、語の同一性を扱うが、格納位置をハッシュで算出する方式とは区別されます。
• 「ビットマップは衝突を起こさないから万能」との誤認：ビットマップは列挙可能な値ごとにビット列を持つため衝突は起きにくいが、値の種類が多い場合や更新コスト・空間効率の問題があります。

解法ステップ

1. 問題文のキーワード「キー値を基にして格納位置を算出」を把握する。
2. 各インデックス方式の基本動作を思い出す（位置算出の手法がハッシュか順序構造か、値ごとに列挙するか）。
3. 「異なったキーでも同一の算出結果があり得る」＝ハッシュ関数による写像（衝突）が関係することを確認。
4. ハッシュインデックスを選択する。

選択肢別の誤答解説

• ア: B+木インデックス — 整列された木構造で範囲検索や順序保持に強い。キーからノードを辿ってポインタに到達するため、ハッシュのような「同一ハッシュ値による衝突」という概念とは異なる。
• イ: 転置インデックス — 文書検索で用いる語→出現リストを保持する索引。語ごとのポスティングリストを参照する方式で、キーをハッシュして格納位置を算出する方式とは性質が違う。
• ウ: ハッシュインデックス — キーにハッシュ関数を適用してバケットを決定するため、異なるキーが同一バケットに写る（ハッシュ衝突）が発生し得る。これが正解。
• エ: ビットマップインデックス — 各値（あるいは値のカテゴリ）ごとにビット列を持ち、該当レコードのビットを立てる方式。値ごとのビット集合を用いるため、ハッシュ衝突の概念は当てはまりにくい。

補足コラム

• 衝突解決法の例：チェイニング（同じバケットにリストを持つ）やオープンアドレッシング（再ハッシュや線形探索）があります。性能は負荷係数（load factor）やハッシュ関数の品質に依存します。
• 用途での使い分け：等価検索が多い場合はハッシュインデックスが高速、範囲検索や順序が必要な場合はB+木（B+ tree）が適していることが多いです。ビットマップインデックスは低多様性（少ない異なる値）かつ集計／論理演算が多い列に有効です。
• 実装上の注意：ハッシュインデックスはバケット数や再ハッシュ戦略、衝突時のメモリ／ディスク利用に注意が必要で、並列処理や分散環境ではハッシュ分散の均一性が重要になります。

FAQ