ハッシュ衝突と削除後の探索
同じ格納先になったキーを、連鎖方式と線形探索で保持する方法を学びます。
説明
ハッシュ表は、キーから計算した値を使って格納先を決めます。格納先の数は有限なので、異なるキーが同じ場所を指す衝突が起こります。衝突したキーを失わず、元のキーを照合して検索する仕組みが必要です。
この演習では整数キーを5で割った余りを格納先とします。10・15・7を使い、同じ場所に複数個をつなぐ連鎖方式と、別の空きへ進む開番地方式を操作します。開番地方式では削除した場所を単なる空欄にすると検索が途切れる問題も扱います。
1格納先の衝突
容量5の表に10・15・7を入れます。余りを使うこの関数は計算が見えるようにした例で、暗号用のハッシュ関数ではありません。
keys = [10, 15, 7]格納するキー; capacity = 5表の容量; [(key, key % capacity) for key in keys]キーと格納先10と15はともに0、7は2です。ハッシュ値だけではキーを一意に識別できないため、検索時にはキーそのものも比較します。
2連鎖方式のバケット
格納先ごとにリストを用意し、衝突したキーを同じリストへ追加します。空のリストは内包表記で別々に作ります。
buckets = [[] for _ in range(capacity)]独立した5個のバケット; buckets[10 % capacity].append(10); buckets[15 % capacity].append(15); buckets[7 % capacity].append(7)各格納先へ追加; bucketsバケット一覧バケット0に10・15、バケット2に7が入ります。同じハッシュ値でもキーを両方保持できます。リストの共有を避けるため、[[]]*5ではなく各バケットを個別に作りました。
3バケット内でキーを照合
15と20を探します。どちらも格納先0ですが、20は入れていません。
[(target, buckets[target % capacity], target in buckets[target % capacity]) for target in [15, 20]]格納先の中でキーを検索15はTrue、20はFalseです。衝突が増えて一つのバケットが長くなると、そこで比較するキー数が増えます。ハッシュ計算だけで検索が終わるわけではありません。
4開番地方式では空きへ進む
同じ5枠に、各枠1個だけ格納します。10は0、15は0が使用中なので1、7は2へ置きます。このように一つずつ先へ進む方法を線形探索法と呼びます。
slots = [None] * capacity5枠の表; slots[0] = 10; slots[1] = 15; slots[2] = 7衝突した15を次へ格納; list(enumerate(slots))添字とキー配列は10・15・7・空・空です。15の本来の位置は0ですが、探索も0から始めて1へ進めば見つかります。格納と検索で同じ探索順を使います。
5探索を止める条件
探索では一致したら成功、未使用枠なら失敗です。表を一周しても見つからなければ終了するよう、容量回までに制限します。
def lookup(target):検索値を受け取る
visited = []通過位置
for offset in range(capacity):最大1周まで
index = (target + offset) % capacity格納先から順に進む
visited.append(index)位置を記録
if slots[index] == target: return visited, True一致で成功
if slots[index] is None: return visited, False未使用で失敗
return visited, False一周して失敗次の実行では通過した添字も返します。末尾から先頭へは余りで折り返します。未使用と削除済みを同じ扱いにすると問題になるため、この後で削除を試します。
6検索経路と未登録キー
15は0を通り1で見つかります。20は同じ0から始めますが、3の未使用枠まで進みます。
lookup(15)衝突後の15を検索, lookup(20)未登録の20を検索15の経路は0・1、20は0・1・2・3です。7は別の格納先から入りましたが、20の探索経路上にあるため比較されます。占有率が高まると長い連続領域ができやすくなります。
7削除を空欄にすると途切れる
10を削除し、その場所を未使用のNoneにしてみます。15は添字1に残っていますが、探索は0で止まります。
slots[0] = None10を空欄にする; slots, lookup(15)15の検索が途切れる15が存在するのにFalseになりました。未使用枠は「この先まで格納されなかった」という探索終了の印なので、途中の削除にそのまま使うと経路を切ってしまいます。
8削除済みの印を残す
整数キーと衝突しない文字列を削除済みの印にします。探索はこの印では止まらず、後ろのキーへ進みます。
slots[0] = '<deleted>'未使用と異なる削除印; slots, lookup(15), lookup(20)探索が続くことを確認15は再び見つかり、20は未登録のままです。挿入時には削除済み枠を再利用できますが、同じキーが後方にないかという重複確認も必要です。削除済み枠が増えた場合は再構築して探索経路を短くできます。
まとめ
ハッシュ値が一致してもキーが同じとは限りません。格納後もキーを照合します。
連鎖方式はバケット内へ複数キーを置き、開番地方式は別の空き枠へ進みます。
開番地方式の削除では、探索経路を維持するため未使用と削除済みを分けます。
操作履歴と解説を振り返れます。
Python 3
keys = [10, 15, 7]; capacity = 5; [(key, key % capacity) for key in keys][(10, 0), (15, 0), (7, 2)]
buckets = [[] for _ in range(capacity)]; buckets[10 % capacity].append(10); buckets[15 % capacity].append(15); buckets[7 % capacity].append(7); buckets[[10, 15], [], [7], [], []]
[(target, buckets[target % capacity], target in buckets[target % capacity]) for target in [15, 20]][(15, [10, 15], True), (20, [10, 15], False)]
slots = [None] * capacity; slots[0] = 10; slots[1] = 15; slots[2] = 7; list(enumerate(slots))[(0, 10), (1, 15), (2, 7), (3, None), (4, None)]
def lookup(target):
visited = []
for offset in range(capacity):
index = (target + offset) % capacity
visited.append(index)
if slots[index] == target: return visited, True
if slots[index] is None: return visited, False
return visited, Falselookup(15), lookup(20)(([0, 1], True), ([0, 1, 2, 3], False))
slots[0] = None; slots, lookup(15)([None, 15, 7, None, None], ([0], False))
slots[0] = '<deleted>'; slots, lookup(15), lookup(20)(['<deleted>', 15, 7, None, None], ([0, 1], True), ([0, 1, 2, 3], False))
演習完了