Implementación de una tabla hash bidireccional eficiente

Una tabla hash bidireccional permite búsquedas tanto de clave a valor como de valor a clave. Si bien la estructura de datos dict incorporada de Python sobresale en las búsquedas de clave a valor, no ofrece recuperaciones eficientes de valor a clave.

Un método eficaz para implementar una tabla hash bidireccional es utilizar una clase eso extiende el dictado estándar. Esta clase, denominada bidict, mantiene un directorio inverso que se actualiza automáticamente con cualquier modificación del dict normal.

Implementación del 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)

Características clave:

• El directorio inverso (bd.inverse) es un diccionario que asigna valores a una lista de claves con ese valor.
• El directorio inverso se actualiza automáticamente cuando se modifica el bidict.
• A diferencia de algunas implementaciones de bidict, esta clase permite que varias claves tengan el mismo valor.

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