How to implement an efficient bidirectional hash table?

by

Here is a class for a bidirectional dict, inspired by Finding key from value in Python dictionary and modified to allow the following 2) and 3).

Note that :

    1. The inverse directory bd.inverse auto-updates itself when the standard dict bd is modified.
    1. The inverse directory bd.inverse[value] is always a list of key such that bd[key] == value.
    1. Unlike the bidict module from https://pypi.python.org/pypi/bidict, here we can have 2 keys having same value, this is very important.

Code:

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)

Usage example:

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

More Related Contents:

  1. What’s a correct and good way to implement __hash__()?
  2. Is a Python dictionary an example of a hash table?
  3. Improving performance of very large dictionary in Python
  4. ValueError: Tensor must be from the same graph as Tensor with Bidirectinal RNN in Tensorflow
  5. Not all arguments converted error in python string format
  6. python program doesn’t work
  7. Why does this iterative list-growing code give IndexError: list assignment index out of range?
  8. Django dynamic model fields
  9. How to get the caller’s method name in the called method?
  10. Removing white space around a saved image
  11. Python app does not print anything when running detached in docker
  12. Run a .bat file using python code
  13. Building Python with SSL support in non-standard location
  14. List attributes of an object [duplicate]
  15. matplotlib (equal unit length): with ‘equal’ aspect ratio z-axis is not equal to x- and y-
  16. Python urllib2, basic HTTP authentication, and tr.im
  17. Basic Python client socket example
  18. How to display an image after a time interval?
  19. How to add noise (Gaussian/salt and pepper etc) to image in Python with OpenCV [duplicate]
  20. pandas – get most recent value of a particular column indexed by another column (get maximum value of a particular column indexed by another column)
  21. Python: import module from another directory at the same level in project hierarchy
  22. Cropping pages of a .pdf file
  23. Dynamic Class Creation in SQLAlchemy
  24. Nested Dictionary to MultiIndex pandas DataFrame (3 level)
  25. Definition of def, cdef and cpdef in cython
  26. Python get proper line ending
  27. Elegant way to remove items from sequence in Python? [duplicate]
  28. Why are python static/class method not callable?
  29. Plotting time on the independent axis
  30. Why Python `Memory Error` with list `append()` lots of RAM left

Leave a Comment