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

ハッシュ法による表探索【午前解説】

正解の理由

解法ステップ

1. 問題文のキーワードを探す：「関数値」「格納場所」「衝突」「2分木」などを確認する。
2. 各選択肢をキーワードで照合する：「関数値によって格納場所を決める」はハッシュ法の定義に一致する。
3. 残りの選択肢を排除する：2分木は木構造、衝突が発生しないは誤、探索時間が表全体比例は配列線形探索の説明に近い。
4. 正解を確定する：ハッシュ法の定義に一致する選択肢を選ぶ。

選択肢別の誤答解説

• ア: 2分木を用いる方法の一種である。
  → 誤り。2分木（二分探索木）はノードとポインタで構成する木構造の探索法であり、ハッシュ法とは根本的に異なります。
• イ: 格納場所の衝突が発生しない方法である。
  → 誤り。ハッシュ法では衝突は一般に発生し得るため、チェイニングやオープンアドレッシング等の衝突解決が必要です。
• ウ: キーの関数値によって格納場所を決める。
  → 正解。キーをハッシュ関数で写像してインデックスを決定するという記述がハッシュ法の本質を示しています。
• エ: 探索に要する時間は表全体の大きさにほぼ比例する。
  → 誤り。線形探索は表全体の大きさに比例しますが、ハッシュ法の平均探索時間は $O(1)$（定数時間）であり、表全体に比例するとは言えません。

よくある誤解

• 「ハッシュ法では衝突が発生しない」：衝突（異なるキーが同じインデックスに写像される）は一般に発生し得るため、衝突解決手法が必須です。
• 「探索は常に一定時間（完全に O(1)）」：平均は $O(1)$ でも、衝突が偏ると最悪で $O(n)$ になります。
• 「ハッシュ関数は何でもよい」：不適切なハッシュ関数は衝突増加や偏りを生み、実行性能を大きく低下させます。

補足コラム

• 衝突解決法：チェイニング（バケットにリストを使う）やオープンアドレッシング（線形探索・二次探索・再ハッシュ）があります。
• 負荷率（load factor）α = 要素数 / バケット数 は性能指標で、α が大きいと衝突が増え性能低下します。動的リサイズ（リハッシュ）で管理します。
• ハッシュ関数は均一分布を目指し、キーの偏りを避けること。暗号学的ハッシュと実用的ハッシュ（高速で分布が良いもの）を使い分けます。
  簡単なPython例（チェイニング風の概念示例）：

class SimpleHashTable:
    def __init__(self, size=8):
        self.size = size
        self.table = [[] for _ in range(size)]
    def _hash(self, key):
        return hash(key) % self.size
    def insert(self, key, value):
        idx = self._hash(key)
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        self.table[idx].append((key, value))
    def find(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None

FAQ