ハッシュ衝突の解決法（チェイン法、オープンアドレス法）

ハッシュテーブルを使用する際、同じインデックスに複数の要素がハッシュされることがあります。これをハッシュ衝突と言います。ハッシュ衝突を解決するための主な方法として、チェイン法とオープンアドレス法があります。以下では、これらの手法について説明し、それぞれの実装をPythonで行います。

チェイン法

チェイン法は、ハッシュ衝突が発生した場合に、同じインデックスにリスト（または別のデータ構造）を用いて複数の値を格納する手法です。具体的には、ハッシュテーブルの各インデックスに、衝突した要素を格納するためのリストを持たせます。

チェイン法の実装

以下は、チェイン法を用いたハッシュテーブルの実装例です。

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        # 既存のキーがある場合は更新
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        # 新たに挿入
        self.table[index].append((key, value))

    def search(self, key):
        index = self.hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self.hash_function(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return True
        return False

# 実行例
hash_table = HashTable(10)
hash_table.insert("apple", 10)
hash_table.insert("banana", 20)
hash_table.insert("apple", 30)  # appleの値を更新
print(hash_table.search("apple"))  # 30
print(hash_table.search("banana"))  # 20
hash_table.delete("apple")
print(hash_table.search("apple"))  # None

コードの解説

1. 初期化 (__init__ メソッド):

   • size はハッシュテーブルのサイズを指定します。
   • table はサイズに基づいて空のリストで初期化されます。このリストはハッシュテーブルの各バケットを表します。

2. ハッシュ関数 (hash_function メソッド):

   • Pythonの組み込み hash 関数を使い、キーをハッシュ化し、テーブルのサイズで割った余りを返します。

3. 挿入 (insert メソッド):

   • 指定された key と value をテーブルに挿入します。既に存在するキーがあれば、その値を更新します。

4. 検索 (search メソッド):

   • 指定された key に対応する value を検索します。見つからなければ None を返します。

5. 削除 (delete メソッド):

   • 指定された key を持つ要素を削除します。成功すれば True を返し、見つからなければ False を返します。

オープンアドレス法

オープンアドレス法は、ハッシュ衝突が発生した場合、空いている別のインデックスを探して要素を格納する手法です。この方法では、全ての要素はハッシュテーブル内の配列に格納され、衝突が発生した際には、次の空いているインデックスを線形に探します。

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

以下は、オープンアドレス法を用いたハッシュテーブルの実装例です。

class OpenAddressingHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:  # 更新
                self.table[index] = (key, value)
                return
            index = (index + 1) % self.size  # 次のインデックスへ
            if index == original_index:  # 一周したら終了
                raise Exception("Hash table is full")
        self.table[index] = (key, value)

    def search(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                return self.table[index][1]
            index = (index + 1) % self.size
            if index == original_index:  # 一周したら終了
                break
        return None

    def delete(self, key):
        index = self.hash_function(key)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == key:
                self.table[index] = None  # 削除
                return True
            index = (index + 1) % self.size
            if index == original_index:  # 一周したら終了
                break
        return False

# 実行例
hash_table = OpenAddressingHashTable(10)
hash_table.insert("apple", 10)
hash_table.insert("banana", 20)
hash_table.insert("apple", 30)  # appleの値を更新
print(hash_table.search("apple"))  # 30
print(hash_table.search("banana"))  # 20
hash_table.delete("apple")
print(hash_table.search("apple"))  # None

コードの解説

1. 初期化 (__init__ メソッド):

   • size はハッシュテーブルのサイズを指定し、table は None で初期化された配列を持ちます。

2. ハッシュ関数 (hash_function メソッド):

   • チェイン法と同様に、ハッシュ値を計算します。

3. 挿入 (insert メソッド):

   • インデックスが空いている間、次のインデックスを探索し、見つかれば要素を挿入します。すでに存在するキーがあれば更新します。テーブルが満杯の場合は例外を発生させます。

4. 検索 (search メソッド):

   • 指定された key に対応する value を探します。見つからなければ None を返します。

5. 削除 (delete メソッド):

   • 指定された key を持つ要素を削除します。削除されたインデックスは None になります。

まとめ

ハッシュ衝突の解決法として、チェイン法とオープンアドレス法を紹介しました。チェイン法は各インデックスにリストを持たせることで衝突を解決し、オープンアドレス法は空いているインデックスを探して要素を格納します。それぞれの手法には利点と欠点があり、用途に応じて使い分けることが重要です。