この記事は前回の記事の続きです。ハッシュテーブルの解説もあるので、未読の方は先に前回の記事を読むことをお勧めします。
前回の記事ではチェイン法を用いてハッシュテーブルを実装しました。
今回はオープンアドレス法（Open Addressing）を使ったハッシュテーブルの解説をします！
今回もPythonで実装しましたが約100行ほどのコードで書けちゃいます！
お品書きです。
- オープンアドレス法とは？
- 線形探査法（Linear Probing）の仕組み
- TOMBSTONE
- 実際のコードによる実装
- benchmarkで比較
オープンアドレス法とは？
オープンアドレス法は、ハッシュテーブルの衝突（collision）を解決する方法の一つです。チェイン法が「同じインデックスに線形リストを置く」というアプローチだったのに対し、オープンアドレス法は「別の空いているスロットを探してそこに格納する」というアプローチです。
イメージとしては、こんな感じ：
チェイン法: 同じインデックスにリストでつなげる
┌─────┐
│ [1] │ → [Entry1] → [Entry2] → None
└─────┘
オープンアドレス法: 空いているスロットを探して入れる
┌─────┐
│ [1] │ → Entry1
├─────┤
│ [2] │ → Entry2 (衝突したので次のスロットへ)
└─────┘
線形探査法（Linear Probing）
オープンアドレス法にはいくつかのバリエーションがありますが、今回は線形探査法（Linear Probing）を実装しました。これは、衝突が起きたら「次のスロット、その次のスロット...」と順番に空いている場所を探していく方法です。オープンアドレス法でもっともシンプルな実装ではないでしょうか。
index = key_hash % self.capacity
# 衝突したら次のインデックスへ
while self.arr[index] is not self.NULL:
index = (index + 1) % self.capacity # 次のスロットへ
シンプルで理解しやすいですね！負荷率を低く保つことで衝突が起こる回数を低く抑えます。負荷率が0.75を超えたらリサイズするようにしています。
負荷率とは、ハッシュテーブルの「埋まり具合」を表す指標です。
負荷率 = 格納されている要素数 ÷ スロット数
例えば、スロット数が16で要素が12個格納されている場合、負荷率は 12 ÷ 16 = 0.75 となります。
TOMBSTONE
オープンアドレス法で削除を実装する際、考慮しないといけないことが「削除したスロットをどう扱うか」です。
単純にNULLに戻してしまうと、検索時に問題が起きます。例えば：
1. "apple"をインデックス5に挿入
2. 衝突して"banana"がインデックス6に挿入
3. "apple"を削除してインデックス5をNULLに
4. "banana"を検索 → インデックス5がNULLなので「見つからない」と判断してしまう！
これを解決するのがTOMBSTONEです。削除したスロットには特別なマーカーを置いて、「ここは削除されたけど、その先に要素があるかもしれない」ということを示します。
NULL = Entry(None, None, -1) # 空いているスロット
TOMBSTONE = Entry(None, None, -2) # 削除されたスロット
def remove(self, key) -> bool:
# ...
if key_hash == entry.hash and key == entry.key:
self.arr[index] = self.TOMBSTONE # 墓石を置く
return True
検索時は、TOMBSTONEの場合は「削除されたけど、その先を探し続ける」ようにします：
def _find(self, key):
while True:
entry = self.arr[index]
if entry is self.NULL:
return None # ここで終了
if entry is not self.TOMBSTONE and key_hash == entry.hash and key == entry.key:
return entry # 見つかった！
index = (index + 1) % self.capacity # TOMBSTONEの場合は続ける
これで、削除後も正しく検索できるようになります。
TOMBSTONEの直訳は「墓石」「墓標」。
技術的な文脈だと、削除マーカーの意味でよく使われるみたいです。
オープンアドレス法のメリット
- メモリ効率が良い: ポインタが不要なので、メモリ使用量が少ない
- キャッシュ効率が良い: 連続したメモリ領域を使うので、CPUキャッシュに優しい
オープンアドレス法のデメリット
- 実装が複雑になる可能性: TOMBSTONEが必要で、実装がやや複雑
- 負荷率に敏感: 負荷率が高くなると性能が急激に低下
- リサイズのコスト: 負荷率を低く保つため、頻繁にリサイズが必要
ちなみに、Pythonのdictはオープンアドレス法を使っています
衝突を解決するアルゴリズムは線形探索法ではありませんが、、
オープンアドレス法でハッシュテーブルを実装してみた
それでは、実際のコードを見ていきましょう。約100行程度で実装します！
Entryクラス
まず、各エントリを表すEntryクラスです。チェイン法と違って、nextポインタは不要です。
class Entry:
__slots__ = ("key", "value", "hash")
def __init__(self, key, value, hash):
self.key = key
self.value = value
self.hash: int = hash
シンプルですね！そして、特別なエントリとしてNULLとTOMBSTONEを定義します：
NULL = Entry(None, None, -1) # 空いているスロット
TOMBSTONE = Entry(None, None, -2) # 削除されたスロット
挿入（insert）
挿入処理は、空いているスロットを線形探査で探していきます：
def insert(self, key, value):
if (self.size + 1) / self.capacity >= self.TABLE_MAX_LOAD:
self._resize()
key_hash = hash(key)
index = key_hash % self.capacity
while True:
entry = self.arr[index]
if entry is self.NULL:
break # 空いているスロットを見つけた！
if key_hash == entry.hash and key == entry.key:
# 既に存在する場合は上書き
entry.value = value
return
# 衝突したので次のインデックスへ
index = (index + 1) % self.capacity
self.arr[index] = self.Entry(key, value, key_hash)
self.size += 1
TOMBSTONEの場合は、次のスロットへ進みます。実装によってはTOMBSTONEのスロットに直接挿入することもできますが、今回はシンプルに次のスロットを探す実装にしています。
検索（get）
検索も線形探査で、NULLに当たるまで探し続けます：
def _find(self, key):
key_hash = hash(key)
index = key_hash % self.capacity
while True:
entry = self.arr[index]
if entry is self.NULL:
return None # 見つからなかった
if key_hash == entry.hash and key == entry.key:
return entry # 見つかった！
index = (index + 1) % self.capacity
TOMBSTONEの場合は、if文の条件に一致しないので、そのまま次のスロットへ進みます。これにより、削除されたスロットをスキップしながら、その先にある要素を正しく見つけられます。
削除（remove）
削除時は、見つけたエントリをTOMBSTONEに置き換えます：
def remove(self, key) -> bool:
key_hash = hash(key)
index = key_hash % self.capacity
while True:
entry = self.arr[index]
if entry is self.NULL:
return False # 見つからなかった
if key_hash == entry.hash and key == entry.key:
self.arr[index] = self.TOMBSTONE # 墓石を置く
return True
index = (index + 1) % self.capacity
見つけたエントリをTOMBSTONEに置き換えるだけで、削除が完了します。シンプルですね！
リサイズ
負荷率が0.75を超えたら、テーブルを2倍に拡張します。リサイズ時は、TOMBSTONEを無視して有効なエントリだけを新しいテーブルに再挿入します：
def _resize(self):
old_arr = self.arr
old_capacity = self.capacity
self.capacity = old_capacity * 2
self.arr = [self.NULL] * (self.capacity)
self.size = 0
for entry in old_arr:
if entry is self.NULL or entry is self.TOMBSTONE:
continue # 空きスロットとTOMBSTONEはスキップ
self.insert(entry.key, entry.value)
これで、TOMBSTONEが蓄積されるのを防げます。リサイズはO(n)の時間がかかりますが、頻繁には発生しないので、平均的な時間計算量はO(1)のままです。
これで完成です。完成したコードは以下になります。
class OpenAddrHashTable:
"""
HashTable implementation using open addressing with linear probing.
"""
class Entry:
__slots__ = ("key", "value", "hash")
def __init__(self, key, value, hash):
self.key = key
self.value = value
self.hash: int = hash
def __str__(self):
return f"Node(key={self.key}, value={self.value}, hash={self.hash})"
NULL = Entry(None, None, -1) # 空いているスロット
TOMBSTONE = Entry(None, None, -2) # 削除されたスロット。ここには挿入しない
TABLE_MAX_LOAD = 0.75 # 最大保有率。これを超えたらリサイズする
def __init__(self):
self.size: int = 0
self.capacity: int = 8
self.arr: list[self.Entry] = [self.NULL] * self.capacity
def insert(self, key, value):
if (self.size + 1) / self.capacity >= self.TABLE_MAX_LOAD:
self._resize()
key_hash = hash(key)
index = key_hash % self.capacity
while True:
entry = self.arr[index]
if entry is self.NULL:
break
if key_hash == entry.hash and key == entry.key:
# 既に存在する場合は上書き
entry.value = value
return
# tombstoneもしくはcollisionの場合は次のインデックスへ
index = (index + 1) % self.capacity
self.arr[index] = self.Entry(key, value, key_hash)
self.size += 1
def _find(self, key) -> Entry | None:
key_hash = hash(key)
index = key_hash % self.capacity
while True:
entry = self.arr[index]
if entry is self.NULL:
return None
if key_hash == entry.hash and key == entry.key:
return entry
index = (index + 1) % self.capacity
def get(self, key):
entry = self._find(key)
return entry.value if entry else None
def remove(self, key) -> bool:
key_hash = hash(key)
index = key_hash % self.capacity
while True:
entry = self.arr[index]
if entry is self.NULL:
return False
if key_hash == entry.hash and key == entry.key:
self.arr[index] = self.TOMBSTONE
return True
index = (index + 1) % self.capacity
def _resize(self):
old_arr = self.arr
old_capacity = self.capacity
self.capacity = old_capacity * 2
self.arr = [self.NULL] * (self.capacity)
self.size = 0
for entry in old_arr:
if entry is self.NULL or entry is self.TOMBSTONE:
continue
self.insert(entry.key, entry.value)
def __setitem__(self, key, value):
self.insert(key, value)
def __getitem__(self, key):
return self.get(key)
def __delitem__(self, key):
return self.remove(key)
def __contains__(self, key):
return self._find(key) is not None
def __str__(self):
return str([str(entry) for entry in self.arr])
ベンチマークで比較する
では前回と今回の記事で作成したハッシュテーブルをベンチマークで比較してみたいと思います！！どちらのハッシュテーブルが速いか予想してみると面白いかも
徐々に要素数を増やしながら比較してみます
以下の3つを比較します
- オープンアドレス法
- チェイン法
- Pythonのdict(オープンアドレス法)
要素数10
オープンアドレス法のinsertが結構時間かかってますね、平均してもチェイン法と約2倍くらいの差がありました
リサイズの処理が原因っぽいですね。
----------------------------------------------------------------------------------------------------
Benchmarking OpenAddrHashTable with 10 items
Insert: 0.000018 sec
Lookup: 0.000006 sec
Delete: 0.000004 sec
Benchmarking ChainedHashTable with 10 items
Insert: 0.000009 sec
Lookup: 0.000005 sec
Delete: 0.000005 sec
Benchmarking dict with 10 items
Insert: 0.000002 sec
Lookup: 0.000001 sec
Delete: 0.000000 sec
----------------------------------------------------------------------------------------------------
要素数50
----------------------------------------------------------------------------------------------------
Benchmarking OpenAddrHashTable with 50 items
Insert: 0.000060 sec
Lookup: 0.000012 sec
Delete: 0.000012 sec
Benchmarking ChainedHashTable with 50 items
Insert: 0.000036 sec
Lookup: 0.000013 sec
Delete: 0.000016 sec
Benchmarking dict with 50 items
Insert: 0.000004 sec
Lookup: 0.000001 sec
Delete: 0.000001 sec
----------------------------------------------------------------------------------------------------
要素数100と1000
----------------------------------------------------------------------------------------------------
Benchmarking OpenAddrHashTable with 100 items
Insert: 0.000125 sec
Lookup: 0.000025 sec
Delete: 0.000026 sec
Benchmarking ChainedHashTable with 100 items
Insert: 0.000082 sec
Lookup: 0.000026 sec
Delete: 0.000034 sec
Benchmarking dict with 100 items
Insert: 0.000011 sec
Lookup: 0.000003 sec
Delete: 0.000003 sec
----------------------------------------------------------------------------------------------------
Benchmarking OpenAddrHashTable with 1000 items
Insert: 0.001294 sec
Lookup: 0.000248 sec
Delete: 0.000263 sec
Benchmarking ChainedHashTable with 1000 items
Insert: 0.000695 sec
Lookup: 0.000250 sec
Delete: 0.000332 sec
Benchmarking dict with 1000 items
Insert: 0.000058 sec
Lookup: 0.000022 sec
Delete: 0.000022 sec
----------------------------------------------------------------------------------------------------
要素数100000
オープンアドレス法の衝突解決アルゴリズムを改善すれば、さらに高速化できそうです。
やはりPythonのビルトインのdictはすごい速い、、
桁違いの性能差があります（C言語で実装されているため、これは当然）
----------------------------------------------------------------------------------------------------
Benchmarking OpenAddrHashTable with 100000 items
Insert: 0.107750 sec
Lookup: 0.021861 sec
Delete: 0.018677 sec
Benchmarking ChainedHashTable with 100000 items
Insert: 0.070513 sec
Lookup: 0.018491 sec
Delete: 0.022477 sec
Benchmarking dict with 100000 items
Insert: 0.004909 sec
Lookup: 0.001678 sec
Delete: 0.001695 sec
----------------------------------------------------------------------------------------------------
まとめ
今回はオープンアドレス法を用いたハッシュテーブルを実装しました。
オープンアドレス法が、想像以上に簡単に実装できたことに驚いた方も多いのではないでしょうか。
ベンチマークの結果ではチェイン法を用いたハッシュテーブルの方が良いスコアを出していましたが、必ずしもチェイン法が優れているとは限りません。
オープンアドレス法には衝突した際に用いるアルゴリズムも他に選択肢がありますし、改善の余地も十分あります。
ハッシュテーブルというデータ構造がブラックボックス化された不思議なものから、少しでも身近なものに感じていただけたら幸いです