オープンアドレス法（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、前回学んだハッシュ法（Hashing）の衝突を回避するオープンアドレス法について学んでいきます。

オープンアドレス法とは
Pythonでオープンアドレス法を実装してみる
再ハッシュの手順
動作確認
参考書籍

オープンアドレス法とは

前回はハッシュ値の衝突を回避する方法として、連結リストを使用したチェイン法について学びました。

今回のオープンアドレス法においてもハッシュ値の衝突を回避するものになります。

オープンアドレス法（Open Addressing）とは、同じハッシュ値を持つデータが存在した場合に、再ハッシュ（Rehashing）という手順を取る方式を言います。

例えばキーaのハッシュ値をh(a)で生成する場合、既にリストが埋まっている場合は、空のリストが見つかるまで再ハッシュを繰り返します。

繰り返す回数をiとした場合の再ハッシュ手順は、h( (h(a) + k) )で表され、繰り返し再ハッシュをしても空のリストが見つからなかった場合は、ハッシュテーブルが満杯であるため、これ以上データを挿入することが出来ません。

なお、オープンアドレス表ではリストのサイズ（ハッシュテーブルの大きさ）は素数、もしくは2^n - 1（nは整数）であることが望ましいとされます。

Pythonでオープンアドレス法を実装してみる

それでは、Pythonでオープンアドレス法を実装してみます。

# open_address.py
class HashTable:
    def __init__(self, size):
        self.size = size
        self.values = [None for _ in range(size)]

    def my_hash(self, value):
        length = 0
        for c in value:
            length += ord(c)
        return length % self.size

    def rehash(self, hash):
        return (hash + 1) % self.size

    def find(self, target):
        count = 1
        hash = self.my_hash(target)
        while self.values[hash]:
            if self.values[hash] == target:
                return hash
            elif count > self.size:
                return None
            else:
                hash = self.rehash(hash)
                count += 1
        return None

    def insert(self, value):
        try:
            count = 1
            hash = self.my_hash(value)
            if self.find(value):
                print('[*] value already exists.')
                return False
            while self.values[hash]:
                if count > self.size:
                    print('[*] HashTable is overflow.')
                    return False
                hash = self.rehash(hash)
                count += 1
            self.values[hash] = value
            return True
        except:
            print("[*] Failed to insert.")
            return False

    def delete(self, value):
        hash = self.find(value)
        if hash:
            self.values[hash] = None
            return True
        else:
            print("[*] No data found")
            return False

table = HashTable(100)
table.insert('one')
table.insert('neo')
table.insert('one')
index = table.find('one')
print("'{}' at position: {}".format(table.values[index], index))

今回の再ハッシュ手順は、単純にハッシュ値に1を加算し、さらにハッシュ値を求めています。

再ハッシュの手順

上記のスクリプトでは、単純な再ハッシュ手順を用いていますが、この場合一度衝突が起こると連鎖的に衝突が起こりやすくなり、塊ができてしまうため、あまり効率的ではありません。

上記の場合、1ではなくc個（5や7など）の間隔を取ることで、塊が出来にくくなりますが、根本的にこのような塊を避けることが出来ません。

また、ハッシュ値ごとにランダムな値を作成し、その値を利用して再ハッシュを行うなどで、改善されるようですが、最終的にはハッシュテーブルの利用率が90％を超えると、探索に要する時間が急激に増えるため、こちらもハッシュテーブルの大きさと登録するデータ数を考慮する必要があります。

動作確認

それでは上記で作成したスクリプトを実行してみます。

 > python open_address.py
 [*] value already exists.
 'one' at position: 22

上記では、まず"one"と"neo"という同じハッシュ値を持つデータを挿入します。

再度"one"を挿入しようとすると重複エラーが発生します。

その後、"one"のインデックスを取得し、結果を表示しています。

基本的にハッシュ値にはある程度の偏りがあるのが普通のようです。

また、キーの値の二乗の中央値を取る（平方採中法）方法も良好な結果が得られるようです。

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)

Engineering Note

プログラミングなどの技術的なメモ