データ構造 - ハッシュテーブル
ハッシュテーブル(Hash Table)は、ハッシュ関数によってキーを配列の特定の位置にマッピングし、平均 O(1) の時間計算量で検索、挿入、削除操作を実現するデータ構造です。
ハッシュ関数とハッシュ衝突
ハッシュテーブルの原理 — ハッシュ関数によるマッピング
key=1
key=2
key=11
→
hash(key) = key % 10
→
[0]
[1] 1,11
[2] 2
[3]
[4]
[5]
[6]
[7]
[8]
[9]
赤いスロット = 衝突!key=1 と key=11 が同じ位置にマッピングされる
ハッシュ関数の設計目標は、任意の入力(キー)を固定範囲内の整数(配列インデックス)に変換することです。
優れたハッシュ関数は、計算速度が速く、結果の分布が均一であるという特性を備えている必要があります。
しかし、ハッシュテーブルの容量は常に有限であるため、ハッシュ衝突——2つの異なるキーが同じ位置にマッピングされる——という現象は避けられません。
衝突解決方法
ハッシュ衝突の解決 — チェイン法 vs オープンアドレッシング法
チェイン法
各スロットに連結リストを格納し、衝突したキーを追加する
利点:実装が簡単、削除が容易
欠点:ポインタのオーバーヘッド、キャッシュに不向き
負荷係数は 1.0 を超えてもよい
オープンアドレッシング法
衝突時に次の空き位置を探査する
利点:ポインタなし、キャッシュに友好的
欠点:削除には遅延マークが必要
負荷係数は ≤ 0.7 である必要がある
| 方法 | 原理 | 利点 | 欠点 |
|---|---|---|---|
| チェイン法 | 各スロットに連結リストを1つ格納し、衝突したキーを連結リストに追加する | 実装が簡単、削除が容易、負荷係数を 1 より大きくできる | 追加のポインタオーバーヘッド、キャッシュに不向き |
| オープンアドレッシング法 | 衝突時は探査規則に従って配列内の次の空き位置を探す | ポインタが不要で、キャッシュに友好的 | 削除が複雑(遅延削除が必要)、負荷係数の管理が必要 |
オープンアドレッシング法では、要素を削除する際に単純にスロットを空にすることはできません。そうしないと後続の要素の検索チェーンが壊れてしまうからです。通常は「遅延削除」を使用します——その位置を「空」ではなく「削除済み」としてマークします。
チェイン法の実装
実例
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* ハッシュテーブル容量 */
/* ハッシュテーブルのノード */
struct HashNode {
int key;
int value;
struct HashNode* next; /* 同じスロット内の次のノードを指す */
};
/* ハッシュ関数:単純な剰余法 */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* キーと値のペアを挿入(チェイン法)
時間計算量:平均 O(1)、最悪 O(n)(すべてのキーが同じスロットにマッピングされる場合) */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* 先頭挿入法 */
table[index] = newNode;
}
/* 検索:キーに基づいて値を取得
まずハッシュ値を計算してスロットを特定し、連結リストを走査して一致するキーを探す */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* 見つかった */
}
cur = cur->next;
}
return -1; /* 見つからなかった */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* すべてのスロットを空に初期化する */
insert(table, 1, 100); /* key=1, value=100, index=1 */
insert(table, 2, 200); /* key=2, value=200, index=2 */
insert(table, 11, 300); /* key=11, value=300, index=1 — key=1 と衝突! */
printf("key=1 → %d\n", search(table, 1)); /* 出力: 100 */
printf("key=2 → %d\n", search(table, 2)); /* 出力: 200 */
printf("key=11 → %d\n", search(table, 11)); /* 出力: 300 (チェイン法が衝突を正しく処理した) */
printf("key=99 → %d\n", search(table, 99)); /* 出力: -1 (見つからなかった) */
return 0;
}
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* ハッシュテーブル容量 */
/* ハッシュテーブルのノード */
struct HashNode {
int key;
int value;
struct HashNode* next; /* 同じスロット内の次のノードを指す */
};
/* ハッシュ関数:単純な剰余法 */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* キーと値のペアを挿入(チェイン法)
時間計算量:平均 O(1)、最悪 O(n)(すべてのキーが同じスロットにマッピングされる場合) */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* 先頭挿入法 */
table[index] = newNode;
}
/* 検索:キーに基づいて値を取得
まずハッシュ値を計算してスロットを特定し、連結リストを走査して一致するキーを探す */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* 見つかった */
}
cur = cur->next;
}
return -1; /* 見つからなかった */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* すべてのスロットを空に初期化する */
insert(table, 1, 100); /* key=1, value=100, index=1 */
insert(table, 2, 200); /* key=2, value=200, index=2 */
insert(table, 11, 300); /* key=11, value=300, index=1 — key=1 と衝突! */
printf("key=1 → %d\n", search(table, 1)); /* 出力: 100 */
printf("key=2 → %d\n", search(table, 2)); /* 出力: 200 */
printf("key=11 → %d\n", search(table, 11)); /* 出力: 300 (チェイン法が衝突を正しく処理した) */
printf("key=99 → %d\n", search(table, 99)); /* 出力: -1 (見つからなかった) */
return 0;
}
応用シーン
| シーン | 説明 |
|---|---|
| 辞書/Map | キーと値のペアの格納と高速検索。例:Python の dict、Java の HashMap |
| キャッシュシステム | LRU Cache などのキャッシュシステムの基盤実装 |
| データベースインデックス | ハッシュインデックスによる等価クエリの O(1) 検索の実現 |
| コンパイラのシンボルテーブル | 変数名、関数名とその型のマッピング関係を記録する |