組み込みライブラリを使わずにPythonでHashSet（ハッシュセット）を実装する方法

本記事では、Pythonの組み込みハッシュテーブルライブラリを使用せずに、HashSet（ハッシュセット）データ構造をゼロから設計・実装する方法を解説します。実装すべき主な操作は以下の3つです。

• add(x) ― 値 x をHashSetに挿入します
• contains(x) ― 値 x がHashSetに存在するかどうかを判定します
• remove(x) ― 値 x をHashSetから削除します。値が存在しない場合は何もしません

動作確認のシナリオ

まずHashSetを初期化し、その後 add(1) → add(3) → contains(1) → contains(2) → add(2) → contains(2) → remove(2) → contains(2) の順に呼び出してテストします。期待される出力は次のとおりです。

• contains(1) → True（1は存在する）
• contains(2) → False（2はまだ存在しない）
• add(2)後の contains(2) → True（2は存在する）
• remove(2)後の contains(2) → False（2は削除された）

設計のアプローチ

この問題を解くためには、「バケット方式」と呼ばれる手法を用います。大きな配列（ハッシュテーブル）を用意し、キーをハッシュ関数で振り分けることで、各バケット内に格納される要素数を抑えられます。具体的な手順は以下のとおりです。

1. Bucketクラスの定義

• bucket として新しいリストを初期化します

update(key) メソッド：

• found := False として初期化
• bucket内の各インデックス i と要素 k について走査し、key と k が一致すれば bucket[i] = key として found を True に設定しループを抜けます
• 見つからなかった場合は、bucketの末尾に key を追加します

get(key) メソッド：

• bucket内の各要素 k を走査し、k が key と一致すれば True を返します
• 最後まで一致しなければ False を返します

remove(key) メソッド：

• bucket内の各インデックス i と要素 k を走査し、key と一致したら del bucket[i] で削除します

2. MyHashSetクラスの定義

• key_space := 2096（バケットの総数）
• hash_table として、Bucketオブジェクトを key_space 個格納したリストを作成します

add(key) メソッド：

• hash_key = key % key_space でハッシュ値を計算
• hash_table[hash_key] の update(key) を呼び出します

remove(key) メソッド：

• hash_key = key % key_space でハッシュ値を計算
• hash_table[hash_key] から key を削除します

contains(key) メソッド：

• hash_key = key % key_space でハッシュ値を計算
• hash_table[hash_key] の get(key) の結果を返します

実装例

それでは、実際のコードを見てみましょう。

class Bucket:
    def __init__(self):
        self.bucket=[]
    def update(self, key):
        found=False
        for i,k in enumerate(self.bucket):
            if key==k:
                self.bucket[i]=key
                found=True
                break
        if not found:
            self.bucket.append(key)
    def get(self, key):
        for k in self.bucket:
            if k==key:
                return True
        return False
    def remove(self, key):
        for i,k in enumerate(self.bucket):
            if key==k:
                del self.bucket[i]
class MyHashSet:
    def __init__(self):
        self.key_space = 2096
        self.hash_table=[Bucket() for i in range(self.key_space)]
    def add(self, key):
        hash_key=key%self.key_space
        self.hash_table[hash_key].update(key)
    def remove(self, key):
        hash_key=key%self.key_space
        self.hash_table[hash_key].remove(key)
    def contains(self, key):
        hash_key=key%self.key_space
        return self.hash_table[hash_key].get(key)
ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

入力

ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

出力

True
False
True
False

まとめ

この実装では、モジュロ演算（剰余計算）による単純なハッシュ関数を使ってキーを2096個のバケットに振り分けています。これにより、各バケットに含まれる要素数が平均的に少なくなり、検索・挿入・削除の処理を高速に行えます。ハッシュの衝突が起きても、バケット内部では線形探索によって正しく処理されるため、HashSetとして必要な機能をすべて満たしています。