データベーススペシャリスト 2020年 午前2 問13

ハッシュ方式の格納【午前2解説】

正解の理由

解法ステップ

1. 設問のキーワードを探す：「関数の結果」「格納場所」などハッシュを示す語を確認する。
2. 各選択肢の技術分類を当てはめる：順序保持＝B+木、ポインタで鎖状＝チェイン（衝突処理）、同一ブロックに隣接格納＝クラスタリング的配置。
3. 「キーを関数で写像して位置を決める」記述がある選択肢を選ぶ（= ハッシュ方式）。

選択肢別の誤答解説

• ア: 「同一ブロック又はできる限り隣接したブロックに格納」
  → これはレコードの近接配置やクラスタ化（クラスタリング）によるファイル配置の説明に当たります。論理的に関連するレコードを近接配置することでアクセス性能を高めますが、キーを関数で写像するハッシュ方式の定義ではありません。
• イ: 「特定のデータ項目の値に対応した子レコード同士を、ポインタで鎖状に連結して格納」
  → ここで述べられている「ポインタで鎖状に連結する」方式はチェイン法（チェイニング）を示しています。チェイン法はハッシュ方式における代表的な衝突解決法の一つで、同じハッシュ値（同じバケット）に入る複数のレコードをリンクリスト等でつなげて格納します。しかし選択肢イは「チェイン法による格納形態」を表すに過ぎず、ハッシュ方式そのもの（キーをハッシュ関数で写像して格納位置を決めること）の定義としては不十分です。したがって本問では選択肢エがより適切です。
• ウ: 「特定のデータ項目の値の順序を保持して、中間ノードとリーフノードの平衡木構造のブロックを作り、リーフブロックにレコード格納位置へのポインタを格納」
  → これはB+木（または平衡木型のインデックス）の説明です。順序性を維持し範囲検索に有利な構造であり、ハッシュ方式の「順序を破る」特性とは対照的です。
• エ: 「特定のデータ項目の値を引数とした関数の結果に従って決められたレコード格納場所に格納する」
  → これがハッシュ方式の本質的な定義です。ハッシュ関数によってキーをバケット番号や記憶位置に写像し、その結果に基づき格納・検索を行います。したがって選択肢エが正解となります。

よくある誤解

• ハッシュ方式はレコードの順序を保持すると思い込みやすい：ハッシュはキーを分散させるため順序は保持しません。範囲検索や順序走査は不得意です。
• チェイン法はハッシュ方式と別物と断定する誤り：チェイン法はハッシュ方式における衝突処理手法の一つであり、ハッシュ法の実装形式として正当に含まれます。問題文の定義（ハッシュ方式の本質）は「写像する関数による位置決定」である点を区別しましょう。
• ハッシュ関数は衝突を完全に避けられると思い込む誤り：有限のバケットに対し無限（または多数）のキーがあるため衝突は原理的に発生し得ます。衝突処理（チェイン法、オープンアドレッシング等）が必要です。

補足コラム

• ハッシュ関数とバケット：典型的には格納位置は「ハッシュ値 mod バケット数」で決定します。たとえばバケット数を $m$、要素数を $n$ とするとロードファクタ（負荷率）を $\alpha =n/m$ と表し、パフォーマンス評価に使います。
• 主な衝突解決法：
  • チェイン法（チェイニング）：各バケットがリストや別構造を持ち、衝突要素を連結して格納。実装が容易で削除が簡単。
  • オープンアドレッシング：衝突時に別の空きスロットを探して格納（線形探索、二次探索、ダブルハッシュなど）。
• 簡単なPython例（バケットにキーを割当て、チェイン法で保存）:

def simple_hash(key, m):
    return hash(key) % m

m = 8  # バケット数
buckets = [[] for _ in range(m)]  # チェイン法：各バケットはリスト
keys = ["apple", "banana", "grape", "lemon"]
for k in keys:
    idx = simple_hash(k, m)
    buckets[idx].append(k)  # 衝突があれば同じバケットに連結
print(buckets)

FAQ