효율적인 양방향 해시 테이블 구현

양방향 해시 테이블은 키 대 값 조회와 값 대 키 조회를 모두 허용합니다. Python의 내장 dict 데이터 구조는 키-값 조회에 탁월하지만 효율적인 값-키 검색을 제공하지 않습니다.

양방향 해시 테이블을 구현하는 효과적인 방법은 클래스를 활용하는 것입니다. 그것은 표준 사전을 확장합니다. biddict라는 이 클래스는 일반 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)는 값을 매핑하는 사전입니다. 해당 값을 가진 키 목록입니다.
• 입찰이 수정되면 역방향 디렉터리가 자동으로 업데이트됩니다.
• 일부 입찰 구현과 달리 이 클래스는 여러 키가 동일한 값을 가질 수 있도록 허용합니다.

사용 예:

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