ハッシュテーブル#
ハッシュテーブル（Hash Table） は、キーと値のペアを格納するデータ構造
（例：Pythonのdict）
ハッシュ関数でキーをインデックスに変換し、配列に値を格納することで高速なアクセスを実現する
特徴：
検索・挿入・削除の平均計算量は \(O(1)\)
ハッシュ衝突が発生すると最悪 \(O(n)\) になる
キーの順序は保持されない
操作：
insert(key, value): キーと値のペアを挿入するsearch(key): キーに対応する値を返すdelete(key): キーに対応するエントリを削除する
ハッシュ関数#
ハッシュ関数はキーを受け取り、配列のインデックスを返す関数
良いハッシュ関数の条件：
決定性: 同じキーには常に同じハッシュ値を返す
一様分布: ハッシュ値が均一に分散される
高速計算: 計算コストが低い
最もシンプルな例として、整数キーに対する除算法（Division Method）がある：
\(m\) はハッシュテーブルのサイズ（素数が望ましい）
衝突（コリジョン）#
異なるキーが同じハッシュ値を持つことを 衝突（collision） という
衝突の解決策：
方法 |
概要 |
長所 |
短所 |
|---|---|---|---|
チェイン法 |
同じインデックスの要素をリストで管理 |
実装が簡単、負荷率に柔軟 |
キャッシュ効率が低い |
オープンアドレス法 |
空きスロットを探して格納 |
キャッシュ効率が良い |
負荷率が高いと性能劣化 |
チェイン法による実装#
class HashTableChaining:
def __init__(self, size=11):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
idx = self._hash(key)
for i, (k, _) in enumerate(self.table[idx]):
if k == key:
self.table[idx][i] = (key, value) # 上書き
return
self.table[idx].append((key, value))
def search(self, key):
idx = self._hash(key)
for k, v in self.table[idx]:
if k == key:
return v
raise KeyError(key)
def delete(self, key):
idx = self._hash(key)
self.table[idx] = [(k, v) for k, v in self.table[idx] if k != key]
def __repr__(self):
return "\n".join(f"[{i}]: {chain}" for i, chain in enumerate(self.table) if chain)
ht = HashTableChaining()
ht.insert("apple", 100)
ht.insert("banana", 200)
ht.insert("cherry", 300)
ht.insert("apple", 150) # 上書き
print("apple ->", ht.search("apple"))
print("banana ->", ht.search("banana"))
ht.delete("banana")
print("\nbanana削除後のテーブル:")
print(ht)
apple -> 150
banana -> 200
banana削除後のテーブル:
[5]: [('apple', 150)]
[9]: [('cherry', 300)]
オープンアドレス法（線形探索）による実装#
衝突時に次の空きスロットを線形にたどる方法（Linear Probing）
\(i\) は探索回数、\(h'\) は補助ハッシュ関数
クラスタリング（連続した埋まりスロット）が発生しやすいため、二次探索（Quadratic Probing）やダブルハッシングが代替として使われる
_DELETED = object() # 削除済みスロットのセンチネル
class HashTableOpenAddressing:
def __init__(self, size=11):
self.size = size
self.table = [None] * size
self.count = 0
def _hash(self, key):
return hash(key) % self.size
def _probe(self, key):
idx = self._hash(key)
for i in range(self.size):
yield (idx + i) % self.size
def insert(self, key, value):
if self.count / self.size > 0.7:
raise RuntimeError("負荷率が高すぎます。リサイズが必要です。")
for idx in self._probe(key):
slot = self.table[idx]
if slot is None or slot is _DELETED:
self.table[idx] = (key, value)
self.count += 1
return
if slot[0] == key:
self.table[idx] = (key, value) # 上書き
return
raise RuntimeError("テーブルが満杯です")
def search(self, key):
for idx in self._probe(key):
slot = self.table[idx]
if slot is None:
raise KeyError(key)
if slot is not _DELETED and slot[0] == key:
return slot[1]
raise KeyError(key)
def delete(self, key):
for idx in self._probe(key):
slot = self.table[idx]
if slot is None:
raise KeyError(key)
if slot is not _DELETED and slot[0] == key:
self.table[idx] = _DELETED
self.count -= 1
return
raise KeyError(key)
def __repr__(self):
rows = []
for i, slot in enumerate(self.table):
if slot is None:
label = "None"
elif slot is _DELETED:
label = "<deleted>"
else:
label = str(slot)
rows.append(f"[{i:2d}]: {label}")
return "\n".join(rows)
ht2 = HashTableOpenAddressing()
ht2.insert("apple", 100)
ht2.insert("banana", 200)
ht2.insert("cherry", 300)
print("apple ->", ht2.search("apple"))
ht2.delete("banana")
print("\nbanana削除後:")
print(ht2)
apple -> 100
banana削除後:
[ 0]: <deleted>
[ 1]: None
[ 2]: None
[ 3]: None
[ 4]: None
[ 5]: ('apple', 100)
[ 6]: None
[ 7]: None
[ 8]: None
[ 9]: ('cherry', 300)
[10]: None
計算量まとめ#
負荷率 \(\alpha = n / m\)（\(n\): 要素数, \(m\): テーブルサイズ）
操作 |
平均 |
最悪 |
|---|---|---|
検索 |
\(O(1 + \alpha)\) |
\(O(n)\) |
挿入 |
\(O(1)\) |
\(O(n)\) |
削除 |
\(O(1)\) |
\(O(n)\) |
負荷率を一定以下（例: \(\alpha \le 0.7\)）に保つことで平均 \(O(1)\) を維持できる
dictはハッシュテーブルCPythonのdictはオープンアドレス法（ランダム探索）で実装されており、Python 3.7以降は挿入順序を保持する
特性 |
Python |
|---|---|
検索・挿入・削除（平均） |
\(O(1)\) |
順序の保持 |
挿入順（3.7以降） |
キーの制約 |
ハッシュ可能（immutable）なオブジェクト |