【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
3-4 ハッシュ法
ハッシュ法は探索だけでなく追加削除も効率良く行うための手法です。
ソート済みの配列の場合、新しく要素を追加するために、後続の要素をすべて後ろにずらす必要があります。
ハッシュ法では各要素の値(キー)を配列の要素数で割った剰余を添字として配列する。
a = [5,6,14,20,29,34,37,51,69,75,-,-,-] len(a) = 13としたとき
各要素を13で割った剰余は
[5,6,1,7,3,8,11,12,4,10,-,-,-]
となります。
これを添字として並べ替えると
[-,14,-,29,69,5,6,20,34,-,75,37,51]
となります。
この時35を挿入するときに剰余は9なので、34の次に挿入されます。
衝突
ハッシュ法によって、挿入がしやすくなったとしても、値が被らないとは限りません。
値が被ってしまったときの減少を衝突と言います。
衝突が発生した際の対処法として
チェイン法：同一ハッシュ地を持つ要素を線形リストで管理する方法
オープンアドレス法：空きバケットえお見つけるまでハッシュを繰り返す方法
があります。
チェイン法
実際にチェイン法によるハッシュを行います
#チェイン法によるハッシュ
from __future__ import annotations
from typing import Any, Type
import hashlib
class Node:
"""ハッシュを構成するノード"""
def __init__(self, key: Any, value: Any, next:Node) -> None:
"""初期化"""
self.key = key #キー
self.value = value #値
self.next = next #後続ノードへの参照
class ChainedHash:
"""チェイン法を実現するハッシュクラス"""
def __init__(self, capacity: int) -> None:
"""初期化"""
self.capacity = capacity #ハッシュ表の容量
self.table = [None] * self.capacity #空のハッシュ表（リスト）を生成
def hash_value(self, key: Any) -> int:
"""引数keyに対応するハッシュ値を求める"""
if isinstance(key, int):
return key % self.capacity #keyがintの時はkeyをcapacitで割った剰余
return (int(hashlib.sha256(str(key).encode()).hexdigest(),16) % self.capacity)
#keyがint型でないときはsha256,encode関数,hexdigestメソッドを利用して求める。
def search(self, key: Any) -> Any:
"""キーkeyをもつ要素の探索(値を返却)"""
hash = self.hash_value(key) #探索するキーのハッシュ値
p = self.table[hash]
while p is not None:
if p.key == key:
return p.value
p = p.next
return None
def add(self, key: Any, value: Any) -> bool:
"""キーがkeyで値がvalueの要素の追加"""
hash = self.hash_value(key) #追加するキーのハッシュ値
p = self.table[hash] #着目ノード
while p is not None:
if p.key == key:
return False #追加失敗
p = p.next #後続ノードに着目
temp = Node(key, value, self.table[hash])
self.table[hash] = temp #ノードを挿入
return True #追加成功
def remove(self, key: Any) -> bool:
"""キーkeyをもつ要素の削除"""
hash = self.hash_value(key) #削除するキーのハッシュ値
p = self.table[hash] #着目ノード
pp = None #前回の着目ノード
while p is not None:
if p.key == key:
if pp is None:
self.table[hash] = p.next
else:
pp.next = p.next
return True #削除成功
pp = p
p = p.next
return False
def dump(self) -> None:
"""ハッシュ表をダンプ"""
for i in range(self.capacity):
p = self.table[i]
print(i, end='')
while p is not None:
print(f' →{p.key}({p.value})', end='')
p = p.next
print()
sha256：hashlibモジュールで提供されている。RSAのFIPSアルゴリズムに基づいて、与えられたバイト文字列のハッシュ値を求めるハッシュアルゴリズムのコンストラクタのこと。
encode関数：hashlib.sha256に対して、バイト文字列の引数を与えるため、keyをいったんstr型に変換したものをencode関数に与えることによってバイト文字列を生成する。
hexdigestメソッド：sha256アルゴリズムからハッシュ値を16進の文字列として取り出す。
#チェイン法を実現するハッシュクラスChaineHashの利用例
from enum import Enum
from chained_hash import ChainedHash
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 = ChainedHash(19)
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
メニューの表示選択を実現するために列挙型(Enum型)を使っています。関数selct_menuは5個のメニューを表示したうえで1から5の整数値を読み込み、その値に対応する列挙値(Menu.追加,Menu.削除,
など)を返却します。
本日は以上です。ありがとうございました。
まだまだ、アルゴリズムをどう活用していけばわかっていませんが、ほんの少しずつpythonに対する理解は進んでいる気がします。
それでも実際に何かを作ってみない限りはマスターできたとは言えないので、事例など探しながらプログラムを組んでいきたいですね。