ハッシュテーブル — 辞書の仕組み

このトピックを終えると

ハッシュテーブルがどのように動作するかを説明でき、Pythonの辞書がO(1)検索を達成する仕組みを理解できます。

問題：100万個の中から1つを探す

リスト内で特定の値を検索する場合、最初から1つずつ比較する必要があります。

users = ["김훈", "이수", "박진", ...]  # 100万人
"김훈" in users  # 最悪の場合、100万回比較 — O(n)

データが10倍になると、検索時間も10倍になります。何か別の方法はないでしょうか？

ハッシュテーブルは、データがどれだけ増えても、検索時間がほぼ一定であるデータ構造です。

ハッシュ関数 — キーをアドレスに変換

ハッシュテーブルの基本的な考え方は簡単です。キーを数値（アドレス）に変換し、そのアドレスに直接アクセスします。

"김훈" → ハッシュ関数 → 427 → table[427]に保存
"이수" → ハッシュ関数 → 12 → table[12]に保存
"박진" → ハッシュ関数 → 891 → table[891]に保存

図書館の例えが適切です。図書館で本を探すとき、棚を最初から探すわけではありません。分類番号（蔵書記号）を見て、対応する棚に直接行きます。ハッシュ関数は、まさにこの「分類番号付与装置」です。

# Python組み込みのハッシュ関数
hash("김훈")     # -4340382828924905128 (実行ごとに異なる)
hash("이수")     # 7421390584116839301
hash(42)         # 42 (整数は自分自身がハッシュ値)

# テーブルのサイズで割り、インデックスを決定
index = hash("김훈") % 1000  # 0〜999の範囲のインデックス

衝突 — 同じアドレスに2つが来た場合

ハッシュ関数が、異なるキーに対して同じインデックスを生成する可能性があります。これを衝突と呼びます。

"김훈" → hash → 427
"최영" → hash → 427 ← 衝突！

解決策として最も一般的なのはチェイニングです。同じインデックスに連結リストを作成し、複数の項目を格納します。

table[427] → ("김훈", "010-1234") → ("최영", "010-5678")
table[12] → ("이수", "010-9012")

衝突が少ない場合、チェインの長さは1となり、O(1)になります。衝突が多い場合、チェインが長くなり、処理が遅くなります。したがって、優れたハッシュ関数は、データを均等に分散させることが重要です。

Python辞書 = ハッシュテーブル

Pythonのdictはハッシュテーブルで実装されています。そのため、このようなパフォーマンスが得られます。

# 辞書 — O(1)検索
users = {"김훈": "010-1234", "이수": "010-5678"}
users["김훈"]     # ハッシュ計算 → 直接アクセス — O(1)
"박진" in users   # O(1)

# リスト — O(n)検索
user_list = [("김훈", "010-1234"), ("이수", "010-5678")]
# "김훈"を探すには、1つずつ比較 — O(n)

100万件でも1000万件でも、辞書の検索にかかる時間はほぼ同じです。

ハッシュテーブルの弱点

万能ではありません。

• メモリ使用量: 空のスロットを事前に確保する必要があるため、リストよりも多くのメモリを使用します。
• 順序: 元のハッシュテーブルは、挿入順序を保証しません（Pythonのdictは3.7以降で保証）。
• キーの制約: キーは**不変（immutable）**である必要があります。文字列、数値、タプルは可能ですが、リストはキーにできません。

# リストはキーとして使用できません
d = {[1, 2]: "値"}  # TypeError: unhashable type: 'list'

# タプルは可能です
d = {(1, 2): "値"}  # OK — タプルは不変であるため、ハッシュ可能です

重要なまとめ

ハッシュテーブルは、「キー → ハッシュ関数 → インデックス → 直接アクセス」という単純な原理で、O(1)検索を実現します。Pythonでdictを使用するたびに、内部ではハッシュ関数が実行されています。「このデータから何かを頻繁に検索する必要がある」場合は、リストの代わりに辞書を使用するのがほとんどの場合、正解です。