では、Pythonで「ハッシュ衝突（シノニム）を処理する方法」として、
以下の2つの方法を簡単なコード付きで紹介します：
✅ 方法①：チェイン法（Separate Chaining）
各ハッシュ値のバケットに「リスト（複数のデータ）」を持たせる方式です。
● 実装例：
class HashTableChaining: def __init__(self, size=10): self.size = size self.table = [[] for _ in range(size)] def _hash(self, key): return hash(key) % self.size def insert(self, key, value): index = self._hash(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(key) for k, v in self.table[index]: if k == key: return v return None def delete(self, key): index = self._hash(key) self.table[index] = [(k, v) for k, v in self.table[index] if k != key]
● 使用例：
ht = HashTableChaining()ht.insert("apple", 10)ht.insert("banana", 20)ht.insert("orange", 30)# シノニムを意図的に起こす（衝突するキーを作るのは難しいが、強制的に検証することも可能）print(ht.search("banana")) # → 20ht.delete("banana")print(ht.search("banana")) # → None
✅ 方法②：オープンアドレス法（線形探索）
空いている次のスロットを探してデータを格納します。
● 実装例：
class HashTableOpenAddressing: def __init__(self, size=10): self.size = size self.table = [None] * size def _hash(self, key): return hash(key) % self.size def insert(self, key, value): index = self._hash(key) for i in range(self.size): idx = (index + i) % self.size if self.table[idx] is None or self.table[idx][0] == key: self.table[idx] = (key, value) return raise Exception("Hash table is full") def search(self, key): index = self._hash(key) for i in range(self.size): idx = (index + i) % self.size if self.table[idx] is None: return None if self.table[idx][0] == key: return self.table[idx][1] return None def delete(self, key): index = self._hash(key) for i in range(self.size): idx = (index + i) % self.size if self.table[idx] is None: return if self.table[idx][0] == key: self.table[idx] = ("<DELETED>", None) # 削除フラグ return
✅ 違いのまとめ：
| 方式 | 特徴 | メモ |
|---|
| チェイン法 | 各バケットにリスト | リストが長くなってもOK |
| オープンアドレス法 | 空き場所を探して格納 | 配列サイズが限界になると挿入失敗 |
この記事へのコメント