How to have multimap functionality in Java?

Question

I want to have the functionality of MultiMap in Java, providing the same functionality as that of cpp MultiMap so that I am able to have multiple keys with the same value. Multiple elements in the container can have equivalent keys. I thought this will work :

TreeMap<Key, TreeMap<Key, Value> >. 

Any help is appreciated.

Answer 1

The Answer by Vivin Paliath is correct. I’ll add more information, and more code.

Map#computeIfAbsent

To pair multiple values with one key, use collection as the value type. Often the collection is a List or Set. Or perhaps a Map for more complicated structures.

As an example, suppose we want to track which employees are going to be working on which days of the week.

We define Employee as a record.

record Employee( int empNum , String name ) { }

Make some sample data.

Employee alice = new Employee( 1 , "Alice" );
Employee bob = new Employee( 2 , "Bob" );
Employee carol = new Employee( 3 , "Carol" );

Each employee maps to a set of day-of-week values. For day-of-week, we can use enum objects defined on java.time.DayOfWeek. So we need a Map < Employee, Set < DayOfWeek > >.

Map < Employee, Set < DayOfWeek > > workDaysForEachEmployee = new HashMap <>();

Suppose we want to assign Monday to Alice.

In earlier Java

Here is the old way to make that assignment. We try to retrieve an existing collection value. We do a null-check to see if indeed there was an existing collection value. If so, we add to it, and put it back into map. If not, we instantiate a new collection, add to it, and put it into map.

Set < DayOfWeek > assignedDays = workDaysForEachEmployee.get( alice );
if ( null == assignedDays )
{
    assignedDays = EnumSet.noneOf( DayOfWeek.class );
}
assignedDays.add( DayOfWeek.MONDAY );
workDaysForEachEmployee.put( alice , assignedDays );

When run.

workDaysForEachEmployee.toString() = {Employee[empNum=1, name=Alice]=[MONDAY]}

In modern Java 8+

Modern Java brought lambdas, a compact way of passing code as an argument.

We can use lambdas and other new Java 8 functionality to reduce that code seen above to a single line.

We call Map#computeIfAbsent. In that call we pass a lambda. The lambda creates a collection in which to hold values. If the map already has an entry with our desired collection, the lambda is not executed. One way or another, that computeIfAbsent method returns a collection value, a Set< DayOfWeek > in our case.

• If the collection value exists (has already been mapped to a key), the value is returned. In our case, if the employee has already been put into the map with a set of days, that set is retrieved and returned.
• If the collection value does not exist, a new collection is instantiated and returned.

In either case, pre-existing or freshly instantiated, we end up with a set in which to add our DayOfWeek object for the alice key.

workDaysForEachEmployee
        .computeIfAbsent( alice , ( x -> EnumSet.noneOf( DayOfWeek.class ) ) )  // Returns a `Set< DayOfWeek >`, either a retrieved existing set, or a fresh new set. 
        .add( DayOfWeek.MONDAY );

workDaysForEachEmployee.toString() = {Employee[empNum=1, name=Alice]=[MONDAY]}

In that code above we instantiate a new collection by calling EnumSet.noneOf( DayOfWeek.class ). The EnumSet class is an implementation of Set that is highly optimized for containing enum objects, using very little memory, and very fast to execute. If you were using another type, such as a List you might use new ArrayList<>().

Answer 2

I think in this case guava BiMap is the best option. Since you don't want to use it then you may create own collection - TwoWayHashMap something like this:

public class TwoWayHashmap<K extends Object, V extends Object> {

  private Map<K,V> forward = new Hashtable<K, V>();
  private Map<V,K> backward = new Hashtable<V, K>();

  public synchronized void add(K key, V value) {
    forward.put(key, value);
    backward.put(value, key);
  }

  public synchronized V getForward(K key) {
    return forward.get(key);
  }

  public synchronized K getBackward(V key) {
    return backward.get(key);
  }
}

Visit the attached link for more details.

Answer 3

If you want consistent semantics, you would have to roll your own. The easiest way to implement it would be to back it by a Map<K, List<V>>. This way you can map one key to multiple values.

However, there are some things you need to consider regarding semantics. For example, assume you have the following multimap:

a -> [1, 2, 3]
b -> [4, 5]

The size of the above will be reported as 2, but could be interpreted as 5 also, if you consider that the Map can be represented as so:

a -> 1
a -> 2
a -> 3
b -> 4
b -> 5

This has implications for the values that you return as well. It would make more sense to return [1, 2, 3, 4, 5] and not [[1, 2, 3], [4, 5]]. This would also apply to the entry set; you may want to return pairs as displayed above.

Hence a possible implementation would be to implement Map<K, V> and use a backing Map<K, List<V>>. You would then have to implement the various methods while adhering to the multimap semantic.

If you don't care about the semantics but just want an ability to map a single key to multiple values, you can just use a Map<K, List<V>> directly and still get what you need.