ハッシュテーブル (Hash Table)とは
ハッシュテーブル とは、
です。
ハッシュテーブルは、キーをハッシュ関数で処理し、得られたハッシュ値を使ってデータを格納・検索します。
キーのハッシュ化
キーをハッシュ関数に入力し、配列のインデックス(固定サイズのハッシュ値)に変換します。
理想的なハッシュ関数は、異なるキーに対して均等にハッシュ値を分散させ、衝突（同じハッシュ値を持つ異なるキー）が最小になるように設計されています。
値の格納
ハッシュ化されたキーを配列のインデックスとして、ペアが格納されます。
検索
検索時も同じハッシュ関数を使用してインデックスを計算します。
計算されたインデックスの位置に直接アクセスし、データを取得します。
衝突（Collision）とその解決
異なるキーが同じハッシュ値を生成することがあり、これを衝突と呼びます。
衝突の解決には主に2つの方法があります
チェイン法（Separate Chaining）
値の格納時にlinked listのデータ構造を使用します。
衝突が発生した場合、同じバケット内にリストとして要素を追加します。
[0] -> ("key1", value1) -> ("key2", value2)
[1] -> ("key3", value3)
[2] -> ("key4", value4) -> ("key5", value5)
オープンアドレス法（Open Addressing）
衝突が発生した場合、別の空きスロットを探します。
hash("key1") = 2 → [2] に格納
hash("key2") = 2 → [2] は埋まっているので [3] に格納
hash("key3") = 2 → [2], [3] は埋まっているので [4] に格納
空きスロットの探し方は、線形探索、二次探索、ダブルハッシングなどの方法があります。
特徴
長所
短所
用途
実装(Python)
実装
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def hash_function(self, key):
# キーの文字コードの合計をサイズで割った余りをハッシュ関数として使用
return sum(ord(char) for char in key) % self.size
def insert(self, key, value):
# ハッシュ値を計算し、対応するバケットにキーと値のペアを追加
hash_index = self.hash_function(key)
bucket = self.table[hash_index]
# 同じキーが既に存在する場合は値を更新
for i, kv in enumerate(bucket):
k, v = kv
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
# ハッシュ値を計算し、対応するバケットから値を検索
hash_index = self.hash_function(key)
bucket = self.table[hash_index]
for k, v in bucket:
if k == key:
return v
return None
# ハッシュテーブルの使用例
ht = HashTable()
# 値の挿入
ht.insert("apple", "赤")
ht.insert("banana", "黄")
ht.insert("orange", "橙")
# 値の取得
print(ht.get("apple")) # 出力: "赤"
print(ht.get("banana")) # 出力: "黄"
print(ht.get("orange")) # 出力: "橙"
# ハッシュテーブルの内容を表示
print(ht.table) # 出力: ハッシュテーブルの内部構造を表示赤
黄
橙
[[('apple', '赤')], [], [], [], [], [], [('orange', '橙')], [], [], [('banana', '黄')]]
ハッシュテーブルのライブラリ
Pythonにはdictとしてハッシュテーブルが標準ライブラリに含まれています。
dictを使用するとハッシュテーブルがより簡潔に実装できます。
table = dict()
# 値の挿入
table["apple"] = "赤"
table["banana"] = "黄"
table["orange"] = "橙"
# 値の取得
print(table["apple"]) # 出力: "赤"
print(table["banana"]) # 出力: "黄"
print(table["orange"]) # 出力: "橙"
# dictの内容を表示
print(table)赤
黄
橙
{'apple': '赤', 'banana': '黄', 'orange': '橙'}
参考文献
コメント