Bidirectional Multiphase Equivalent Data Structure

Question

I know that Guava has a BiMultimap class inside, but did not outsource it. I need a data structure that is bidirectional, that is, a search by key and by value, and also accept duplicates.

i.e. something like this: (in my case, the 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) → return 2 and get(2) return [7, 8] . Is there any other library that has a data structure that I can use?

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

PS: I read this question: Bi-directional multi-valued map in Java , but considering that it is dated 2011, it seemed to me that I would open a more recent question

Answer 1

What do you mean by

Guava has a BiMultimap class inside, but it did not outsource the code

implementation code here .

I did not check if this is a working implementation, and does not turn it into a release, or if I just look at some kind of snapshot. Everything is open, so you can get it.

With a quick look at the source code, it looks like the implementation supports two MultMaps, and this should be good for the general case.

Answer 2

If you don’t need a whole bunch of Guava HashBiMultimap functions, but only getByKey () and getByValue (), as you pointed out, I can offer an approach where only one HashMultiMap is used as storage.

The idea is to consider the provided key and value as equilibrium objects and put them on the memory card as keys and values.

For example: suppose we have the following multiMap.put(0, 5) , so we should get a memory card containing something like this [[key:0, value:5], [key:5, value:0]] .

Since we need our BiMultiMap to be shared, we also need to provide some wrapper classes that should be used as parameters for the storage card type.

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; } } 

A thing that may seem strange is the variable left and right . You can think of them as left - this is the original key that was placed on the card, 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 the left value, we need to specify the right value as the key and get the right value, we need to provide left as the key.

And of course, to make the full function of the map, we need to provide other methods, such as remove() , contains() , etc.