本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、探索アルゴリズムの中のハッシュ法（Hashing）について学んでいきます。
ハッシュ法とは
ハッシュ法（Hashing）とは、データのキーの値からハッシュ関数というものを使いインデックス（ハッシュ値）を生成し、それをもとに探索などを行います。
もしn個のデータがある場合でも、そのデータの探索、挿入および削除などの操作が実質O(1)の計算量で行うことができます。
例えば、リストのサイズで剰余演算し、インデックスを生成する単純なハッシュ関数がある場合、1というキーを登録するのに"1 % 10 = 1"となるので、インデックスを1とすることができます。
ハッシュ値の衝突
前述の単純なハッシュ関数の場合、"11 % 10"でもインデックスとして1を生成してしまうため、ハッシュ値が重複してしまいます。
これを衝突（Collision）といいます。
上記のハッシュ関数の場合は、リストのサイズを幾分か大きくすることで衝突を避けられますが、その分メモリを消費するため、ある程度使用するデータ量の把握や、使用できるメモリ量についての考慮が必要となります。
なお、これらの衝突を回避するためにチェイン法やオープンアドレス法という考え方があります。
Pythonで簡単なハッシュ関数を作ってみる
それでは、Pythonで簡単なハッシュ関数を実装してみます。
# my_hash.py
size = 100
sequence = [None for _ in range(size)]
def my_hash(string):
length = 0
for c in string:
length += ord(c)
return length % size
def insert(string):
hash = my_hash(string)
if sequence[hash]:
return None
sequence[hash] = string
return hash
string = 'one'
hash = insert(string)
if hash:
print("'{}' at position: {}".format(string, hash))
else:
print('already occupied.')
print(sequence[hash])
上記では、入力した文字列からアスキー文字を10進数に置き換えて、その総和をリストのサイズで剰余演算し、ハッシュ値（インデックス）を取得します。
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python my_hash.py 'one' at position: 22 one
問題なくリストへの登録ができました。
しかし、上記のハッシュ関数では"neo"という文字列もハッシュ値として22を返すことから衝突が起こります。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
