Is there a better way to store a twoway dictionary

Question

This question already has answers here:

How to implement an efficient bidirectional hash table? (6 answers)

Closed 6 years ago.

Given a one-to-one dictionary (=bijection) generated à la

for key, value in someGenerator:
     myDict[key] = value

an inverse lookup dictionary can be trivially created by adding

    invDict[value] = key

to the for loop. But is this a Pythonic way? Should I instead write a class Bijection(dict) which manages this inverted dictionary in addition and provides a second lookup function? Or does such a structure (or a similar one) already exist?

Answer 1

if you want O(log(n)) time for accessing values, you will need both a representation of the map and a representation of the inverse map.

otherwise the best you can do is O(log(n)) in one direction and O(n) in the other.

Edit: not O(log(n)), thanks Claudiu, but you are still going to need two data structures to implement the quick access times. And this will be more or less the same space as a dict and an inverse dict.

Answer 2

What I've done in the past is created a reversedict function, which would take a dict and return the opposite mapping, either values to keys if I knew it was one-to-one (throwing exceptions on seeing the same value twice), or values to lists of keys if it wasn't. That way, instead of having to construct two dicts at the same time each time I wanted the inverse look-up, I could create my dicts as normal and just call the generic reversedict function at the end.

However, it seems that the bidict solution that Jon mentioned in the comments is probably the better one. (My reversedict function seems to be his bidict's ~ operator).