[データ構造] 連想配列をPythonで実装

Python では、連想配列として辞書型が組み込まれているので、そちらを通常は利用します。

5.5. 辞書型 (dictionary)

マッピング型 — dict

ここでは辞書は使わず、自分の理解のため簡単な連想配列をスクラッチから実装してみます。

キーとしてASCII文字を使い、衝突が起こったときは、オープンアドレス法の線形走査法を使います。

HashTable クラス

初期化

__init__ では、配列のサイズを決めて、キーと値の配列をそれぞれ生成します。

class HashTable(object):
    def __init__(self):
        self.size = 11
        self.keys = [None] * self.size
        self.values = [None] * self.size

ハッシュ関数

ハッシュ関数は、キーのそれぞれの文字をordで数値化して足し、配列のインデックスに収まるよう配列サイズの剰余を取ることでハッシュ値にします。

class HashTable(object):
    def __init__(self):
        self.size = 11
        self.keys = [None] * self.size
        self.values = [None] * self.size

    def make_hash(self, key):
        hash_val = 0
        for pos in range(len(key)):
            hash_val += ord(key[pos])
        
        hash_val %= self.size
        return hash_val

値の挿入・更新

ハッシュ関数でインデックスを取得し、そのインデックスを基に加えるキーを探します。

キーが見つかればそのインデックスの値を更新、見つからなければそのインデックスで値の挿入を行います。

もしインデックスが埋まっている場合は、線形走査法、つまり次のインデックスが空かどうかを調べます。剰余を取ることでインデックスがサイズを超えたら0に戻り調べます。

class HashTable(object):
    def __init__(self):
        self.size = 11
        self.keys = [None] * self.size
        self.values = [None] * self.size

    def make_hash(self, key):
        hash_val = 0
        for pos in range(len(key)):
            hash_val += ord(key[pos])
        
        hash_val %= self.size
        return hash_val

    def add(self, key, data):
        index = self.make_hash(key)

        # 空のインデックスを探す。もし同じキーが存在したら値を更新。
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = data
                return
            # 次のインデックスに進む　サイズを超えたら最初に戻る
            index = (index + 1) % self.size

        self.keys[index] = key 
        self.values[index] = data

値の取得

追加と同じように、ハッシュ関数でキーからインデックスを求めて、インデックスに基づき値を探します。

class HashTable(object):
    def __init__(self):
        self.size = 11
        self.keys = [None] * self.size
        self.values = [None] * self.size

    def make_hash(self, key):
        hash_val = 0
        for pos in range(len(key)):
            hash_val += ord(key[pos])
        
        hash_val %= self.size
        return hash_val

    def add(self, key, data):
        index = self.make_hash(key)

        # 空のインデックスを探す。もし同じキーが存在したら値を更新。
        while self.keys[index] is not None:
            if self.keys[index] == key:
                self.values[index] = data
                return
            # 次のインデックスに進む　サイズを超えたら最初に戻る
            index = (index + 1) % self.size

        self.keys[index] = key 
        self.values[index] = data

    def lookup(self, key):
        index = self.make_hash(key)

        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size

        return False


if __name__ == '__main__':
    hash_table = HashTable()
    hash_table.add('apple', 10)
    hash_table.add('banana', 5)
    hash_table.add('orange', 20)
    # [None, None, 'apple', None, 'banana', None, None, None, None, 'orange', None]
    print(hash_table.keys)
    # [None, None, 10, None, 5, None, None, None, None, 20, None]
    print(hash_table.values)
    # 10
    print(hash_table.lookup('apple'))