データ構造 - ハッシュテーブル

ハッシュテーブル(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;
}

応用シーン

シーン説明
辞書/Mapキーと値のペアの格納と高速検索。例:Python の dict、Java の HashMap
キャッシュシステムLRU Cache などのキャッシュシステムの基盤実装
データベースインデックスハッシュインデックスによる等価クエリの O(1) 検索の実現
コンパイラのシンボルテーブル変数名、関数名とその型のマッピング関係を記録する
その他の拡張