ハッシュテーブル

Q: ハッシュテーブルの時間計算量は？

ハッシュ関数がキーを均等に分散させ、負荷率が低く保たれている場合、挿入・検索・削除は平均 `O(1)` です。最悪の場合 - すべてのキーが1つのバケットに衝突する場合 - それらは `O(n)` に劣化します。だからこそ良いハッシュ関数とリサイズが重要です。

Q: 二分探索木の代わりにハッシュテーブルを使うべきなのはいつですか？

完全一致の検索だけが必要で、順序の要件なしに平均 `O(1)` の速度が欲しいときはハッシュテーブルを使います。ソートされたキー、範囲クエリ、前者/後者の検索が必要なときは平衡二分探索木を使います。これらはハッシュテーブルでは効率的に行えません。BSTは保証された `O(log n)` 操作を提供する一方、ハッシュテーブルはその保証をより速い平均性能と引き換えにします。

最終更新 2026年7月1日

ハッシュテーブルは項目をバケットの配列に格納します。キーを配置または検索するには、キーをハッシュ関数に通し、その結果をバケット数で割った余りを取ります。これにより O(1) でバケットのインデックスが得られます。上の再生を押すと、各キーがバケットにハッシュされて格納され、検索が正しいバケットへ直接ジャンプする様子を見られます。

2つのキーが同じバケットに入ると（衝突）、この可視化は分離連鎖法を使います。各バケットは小さなリストを保持し、衝突したキーはそこに追加されます。テーブルが満杯になりすぎず（負荷率が低く）、ハッシュがキーをうまく分散させている限り、連鎖は短いままで、挿入・検索・削除は平均 O(1) になります。

時間計算量

操作	平均	最悪の場合
挿入	O(1)	O(n)（すべてのキーが衝突）
検索	O(1)	O(n)
削除	O(1)	O(n)
空間	O(n)	O(n)

主要な概念

用語	意味
ハッシュ関数	キーをバケットのインデックスに対応づける
衝突	2つのキーが同じバケットに入る
分離連鎖法	各バケットが衝突したエントリのリストを保持する
開番地法	代替案: 次の空きスロットを探索する
負荷率	エントリ数 / バケット数 - リサイズを決める

具体例

hash(k) = k % 7 を使い、キー 20、34、9、13 を7バケットのテーブルに挿入:

ステップ	構造	動作
`20` を挿入	バケット6: `[20]`	`20 % 7 = 6`、バケット6は空、`20` を格納
`34` を挿入	バケット6: `[20, 34]`	`34 % 7 = 6`、`20` と衝突、`34` を連鎖に追加
`9` を挿入	バケット2: `[9]`	`9 % 7 = 2`、バケット2は空、`9` を格納
`13` を挿入	バケット6: `[20, 34, 13]`	`13 % 7 = 6`、衝突、`13` をバケット6の連鎖に追加
`34` を検索	バケット6: `[20, 34, 13]`	`34 % 7 = 6`、連鎖を走査: `20` は違う、`34` が一致 - 発見

ハッシュテーブルを使うべき場面

使うべき場面	避けるべき場面
キーによる挿入・検索・削除を平均 `O(1)` で行いたい	キーをソート順に保つ必要がある - 平衡BSTを使う
キーに有用な順序がなく、完全一致の存在確認だけを行う	範囲クエリや最も近いキーの検索が必要
バケットと低い負荷率のために追加のメモリを割ける	メモリが極端に厳しく、1バイトも惜しい
キーの型に対して良いハッシュ関数が存在する	最悪ケースのレイテンシに上限が必要 - 衝突により `O(n)` になる

Hash Tableのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なHash Tableの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのHash TableのコードPython
1class HashTable:2    def __init__(self, size=8):3        self.size = size4        self.buckets = [[] for _ in range(size)]5
6    def _index(self, key):7        # Hash the key to a bucket; different keys can collide8        return sum(ord(ch) for ch in key) % self.size9
10    def set(self, key, value):11        bucket = self.buckets[self._index(key)]12        for i, (k, _) in enumerate(bucket):13            if k == key:14                bucket[i] = (key, value)  # update existing key15                return16        bucket.append((key, value))  # chain on collision17
18    def get(self, key):19        for k, v in self.buckets[self._index(key)]:20            if k == key:21                return v22        raise KeyError(key)23
24    def delete(self, key):25        bucket = self.buckets[self._index(key)]26        for i, (k, _) in enumerate(bucket):27            if k == key:28                del bucket[i]29                return30        raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple  ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple  ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])
このコードをPythonプレイグラウンドで実行

JavaScriptでのHash TableのコードJavaScript
1class HashTable {2    constructor(size = 8) {3        this.size = size;4        this.buckets = Array.from({ length: size }, () => []);5    }6
7    // Fold character codes into a bucket index8    hash(key) {9        let h = 0;10        for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11        return h;12    }13
14    set(key, value) {15        const bucket = this.buckets[this.hash(key)];16        const pair = bucket.find(([k]) => k === key);17        if (pair) pair[1] = value;18        else bucket.push([key, value]); // Separate chaining on collision19    }20
21    get(key) {22        const bucket = this.buckets[this.hash(key)];23        const pair = bucket.find(([k]) => k === key);24        return pair ? pair[1] : undefined;25    }26
27    delete(key) {28        const bucket = this.buckets[this.hash(key)];29        const index = bucket.findIndex(([k]) => k === key);30        if (index === -1) return false;31        bucket.splice(index, 1);32        return true;33    }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));
このコードをJavaScriptプレイグラウンドで実行

JavaでのHash TableのコードJava
1public class Main {2    static class Entry {3        String key; int value;4        Entry next; // chain for keys sharing a bucket5        Entry(String key, int value) { this.key = key; this.value = value; }6    }7
8    static final int CAPACITY = 8;9    static Entry[] buckets = new Entry[CAPACITY];10
11    static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13    static void put(String key, int value) {14        int i = index(key);15        for (Entry e = buckets[i]; e != null; e = e.next) {16            if (e.key.equals(key)) { e.value = value; return; }17        }18        Entry entry = new Entry(key, value);19        entry.next = buckets[i]; // prepend to the chain20        buckets[i] = entry;21    }22
23    static Integer get(String key) {24        for (Entry e = buckets[index(key)]; e != null; e = e.next) {25            if (e.key.equals(key)) return e.value;26        }27        return null;28    }29
30    static void remove(String key) {31        int i = index(key);32        Entry prev = null;33        for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34            if (e.key.equals(key)) {35                if (prev == null) buckets[i] = e.next;36                else prev.next = e.next;37                return;38            }39        }40    }41
42    public static void main(String[] args) {43        put("apple", 3); put("banana", 7); put("cherry", 5);44        System.out.println("apple -> " + get("apple"));45        put("apple", 10); // update in place46        System.out.println("apple -> " + get("apple"));47        remove("banana");48        System.out.println("banana -> " + get("banana"));49    }50}
このコードをJavaプレイグラウンドで実行

C++でのHash TableのコードC++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6    static constexpr int CAPACITY = 8;7    // Separate chaining: each bucket holds (key, value) pairs8    std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10    size_t hash(const std::string& key) const {11        size_t h = 0;12        for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13        return h % CAPACITY;14    }15
16    void set(const std::string& key, int value) {17        auto& bucket = buckets[hash(key)];18        for (auto& entry : bucket) {19            if (entry.first == key) {20                entry.second = value;  // update existing key21                return;22            }23        }24        bucket.push_back({key, value});25    }26
27    const int* get(const std::string& key) const {28        for (const auto& entry : buckets[hash(key)]) {29            if (entry.first == key) return &entry.second;30        }31        return nullptr;32    }33
34    void erase(const std::string& key) {35        auto& bucket = buckets[hash(key)];36        for (size_t i = 0; i < bucket.size(); ++i) {37            if (bucket[i].first == key) {38                bucket.erase(bucket.begin() + i);39                return;40            }41        }42    }43};44
45int main() {46    HashTable table;47    table.set("apple", 3);48    table.set("banana", 7);49    table.set("apple", 4);  // overwrites the old value50    for (const std::string& key : {"apple", "banana", "grape"}) {51        const int* value = table.get(key);52        if (value != nullptr) std::cout << key << " = " << *value << "\n";53        else std::cout << key << " not found\n";54    }55    table.erase("banana");56    std::cout << "banana after erase: "57              << (table.get("banana") ? "found" : "not found") << "\n";58    return 0;59}
このコードをC++プレイグラウンドで実行

CでのHash TableのコードC
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9    char key[16];10    int value;11    struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17    unsigned int h = 5381;  // djb2, then modulo the bucket count18    for (; *key; key++) h = h * 33 + (unsigned char)*key;19    return h % CAPACITY;20}21
22void set(const char* key, int value) {23    unsigned int i = hash(key);24    for (Entry* e = buckets[i]; e != NULL; e = e->next) {25        if (strcmp(e->key, key) == 0) {26            e->value = value;  // update existing key27            return;28        }29    }30    Entry* e = malloc(sizeof(Entry));31    strcpy(e->key, key);32    e->value = value;33    e->next = buckets[i];34    buckets[i] = e;35}36
37int* get(const char* key) {38    for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39        if (strcmp(e->key, key) == 0) return &e->value;40    }41    return NULL;42}43
44void removeKey(const char* key) {45    Entry** link = &buckets[hash(key)];46    while (*link != NULL) {47        if (strcmp((*link)->key, key) == 0) {48            Entry* old = *link;49            *link = old->next;50            free(old);51            return;52        }53        link = &(*link)->next;54    }55}56
57void printBuckets(void) {58    for (int i = 0; i < CAPACITY; i++) {59        printf("bucket %d:", i);60        for (Entry* e = buckets[i]; e != NULL; e = e->next) {61            printf(" (%s=%d)", e->key, e->value);62        }63        printf("\n");64    }65}66
67int main(void) {68    set("apple", 3);69    set("banana", 7);70    set("apple", 4);  // overwrites the old value71    set("grape", 9);72    printBuckets();73    int* value = get("apple");74    printf("get(apple): %d\n", value ? *value : -1);75    removeKey("banana");76    printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77    return 0;78}
このコードをCプレイグラウンドで実行

ハッシュテーブルよくある質問

ハッシュ衝突とは何で、どう解決しますか？

衝突は、2つの異なるキーが同じバケットにハッシュされたときに起こります。一般的な2つの解決策は、分離連鎖法（各バケットがリストを保持し、衝突したキーを追加する - ここで示している方法）と開番地法（配列内の次の空きスロットを探索する）です。どちらも検索の正しさを保ちますが、メモリレイアウトと高負荷時の性能が異なります。

ハッシュテーブルの時間計算量は？

ハッシュ関数がキーを均等に分散させ、負荷率が低く保たれている場合、挿入・検索・削除は平均 O(1) です。最悪の場合 - すべてのキーが1つのバケットに衝突する場合 - それらは O(n) に劣化します。だからこそ良いハッシュ関数とリサイズが重要です。

負荷率とは何ですか？

負荷率は、格納されているエントリ数をバケット数で割ったものです。これが大きくなると連鎖が長くなり操作が遅くなるため、ほとんどのハッシュテーブルは 0.75 のようなしきい値を超えるとリサイズ（より大きな配列へ再ハッシュ）します。

二分探索木の代わりにハッシュテーブルを使うべきなのはいつですか？

完全一致の検索だけが必要で、順序の要件なしに平均 O(1) の速度が欲しいときはハッシュテーブルを使います。ソートされたキー、範囲クエリ、前者/後者の検索が必要なときは平衡二分探索木を使います。これらはハッシュテーブルでは効率的に行えません。BSTは保証された O(log n) 操作を提供する一方、ハッシュテーブルはその保証をより速い平均性能と引き換えにします。

分離連鎖法と開番地法の違いは何ですか？

分離連鎖法は衝突したキーをバケットごとのリストに格納するため、1つのバケットが多くのエントリを保持でき、テーブルが本当に満杯になることはありません。開番地法はすべてを配列自体に保持し、衝突時に次の空きスロットを探索します。これはキャッシュに優しい一方、負荷率が1に近づくと急激に劣化し、削除の慎重な扱いが必要です。連鎖法はより高い負荷率を許容し、開番地法はメモリをよりコンパクトに使います。

ハッシュテーブルがキーを挿入順やソート順に保つことに頼れないのはなぜですか？

ハッシュ関数はクラスタリングを避けるために意図的にキーをバケット全体に散らすため、反復順序は挿入順やソート順ではなくバケットの配置を反映します。順序が必要なら、順序付きマップ/木、または挿入順を保持するマップのような構造を使ってください（例えばPythonの dict は挿入順を保持しますが、それは言語の保証であり、ハッシュテーブル本来の性質ではありません）。言語が明示的に約束しない限り、反復順序がキーを挿入した順と一致すると決して仮定しないでください。