ALGORITHM VISUALIZER
ハッシュインデックス（Hash Index）
ハッシュ関数でキーからバケットを直接計算し、平均 O(1) で検索・挿入・削除を実現する静的ハッシュインデックス
設定
バケット数
バケット容量
挿入
自動再生
スピード1.2秒
統計
0
総キー数
4
バケット数
0
オーバーフロー
0.00
負荷率
0
最大チェーン長
凡例
通常バケット
ハイライト（操作対象）
オーバーフローバケット
操作ログ
操作なし
解説
📌ハッシュインデックスとは
ハッシュインデックスは、ハッシュ関数を使ってキーからデータの格納位置を直接計算するインデックス構造です。B-Treeがルートから枝を辿って目的のデータにたどり着く「木構造型」の索引であるのに対し、ハッシュインデックスは計算一発で格納場所を特定する「直接アドレッシング型」の索引です。内部的にはバケット（固定容量のスロット配列）を持ち、ハッシュ関数の出力値をバケット番号としてデータを振り分けます。
日常的な例で考えてみましょう。500ページの本から特定の単語を探すとき、B-Treeは「索引のページを開いて、該当する範囲を絞り込んでいく」方法です。一方ハッシュインデックスは、「単語を計算式に入れると即座にページ番号が出てくる」方法です。途中の比較や絞り込みが一切不要で、一発で目的地にたどり着けます。
技術的に見ると、ハッシュ関数は任意の入力を固定範囲の整数値に変換する決定的関数です。「決定的」とは、同じ入力に対して必ず同じ出力を返すこと。最も基本的なハッシュ関数は h(key) = key mod N（Nはバケット数）で、割り算の余りをそのままバケット番号として使います。
例：バケット数 N = 4 の場合
- h(42)=42 mod 4 = 2→バケット[2]
- h(17)=17 mod 4 = 1→バケット[1]
- h(8)= 8 mod 4 = 0→バケット[0]
- h(37)=37 mod 4 = 1→バケット[1]（キー17と衝突）
どんなに大きな数字でも余りは必ず 0〜N-1 の範囲に収まるので、必ずどこかのバケットに入ります。
この仕組みにより、ハッシュインデックスは平均O(1)（定数時間）で等価検索を実現します。B-Treeの検索がO(log n)であるのに対し、ハッシュインデックスはデータ量に依存しません。1万件でも1億件でも、ハッシュ値を1回計算してバケットにアクセスするだけです。これは配列の添字アクセス array[i] がO(1)であるのと同じ原理で、ハッシュ値がそのまま配列のインデックスになります。
ただし、重要なトレードオフがあります。ハッシュ関数は入力値の大小関係（順序）を保存しません。h(100)=0, h(101)=1, h(102)=2 のように連続する保証はなく、h(104)=0 のように飛びます。このため範囲検索には使えません。
ハッシュインデックスが使えないSQLの例
✗ SELECT * FROM products WHERE price BETWEEN 100 AND 500
✗ SELECT * FROM users ORDER BY created_at
✗ SELECT * FROM users WHERE name LIKE 'Tanaka%'
範囲検索・ソート・前方一致はすべてデータの順序に依存するため、順序を保持しないハッシュインデックスでは処理できません。これらにはB-Tree（B+Tree）を使います。
また、複数のキーが同じバケットに割り当てられる「衝突（collision）」が避けられず、衝突が増えると検索性能がO(1)からO(n)に劣化します。そのためバケット数やバケット容量の設計が性能を左右します。
実務では、等価検索が支配的なワークロードで広く採用されています。
ハッシュインデックスを採用している製品
- MySQLMEMORYストレージエンジンでインメモリテーブル専用のハッシュインデックスを提供
- PostgreSQLHash Index をサポート。バージョン10以降でWAL（書き込み先行ログ）対応し実用レベルに
- Redis内部データ構造としてハッシュテーブルを採用。全キー検索の基盤
- Memcachedキャッシュルックアップにハッシュテーブルを使用。キーを指定すれば即座にデータを返す
ほとんどのRDBMSではB-Tree（B+Tree）がデフォルトのインデックスであり、ハッシュインデックスは明示的に指定して初めて使われます。
💡 試してみよう： 上のツールで値を挿入して、ハッシュ値がどのバケットに入るか確認してみましょう。たとえば「42」と「5」を入れた後に「37」を入れると、5と37が同じバケットに入り衝突する様子が見えます。バケット数を変えると衝突の起こりやすさが変化します。
🔧ハッシュインデックスの仕組み
ハッシュインデックスは、ハッシュ関数とバケット配列の2つで構成されます。キーをハッシュ関数に通してバケット番号を得て、そのバケットにデータを格納・検索します。下の図で全体の流れを見てみましょう。
全体構造：キーからバケットへの流れ
キー42をハッシュ関数に通すと 42 mod 4 = 2 が得られ、バケット[2]に直接アクセスします。B-Treeのようにルートから枝をたどる必要はなく、配列の添字アクセスと同じO(1)です。
衝突が起きたとき：オーバーフローチェーン
負荷率（Load Factor）と性能の関係
負荷率 α = 総キー数 ÷（バケット数 × 容量）。α が0.7以下なら衝突は少なく高速。1.0を超えるとオーバーフローが頻発し、検索がチェーンをたどるぶん遅くなります。上のツールの統計欄で負荷率の変化を確認できます。
💾実際のデータベースではどんな値がハッシュされる？
上のツールでは簡略化のために整数のキーを直接 mod N していますが、実際のデータベースでハッシュインデックスの対象になるのはテーブルのカラム値です。ユーザーIDのような整数だけでなく、メールアドレスのような文字列、UUIDなどあらゆるデータ型がハッシュの入力になり得ます。
では文字列のような非数値データはどうやってバケット番号に変換するのでしょうか？ 答えは2段階のハッシュです。
2段階のハッシュ：任意の型 → 整数 → バケット番号
データ型別の具体例
整数（主キー）
WHERE user_id = 42
42 → そのまま mod N → バケット番号
整数はそのままハッシュ関数に渡せるため最もシンプル
文字列（メール）
WHERE email = 'tanaka@example.com'
'tanaka@...' → hashtext() → 829174 → mod N → バケット番号
文字列は内部ハッシュ関数（PostgreSQLならhashtext()）で整数に変換してからmod N
UUID（セッションID）
WHERE session_id = 'a3f8-b2c1-...'
'a3f8-...' → hashuuid() → 571032 → mod N → バケット番号
UUIDもバイト列として内部ハッシュ関数で整数化される
PostgreSQLでハッシュインデックスを作るSQL
-- emailカラムにハッシュインデックスを作成
CREATE INDEX idx_users_email
ON users USING hash (email);
-- このインデックスが効くクエリ
✓ SELECT * FROM users WHERE email = 'tanaka@example.com';
-- このインデックスが効かないクエリ
✗ SELECT * FROM users WHERE email LIKE 'tanaka%';
CREATE INDEX idx_users_email
ON users USING hash (email);
-- このインデックスが効くクエリ
✓ SELECT * FROM users WHERE email = 'tanaka@example.com';
-- このインデックスが効かないクエリ
✗ SELECT * FROM users WHERE email LIKE 'tanaka%';
USING hash を指定しなければB-Tree（デフォルト）が使われます。ハッシュインデックスは等価検索（=）にのみ有効です。
💡 ポイント： 上のツールで使っている整数キーは、実際のデータベースでは「カラム値を内部ハッシュ関数で整数に変換した後の値」に相当します。文字列でもUUIDでも、最終的には整数になってからバケットに振り分けられるため、ハッシュインデックスの動作原理は同じです。
✅ハッシュインデックスの特徴
- ⚡平均O(1)のランダムアクセス — なぜO(1)なのか？ それは配列のインデックスアクセスと同じ原理だからです。array[2] が一瞬で取得できるのと同じように、h(key) の計算結果がそのままバケット番号になり、メモリ上のアドレスが即座に判明します。WHERE id = 42 のような等価検索（=）に最適です。
- 🚫範囲検索に使えない — WHERE price BETWEEN 100 AND 500 のようなクエリには不向きです。なぜなら、h(100) = 0, h(101) = 1, h(102) = 2... というように、ハッシュ値は元の数字の順序を保たないためです。100から200の範囲を取得するには、すべてのバケットを調べる必要があり、ハッシュインデックスの意味がなくなります。
- 📦バケット方式 — バケットとは「郵便局の仕分け棚」のようなものです。手紙の宛先（キー）を見て、対応する棚（バケット）に入れます。h(key) = key mod N でバケット番号を決定し、シンプルな計算で格納先が即座に判明します。
- ⛓️オーバーフローチェーン — 棚が満杯になったら隣に仮の棚を増設するイメージです。バケットが満杯になると、新しいバケットを鎖状に連結して対応します。ただし、チェーンが長くなるほど目的のデータを見つけるのに時間がかかり、最悪の場合O(1)ではなくO(n)に近づきます。
- 📊負荷率が性能の鍵 — 具体的に計算してみましょう。バケット4個 × 容量3 = 最大12個のスロットがあります。8個のキーが入っていれば負荷率は 8/12 ≒ 0.67 です。0.7を超えたら注意、1.0を超えるとオーバーフローが頻発し、性能が大幅に低下します。
💡 試してみよう： 上のツールで負荷率の変化を確認してみてください。値を多く挿入すると負荷率が上がり、オーバーフローが発生する様子が見えます。
🎯ユースケース
🗄️ インメモリDB
データがすべてメモリ上にあるため、ディスクI/Oの心配がなく、O(1)のルックアップが最大限に活きます。Redisはハッシュテーブルを主要なデータ構造として使用しています。SET key value → GET key が内部的にハッシュテーブルで処理されます。
🔑 セッション管理
ユーザーがログインするとランダムなセッションID（例：a3f8c...）が生成され、ハッシュテーブルに保存されます。次のリクエストでセッションIDが送られてくると、O(1)でユーザー情報を特定できます。セッションIDはランダム文字列なので範囲検索は不要 — ハッシュの最適な用途です。
📋 ユニーク制約
INSERT INTO users (email) VALUES ('a@b.com') を実行すると、DBは「a@b.com」がすでに存在するかチェックする必要があります。ハッシュインデックスならこの重複チェックがO(1)で完了します（B-TreeだとO(log n)）。
🔄 Hash Join
2つの大きなテーブルを等価条件（WHERE a.id = b.id）で結合するとき、PostgreSQLは小さい方のテーブルからハッシュテーブルを構築し、大きい方のテーブルの各行でプローブ（検索）します。これにより大規模な結合も効率的に処理できます。
📖用語解説
ハッシュ関数（Hash Function）
＝ キーから格納場所を計算する関数
ミンチ機をイメージしてください。どんな食材（キー）を入れても、ミンチ（ハッシュ値）が出てきます。同じ食材を入れれば必ず同じミンチが出る — これがハッシュ関数の最も重要な性質「決定性」です。同じ入力からは必ず同じ出力が得られます。
具体例（PostgreSQLの場合）：
・整数: hashint4(42) → 内部整数値 → mod N
・文字列: hashtext('tanaka@example.com') → 内部整数値 → mod N
・UUID: hashuuid('a3f8-...') → 内部整数値 → mod N
・文字列: hashtext('tanaka@example.com') → 内部整数値 → mod N
・UUID: hashuuid('a3f8-...') → 内部整数値 → mod N
良いハッシュ関数の条件は、(1) 計算が高速であること、(2) 出力がバケット全体に均等に分散すること（一箇所に集中しないこと）の2つです。
このデモでは最もシンプルなハッシュ関数を使っています：
h(key) = key mod N （N = バケット数）
実際のデータベースでは、mod演算だけでなくビット演算や乗算を組み合わせたより高度なハッシュ関数が使われます。上のツールではハッシュ関数の計算過程がアニメーションで表示されます。キーが入力され、ハッシュ値が計算され、対応するバケットがハイライトされる様子を確認してみてください。
バケット（Bucket）
＝ データを入れる固定容量の箱
郵便受けのようなものです。各バケットにはあらかじめ決まった容量があり、その数だけエントリを格納できます。キー42を挿入すると、h(42) = 2 なのでバケット2に入ります。
データベースの文脈では、バケットは実際にはディスク上の固定サイズのページ（通常4KB〜8KB）に対応します。1つのページに入るレコード数がバケットの容量になります。
たとえばページサイズが8KBで1レコードが100バイトなら、1バケットに約80レコードが入ります。上のツールでは容量を2〜5に簡略化していますが、実際のDBではもっと多くのレコードが1バケットに入ります。
上のツールではバケットは横長の四角形で表示されます。各スロットにキーの値が表示され、空きスロットは灰色で表示されます。
衝突（Collision）
＝ 異なるキーが同じバケットに入ること
ハッシュテーブルでは衝突は避けられません。たとえば5と9は、どちらも h(key) mod 4 = 1 で同じバケットに入ります。これはエラーではなく、ハッシュの性質上必ず起こることです。
衝突率はバケット数とデータ量の関係で決まります。誕生日のパラドックスと同じ原理で、バケット数に対して驚くほど少ないデータ数で衝突が発生し始めます。たとえば、365個のバケットに23個のキーを入れると、少なくとも1つの衝突が起きる確率が50%を超えます。
衝突への対処法は主に2つあります。(1) チェーン法（このデモで使用）：同じバケットに連結リストでデータをつなげる。実装がシンプルで削除も容易だが、キャッシュ局所性が悪い。(2) オープンアドレス法：衝突したら空いているバケットを探して入れる。メモリ効率が良くキャッシュに優しいが、削除が複雑です。
オーバーフローチェーン（Overflow Chain）
＝ 満杯バケットに連結する追加の箱
本棚が満杯になったら、隣に増設棚を設置するイメージです。各オーバーフローバケットも元のバケットと同じ容量を持っています。さらに満杯になれば、また新しいオーバーフローバケットをチェーンでつなげます。
チェーンの長さは性能に直結します。チェーン長がkのとき、検索は最悪k回の比較が必要です。
チェーン長1: 比較1回（最速）
チェーン長3: 比較3回
チェーン長10: 比較10回（かなり遅い）
チェーン長100: 比較100回（ほぼ線形探索と同じ）
チェーン長3: 比較3回
チェーン長10: 比較10回（かなり遅い）
チェーン長100: 比較100回（ほぼ線形探索と同じ）
最悪のケースは、すべてのキーが同じバケットに集中する場合です。チェーンが1本の長いリストになり、検索が O(n) になってしまいます。上のツールではオレンジ色の箱がオーバーフローバケットです。
動的ハッシュ（拡張可能ハッシング・線形ハッシング）はこのチェーンの問題を根本的に解決するために考案されました。
負荷率（Load Factor）
＝ テーブルの混み具合を表す数値
計算式は以下の通りです：
α = n / (B × C)
n = 総キー数、B = バケット数、C = バケット容量。具体例：4バケット × 容量3 = 12スロット。8個のキーが入っていれば α = 8/12 ≒ 0.67。
0.7未満：良好。0.7以上：衝突が増加し始める。1.0以上：オーバーフローが確実に発生。上のツールの統計欄に負荷率がリアルタイムで表示されています。
実際のデータベースでの推奨値はシステムによって異なります：
PostgreSQL Hash Index: 内部的に75%程度で自動拡張
Java HashMap: デフォルト閾値0.75（超えると2倍にリサイズ）
Redis: 負荷率1.0を超えると段階的にリハッシュ
Java HashMap: デフォルト閾値0.75（超えると2倍にリサイズ）
Redis: 負荷率1.0を超えると段階的にリハッシュ
負荷率は「空間効率」と「時間効率」のトレードオフです。低い閾値はメモリを多く使うが検索が速い。高い閾値はメモリを節約できるが衝突が増えて遅くなります。
🪜ハッシュインデックスの手順
バケット数4、容量3の設定で、キー 5, 12, 42, 37 を順に挿入する例で手順を見ていきましょう。
1
ハッシュ値を計算
キーをハッシュ関数に入れてバケット番号を求めます。計算はとてもシンプルで、割り算の余り（mod）を使います。例：42 ÷ 4 = 10 余り 2。この「余り 2」がバケット番号です。どんなに大きな数字でも、余りは必ず 0〜3（バケット数-1）の範囲に収まるので、必ずどこかのバケットに入ります。
2
バケットを特定
配列のインデックスアクセスと同じです。bucket[2] に直接アクセスするので、他のバケットを見る必要はありません。これがO(1)の秘密です。B-Treeのようにルートから枝を辿る必要がないのです。
3
バケットに空きがあれば挿入
バケットには容量があります（この例では3個）。まだ空きがあれば、そのまま値を末尾に追加して完了。これが最も速いケースです。たとえばバケット2が空であれば、42はそのままバケット2の最初のスロットに入ります。
4
満杯ならオーバーフローバケットを作成
もしバケットがすでに満杯（3個入っている）なら、新しい「オーバーフローバケット」を作成して元のバケットにチェーンでつなげます。新しい値はこのオーバーフローバケットに入ります。上のツールでは、オーバーフローバケットはオレンジ色の矢印でつながれて表示されます。
5
検索時も同じ手順
検索時も同じ流れです。まず h(37) = 37 mod 4 = 1 でバケット1を特定。バケット1の中を順に見ていき、37が見つかれば完了。見つからなければオーバーフローチェーンをたどります。バケット内のスキャンは高々「容量」個なので、チェーンが短ければ非常に高速です。
// 例）バケット数=4, 容量=3 で 5, 12, 42, 37 を挿入
h(5) = 5 mod 4 = 1 → バケット[1]に挿入
h(12) = 12 mod 4 = 0 → バケット[0]に挿入
h(42) = 42 mod 4 = 2 → バケット[2]に挿入
h(37) = 37 mod 4 = 1 → バケット[1]に挿入（5と衝突）
h(5) = 5 mod 4 = 1 → バケット[1]に挿入
h(12) = 12 mod 4 = 0 → バケット[0]に挿入
h(42) = 42 mod 4 = 2 → バケット[2]に挿入
h(37) = 37 mod 4 = 1 → バケット[1]に挿入（5と衝突）
💡 試してみよう： 上のツールで 5, 12, 42, 37 の順に挿入してみてください。同じ手順が可視化されます。特に37を挿入するときに衝突が起きる様子を確認しましょう。
📊計算量と他の手法との比較
いつハッシュインデックスを選ぶべきか
- ✓等価検索（WHERE id = ?）がほとんどの場合 — たとえば「ユーザーIDでプロフィールを取得」のようなクエリが大部分を占めるテーブル
- ✓セッション管理・キャッシュなどキーで1件取得する用途 — セッションIDやAPIキーなどランダム文字列でのルックアップ
- ✓ユニーク制約の重複チェック — メールアドレスやユーザー名の一意性を高速に確認したい場合
- ✓順序やソートが一切不要な場合 — ORDER BY や GROUP BY を使わないことが確実なテーブル
いつB-Treeを選ぶべきか
- ✓範囲検索（BETWEEN, >, <）が必要な場合 — 例：WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'
- ✓ORDER BYでソートされた結果が必要な場合 — 例：ORDER BY price ASC でインデックスの順序をそのまま利用
- ✓LIKE 'prefix%' のような前方一致検索 — 例：WHERE name LIKE '田中%' で「田中」で始まる名前を効率的に検索
- ✓インデックスを使った最小値・最大値の取得 — MIN(price) や MAX(date) をインデックスの端から即座に取得
💡 実務でのポイント多くのRDBMS（PostgreSQL、MySQL InnoDB など）では、CREATE INDEX するとデフォルトでB-Treeが使われます。ハッシュインデックスを使いたい場合は、明示的に指定する必要があります。
-- PostgreSQLでハッシュインデックスを作成する例
CREATE INDEX idx_users_email ON users USING hash (email);
ハッシュインデックスは「等価検索しか使わない」と確信できる場面、 たとえばRedis のようなインメモリKVSや、セッションテーブルの主キー検索など、 限定的なユースケースで威力を発揮します。迷ったらまずB-Treeを使い、等価検索のボトルネックが明確になってからハッシュを検討するのが安全です。B-Treeは範囲検索もソートも等価検索もこなせる万能選手ですが、ハッシュは等価検索に特化した専門家 — 得意分野では圧倒的に速いのです。CREATE INDEX idx_users_email ON users USING hash (email);
関連コンテンツ
拡張可能ハッシング（Extendible Hashing）
ディレクトリを倍増させて動的にバケットを拡張するハッシュ方式
Hash Join
小テーブルからハッシュテーブルを構築し大テーブルでプローブする等価結合アルゴリズム
Grace Hash Join
メモリに収まらないテーブルをパーティション分割してディスク上でHash Joinする手法
Hybrid Hash Join
Grace Hash Joinの改良版。1パーティションをメモリに保持してI/Oを30-50%削減
ビットマップインデックス（Bitmap Index）
カラム値ごとにビット配列を持ちAND/OR/NOTをビット演算で高速処理するインデックス
コストベース最適化
テーブル統計情報を元に複数の実行プランのコストを比較し最小コストのプランを選択する最適化手法