Pythonのsetを再発明！ハッシュテーブルの仕組みをフルスクラッチ実装で徹底解説

1. はじめに

こんにちは！皆さん、Pythonのsetは使っていますか？

「リストから重複をサクッと消したい」「ある要素が含まれているか高速にチェックしたい」…そんな時にsetは便利ですよね。listのin演算子は、要素を一つずつ順番に探すため、要素数nが増えるほど時間がかかります（時間計算量 O(n)）。一方、setは要素数によらず、ほぼ一瞬で探せます（平均時間計算量 O(1)）。

では、なぜsetはこんなに速いのでしょうか？その内部では何が起きているのでしょうか？

この記事では、Pythonのsetをフルスクラッチで"再発明"することを通じて、ハッシュテーブルというデータ構造の仕組みをゼロから理解し、setがなぜ高速なのかを明らかにします。

🎯 この記事のゴール

• ハッシュテーブルの基本的な考え方を理解する。
• 衝突解決の代表的なアルゴリズム「チェイン法」と「オープンアドレス法」を実装しながら学ぶ。

👥 対象読者

• エンジニア、またはプログラミングを勉強中の大学生
• データ構造やアルゴリズムに興味がある方
• Pythonの内部実装にワクワクする方

この記事で扱わないこと
今回はアルゴリズムの基本を理解することに集中します。そのため、ハッシュテーブルが一杯になったら自動で拡張する「リサイズ」のような、高度な最適化は扱いません。あくまで「最もシンプルな実装」を通じて本質を掴むことを目的とします。

---

2. 「ハッシュテーブル」とは？

setの速さの秘密、それがハッシュテーブルです。これ例えるなら、ハッシュ値を番地(インデックス)として持つ棚に、データを格納していくイメージです。

データ（key）を格納するときに、どの棚（bucket / slot）にしまうかをハッシュ関数を使って決めます。ハッシュ関数は、データからインデックスを計算する関数です。

暗号などの文脈ではハッシュ関数の不可逆性が重要ですが、ここでは単にデータを特定の番号に変換するためのものと考えてください。

• ハッシュ関数 (hash function):
  入力されたデータ（例えば文字列"apple"）を、一見ランダムに見える固定長の数値（ハッシュ値）に変換する関数。Pythonでは組み込みのhash()関数が使えます。hash("apple")は、例えば7822464593423736867のような数値を返します。
• バケット (bucket / slot):
  データを格納する箱。通常はただのリスト（配列）です。

hash()関数について
公式ドキュメントにも記載がありますが、Pythonのhash()関数はプロセスの起動ごとに異なるハッシュ値を返すことがあります。

注釈 デフォルトでは、文字列とバイト列の hash() 値は予測不可能なランダム値で "ソルト" されます。 ハッシュ値は単独の Python プロセス内では定数であり続けますが、Python を繰り返し起動する毎に、予測できなくなります。

3. データモデル — Python 3.13.5 ドキュメント

データを格納する流れは非常にシンプルです。

1. 格納したいデータkeyのハッシュ値 hash(key)を計算する。
2. そのハッシュ値を棚の数（テーブルサイズ）で割った余りhash(key) % table_sizeを計算し、格納先のインデックス（棚の番号）を決定する。

"apple" -> hash() -> 7822464593423736867 -> % 10 -> 7  => インデックス7番の棚へ
"banana"-> hash() -> 6606075058235939965 -> % 10 -> 5  => インデックス5番の棚へ

この仕組みのおかげで、データを探すときも同じ計算をすれば一発で「どの棚を見ればよいか」がわかります。これが平均O(1)の速さの源泉なのです。

💥 衝突 (Collision)

しかし、ここで一つの問題が起こります。"cherry"のインデックスを計算したら、たまたま"banana"と同じインデックス5になってしまったら…？

"cherry"-> hash() -> 7001917010569126015 -> % 10 -> 5  => えっ、5番の棚はもう埋まってる！

このように、異なるデータが同じ格納先インデックスになってしまうことを衝突（Collision）と呼びます。この衝突をいかにうまく解決するかが、ハッシュテーブルの性能を左右する鍵となります。今回は、その代表的な解決策であるチェイン法とオープンアドレス法を実装していきます。

ハッシュ値の衝突について

ハッシュ値は衝突しにくいように思えますが、ハッシュテーブルでは衝突が前提となります。
理由は主に2つあります。第一に、ハッシュ関数の出力（ハッシュ値）は有限であるため、入力データが増えれば「鳩の巣原理」により必ず衝突が起こります。第二に、ハッシュテーブルでは「ハッシュ値 % テーブルサイズ」の余りを使うため、テーブルサイズが小さいと衝突はさらに頻発します。

多少の衝突を許容する代わりにテーブルサイズを小さく保つことで、メモリ使用量を抑えるという大きなメリットを得ているのです。

---

3. 衝突解決アルゴリズム①：チェイン法

最初の解決策は「チェイン法」です。これは "同じ棚に入れたいものは、鎖（チェーン）で繋ごう" というアイデアに基づいています。

つまり、ハッシュテーブルの各バケットを、複数のデータを格納できる連結リスト（データを数珠つなぎにした構造）にしてしまうのです。

ハッシュテーブル
[0] -> None
[1] -> None
[2] -> None
[3] -> None
[4] -> None
[5] -> Node("banana") -> Node("cherry")  <-- "banana"と衝突した"cherry"を鎖で繋ぐ
[6] -> None
[7] -> Node("apple")  <-- "apple"は別のバケットに格納
...

実装してみよう

それでは、チェイン法でMySetを実装してみます。まずは連結リストの要素となるNodeクラスを定義します。

class Node:
    """連結リストのノード"""
    def __init__(self, value):
        self.value = value
        self.next: Node | None = None

これを使い、MySetクラスの骨格を作ります。

class MySet:
    """チェイン法で実装したSet"""

    def __init__(self, table_size: int):
        self.table_size = table_size
        self.hash_table: list[Node | None] = [None] * table_size
        self._num_elements = 0

    # ここにメソッドを実装していく

add メソッド (追加)

新しい要素を追加するロジックです。重複がないかチェックした後、連結リストの先頭に新しいノードを追加します。末尾ではなく先頭に追加する方が、リストを最後まで辿る必要がなく実装が簡単です。1行目の重複チェックのように、 in 演算子を使えるように、__contains__ メソッドを実装しておきます。（__contains__ メソッドは次に説明します）

    def add(self, key: str) -> None:
        # 1. 重複チェック
        if key in self:
            return

        # 2. 格納先のインデックスを計算
        index = hash(key) % self.table_size
        new_node = Node(key)

        # 3. 連結リストの先頭に新しいノードを挿入
        current_head = self.hash_table[index]
        new_node.next = current_head
        self.hash_table[index] = new_node
        self._num_elements += 1

__contains__ メソッド (存在確認)

key in my_set のように書けるようにするための特殊メソッドです。対応するバケットの連結リストを先頭から順に辿り、キーが見つかるか試します。

    def __contains__(self, key: str) -> bool:
        index = hash(key) % self.table_size
        current = self.hash_table[index]

        while current:
            if current.value == key:
                return True
            current = current.next

        return False

discard メソッド (削除)

連結リストの操作で最も少し複雑なのが削除です。削除したいノードの一つ手前のノードを見つけ、そのnextポインタを、削除したいノードのnextに繋ぎ変える必要があります。

    def discard(self, key: str) -> None:
        index = hash(key) % self.table_size
        current = self.hash_table[index]
        prev: Node | None = None # 一つ前のノードを追跡

        while current:
            if current.value == key:
                # --- 削除処理 ---
                if prev: # 削除対象がリストの途中か末尾の場合
                    prev.next = current.next
                else:  # 削除対象がリストの先頭の場合
                    self.hash_table[index] = current.next

                self._num_elements -= 1
                return

            prev = current
            current = current.next

これでチェイン法によるSetの基本機能が完成しました！

動作確認

では実際に使ってみましょう。

N = 10  # ハッシュテーブルのサイズ
# MySetのインスタンスを作成
my_set = MySet(N)
# 要素を追加
my_set.add("apple")
my_set.add("banana")
my_set.add("cherry")
# 重複を追加しようとしても何も起きない
my_set.add("apple")  # 何も起きない
# 存在確認
print("apple" in my_set)  # True
print("grape" in my_set)  # False
print("banana" in my_set)  # True
print("cherry" in my_set)  # True
# 要素を削除
my_set.discard("banana")
print("banana" in my_set)  # False


# bananaとcherryはハッシュ値が衝突しているが、問題なく使えた
print(hash("banana") % N)  # 5
print(hash("cherry") % N)  # 5

全体のコードは付録にまとめておきます。

---

4. 衝突解決アルゴリズム②：オープンアドレス法

次の解決策は「オープンアドレス法」です。これは 「指定の棚が埋まっていたら、隣の空いている棚を探そう！」 というアイデアに基づいています。

つまり、衝突が起きたら、ルールに従って別の「空き（Open）」アドレス（Address）を探しにいく方法です。空きスロットを探すことをプロービング (Probing) と呼びます。次の空きスロットをどう定めるか、には色々な種類があります。

• 線形プロービング（Linear Probing）
  • 衝突したら、次のインデックスを順番に見ていく方法。例えば、hash(key) % table_sizeで衝突した場合、次は(hash(key) + 1) % table_size、その次は(hash(key) + 2) % table_sizeといった具合に、1つずつ隣を見ていきます。cf. https://www.geeksforgeeks.org/dsa/implementing-hash-table-open-addressing-linear-probing-cpp/
  • 数式では$N$をテーブルサイズ、$k$を格納したいデータのキー、$h_a(k)$をハッシュ値、$i$をプロービングの回数として、$h(k, i) = (h_a(k) + i) \mod N$ と表せます。
• Quadratic Probing
  • 衝突したら、次のインデックスを飛ばし飛ばしで見る方法。例えば、hash(key) % table_sizeで衝突した場合、次は(hash(key) + 1^2) % table_size、その次は(hash(key) + 2^2) % table_sizeといった具合に、飛ばしていきます。cf. https://www.geeksforgeeks.org/dsa/quadratic-probing-in-hashing/
  • 数式では$h(k, i) = (h_a(k) + i^2) \mod N$ と表せます。
• Double Hashing
  • 衝突したら、別のハッシュ関数を使って次のインデックスを決定する方法。例えば、hash(key) % table_sizeで衝突した場合、次は(hash(key) + hash2(key)) % table_sizeといった具合に、別のハッシュ関数hash2を使います。 cf. https://www.geeksforgeeks.org/dsa/double-hashing/
  • 数式では$h(k, i) = (h_a(k) + i \cdot h_b(k)) \mod N$ と表せます。
    • ここで、$h_b(k)$は別のハッシュ関数です。

プロービングは全てのスロットを一巡できることという条件を満たすべきです。今回は最も簡単な線形プロービング（1つずつ隣を見ていく方法）で実装します。

"banana" -> hash 5
"cherry" -> hash 5 (衝突！)

ハッシュテーブル
...
[4] NIL
[5] "banana"  <-- "cherry"はここに入りたいが埋まっている
[6] NIL      <-- 隣のここが空いているので、"cherry"はここに入る
[7] NIL
...

データがハッシュテーブルに含まれているかどうかを判定する際も、同じようにプロービングを行います。

1. まずハッシュ値を計算し、格納先のインデックスを決定する。
2. そのインデックスが空いているか、すでにデータが格納されているかを確認する。
3. もし空いていれば「そのデータは存在しない」と判断し、探索を終了する。
4. もし探しているデータがそこにあれば「存在する」と判断し、探索を終了する。
5. もしそこに別のデータが格納されていたら、次のインデックス（隣の棚）を見に行き、2から繰り返す。

重要な概念：DELETEDマーカー

オープンアドレス法には一つ、罠があります。それは削除です。

もし"banana"を削除するために、インデックス5の値を単純に空（NIL）にしてしまうとどうなるでしょう？
後から"cherry"を探しに来たとき、本来のインデックス5が空なので、「このセットには"cherry"は存在しない」と勘違いしてしまいます。"cherry"まで辿り着くための道が途切れてしまうのです。

そこで、特別なマーカーを用意します。

• _NIL: 本当に一度も使われていない空きスロット
• _DELETED: データが削除された空きスロット

探索時は、_DELETEDマーカーは「ここに昔何かあったけど、探しているものではない」と判断して探索を続け、_NILマーカーを見つけたら「これ以上先には何もない」と判断して探索を打ち切ります。

実装してみよう

まずは特別なマーカーを、絶対にデータと衝突しないシングルトンオブジェクトとして定義します。

_NIL = object()     # 空のスロット
_DELETED = object() # 削除済みスロット

これを使ってMySetクラスの骨格を作ります。

class MySet:
    """オープンアドレス法で実装したSet"""

    def __init__(self, table_size: int):
        self.table_size = table_size
        self.hash_table: list[str | object] = [_NIL] * table_size
        self._num_elements = 0

    def _linear_probe(self, hash_val: int, index: int) -> int:
        return (hash_val + index) % self.table_size

    # ここにメソッドを実装していく

add メソッド (追加)

プロービングしながら、_NILか_DELETEDのどちらかの空きスロットを見つけたら、そこにデータを挿入します。

    def add(self, key: str) -> None:
        if self._num_elements >= self.table_size:
            raise OverflowError("Hash table is full.")

        hash_val = hash(key)
        for i in range(self.table_size):
            probe_index = self._linear_probe(hash_val, i)
            slot = self.hash_table[probe_index]

            if slot == key: # すでに存在
                return

            if slot is _NIL or slot is _DELETED:
                # 空きスロットを見つけたら挿入
                self.hash_table[probe_index] = key
                self._num_elements += 1
                return

__contains__ メソッド (存在確認)

オープンアドレス法の肝です。_DELETEDは無視して探索を続け、_NILを見つけたら探索を終了します。

    def __contains__(self, key: str) -> bool:
        hash_val = hash(key)
        for i in range(self.table_size):
            probe_index = self._linear_probe(hash_val, i)
            slot = self.hash_table[probe_index]

            if slot == key:
                return True

            if slot is _NIL:
                # 本当の空きスロットに到達したら、キーは存在しない
                return False
            # _DELETEDの場合は探索を続行

        return False

discard メソッド (削除)

キーを見つけたら、そのスロットを_NILにするのではなく、_DELETEDマーカーで上書きします。

    def discard(self, key: str) -> None:
        hash_val = hash(key)
        for i in range(self.table_size):
            probe_index = self._linear_probe(hash_val, i)
            slot = self.hash_table[probe_index]

            if slot == key:
                self.hash_table[probe_index] = _DELETED
                self._num_elements -= 1
                return

            if slot is _NIL:
                # 探しているキーがないことが確定
                return

オープンアドレス法によるSetも完成です！なお、オープンアドレス法では、ハッシュテーブルが高負荷状態になると、性能が急激に劣化するという特性があります。これは、空きスロットを探すのに時間がかかるためです。そのため、実際のアプリケーションでは、テーブルサイズを動的に設定し、負荷が高くなりすぎないようにすることが一般的です。

動作確認

では実際に使ってみましょう。

N = 10  # ハッシュテーブルのサイズ
# MySetのインスタンスを作成
my_set = MySet(N)
# 要素を追加
my_set.add("apple")
my_set.add("banana")
my_set.add("cherry")
# 重複を追加しようとしても何も起きない
my_set.add("apple")  # 何も起きない
# 存在確認
print("apple" in my_set)  # True
print("grape" in my_set)  # False
print("banana" in my_set)  # True
print("cherry" in my_set)  # True
# 要素を削除
my_set.discard("banana")
print("banana" in my_set)  # False

全体のコードは付録にまとめておきます。

---

5. 2つの方法の比較

どちらの方法にも一長一短があります。

観点	チェイン法	オープンアドレス法
メモリ	ノードのポインタ分のオーバーヘッドがある	ポインタが不要で省メモリ
削除	実装が比較的シンプル	DELETEDマーカーの管理が必要で複雑
キャッシュ	データがメモリ上に散らばりがちで、キャッシュ効率が悪い場合がある	データがリストにまとまっており、キャッシュ効率が良い傾向がある
性能劣化	負荷が高くなっても性能劣化は比較的緩やか	負荷が高くなると空きスロット探しに時間がかかり急激に性能が劣化する

どちらが良いかはケースバイケースですが、このようなトレードオフを理解しておくことが重要です。

---

6. まとめと次のステップ

今回は、Pythonのsetをフルスクラッチで実装しました。

• チェイン法: 衝突したデータを連結リストで繋いで解決。
• オープンアドレス法: 衝突したら別の空きスロットを探して解決。

set（ハッシュテーブル）が巧妙なデータ構造とアルゴリズムの上に成り立っていることを感じていただけたなら幸いです。

しかし、本物のPythonのsetは、ここで実装したものよりもっと賢く、もっと高性能です。

例えばCPythonのsetではオープンアドレス法が使われていて、テーブルがいっぱいになったら自動的にリサイズしたり、プロービングの戦略を工夫したりと、数々の最適化が施された実装になっています（リサイズをした場合でも、ならした平均時間計算量はO(1)になるように工夫されています）。興味がある方は https://github.com/python/cpython/blob/main/Objects/setobject.c をぜひ覗いてみてください。

余裕があればCythonのソースコードを読み解く記事も書いてみたいと思います。

7. 付録

参考リンク

• Hash Table Data Structure - GeeksforGeeks
• Python で学ぶハッシュ探索法 - チェーン法とオープンアドレス法 -
• Pythonのハッシュ衝突攻撃の考察2: 辞書のキー検索を故意に衝突させられました 競技プログラミング - Qiita
• Pythonでハッシュ法（オープンアドレス法） algorithm - Qiita

ソースコード全体

1. チェイン法の実装

class Node:
    """連結リストのノード"""
    def __init__(self, value):
        self.value = value
        self.next: Node | None = None
class MySet:
    """チェイン法で実装したSet"""
    def __init__(self, table_size: int):
        self.table_size = table_size
        self.hash_table: list[Node | None] = [None] * table_size
        self._num_elements = 0
    def add(self, key: str) -> None:
        if key in self:
            return
        index = hash(key) % self.table_size
        new_node = Node(key)
        current_head = self.hash_table[index]
        new_node.next = current_head
        self.hash_table[index] = new_node
        self._num_elements += 1
    def __contains__(self, key: str) -> bool:
        index = hash(key) % self.table_size
        current = self.hash_table[index]
        while current:
            if current.value == key:
                return True
            current = current.next
        return False
    def discard(self, key: str) -> None:
        index = hash(key) % self.table_size
        current = self.hash_table[index]
        prev: Node | None = None
        while current:
            if current.value == key:
                if prev:
                    prev.next = current.next
                else:
                    self.hash_table[index] = current.next
                self._num_elements -= 1
                return
            prev = current
            current = current.next

1. オープンアドレス法の実装

_NIL = object()     # 空のスロット
_DELETED = object() # 削除済みスロット

class MySet:
    """オープンアドレス法で実装したSet"""

    def __init__(self, table_size: int = 11):
        self.table_size = table_size
        self.hash_table: list[str | object] = [_NIL] * table_size
        self._num_elements = 0

    def _linear_probe(self, hash_val: int, index: int) -> int:
        return (hash_val + index) % self.table_size

    def add(self, key: str) -> None:
        if self._num_elements >= self.table_size:
            raise OverflowError("Hash table is full.")
        hash_val = hash(key)
        for i in range(self.table_size):
            probe_index = self._linear_probe(hash_val, i)
            slot = self.hash_table[probe_index]
            if slot == key:
                return
            if slot is _NIL or slot is _DELETED:
                self.hash_table[probe_index] = key
                self._num_elements += 1
                return

    def __contains__(self, key: str) -> bool:
        hash_val = hash(key)
        for i in range(self.table_size):
            probe_index = self._linear_probe(hash_val, i)
            slot = self.hash_table[probe_index]
            if slot == key:
                return True
            if slot is _NIL:
                return False
        return False

    def discard(self, key: str) -> None:
        hash_val = hash(key)
        for i in range(self.table_size):
            probe_index = self._linear_probe(hash_val, i)
            slot = self.hash_table[probe_index]
            if slot == key:
                self.hash_table[probe_index] = _DELETED
                self._num_elements -= 1
                return
            if slot is _NIL:
                return