さえぴ の めも

色んなアウトプットする。

Python3でハッシュ探索

前回の記事(Python3で構造体っぽいことをしてみる - さえぴ の めも)にて、Python3で構造体っぽいものを作り、さらにその要素をリニアサーチ&バイナリサーチで探索するという課題のコードを載せました。

今週の授業ではさらにハッシュ探索の実装が追加されたので、Python3でのハッシュ探索を書きました。というわけでこまめにアウトプットします(あんまりできてない)

ハッシュ探索とは

  • 配列の要素を一定の規則でハッシュ化し、そのハッシュ値を使って探索を行う。
  • ハッシュ値に従っての格納さえ済んでいれば、探索の計算量は常にO(1)

というウルトラスーパー早い探索アルゴリズムです。
ただ格納の際に時間がかかるので、探索したいデータが小さい場合はかえって効率が悪いこともあります。


簡単なコードを書くと、

import hashlib

# ハッシュ関数
def get_hash(n):
	hash = hashlib.md5(n.encode('utf-8')).hexdigest()
	hash = int(hash,16) % 61
	return hash

# ハッシュ探索
def hash_search(list,target):
	index = get_hash(target)
	if list[index] == "":
		print("見つかりませんでした")
	else:
		print("見つかりました")

# 探索したいリスト
ary = ["あ","い","う","え","お","か"]
# 格納先のリスト
hash_list = []
for i in range(61):
	hash_list.append("")

# ハッシュに基づいて格納
for i in range(len(ary)):
	index = get_hash(ary[i])
	hash_list[index] = ary[i]

# あを探す
hash_search(hash_list,"あ")
# きを探す
hash_search(hash_list,"き")

こんな感じになります。

探索したい配列aryの中身をハッシュ関数でハッシュ化し、格納先のリストの要素数素数、この場合は61)で割って格納します。
今回は簡単なハッシュかですが、衝突を考えなければいけないので実際は対策が必要です。

そして、ハッシュはユニークなものなので、格納先リストのハッシュ番目をのぞけば探したい数字があるかないかわかるという寸法です。


このハッシュ探索を前回のコード(空クラスを使用した構造体もどき)に盛り込んでみました。
github.com