今回はハッシュ法について説明していきます。あくまで自分の理解のためなので、自分的にこのくらいの理解でいいだろうと満足してしまった箇所はあっさりしていたり、他方で理解に時間のかかった箇所はくどくど説明したりしています。その点ご了承ください。
ハッシュ法とは
ハッシュ法とは、探索だけではなく、要素の追加や削除も効率よく行えるアルゴリズムのことです。ある配列を考えた時、要素の追加には、探索を行った後に挿入を行い、後ろの要素を全てずらさなくてはならないのでその処理コストは意外に大きかったりします。そこでこのハッシュ法を使おうという話です。
ハッシュ値が添字となるようにキーを格納した配列がハッシュ表です。例えば、13で割ったあまりをハッシュ値としたハッシュ表を考えてみましょう。
| キー | 5 | 6 | 14 | 20 | 29 | 34 | 37 | 51 | 69 | 75 |
|---|---|---|---|---|---|---|---|---|---|---|
| 値 | 山本君 | 野崎君 | 高橋君 | 鈴木君 | 橋本君 | 長谷川君 | 小川君 | 佐藤君 | 四月一日君 | ブライアン |
| ハッシュ値(13で割った剰余) | 5 | 6 | 1 | 7 | 3 | 8 | 11 | 12 | 4 | 10 |
この場合、a[5]に山本君を入れ、a[6]に野崎君、a[1]に高橋君という具合に配列aにセットしていきます。もちろん、用意した配列の全ての要素を全て埋める必要はありません。例えばa[0]はここではNoneです。
また、ここに出てくる配列aの各要素のことをバケットと言います。
オープンアドレス法
オープンアドレス法とは、ハッシュ値の衝突が生じる際に、衝突しなくなるまで再ハッシュする方法です。要素を探索、追加、削除の際に必要であれば再ハッシュが行われます。
要素の追加
| キー | 5 | 6 | 14 | 20 | 29 | 34 | 37 | 51 | 69 | 75 |
|---|---|---|---|---|---|---|---|---|---|---|
| 値 | 山本君 | 野崎君 | 高橋君 | 鈴木君 | 橋本君 | 長谷川君 | 小川君 | 佐藤君 | 四月一日君 | ブライアン |
| ハッシュ値(13で割った剰余) | 5 | 6 | 1 | 7 | 3 | 8 | 11 | 12 | 4 | 10 |
| 配列 | a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] | a[9] | a[10] | a[11] | a[12] |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 値 | None | 高橋君 | None | 橋本君 | 四月一日君 | 山本君 | 野崎君 | 鈴木君 | 長谷川君 | None | ブライアン | 小川君 | 佐藤君 |
もしこの配列に(key: 18, Value: ジョニー)を追加する場合、ハッシュ値は18%13=5ですから、すでに山本君で埋まってしまっています。そこで、(18+1)%13=6と再ハッシュします。これも野崎君で埋まっていますからもう一度、7も鈴木君で埋まっているのでもう一度...ハッシュ値9のキーを持った要素はないので、ようやくa[9]にジョニーを追加する事に成功しました。
| 配列 | a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] | a[9] | a[10] | a[11] | a[12] |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 値 | None | 高橋君 | None | 橋本君 | 四月一日君 | 山本君 | 野崎君 | 鈴木君 | 長谷川君 | ジョニー | ブライアン | 小川君 | 佐藤君 |
要素の削除
さて、要素の削除はどうすればいいでしょう。例えば、この配列から山本君を削除したとします。もし単に削除しただけでは、ジョニーを探索すると、ここでは再ハッシュの結果としてa[9]にいますが、元々のハッシュ値は5でした。なので、ハッシュ値5の値は見つからないとなり、探索に失敗してしまいます。
a[5]が初めから空だったなら、探索失敗でいいのですが、削除されたあとであれば、もしかすると再ハッシュによって後の方に探索したい値が埋まっているかもしれませんよね。そこで、この辺りを判断させるために、配列の各バケットにEMPTY, OCCUPIED, DELETEDの３つの状態を持てるようにします。こうすれば、キー18の値を探索する際に、a[5]はDELETEDの状態なので、再ハッシュして探索を続けることができます。
クラス1
class Status(Enum):
OCCUPIED = 0
EMPTY = 1
DELETED = 2
バケットの状態を定義しています。
C言語でいう
#define OCCUPIED 0
#define EMPTY 1
#define DELETED 2
と同じですね。
クラス2
class Bucket:
#ハッシュを構成するバケット
def __init__(self, key: Any = None, value: Any = None, stat: Status = Status.EMPTY) -> None:
self.key = key
self.value = value
self.stat = stat
def set(self, key: Any, value: Any, stat: Status) -> None:
self.key = key
self.value = value
self.stat = stat
def set_status(self, stat: Status) -> None:
self.stat = stat
このクラスでは、バケットのインスタンスを作成しています。バケットインスタンスは、要するに先ほど見た配列の一つ一つの要素のことです。この各要素は、キー、値、状態の三つの属性(attribute)をもちます。
クラス3
class OpenHash:
def __init__(self, capacity: int) -> None:
"""初期化"""
self.capacity = capacity
self.table = [Bucket()] * self.capacity
def hash_value(self, key: Any) -> int:
"""keyからハッシュ値を求める"""
if isinstance(key, int):
return key % self.capacity
return (int(hashlib.md5(str(key).encode()).hexdigest(), 16) % self.capacity)
def rehash_value(self, key: Any) -> int:
"""再ハッシュしてハッシュ値を返却"""
return (self.hash_value(key) + 1) % self.capacity
def search_node(self, key: Any) -> Any:
"""キーがkeyであるバケットの探索"""
hash = self.hash_value(key)
p = self.table[hash] #hash番目のバケットがpに入る。
for i in range(self.capacity): #配列のバケット数分ループ
if p.stat == Status.EMPTY: #バケットが空なら最初から何も入っていなかったということなので、breakしてNoneを返却
break
elif p.stat == Status.OCCUPIED and p.key == key: #探したいキーを持ったバケットが見つかればそのバケットを返却
return p
hash = self.rehash_value(hash)
p = self.table[hash]
return None
def search(self, key: Any) -> Any:
"""キーkeyを持つ要素を探索し、値を返却する"""
p = self.search_node(key)
if p is not None:
return p.value
else:
return None
def add(self, key: Any, value: Any) -> bool:
"""キーがkeyで値がvalueである要素の追加"""
if self.search(key) is not None:
return False
hash = self.hash_value(key)
p = self.table[hash]
for i in range(self.capacity):
if p.stat == Status.EMPTY or p.stat == Status.DELETED:
self.table[hash] = Bucket(key, value, Status.OCCUPIED)
return True
hash = self.rehash_value(hash)
p = self.table[hash]
return False
def remove(self, key: Any) -> int:
"""キーkeyを持つ要素の削除"""
p = self.search_node(key)
if p is None:
return False
p.set_status(Status.DELETED)
return True
def dump(self) -> None:
"""ハッシュ表をダンプ"""
for i in range(self.capacity):
print(f'{i:2} ', end = '')
if self.table[i].stat == Status.OCCUPIED:
print(f'{self.table[i].key} ({self.table[i].value})')
elif self.table[i].stat == Status.EMPTY:
print('---未登録---')
elif self.table[i].stat == Status.DELETED:
print('---削除済み---')
先ほど、a[5]が削除された後key:18の値を探そうとすると失敗してしまうと言いましたが、どのようにこれが回避されているか見ていきましょう。
def search_node(self, key: Any) -> Any:
"""キーがkeyであるバケットの探索"""
hash = self.hash_value(key)
p = self.table[hash] #hash番目のバケットがpに入る。
for i in range(self.capacity): #配列のバケット数分ループ
if p.stat == Status.EMPTY: #バケットが空なら最初から何も入っていなかったということなので、breakしてNoneを返却
break
elif p.stat == Status.OCCUPIED and p.key == key: #探したいキーを持ったバケットが見つかればそのバケットを返却
return p
hash = self.rehash_value(hash)
p = self.table[hash]
return None
探索の際search_node(key)はsearch(key)から呼び出されますが、これはkeyを持ったバケットを返却するメソッドです。keyとしてsearch()に18を与えると、a[5]を対象に探索が始まります。ここはDELETEという状態ですから、ifやelifをスルーして再ハッシュし、a[(18+1)%13]を対象にします。これを繰り返し、結局a[9]のジョニーを見つけることができます。
最後に
実際に上記クラスの利用例を見ていきましょう。
from enum import Enum
Menu = Enum('Menu', ['追加', '削除', '探索', 'ダンプ', '終了'])
def select_menu() -> Menu:
"""メニューの選択"""
s = [f'({m.value}){m.name}'for m in Menu]
while True:
print(*s, sep=' ', end='')
n = int(input(' : '))
if 1 <= n <= len(Menu):
return Menu(n)
hash = OpenHash(13)
while True:
menu = select_menu()
if menu == Menu.追加:
key = int(input('キー : '))
val = input('値 : ')
if not hash.add(key, val):
print('追加失敗')
elif menu == Menu.削除:
key = int(input('キー : '))
if not hash.remove(key):
print('削除失敗')
elif menu == Menu.探索:
key = int(input('キー : '))
t = hash.search(key)
if t is not None:
print(f'そのキーを持つ値は{t}です。')
else:
print('該当するデータはありません。')
elif menu == Menu.ダンプ:
hash.dump()
else:
break
以下入力と出力
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 5
値 : 山本君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 6
値 : 野崎君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 14
値 : 高橋君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 20
値 : 鈴木君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 29
値 : 橋本君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 34
値 : 長谷川君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 37
値 : 小川君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 51
値 : 佐藤君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 69
値 : 四月一日君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 75
値 : ブライアン
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 4
0 ---未登録---
1 14 (高橋君)
2 ---未登録---
3 29 (橋本君)
4 69 (四月一日君)
5 5 (山本君)
6 6 (野崎君)
7 20 (鈴木君)
8 34 (長谷川君)
9 ---未登録---
10 75 (ブライアン)
11 37 (小川君)
12 51 (佐藤君)
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 5
値 : ジョニー
追加失敗！
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 4
0 ---未登録---
1 14 (高橋君)
2 ---未登録---
3 29 (橋本君)
4 69 (四月一日君)
5 5 (山本君)
6 6 (野崎君)
7 20 (鈴木君)
8 34 (長谷川君)
9 ---未登録---
10 75 (ブライアン)
11 37 (小川君)
12 51 (佐藤君)
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 5
あれ...山本君のところにジョニーを追加しようとしたら、追加失敗となってしまいました。オープンアドレス法は、a[5]が埋まっていたとしても、全ての要素が満杯でない限りは再ハッシュして何とか埋めるはずなのに...
問題がありそうなのは、add()の中の
if self.search(key) is not None:
の部分ですね。
if self.search(key) == value:
と書き換えまして、再度やって見ます。
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 5
値 : 山本君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 6
値 : 野崎君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 14
値 : 高橋君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 20
値 : 鈴木君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 29
値 : 橋本君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 34
値 : 長谷川君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 37
値 : 小川君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 51
値 : 佐藤君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 69
値 : 四月一日君
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 75
値 : ブライアン
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 4
0 ---未登録---
1 14 (高橋君)
2 ---未登録---
3 29 (橋本君)
4 69 (四月一日君)
5 5 (山本君)
6 6 (野崎君)
7 20 (鈴木君)
8 34 (長谷川君)
9 ---未登録---
10 75 (ブライアン)
11 37 (小川君)
12 51 (佐藤君)
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 1
キー : 18
値 : ジョニー
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 4
0 ---未登録---
1 14 (高橋君)
2 ---未登録---
3 29 (橋本君)
4 69 (四月一日君)
5 5 (山本君)
6 6 (野崎君)
7 20 (鈴木君)
8 34 (長谷川君)
9 18 (ジョニー)
10 75 (ブライアン)
11 37 (小川君)
12 51 (佐藤君)
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 2
キー : 5
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 4
0 ---未登録---
1 14 (高橋君)
2 ---未登録---
3 29 (橋本君)
4 69 (四月一日君)
5 ---削除済み---
6 6 (野崎君)
7 20 (鈴木君)
8 34 (長谷川君)
9 18 (ジョニー)
10 75 (ブライアン)
11 37 (小川君)
12 51 (佐藤君)
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 3
キー : 18
そのキーを持つ値はジョニーです。
(1)追加 (2)削除 (3)探索 (4)ダンプ (5)終了 : 5
何とかジョニーも無事追加され、山本君削除後のジョニーの探索にも成功しました。