ハッシュテーブルを実装して理解するぜ

Pythonのdict、JavaScriptのObject、JavaのHashMap、Goのmap、C++のstd::unordered_map、RustのHashMap――これらは名前は微妙に違えど、ハッシュテーブルです。
ハッシュテーブルは、キーと値のペアを効率的に管理するデータ構造として、現代のプログラミングにおいて欠かせない存在です。平均的にO(1)の時間計算量で要素の挿入、検索、削除を実現できるため、多くの言語において、標準ライブラリで提供されているデータ構造です。

操作	平均ケース	最悪ケース
検索 (Search)	O(1)	O(n)
挿入 (Insert)	O(1)	O(n)
削除 (Delete)	O(1)	O(n)
空間計算量	O(n)	O(n)

これほど便利で普段使っているデータ構造は、どのように実装されているのか気になりますよね？？
今回はPythonでハッシュテーブルを実装したのですが、実は約200行くらいのコードで簡単に実装できます！
この記事では、ハッシュテーブルの基本原理から実装まで解説していきます。

• ハッシュテーブルとは
• ハッシュ関数の役割と設計のポイント
• 衝突（collision）の解決方法（チェイン法とオープンアドレス法）
• 動的なサイズ変更（リハッシュ）の仕組み
• 実際のコードによる実装例

ハッシュテーブルとは

ハッシュテーブル（Hash Table）は、キーと値のペアを効率的に格納・検索するためのデータ構造です。ハッシュ関数を使ってキーを配列のインデックスに変換し、その位置に値を格納することで、平均的にO(1)の時間計算量で要素へのアクセスを実現します。

基本的な仕組みは以下の通りです：

1. ハッシュ関数: キーを受け取り、配列のインデックスとなる整数値（ハッシュ値）を返す
2. 配列: ハッシュ値に対応する位置に値を格納する
3. 衝突処理: 異なるキーが同じハッシュ値を持つ場合（衝突）の処理方法

ハッシュテーブルの実態は単なる配列です。「ハッシュテーブル」という名前から特別なデータ構造を想像しがちですが、本質的には配列＋ハッシュ関数という組み合わせに過ぎません。

計算量の観点

ハッシュテーブルの最大の特徴は、平均的な時間計算量がO(1)であることです。これは、配列のインデックスで直接アクセスできるため、要素数が増えても検索・挿入・削除の速度がほぼ一定に保たれることを意味します。ただし、最悪ケース（全てのキーが同じハッシュ値を持つ場合など）ではO(n)となり、線形探索と同等の性能になってしまいます。そのため、良いハッシュ関数の設計と適切な衝突処理が重要になります。

ハッシュテーブルの構造

ハッシュテーブルの動作を図で表すと以下のようになります：

キー "apple"  →  [ハッシュ関数]  →  ハッシュ値: 12345  →  インデックス: 5  →  [配列[5]]  →  値: 100
キー "banana" →  [ハッシュ関数]  →  ハッシュ値: 67890  →  インデックス: 2  →  [配列[2]]  →  値: 200
キー "cherry" →  [ハッシュ関数]  →  ハッシュ値: 11111  →  インデックス: 1  →  [配列[1]]  →  値: 300

実際のハッシュテーブルの内部構造は以下のようになります：

配列
┌─────┬─────────────────────┐
│ [0] │ empty               │
├─────┼─────────────────────┤
│ [1] │ ("cherry", 300)     │
├─────┼─────────────────────┤
│ [2] │ ("banana", 200)     │
├─────┼─────────────────────┤
│ [3] │ empty               │
├─────┼─────────────────────┤
│ [4] │ empty               │
├─────┼─────────────────────┤
│ [5] │ ("apple", 100)      │
├─────┼─────────────────────┤
│ ... │                     │
└─────┴─────────────────────┘

ハッシュ関数によってキーが配列のインデックスに変換され、その位置にキーと値のペアが格納されます。これにより、キーから直接インデックスを計算できるため、平均的にO(1)の時間で要素にアクセスできます。

ハッシュ関数の役割と設計のポイント

ハッシュテーブルの核心は、ハッシュ関数にあります。ハッシュ関数は、任意のキーを受け取って、固定範囲の整数値（ハッシュ値）を返す関数です。

key_hash = hash(key)
index = key_hash % self.capacity

ハッシュ関数の役割

1. キーを配列のインデックスに変換: 文字列やオブジェクトなど、どんな型のキーでも整数のインデックスに変換します
2. 均等な分布: 理想的なハッシュ関数は、キーを均等に分散させ、衝突を最小限に抑えます
3. 高速な計算: O(1)の時間計算量で計算できる必要があります

設計のポイント

良いハッシュ関数には以下の特徴があります：

• 決定性: 同じキーには常に同じハッシュ値を返す
• 均等分布: 異なるキーは異なるハッシュ値になりやすい（衝突が少ない）
• 高速性: 計算が速い
• 雪崩効果: キーの小さな変化でもハッシュ値が大きく変わる

衝突（collision）の解決方法

異なるキーが同じハッシュ値を持つことを衝突（collision）と呼びます。衝突は避けられないため、適切な解決方法が必要です。ここでは代表的な衝突の解決方法二つを簡単に紹介します。

チェイン法（Chaining）

今回実装する方法で、各スロットに線形リストを保持します。衝突が起きたら、同じインデックスのリストに追加します。

メリット:

• 実装がシンプル
• 削除が簡単
• 理論上、無限に要素を追加できる

デメリット:

• メモリオーバーヘッド（各エントリにポインタが必要）
• キャッシュ効率が悪い

オープンアドレス法（Open Addressing）

衝突が起きたら、別の空いているスロットを探してそこに格納します。代表的な方法には以下のものがあります：

• 線形探査法（Linear Probing）: 次のスロット、その次のスロット...と順番に探す
• 二次探査法（Quadratic Probing）: 1²、2²、3²...と距離を増やしながら探す
• 二重ハッシュ法（Double Hashing）: 別のハッシュ関数を使って次の位置を決定

メリット:

• メモリ効率が良い（ポインタが不要）
• キャッシュ効率が良い（連続したメモリ領域を使用）

デメリット:

• 削除が複雑（トゥームストーンが必要）
• 負荷率が高くなると性能が急激に低下

動的なサイズ変更（リハッシュ）の仕組み

ハッシュテーブルの性能を保つため、要素数が増えてきたらテーブルのサイズを拡張する必要があります。これをリハッシュ（rehashing）と呼びます。

負荷率（Load Factor）

負荷率は、テーブルの使用率を表す指標です：

負荷率 = 要素数 / テーブルの容量

負荷率が高すぎると、衝突が頻発して性能が低下します。一般的には、0.7〜0.75を超えたらリサイズすることが多いですが、チェイン法では2.0程度まで許容できることもあります。

リサイズはO(n)の時間がかかりますが、頻繁には発生しないため、平均的な時間計算量はO(1)のままです。

チェイン法でハッシュテーブルを実装してみた

ハッシュテーブルを実装する際、衝突（collision）の代表的な処理方法のうちの1つ、チェイン法（Chaining）を使ったHashTableの実装について解説します。

チェイン法とは？

チェイン法は、ハッシュテーブルの各スロットに線形リストを保持する方法です。ハッシュ値が衝突した場合、同じインデックスの線形リストに要素を追加していきます。

イメージとしては、こんな感じです：

インデックス0: [Entry1] -> [Entry2] -> None
インデックス1: None
インデックス2: [Entry3] -> None
インデックス3: [Entry4] -> [Entry5] -> [Entry6] -> None
...

同じハッシュ値を持つ要素が複数あっても、線形リストでつなげることで全て保持できます。

スロットは、ハッシュテーブルの配列における個々の格納位置を指します。ハッシュ関数の出力がそのままインデックスとなり、各スロットに線形リストが格納されます。

実装のポイント

Entryクラス

まず、各エントリを表すEntryクラスを見てみましょう。

class Entry:
    __slots__ = ("key", "value", "hash", "next")

    def __init__(self, key, value, hash, next):
        self.key = key
        self.value = value
        self.hash: int = hash
        self.next: self.Entry | None = next

通常のハッシュテーブルのエントリと違うのは、nextポインタを持っている点です。これで線形リストを構成します。

挿入（insert）

挿入処理の流れは以下の通りです：

1. ハッシュ値を計算してインデックスを決定
2. そのインデックスの線形リストを確認
3. 空なら新しいエントリを作成
4. 既に要素があれば、線形リストを辿って同じキーがないか確認
5. 同じキーがあれば値を更新、なければ末尾に追加

def insert(self, key, value):
    if (self.size + 1) / self.capacity >= self.TABLE_MAX_LOAD:
        self._resize()
    key_hash = hash(key)
    index = key_hash % self.capacity

    entry = self.arr[index]
    if entry is None:
        # 空のスロットなら新規作成
        self.arr[index] = self.Entry(key, value, key_hash, None)
        self.size += 1
        return

    # 線形リストを辿る
    while entry is not None:
        if key_hash == entry.hash and key == entry.key:
            # 同じキーなら値を更新
            entry.value = value
            return
        last_entry = entry
        entry = entry.next
    # 末尾に追加
    last_entry.next = self.Entry(key, value, key_hash, None)
    self.size += 1

複雑に見えるかもしれませんが、行っていることは各スロットごとに線形リストを作成しているだけです。
とてもシンプルです。

検索（get）

検索もシンプルです。ハッシュ値からインデックスを計算し、その線形リストを先頭から順に辿ってキーが一致するエントリを見つけます。

def get(self, key):
    _, entry = self._find(key)
    return entry.value if entry else None

def _find(self, key) -> Optional[Tuple[Entry, Entry]]:
    """
    returns (previous_target, target) or None
    """
    key_hash = hash(key)
    index = key_hash % self.capacity
    
    prev = None
    entry = self.arr[index]
    while entry is not None:
        if key_hash == entry.hash and key == entry.key:
            return prev, entry
        prev = entry
        entry = entry.next
    return None, None

内部で使っている_findメソッドは、線形リストを辿ってkeyが同じノードを探しています。削除処理でも使えるように一つ前のノードも一緒に返しています。

削除（remove）

削除処理では、線形リストから特定のエントリを取り除く必要があります。そのため、_findで前のエントリ（prev）も取得しています。

def remove(self, key) -> bool:
    prev, entry = self._find(key)
    if entry is None:
        return False
    index = entry.hash % self.capacity
    if prev is None:
        # 先頭要素を削除する場合
        self.arr[index] = entry.next
    else:
        # 中間要素を削除する場合
        prev.next = entry.next

    self.size -= 1
    del entry
    return True

prevがNoneの場合は先頭要素なので、配列のインデックスを直接更新します。そうでなければ、前のエントリのnextポインタを更新して線形リストから外します。

リサイズ

負荷率（要素数 / 容量）がTABLE_MAX_LOAD（2.0）を超えたら、テーブルを2倍に拡張します。リサイズ時は、全てのエントリを再ハッシュして新しいテーブルに挿入し直します。

def _resize(self):
    old_arr = self.arr
    old_capacity = self.capacity
    self.capacity = old_capacity * 2
    self.arr = [None] * (self.capacity)
    self.size = 0
    for slot in old_arr:
        entry = slot
        while entry is not None:
            self.insert(entry.key, entry.value)
            entry = entry.next

各スロットの線形リストを全て辿って、新しいテーブルに再挿入しています。
以上のように線形リストを実装するだけで、ハッシュテーブルの完成です！
以下が全体のコードになります。

class ChainedHashTable:
    """
    HashTable implementation using separate chaining.
    """

    class Entry:
        __slots__ = ("key", "value", "hash", "next")

        def __init__(self, key, value, hash, next):
            self.key = key
            self.value = value
            self.hash: int = hash
            self.next: self.Entry | None = next

        def __str__(self):
            return f"Node(key={self.key}, value={self.value}, hash={self.hash})"

    TABLE_MAX_LOAD = 2.0  # 最大保有率。これを超えたらリサイズする

    def __init__(self):
        self.size: int = 0
        self.capacity: int = 8
        self.arr: list[self.Entry | None] = [None] * self.capacity

    def insert(self, key, value):
        if (self.size + 1) / self.capacity >= self.TABLE_MAX_LOAD:
            self._resize()
        key_hash = hash(key)
        index = key_hash % self.capacity

        entry = self.arr[index]
        if entry is None:
            self.arr[index] = self.Entry(key, value, key_hash, None)
            self.size += 1
            return

        while entry is not None:
            if key_hash == entry.hash and key == entry.key:
                entry.value = value
                return
            last_entry = entry
            entry = entry.next
        last_entry.next = self.Entry(key, value, key_hash, None)
        self.size += 1

    def _find(self, key) -> Optional[Tuple[Entry, Entry]]:
        """
        returns (previous_target, target) or None
        """
        key_hash = hash(key)
        index = key_hash % self.capacity

        prev = None
        entry = self.arr[index]
        while entry is not None:
            if key_hash == entry.hash and key == entry.key:
                return prev, entry
            prev = entry
            entry = entry.next
        return None, None

    def get(self, key):
        _, entry = self._find(key)
        return entry.value if entry else None

    def remove(self, key) -> bool:
        prev, entry = self._find(key)
        if entry is None:
            return False
        index = entry.hash % self.capacity
        if prev is None:
            self.arr[index] = entry.next
        else:
            prev.next = entry.next

        self.size -= 1
        del entry
        return True

    def _resize(self):
        old_arr = self.arr
        old_capacity = self.capacity
        self.capacity = old_capacity * 2
        self.arr = [None] * (self.capacity)
        self.size = 0
        for slot in old_arr:
            entry = slot
            while entry is not None:
                self.insert(entry.key, entry.value)
                entry = entry.next

    def __setitem__(self, key, value):
        self.insert(key, value)

    def __getitem__(self, key):
        return self.get(key)

    def __delitem__(self, key):
        return self.remove(key)

    def __contains__(self, key):
        return self.get(key) is not None

    def __str__(self):
        entries: list[self.Entry] = []
        for head in self.arr:
            entry = head
            while entry is not None:
                entries.append(str(entry))
                entry = entry.next
        return str(entries)


def main():
    ht = ChainedHashTable()
    for i in range(10):
        ht.insert(f"key{i}", f"value{i}")

    print(ht)
    for i in range(20):
        if f"key{i}" in ht:
            print(f"Found: {ht[f'key{i}']}")
        else:
            print(f"Not Found: key{i}")

    for i in range(10):
        ht.insert(f"key{i}", f"value{i * 2}")

    for i in range(20):
        if f"key{i}" in ht:
            entry = ht.get(f"key{i}")
            print(f"Found: {entry}")
        else:
            print(f"Not Found: key{i}")

    for i in range(5):
        del ht[f"key{i}"]

    for i in range(20):
        if f"key{i}" in ht:
            entry = ht.get(f"key{i}")
            print(f"Found: {entry}")
        else:
            print(f"Not Found: key{i}")

    for i in range(1, 10):
        ht.insert(f"key{i * 2}", f"value{i * 3}")

    for i in range(20):
        if f"key{i}" in ht:
            entry = ht.get(f"key{i}")
            print(f"Found: {entry}")
        else:
            print(f"Not Found: key{i}")
    print(ht)


if __name__ == "__main__":
    main()

実行結果：

['Node(key=key3, value=value3, hash=-201465989773341024)', 'Node(key=key6, value=value6, hash=319271575831415025)', 'Node(key=key8, value=value8, hash=-7679304020410808670)', 'Node(key=key1, value=value1, hash=-6554417557372830316)', 'Node(key=key4, value=value4, hash=-2712713785723823556)', 'Node(key=key7, value=value7, hash=-1436635174615168300)', 'Node(key=key2, value=value2, hash=2567485762226970581)', 'Node(key=key5, value=value5, hash=-173812099388483547)', 'Node(key=key9, value=value9, hash=3333312648438915117)', 'Node(key=key0, value=value0, hash=-1533823209892358385)']
Found: value0
Found: value1
Found: value2
Found: value3
Found: value4
Found: value5
Found: value6
Found: value7
Found: value8
Found: value9
Not Found: key10
Not Found: key11
Not Found: key12
Not Found: key13
Not Found: key14
Not Found: key15
Not Found: key16
Not Found: key17
Not Found: key18
Not Found: key19
... (長いので省力)

チェイン法のメリット・デメリット

メリット

• シンプルな実装: 線形リストの操作が理解しやすい
• 動的なサイズ管理: 理論上、無限に要素を追加できる（実用上は負荷率で制御）
• 削除が簡単: トゥームストーン（削除マーカー）が不要（こちらは次の記事で紹介するオープンアドレス法にて解説します）

デメリット

• メモリオーバーヘッド: 各エントリにnextポインタが必要
• キャッシュ効率: 線形リストはメモリ上で連続していないため、キャッシュミスが起きやすい
• 最悪ケース: 全ての要素が同じハッシュ値だと、線形リストが長くなり性能が低下

まとめ

チェイン法は、ハッシュテーブルの衝突処理として直感的で理解しやすい方法です。線形リストを使うことで、同じハッシュ値を持つ複数の要素を自然に扱えます。

実装を見ると、基本的なデータ構造（配列と線形リスト）の組み合わせで、強力なハッシュテーブルがすごく簡単に作れることがわかりますね。こんなに簡単なものかと私も驚きました、、
次回はオープンアドレス法を解説し、チェイン法との比較を行います。ベンチマークで実際の性能差も測定してみる予定です！