Bidirectional multimap equivalent data structure

Question

I know that Guava has a BiMultimap class internally but didn't outsource the code. I need a data structure which is bi-directional, i.e. lookup by key and by value and also accepts duplicates.

i.e. something like this: (in my case, values are unique, but two values can point to the same key)

0 <-> 5
1 <-> 10
2 <-> 7
2 <-> 8
3 <-> 11

I want to be able to get(7) -> returning 2 and get(2) returning [7, 8]. Is there another library out there which has a data structure I can make use of?

If not, what do you suggest is the better option to handle this case? Is keeping two Multimaps in memory one with and the other with a bad practice?

P.S.: I have read this question: Bidirectional multi-valued map in Java but considering it is dated in 2011, I thought I'll open a more recent question

Answer 1

If you don't need the whole bunch of Guava HashBiMultimap functionality, but just getByKey() and getByValue(), as you specified, I can suggest the approach, where only one HashMultiMap is used as a storage.

The idea is to treat provided key and value as equilibrium objects and put both of them in the storage map as keys and values.

For example: Let we have the following multiMap.put(0, 5), so we should get the storage map containing something like this [[key:0, value:5], [key:5, value:0]].

As far as we need our BiMultiMap to be generic, we also need to provide some wrapper classes, that should be used as storage map type parameters.

Here is this wrapper class:

public class ObjectHolder {

    public static ObjectHolder newLeftHolder(Object object) {
        return new ObjectHolder(object, false);
    }

    public static ObjectHolder newRightHolder(Object object) {
        return new ObjectHolder(object, true);
    }

    private Object object;
    private boolean flag;

    private ObjectHolder(Object object, boolean flag) {
        this.object = object;
        this.flag = flag;
    }

    public Object getObject() {

        return object;
    }

    @Override
    public boolean equals(Object o) {

        if (this == o) return true;
        if (!(o instanceof ObjectHolder)) return false;

        ObjectHolder that = (ObjectHolder) o;

        if (flag != that.flag) return false;
        if (!object.equals(that.object)) return false;

        return true;
    }

    @Override
    public int hashCode() {

        int result = object.hashCode();
        result = 31 * result + (flag ? 1 : 0);
        return result;
    }
}

And here is the MultiMap:

public class BiHashMultiMap<L, R> {

    private Map<ObjectHolder, Set<ObjectHolder>> storage;

    public SimpleBiMultiMap() {
        storage = new HashMap<ObjectHolder, Set<ObjectHolder>>();
    }

    public void put(L left, R right) {
        ObjectHolder leftObjectHolder = ObjectHolder.newLeftHolder(left);
        ObjectHolder rightObjectHolder = ObjectHolder.newRightHolder(right);

        put(leftObjectHolder, rightObjectHolder);
        put(rightObjectHolder, leftObjectHolder);
    }

    private void put(ObjectHolder key, ObjectHolder value) {
        if (!storage.containsKey(key)) {
            storage.put(key, new HashSet<ObjectHolder>());
        }
        storage.get(key).add(value);
    }

    public Set<R> getRight(L left) {
        return this.get(ObjectHolder.newLeftHolder(left));
    }

    public Set<L> getLeft(R right) {
        return this.get(ObjectHolder.newRightHolder(right));
    }

    private <V> Set<V> get(ObjectHolder key) {
        Set<ObjectHolder> values = storage.get(key);
        if (values == null || values.isEmpty()) {
            return null;
        }
        Set<V> result = new HashSet<V>();
        for (ObjectHolder value : values) {
            result.add((V)value.getObject());
        }
        return result;
    }
}

Thing that could seem strange is the left and right prefixed variable everywhere. You can think of them as left is the original key, that was putted to map and right is the value.

Usage example:

BiHashMultiMap<Integer, Integer> multiMap = new BiHashMultiMap<Integer, Integer>();

multiMap.put(0,5);
multiMap.put(1,10);
multiMap.put(2,7);
multiMap.put(3,7);
multiMap.put(2,8);
multiMap.put(3,11);

Set<Integer> left10 = multiMap.getLeft(10); // [1]
Set<Integer> left7 = multiMap.getLeft(7); // [2, 3]
Set<Integer> right0 = multiMap.getRight(0); // [5]
Set<Integer> right3 = multiMap.getRight(3); // [7, 11]

So to get left value we need to provide right value as key and to get right value we need to provide left as a key.

And of course to make map fully function we need to provide other methods, like remove(), contains() and so on.

Answer 2

What do you mean by

Guava has a BiMultimap class internally but didn't outsource the code

The code of an implementation is here.

I didn't check if this is a working implementation, nor if it made it into a release or if I'm just looking at some kind of snapshot. Everything is out in the open, so you should be able to get it.

From a quick glance at the source code it looks like the implementation does maintain two MultMaps, and this should be fine for the general case.