ハッシュセットをPythonで実装する #445
ハッシュセットは集合の中から要素を高速に検索するためのデータ構造です。既存のライブラリは色々あると思いますが、理解のため自作してみます。
ハッシュテーブルとは
まず、元となるデータ構造であるハッシュテーブルに関してです。
ハッシュテーブルは、キーと値のペアを格納するためのデータ構造で、任意のキーに対して値を迅速に検索、追加、削除することができます。Pythonのdict型はハッシュテーブルの一種で、イメージしやすいと思います。
ハッシュテーブルは、ハッシュ関数を使用して、各キーをデータ構造内の位置（通常は配列のインデックス）にマッピングします。このハッシュ関数によって計算された位置にデータ（キーと値のペア）が格納されます。
ハッシュテーブルの実装では、ハッシュ関数によって同じ位置にマッピングされる異なるキー（衝突と呼ばれる）を扱うための方法が必要です。一般的な衝突解決策には、チェーン法（リンクリストやリストのリストを使用）やオープンアドレッシング（衝突が発生した場合に別の位置を見つける）があります。
ハッシュセットとは
ハッシュセットは、ハッシュテーブルの特殊なケースで、値ではなくキーのみを格納します。キーというとややこしいですが、Pythonのset型のようなイメージです。ただしハッシュテーブルと同じ原理（ハッシュ関数と衝突解決策）を使用してキー（要素）の存在を効率的に管理します。
つまりハッシュセットは、キー（要素）が存在するかどうかを迅速にチェックするために使用されるデータ構造です。
具体的なコード例
まず、要素を追加、削除、検索するだけのクラスを書いてみます。ハッシュ関数は使っておらず、この後やりたいことを理解するためのものです。
class MyHashSet:
def __init__(self):
self.set = []
def add(self, key: int) -> None:
if key not in self.set:
self.set.append(key)
def remove(self, key: int) -> None:
if key in self.set:
self.set.remove(key)
def contains(self, key: int) -> bool:
if key in self.set:
return True
return False
leetcodeのテストケースをこれで実行すると、Runtime: 730 msでした
ではいよいよハッシュ関数を使ってハッシュセットを定義してみます。
上記で触れたうちチェーン法を採用しています。
class MyHashSet:
def __init__(self, capacity=1000):
# バケットの初期化（チェーン法で衝突を解決するためのリストのリスト）
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def hash(self, key: int) -> int:
# シンプルなハッシュ関数：キーをバケット数で割った余り
return key % self.capacity
def add(self, key: int) -> None:
# キーに対応するバケットを決定
bucket_index = self.hash(key)
bucket = self.buckets[bucket_index]
if key not in bucket:
# キーがまだバケットになければ追加
bucket.append(key)
def remove(self, key: int) -> None:
bucket_index = self.hash(key)
bucket = self.buckets[bucket_index]
if key in bucket:
# キーがバケットにあれば削除
bucket.remove(key)
def contains(self, key: int) -> bool:
bucket_index = self.hash(key)
bucket = self.buckets[bucket_index]
# キーがバケットにあればTrue
return key in bucket以下の手順になっています。
初期化時にバケット（配列の中の配列を持つ）を1000個作る
シンプルなハッシュ関数でキーごとのハッシュ値を返す
self.buckects[ハッシュ値]で指定するbucketにキーを保存する
最初の実装では、keyを検索する時に常にself.setをフルスキャンしていました。しかしハッシュセットでは、self.buckects[ハッシュ値]で指定したbucketのみスキャンするので、フルスキャンするより高速になります。
leetcodeの同じテストケースを実行するとRuntime: 105 msとなり、先ほどの7分の1になりました。
びっくりするくらい速いですね。
ここまでお読みいただきありがとうございました！！