Two way/reverse map [duplicate]

python

I'm doing this switchboard thing in python where I need to keep track of who's talking to whom, so if Alice --> Bob, then that implies that Bob --> Alice.

Yes, I could populate two hash maps, but I'm wondering if anyone has an idea to do it with one.

Or suggest another data structure.

There are no multiple conversations. Let's say this is for a customer service call center, so when Alice dials into the switchboard, she's only going to talk to Bob. His replies also go only to her.

Solution 1:

You can create your own dictionary type by subclassing dict and adding the logic that you want. Here's a basic example:

class TwoWayDict(dict):
    def __setitem__(self, key, value):
        # Remove any previous connections with these values
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)

    def __delitem__(self, key):
        dict.__delitem__(self, self[key])
        dict.__delitem__(self, key)

    def __len__(self):
        """Returns the number of connections"""
        return dict.__len__(self) // 2

And it works like so:

>>> d = TwoWayDict()
>>> d['foo'] = 'bar'
>>> d['foo']
'bar'
>>> d['bar']
'foo'
>>> len(d)
1
>>> del d['foo']
>>> d['bar']
Traceback (most recent call last):
  File "<stdin>", line 7, in <module>
KeyError: 'bar'

I'm sure I didn't cover all the cases, but that should get you started.

Solution 2:

In your special case you can store both in one dictionary:

relation = {}
relation['Alice'] = 'Bob'
relation['Bob'] = 'Alice'

Since what you are describing is a symmetric relationship. A -> B => B -> A

Solution 3:

I know it's an older question, but I wanted to mention another great solution to this problem, namely the python package bidict. It's extremely straight forward to use:

from bidict import bidict
map = bidict(Bob = "Alice")
print(map["Bob"])
print(map.inv["Alice"])

Solution 4:

I would just populate a second hash, with

reverse_map = dict((reversed(item) for item in forward_map.items()))

Solution 5:

Two hash maps is actually probably the fastest-performing solution assuming you can spare the memory. I would wrap those in a single class - the burden on the programmer is in ensuring that two the hash maps sync up correctly.