ハッシュ法 （Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 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)