この記事で伝えること
- ハッシュテーブルがどういう仕組みで「平均O(1)」の検索・追加を実現しているのか
- ハッシュ関数・バケット・衝突（コリジョン）といった基本用語の意味
- Pythonの
dictが内部的に何をしているかのイメージ - 衝突が起きたときの解決方法（チェイン法・オープンアドレス法）
「dictってなんで速いの？」と聞かれて、何となく「ハッシュだから」と答えてしまったことがある人に向けて、内部の動きを順番に整理していきます。
ハッシュテーブルとは何か
ハッシュテーブルは、キーと値の組み合わせ（key-value）を保存し、キーから値を高速に取り出すためのデータ構造です。Pythonのdict、JavaScriptのMapやオブジェクト、JavaのHashMapなど、ほとんどの言語の「連想配列」の正体はこれです。
配列（リスト）でキーと値を探す場合、先頭から順番に1件ずつ比較していくしかないため、データ件数が増えるほど検索に時間がかかります（最悪の場合O(n)）。ハッシュテーブルはこの問題を、「キーを計算して、保存場所を直接決めてしまう」という発想で解決します。
ハッシュ関数とバケット
ハッシュテーブルの中身は、実体としては固定サイズの配列です。この配列の各要素のことを「バケット」と呼びます。
キーを保存するとき、まずハッシュ関数にキーを渡し、その結果（ハッシュ値）を配列のサイズで割った余りを使って、どのバケットに入れるかを決めます。
def simple_hash(key: str, table_size: int) -> int:
"""文字列キーを数値に変換し、バケット番号を返す"""
total = sum(ord(c) for c in key)
return total % table_size
例えばtable_size = 8のとき、"apple"というキーは常に同じバケット番号に変換されます。次に値を取り出すときも同じ計算をすれば、配列の先頭から探さなくても一発で目的のバケットにアクセスできます。これが検索が速い理由の核心です。
良いハッシュ関数には次の性質が求められます。
- 決定的: 同じキーなら必ず同じハッシュ値になる
- 高速: 計算コストが低い
- 分散性: 異なるキーがなるべく異なるバケットに散らばる（偏りが少ない）
衝突（コリジョン）とその解決方法
バケットの数は有限なので、異なるキーが同じバケット番号に計算されることがあります。これを**衝突（コリジョン）**と呼びます。衝突は「ハッシュテーブルの設計が悪い」という話ではなく、有限のバケットに無限のキー候補を割り当てる以上、必然的に発生するものです。
衝突の代表的な解決方法は2つあります。
1. チェイン法（オープンハッシュ法）
同じバケットに複数のキーが割り当たった場合、そのバケットの中に連結リスト（やリスト）を持たせて、複数件を並べて保存する方法です。
検索時はバケットまでは一発で辿り着き、その中の数件だけを線形に比較します。バケット内の件数が少なければ、ほぼO(1)に近い速度を維持できます。CPythonのdictの衝突解決はチェイン法とは少し異なる独自方式ですが、考え方の基本はここにあります。
2. オープンアドレス法
衝突したら、別の空いているバケットを探して保存する方法です。「次のバケットを見る」「一定の間隔でスキップして探す」など、空きを探す手順（プロービング）に何種類かのバリエーションがあります。チェイン法のように追加のリスト構造を持たないため、メモリ効率に優れる場合があります。
Pythonのdictでの動作イメージ
実際にPythonで試してみます。
data = {}
data["apple"] = 100
data["banana"] = 200
data["plum"] = 300
print(data["apple"]) # 100
data["apple"] = 100を実行すると、内部的には次のような処理が行われています。
-
"apple"に対してhash("apple")を計算する - ハッシュ値からテーブル内の格納位置を決める
- その位置（または衝突解決後の位置）に
("apple", 100)を格納する
print(hash("apple")) # 実行ごとに異なる値（ハッシュランダム化のため）
なお、Pythonの文字列ハッシュは起動ごとにランダム化されています。これはハッシュ値を推測されることによるDoS攻撃（ハッシュ衝突を悪用した攻撃）を防ぐためのセキュリティ対策で、PYTHONHASHSEED環境変数で制御できます。
また、ハッシュテーブルに保存するキーは**不変（イミュータブル）**であることが前提です。Pythonでdictのキーにリストを使おうとするとTypeError: unhashable type: 'list'が出るのはこのためです。キーの内容が変わるとハッシュ値も変わってしまい、一度格納した場所と探す場所がズレてしまうからです。
筆者の考え・所感
個人的に、ハッシュテーブルは「計算量のトレードオフ」を体感しやすい良い教材だと思っています。配列の線形探索がO(n)なのに対し、ハッシュテーブルは平均O(1)を実現していますが、これは「メモリを余分に使う（テーブルサイズに余裕を持たせる）」「ハッシュ関数の計算コストを払う」という代償の上に成り立っています。何もないところから速度が生まれるわけではなく、別のリソースを使って速度を買っているという視点を持つと、他のデータ構造を学ぶときの理解も早くなる感覚があります。
また、実務でキャッシュ機構やセッション管理の仕組みを読んでいると、結局「キーからハッシュ値を出して、衝突したらどうするか」という同じ構造に何度も出会います。一度この基本原理を腹落ちさせておくと、Redisのようなキー・バリュー型ミドルウェアの設計思想や、データベースのハッシュインデックスの挙動を読み解くときにも応用が効くと感じています。
逆に注意したい点として、「平均O(1)」はあくまで平均であり、ハッシュ関数の質が悪い・衝突が極端に多発するケースでは最悪O(n)まで劣化する可能性があります。「ハッシュテーブルだから速い」と無条件に信じず、キーの分布やハッシュ関数の性質まで意識できると、より一段深い理解になると思います。
まとめ
- ハッシュテーブルは、キーをハッシュ関数で変換し、計算した位置に直接アクセスすることで平均O(1)の検索を実現するデータ構造
- 衝突（コリジョン）は必然的に発生するものであり、チェイン法やオープンアドレス法といった解決方法がある
- Pythonの
dictもこの仕組みの上に成り立っており、キーが不変である必要があるのもハッシュ値の整合性を保つため