[python] 효율적인 양방향 해시 테이블을 구현하는 방법은 무엇입니까?

다음은 Python 사전의 값에서 키 찾기dict 에서 영감을 받아 다음 2) 및 3)을 허용하도록 수정 된 양방향 클래스입니다 .

참고 :

• 1) 역 디렉토리 bd.inverse 는 표준 dict bd가 수정 되면 자동으로 업데이트됩니다 .
• 2) 역 디렉토리 bd.inverse[value] 는 항상 다음 과 key같은 목록 입니다 bd[key] == value.
• 3) https://pypi.python.org/pypi/bidict 의 bidict모듈 과 달리 여기서는 동일한 값을 가진 2 개의 키를 가질 수 있습니다 . 이것은 매우 중요 합니다.

암호:

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 = 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']}