【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
オープンアドレス法
衝突が発生したとき再ハッシュを行うことによって、空いているバケットを探し出す手法で、クローズドハッシュ法とも呼ばれる。
各バケットに対して、
・データが格納されている。
・空。
・削除済み。
の属性を与える。
list3-7,open_hash_test.py
#オープンアドレス法によるハッシュ
from __future__ import annotations
from typing import Any, Type
from enum import Enum
import hashlib
#バケットの属性
class Status(Enum):
OCCUPIED = 0 #データ格納
EMPTY = 1 #空
DELETED = 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
class OpenHash:
"""オープンアドレス法を実現するハッシュクラス"""
def __init__(self,capacity: int) -> None:
"""初期化"""
self.capacity = capacity #ハッシュの容量
self.table = [Bucket()] * self.capacity #ハッシュ表
def hash_value(self, key: Any) -> int:
"""ハッシュ値を求める"""
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] #着目バケット
for i in range(self.capacity):
if p.stat == Status.EMPTY:
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('--削除済み--')
list3-8
#オープンアドレス法によるハッシュの利用例
from enum import Enum
#from open_hash import OpenHash
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からリンクされていた。
オープンアドレス法では、再ハッシュを行い、データをずらした場所に格納します。
短いですが、本日は以上になります。ありがとうございました。
これで3章は終了です。
探索から始まり、データの格納方法などを学ぶことで、データがどのように扱われているのかなどを考えることができそうですね。