衝突の問題とその解決方法

7.1 ハッシュテーブルにおける衝突の定義

ハッシュテーブルにおける衝突は、2つの異なるキーが同じ配列のインデックスにハッシュされるときに発生するよ。この結果、複数の要素が同じセルを占めようとするんだ。

衝突の例:

例えば、キーをテーブルのサイズで割った余りを返す単純なハッシュ関数があるとしよう。テーブルサイズが10のとき、キー5と15は同じインデックスを持つことになる: 5 % 10 = 5 と 15 % 10 = 5。これが衝突だよ。

さらに例を挙げると:

名前の辞書を作るとして、最初の文字を返す簡単なハッシュ関数があるとしよう。でも、80%の名前が「A」で始まるとしたら、これは単なる衝突ではなく問題だね。

7.2 衝突解決法 - チェーン法

ハッシュテーブルの衝突解決にはいくつかの方法があるんだ。最も一般的な方法2つは、チェーン法 (chaining) とオープンアドレッシング (open addressing) だよ。

チェーン法 (Chaining)

メリット:

• 実装が簡単。
• 衝突が少ない場合の効率性。
• ハッシュテーブルの密度にあまり依存しない。

デメリット:

• 連結リストのポインタ用メモリが追加で必要。
• 長いチェーンが多くなるとパフォーマンスが低下するかも。

チェーン法の実装例:

insert関数の動作特徴だけを学ぶつもりかも知れないけど、利便性のために全部のコードを載せておくよ。

class HashTableChaining:
    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)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                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)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

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

# 使用例:
hash_table = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 出力: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # 出力: None

7.3 メソッド2 – オープンアドレッシング

オープンアドレッシング法は、衝突が起きたら次に利用可能な配列セルを探すという方法だよ。新しいセルの探し方には、線形探索法、二次探索法、ダブルハッシングがあるんだ。

メリット:

• ポインタ記憶用のメモリが必要ない。
• データがよりコンパクトに表現できる。

デメリット:

• テーブルの密度が高いとパフォーマンスが著しく低下する可能性がある。
• 衝突解決に計算リソースがより多く必要。

オープンアドレッシング法の戦略例

線形探索法 (Linear Probing):

• ステップ1での探索: index = (index + 1) % size.
• 簡単だけど「クラスタリング」を引き起こす可能性がある。

二次探索法 (Quadratic Probing):

• 二乗ステップでの探索: index = (index + i^2) % size.
• クラスタリング問題を軽減するが実装が複雑。

ダブルハッシング (Double Hashing):

• 2つ目のハッシュ関数を使ってステップ計算: index = (index + i * hash2(key)) % size.
• クラスタリング問題が少なくなるが実装が複雑。

オープンアドレッシング法の実装例（線形探索法）: シンプルにするためにinsertの動作だけ学んでみて

class HashTableOpenAddressing:
    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
            index = (index + 1) % self.size
            if index == original_index:
                break

# 使用例:
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # 出力: 2
hash_table.delete("banana")
print(hash_table.search("banana"))  # 出力: None

7.4 ハッシュテーブルへの衝突の影響

衝突がパフォーマンスに与える影響。

平均アクセス時間:

• 理想的な条件(衝突なし)では、ハッシュテーブルでの平均アクセス時間はO(1)。
• 衝突はアクセス時間を増やし、チェーンやセル探索の処理が必要になるため操作数が増える。

チェーンの長さの増加:

• チェーン法では、多くの衝突でチェーンが長くなると、検索と挿入と削除操作の時間がO(n)になることがある。
• 長いチェーンは、要素の検索や挿入に必要な比較回数を増やす。

空間的複雑性:

• チェーン法では、連結リストのポインタを格納するための追加メモリが必要。
• オープンアドレッシング法では、テーブルが一定レベル(通常70-80%)を超えて埋まると、衝突が大幅に増え、アクセス時間が増加。

クラスタリング: オープンアドレッシング法（特に線形探索法）では、連続したセルが埋まることでクラスタリングが発生し、衝突の可能性が高まりパフォーマンスが悪化。

衝突がパフォーマンスに与える影響の分析例:

これが好きな人向けのちょっと深いところだよ

import time
import random

# 線形探索法
class HashTableOpenAddressing:
    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

# 大量のデータを挿入するための生成
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]

# データの挿入と時間計測
start_time = time.time()
for key in keys:
    hash_table.insert(key, key)
print(f"挿入時間: {time.time() - start_time:.6f} 秒")

# データの検索と時間計測
start_time = time.time()
for key in keys:
    hash_table.search(key)
print(f"検索時間: {time.time() - start_time:.6f} 秒")