Two Way/Reverse Map

Two way/reverse map

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.

Is there a better way to store a twoway dictionary than storing its inverse separate?

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).

How to create a 2 way map in java

It seems like you may be looking for a bimap.

The Google Collections (now a part of Guava) contains an BiMap interface with a few implementations.

From the BiMap documentation:

A bimap (or "bidirectional map") is a
map that preserves the uniqueness of
its values as well as that of its
keys. This constraint enables bimaps
to support an "inverse view", which is
another bimap containing the same
entries as this bimap but with
reversed keys and values.

The BiMap.inverse method appears to return a Map with the values as the keys, and the keys as the values, so that Map can be used to call get on the value and retrieve a key.

In addition the Map returned by inverse is a view of the underlying data, so it does not have to make extra copies of the original data.

From the BiMap.inverse method documentation:

Returns the inverse view of this
bimap, which maps each of this bimap's
values to its associated key. The two
bimaps are backed by the same data;
any changes to one will appear in the
other.

How can I create a two-way mapping in JavaScript, or some other way to swap out values?

Use two objects. One object contains the * -> _asterisk_ mapping, the other object contains _asterisk_ -> *.

var forwardMap = {'*': '__asterisk__', '%': '__percent__', ...};
var reverseMap = {};
for (var key in forwardMap) {
    if (forwardMap.hasOwnProperty(key)) {
        reverseMap[forwardMap[key]] = key;
    }
}

Two-way / bidirectional Dictionary in C#?

I wrote a quick couple of classes that lets you do what you want. You'd probably need to extend it with more features, but it is a good starting point.

The use of the code looks like this:

var map = new Map<int, string>();

map.Add(42, "Hello");

Console.WriteLine(map.Forward[42]);
// Outputs "Hello"

Console.WriteLine(map.Reverse["Hello"]);
//Outputs 42

Here's the definition:

public class Map<T1, T2>
{
    private Dictionary<T1, T2> _forward = new Dictionary<T1, T2>();
    private Dictionary<T2, T1> _reverse = new Dictionary<T2, T1>();

    public Map()
    {
        this.Forward = new Indexer<T1, T2>(_forward);
        this.Reverse = new Indexer<T2, T1>(_reverse);
    }

    public class Indexer<T3, T4>
    {
        private Dictionary<T3, T4> _dictionary;
        public Indexer(Dictionary<T3, T4> dictionary)
        {
            _dictionary = dictionary;
        }
        public T4 this[T3 index]
        {
            get { return _dictionary[index]; }
            set { _dictionary[index] = value; }
        }
    }

    public void Add(T1 t1, T2 t2)
    {
        _forward.Add(t1, t2);
        _reverse.Add(t2, t1);
    }

    public Indexer<T1, T2> Forward { get; private set; }
    public Indexer<T2, T1> Reverse { get; private set; }
}

Injective two-way mappings

The net answer to your question is: NO (for any efficient implementation)

You put up two requirements that can not be fulfilled at the same time:

1. Do not use extra memory for the reverse mapping
2. Do not add extra time for doing (reverse) look-ups

Why are those two restrictions prohibiting a solution?

Mappings are pairs of values (tuples).
The most trivial implementation would be:

Sequential searching all tuples for a match.

This would have identical complexity for forward and backward mapping.

However, this clearly violates the expectation of time-complexity properties you expect from dictionaries:

If you would allow for O(n) complexity, then searching a tuple set sequentially would give you a proper solution.

Usually dictionary implementations try to get down to O(1) or at least O(n*log(n)) complexity. This is being achieved by introducing additional data for speeding up look-ups, like hashes or trees. Unfortunately, such aids only help for one direction as they either deal with keys (forward mapping case) or values (reverse mapping case).

So, as soon as you need to keep look-up complexity down (this also applies for modification complexity, but usually dictionaries are tailored towards fast look-up), you will need to add data for achieving speed.

The whole issue turns down to the classic memory vs. speed trade-off.

EDIT:

An approach for addressing the problem in a general implementation (for cases where keys and values allow for getting a numeric representant if those are not integral numbers in the first place) might be:

Calculate a hash value for key and one for value and register the tuple under both hash values. This way you can take key or value and identify the matching tuple and return the proper result. This would even work for non injective cases when you allow for returning sets of matching tuples.

This will require more space (double the hash entries) while keeping look-up complexity within values typical for hash based dicts. You might need to keep an eye on hash bucket size (length of collision chains) especially when value sets of keys and values are not disjoint)

Does Java have a HashMap with reverse lookup?

There is no such class in the Java API. The Apache Commons class you want is going to be one of the implementations of BidiMap.

As a mathematician, I would call this kind of structure a bijection.

Reverse / invert a dictionary mapping

Python 3+:

inv_map = {v: k for k, v in my_map.items()}

Python 2:

inv_map = {v: k for k, v in my_map.iteritems()}

---

Related Topics