PythonでDict(ハッシュテーブル)を実装する

データ構造やアルゴリズムを勉強していて，ハッシュテーブルの仕組みを軽く学んで実装してみたので備忘録に残しておきます．

Dict(ハッシュテーブル)とは

ハッシュテーブルについてはWikipediaを引用しておきます．

ハッシュテーブル (英: hash table) は、キーと値の組（エントリと呼ぶ）を複数個格納し、キーに対応する値をすばやく参照するためのデータ構造。ハッシュ表ともいう。ハッシュテーブルは連想配列や集合の効率的な実装のうち1つである。(Wikipedia/ハッシュテーブル)

ハッシュテーブルは，キーに対応する値を素早く参照するために，キーをハッシュ化します．しかし，キーをハッシュ値にする際，異なるキーでも同じハッシュ値を生成してしまう，衝突(collision)が発生することがあります．この時衝突を回避する方法として以下のの2種類があります．

チェイン法
オープンアドレス法

今回はチェイン法を使ってこの衝突を回避しています. 具体的には，同じハッシュ値のデータが挿入された場合には，連結リスト(Linked List)を末尾に連結します．

簡単な実装

チェイン法を使って衝突を回避するために，シンプルな連結リストを用意しておきます．

class LinkedList:
    def __init__(self, value):
        self.value = value
        self.next = None

シンプルなハッシュ関数と，データの追加，削除，探索メソッドを実装します．

class MyDict:
    def __init__(self):
        self.table = [None] * 1000

    def hash(self, key):
        # 1000で割った余りをhash値として扱う
        return key % 1000

    def add(self, key, value):
        hashed_key = self.hash(key)
        if self.table[hashed_key]:  # すでにキーにデータが存在したら
            ll = self.table[hashed_key]  # すでに存在しているデータ(連結リストの先頭)
            while ll:  # 連結リストの最後尾までループして，最後にデータを追加する
                if not ll.next:  # 連結リストの最後の場合
                    ll.next = LinkedList(value)  # 新しい値を連結リストに連結
                    break
                else:
                    ll = ll.next
        else:
            self.table[hashed_key] = LinkedList(value)  # データが既に存在していない場合，連結リストとしてデータを挿入

    def get(self, key):
        values = []
        hashed_key = self.hash(key)
        ll = self.table[hashed_key]
        if not ll:  # 指定したキーにデータが存在しない場合は-1を返す
            return -1
        while ll:  # 連結リストが存在する場合
            values.append(ll.value)  # 連結リストの値をリストに追加
            if not ll.next:  # もし連結リストの最後尾だったら
                return values
            else:
                ll = ll.next

    def remove(self, key, value):
        hashed_key = self.hash(key)
        ll = self.table[hashed_key]
        if not ll:  # 指定したキーにデータが存在しなかったら
            print('No Data')
            return
        if ll.value == value:  # 連結リストの先頭を削除する場合
            if ll.next:  # 先頭を削除して，連結リストを一つ前にずらす
                self.table[hashed_key] = ll.next
            else:  # データが一つだけの場合
                self.table[hashed_key] = None
            print(f'Key:{key}, Value:{value} Removed')
            return
        ll_prev = ll
        ll = ll_prev.next
        while ll:  # 指定したキーに複数連結リストが存在する場合
            if ll.value == value:
                ll_prev.next = ll.next
                print(f'Key:{key}, Value:{value} Removed')
                return
            else:
                ll_prev = ll
                ll = ll.next
        print('Data not Found')

実行スクリプトと実行結果を示しておきます

データの追加

dictionary = MyDict()
dictionary.add(1, 'orange')
dictionary.add(2, 'apple')
dictionary.add(3, 'grape')
dictionary.add(1001, 'mikan')
dictionary.add(1003, 'muscat')
dictionary.add(2002, 'green apple')
dictionary.add(3002, 'pineapple')
dictionary.add(2004, 'melon')

# Dict内のデータの表示
for i in range(1, 5):
    print(f'Key: {i}, Value: {dictionary.get(i)}')

出力結果

>>> Key: 1, Value: ['orange', 'mikan']
>>> Key: 2, Value: ['apple', 'green apple', 'pineapple']
>>> Key: 3, Value: ['grape', 'muscat']
>>> Key: 4, Value: ['melon']

データの削除

dictionary.remove(1, 'orange')
dictionary.remove(2002, 'green apple')
dictionary.remove(3, 'muscat')

# データの表示
for i in range(1, 5):
    print(f'Key: {i}, Value: {dictionary.get(i)}')