ハッシュテーブルのしくみ

6.1 ハッシュテーブルの定義とその構造

ハッシュテーブルは、配列またはリスト内のインデックスを計算するためにハッシュ関数を使用して、要素を迅速に検索、挿入、および削除する機能を提供するデータ構造ですよ。ハッシュテーブルは通常、ディクショナリとも知られる連想配列を実現するために使用されます。

ハッシュテーブルの重要な側面

配列は、ハッシュテーブルの主要な要素で、要素または要素リストへのポインタを保持します。

ハッシュ関数: ディクショナリのキーを配列のインデックスに変換します。

衝突: 異なる2つのキーが同じハッシュ値を持つ状況。衝突を解決するために、チェイニングやオープンアドレッシングなどのさまざまな方法が使用されます。

ディクショナリの例:

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

ハッシュテーブルの構造の例:

6.2 ハッシュテーブルにおける基本操作

ハッシュテーブルの基本操作は、挿入、検索、削除だよ。

1. 挿入 (Insertion): ハッシュテーブルに新しい要素（キーと値のペア）を追加するプロセスです。

挿入の手順:

1. キーのハッシュ値をハッシュ関数によって計算します。
2. ハッシュ値に基づいて配列のインデックスを探します。
3. そのインデックスにすでに要素がある場合（衝突）、リストに要素を追加する（チェイニングの場合）か、次の使用可能なインデックスを探します（オープンアドレッシングの場合）。

チェイニングを使用したハッシュテーブルへの挿入の例:

class HashTable:
    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))

# 使用例:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. 検索 (Search): ハッシュテーブルで指定されたキーに基づいて値を見つけるプロセスです。

検索の手順:

1. キーのハッシュ値をハッシュ関数によって計算します。
2. ハッシュ値に基づいて配列のインデックスを探します。
3. キーのリスト内での存在を確認する（チェイニングの場合）か、インデックスで確認する（オープンアドレッシングの場合）。

チェイニングを使用したハッシュテーブルでの検索の例:

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

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

    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

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

3. 削除 (Deletion): ハッシュテーブルから要素（キーと値のペア）を削除するプロセスです。

削除の手順:

1. キーのハッシュ値をハッシュ関数によって計算します。
2. ハッシュ値に基づいて配列のインデックスを探します。
3. リストから要素を削除する（チェイニングの場合）か、インデックスの値をNoneに設定する（オープンアドレッシングの場合）。

チェイニングを使用したハッシュテーブルからの削除の例:

class HashTable:
    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 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 = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # 出力: None

6.3 ハッシュテーブルの時間計算量

ハッシュテーブルの操作の時間計算量。

挿入 (Insertion):

• 平均ケース: O(1)
• 最悪ケース: O(n)（大量の衝突がある場合やすべての要素が同じ場所に入る場合）

検索 (Search):

• 平均ケース: O(1)
• 最悪ケース: O(n)（大量の衝突がある場合やすべての要素が同じ場所に入る場合）

削除 (Deletion):

• 平均ケース: O(1)
• 最悪ケース: O(n)（大量の衝突がある場合やすべての要素が同じ場所に入る場合）

説明:

平均ケース: 平均的なケースでは、ハッシュ関数が要素を均等にテーブルに分布させ、各要素がユニークなセルにあるため、一定のアクセス時間O(1)を保証します。

最悪ケース: 最悪のケースでは、すべての要素が1つのセルに入るか、悪いハッシュ関数や大量の衝突のため、リンクリストに変わり、操作の時間計算量がO(n)になります。

6.4 ハッシュテーブルの利用例

1. ディクショナリ（連想配列）の実装

ハッシュテーブルは、キーと値のペアを保存し、キーに基づいて迅速なアクセスを提供するディクショナリの実装によく使用されます。

例:

# ディクショナリの作成
dictionary = {}

# 要素の挿入
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# 要素の検索
print(dictionary["banana"])  # 出力: 2

# 要素の削除
del dictionary["cherry"]

# キーの存在確認
if "apple" in dictionary:
    print("キー'apple'がディクショナリに存在します")  # 出力: キー'apple'がディクショナリに存在します

これで、Pythonのディクショナリとその仕組みについて少し詳しくなりました。

2. 計算結果のキャッシュ

ハッシュテーブルは、計算結果をキャッシュして後続の要求を高速化するために使用されます。

例:

# キャッシュに結果を保存
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # コストの高い計算の例
    cache[x] = result
    return result

# キャッシュの使用
print(expensive_computation(10))  # 出力: 100（計算とキャッシュ）
print(expensive_computation(10))  # 出力: 100（キャッシュから）

3. テキスト内の単語の頻度カウント

ハッシュテーブルは、テキスト内の単語の出現頻度をカウントするために使用されます。

例:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# 結果の出力
for word, count in word_count.items():
    print(f"単語 '{word}' は {count} 回出現します")

4. リスト内の重複の検出

ハッシュテーブルは、リスト内の重複を効率的に見つけるために使用されます。

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用例
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 出力: [2, 4]