Implementando uma tabela hash bidirecional eficiente

Uma tabela hash bidirecional permite pesquisas de chave para valor e de valor para chave. Embora a estrutura de dados dict integrada do Python seja excelente em pesquisas de chave para valor, ela não oferece recuperações eficientes de valor para chave.

Um método eficaz para implementar uma tabela hash bidirecional é utilizar uma classe que estende o ditado padrão. Esta classe, chamada bidict, mantém um diretório inverso que é atualizado automaticamente com quaisquer modificações no dict regular.

Implementação de código:

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)

Principais recursos:

• O diretório inverso (bd.inverse) é um dicionário que mapeia valores para uma lista de chaves com esse valor.
• O diretório inverso é atualizado automaticamente quando o bidict é modificado.
• Ao contrário de algumas implementações de bidict, esta classe permite que várias chaves tenham o mesmo valor.

Exemplo de uso:

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