効率的な双方向ハッシュ テーブルの実装

双方向ハッシュ テーブルでは、キーから値への検索と値からキーへの検索の両方が可能です。 Python の組み込みの dict データ構造は、キーから値への検索には優れていますが、値からキーへの効率的な取得は提供しません。

双方向ハッシュ テーブルを実装する効果的な方法は、クラスを利用することです。これは標準の dict を拡張したものです。 bidict という名前のこのクラスは、通常の dict への変更を自動的に更新する逆ディレクトリを維持します。

コード実装:

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.items():
            self.inverse.setdefault(value, []).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value, []).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key], []).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

主な機能:

• 逆ディレクトリ (bd.inverse) は、値をマップする辞書です。その値を持つキーのリスト。
• bidict が変更されると、逆ディレクトリは自動的に更新されます。
• 一部の bidict 実装とは異なり、このクラスでは複数のキーが同じ値を持つことができます。

使用例:

bd = bidict({'a': 1, 'b': 2})  
print(bd)                     # {'a': 1, 'b': 2}                 
print(bd.inverse)             # {1: ['a'], 2: ['b']}
bd['c'] = 1                   # Now two keys have the same value (= 1)
print(bd)                     # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse)             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd)                     # {'a': 1, 'b': 2}
print(bd.inverse)             # {1: ['a'], 2: ['b']}
del bd['a']
print(bd)                     # {'b': 2}
print(bd.inverse)             # {2: ['b']}
bd['b'] = 3
print(bd)                     # {'b': 3}
print(bd.inverse)             # {2: [], 3: ['b']}