ハッシュテーブルの仕組み - 衝突解決・負荷率・各言語の実装から理解する
図解でアルゴリズムとデータ構造を直感理解。
定番。データ構造を実装しながら学ぶ。
ハッシュ表の理論を厳密に押さえる古典。
当サイトは Amazon.co.jp を宣伝しリンクすることで紹介料を得る手段を提供する、Amazonアソシエイト・プログラムの参加者です。価格・在庫はリンク先の最新情報をご確認ください。
辞書型（dict）、連想配列、マップ、ハッシュマップ——呼び名は言語ごとに違っても、その正体はほとんどがハッシュテーブルです。キーを渡すと、要素数がどれだけ増えても平均して一定時間で値を取り出せる。この「魔法」の裏側には、ハッシュ関数・バケット・衝突解決という3つの仕掛けがあります。この記事では、その仕組みを土台から組み立て直し、なぜ平均で速いのか、どこで遅くなるのか、そして各言語が実際にどう実装しているのかまでを丁寧に整理します。
ハッシュテーブルとは
ハッシュテーブル（hash table）は、キーと値の対応を格納し、キーから値を高速に引くためのデータ構造です。配列は「0, 1, 2, ...という整数の添字」でしかアクセスできませんが、ハッシュテーブルは文字列でも任意のオブジェクトでもキーにできます。
基本のアイデアはシンプルです。キーをハッシュ関数に通して整数（ハッシュ値）に変換し、それを配列のインデックスに対応づけて、その位置に値を置く。取り出すときも同じ計算をすれば、一発で置いた場所にたどり着けます。配列の添字アクセスが速いという性質を、任意のキーに拡張したものだと考えると腹落ちしやすいはずです。
仕組み: ハッシュ関数とバケット
内部で値を保管する配列の1マスをバケット（bucket）と呼びます。キーからバケットのインデックスを決める流れは次の2段階です。
- ハッシュ関数でキーを整数のハッシュ値に変換する
- そのハッシュ値をバケット数で割った余り（剰余）を取り、インデックスにする
良いハッシュ関数の条件は、入力が少し変わると出力が大きく変わり、値が配列全体に均等にばらけることです。偏ると特定のバケットに集中し、後述する衝突が増えて性能が落ちます。
擬似コードで挿入と検索の骨格を書くと次のようになります。ここではもっとも素直な衝突解決であるチェイン法を使っています。
class HashTable:
def __init__(self, capacity=8):
# 各バケットは (キー, 値) のリスト（チェイン）を持つ
self.buckets = [[] for _ in range(capacity)]
def _index(self, key):
# 1. ハッシュ値を計算し 2. バケット数で割った余りをインデックスに
return hash(key) % len(self.buckets)
def put(self, key, value):
chain = self.buckets[self._index(key)]
for i, (k, _) in enumerate(chain):
if k == key: # 既存キーなら上書き
chain[i] = (key, value)
return
chain.append((key, value)) # 新規キーはチェイン末尾に追加
def get(self, key):
chain = self.buckets[self._index(key)]
for k, v in chain: # 同じバケット内を線形に探す
if k == key:
return v
raise KeyError(key)同じインデックスに複数のキーが来ても、バケットの中でリストにつないでおけば区別できます。これが衝突への対処の一例です。
衝突（コリジョン）とその解決法
バケット数は有限なので、異なるキーが同じインデックスに割り当てられることは避けられません。これを衝突（コリジョン）と呼びます。むしろ衝突は「起きるのが前提」で、どう捌くかが実装の肝になります。代表的な解決法は2系統あります。
チェイン法（separate chaining）は、各バケットに連結リスト（や動的配列）を持たせ、同じインデックスに来た要素をそこにつなぐ方式です。実装が素直で、負荷が高くても破綻しにくい一方、リストのノードをたどるポインタ参照がキャッシュに乗りにくいという弱点があります。
オープンアドレス法（open addressing）は、衝突したら別の空きバケットを探して直接そこに置く方式です。探し方にはいくつかの流儀があります。
- 線形探索法（linear probing）: 埋まっていたら隣、その次と1つずつずらして空きを探す。実装が単純でキャッシュ効率が良い反面、埋まった領域が連なる「クラスタリング」が起きやすい
- 二重ハッシュ法（double hashing）: 2つ目のハッシュ関数で「ずらす歩幅」を決め、クラスタリングを緩和する
- ロビンフッドハッシュ法（Robin Hood hashing）: 挿入時に「本来の位置からより遠くまで追いやられている要素」を優先して置き直し、探索距離のばらつきを平らにする工夫
オープンアドレス法は要素を配列に直接詰めるためメモリ局所性に優れますが、削除の扱いが厄介（単純に空にすると探索が途切れる）で、負荷が高くなると急激に遅くなります。
| 観点 | チェイン法 | オープンアドレス法 |
|---|---|---|
| データの持ち方 | バケットごとにリスト | 配列に直接詰める |
| キャッシュ効率 | 劣りやすい | 良い |
| 高負荷時の耐性 | 比較的なだらかに劣化 | 急激に劣化しやすい |
| 削除の実装 | 単純 | 工夫が必要（墓標など） |
負荷率とリハッシュ
ハッシュテーブルの混み具合を表す指標が負荷率（load factor）です。定義は次の通りで、要素数をバケット数で割った値です。
負荷率 = 要素数 / バケット数負荷率が高いほど衝突が増え、性能が落ちます。そこで多くの実装は、負荷率がしきい値を超えたらより大きな配列を新たに確保し、全要素を計算し直して置き直す操作を行います。これをリハッシュ（rehash）あるいはリサイズと呼びます。
リハッシュはその回だけ全要素をなめ直すためO(n)かかります。しかし容量を倍々に増やしていくため発生頻度はまばらで、多数の挿入でならせば1回あたりは償却O(1)に収まります。この「ならすと定数」という考え方は計算量とBig-O記法 入門の償却計算量のところで詳しく扱っています。
計算量: なぜ平均O(1)なのか
ハッシュ関数が値を均等にばらまき、負荷率が一定以下に保たれていれば、1つのバケットに集まる要素数は平均して小さな定数に抑えられます。したがってキーの読み書きは、ハッシュ計算1回とごく短い探索で済み、平均O(1)で完了します。要素が100個でも100万個でも、平均的な手間がほぼ変わらないのがハッシュテーブルの真価です。
ただしこれは平均の話です。悪意ある入力や質の悪いハッシュ関数のせいですべてのキーが同じバケットに集中すると、実質1本のリスト（あるいは長い探索列）になり、検索は最悪O(n)まで劣化します。「平均は速いが最悪は遅い」という非対称性は、レイテンシが重要な場面ほど意識する価値があります。
| 操作 | 平均計算量 | 最悪計算量 |
|---|---|---|
| 検索 | O(1) | O(n) |
| 挿入 | O(1)（償却） | O(n) |
| 削除 | O(1) | O(n) |
各言語の実装の違い
同じ「ハッシュテーブル」でも、言語ごとに衝突解決や付加的な性質が異なります。主要言語の標準実装を公式情報で確認した範囲でまとめると、次のようになります（定数やアルゴリズムは実装・バージョンにより変わりうるため、細部は各公式ドキュメントで確認してください）。
| 言語 / 型 | 衝突解決の方式 | 特筆点 |
|---|---|---|
| Python dict | オープンアドレス法 | 3.7で挿入順の保持が言語仕様として保証 |
| Java HashMap | チェイン法 | 条件を満たすと連結リストを赤黒木へ変換 |
| Go map | ハッシュテーブル | 反復順序はランダム化され順序非保証 |
| C++ std::unordered_map | チェイン法（バケットごとのリスト相当） | max_load_factor 超過で自動リハッシュ |
| Rust std HashMap | SwissTable由来（hashbrown） | 既定でSipHashを採用しDoS耐性を確保 |
いくつか補足します。
Pythonのdictはオープンアドレス法で実装されています。CPython 3.6で挿入順を保つ「compact dict」実装が入り、続く3.7からは挿入順の保持が言語仕様として保証されました。3.6時点では実装依存の振る舞いにすぎなかった点が、3.7で公式な約束に格上げされたという順序が正確です。
JavaのHashMapはチェイン法ですが、JDK 8以降、1つのバケットのエントリ数がしきい値を超え、かつテーブル容量が十分に大きいと、そのバケットの連結リストを赤黒木に変えます。これにより衝突が集中した最悪ケースでも、そのバケット内の探索がO(log n)に改善されます。しきい値はTREEIFY_THRESHOLDが8、木化に必要な最小容量MIN_TREEIFY_CAPACITYが64で、デフォルト初期容量は16、負荷率は0.75です。
Goのmapは反復順序を意図的にランダム化しており、rangeで回す順番は仕様上不定です。順序に依存したコードを書けないようにする設計上の判断で、後述するハッシュテーブルのレイアウト露出を避ける効果もあります。
C++のstd::unordered_mapは、バケットごとに連結リスト相当を持つチェイン法です。load_factorがmax_load_factor（既定は1.0）を超えると自動でリハッシュされます。
Rustの標準ライブラリのHashMapはGoogleのSwissTableを移植した実装（hashbrownベース）で、既定のハッシャにSipHash系を採用しています。これは次に述べるDoS対策のためです。
ハッシュ衝突を悪用したDoSとSipHash
最悪O(n)という弱点は、攻撃者に狙われます。Hash-flooding（ハッシュフラッディング）は、意図的に同じバケットへ衝突するキーを大量に送り込み、ハッシュテーブルをリスト同然に劣化させてCPUを枯渇させる攻撃です。2011年の28C3で、PHP・Java・Python・Rubyなど多数の処理系が影響を受けると公表され、大きな話題になりました。当時のPHPでは、多数のパラメータを含む1リクエストでサーバーのコアを長時間占有できるケースが報告されています。
緩和策の定番がSipHashに代表されるキー付きハッシュ関数です。プロセス起動時に秘密の鍵（シード）を生成し、それを混ぜてハッシュ値を計算します。攻撃者は鍵を知らないため、どのキーが衝突するかを事前に予測できません。PythonがPYTHONHASHSEEDによるハッシュランダム化を導入し、RustがSipHashを既定に採用しているのは、いずれもこの流れの延長です。
NOTE
ハッシュランダム化は「同じ文字列でも実行ごとにハッシュ値が変わりうる」ことを意味します。ハッシュ値そのものを永続化したり、プロセスをまたいで比較したりする設計は避けましょう。パスワードの保存にハッシュを使う話はまた別問題で、専用の関数が必要です（Argon2によるパスワードハッシュを参照）。
いつ使うべきか（配列・木との使い分け）
ハッシュテーブルは万能ではありません。データ構造は「何を速くしたいか」で選びます。
- 配列（線形探索）: 要素数がごく少ない、または順番になめるだけなら、素直な配列がもっとも単純で速いこともあります。「含まれるか」を何度も問い合わせるなら、
O(n)の線形探索よりハッシュの平均O(1)が有利です - 二分探索木（平衡二分探索木）: キーを順序どおりに巡回したい、範囲検索（ある値以上・以下をまとめて取る）をしたい、最小・最大を素早く取りたい、といった要求があるなら木構造が向きます。木は
O(log n)ですが順序を保てるのが強みです - ハッシュテーブル: 個々のキーの存在確認・読み書きを最速にしたい、順序は不要、という典型的な用途に最適です
順序が要るか要らないかが、ハッシュと木を分ける最初の分岐点だと覚えておくと選びやすくなります。同じ「速く引く」でも、ディスク上の大量データではB木系が使われ、その考え方はデータベースインデックス入門で扱っています。アルゴリズム全体の見取り図はソートアルゴリズム入門も合わせてどうぞ。
まとめ
- ハッシュテーブルは、キーをハッシュ関数でバケットのインデックスに変換して値を出し入れするデータ構造
- 異なるキーが同じ位置に来る衝突は前提で、チェイン法とオープンアドレス法で解決する
- 負荷率がしきい値を超えたらリハッシュで拡張する。1回は
O(n)だが償却O(1) - 読み書きは平均
O(1)、衝突が集中する最悪ケースはO(n) - 実装は言語ごとに異なる（Pythonはオープンアドレス法で3.7から挿入順保証、Javaはチェイン法で条件次第で赤黒木化、Goは順序非保証、Rustは既定SipHash）
- Hash-flooding攻撃への対策としてSipHashなどキー付きハッシュが使われる
- 順序が不要なら配列・木よりハッシュ、順序や範囲検索が要るなら木、という使い分けが基本
仕組みを一度自分の手で組んでみると、普段何気なく使っているdictやmapの速さと限界が腹落ちします。まずは上の擬似コードを写経し、衝突が起きたときの挙動を確かめてみてください。
