How to Store Duplicate Keys in a Map in Java?

1. Overview

In this tutorial, we’re going to explore the available options for handling a Map with duplicate keys or, in other words, a Map that allows storing multiple values for a single key.

2. Standard Maps

Java has several implementations of the interface Map, each one with its own particularities.

However, none of the existing Java core Map implementations allow a Map to handle multiple values for a single key.

As we can see, if we try to insert two values for the same key, the second value will be stored, while the first one will be dropped.

It will also be returned (by every proper implementation of the put(K key, V value) method):

Map<String, String> map = new HashMap<>();
assertThat(map.put("key1", "value1")).isEqualTo(null);
assertThat(map.put("key1", "value2")).isEqualTo("value1");
assertThat(map.get("key1")).isEqualTo("value2");

How can we achieve the desired behavior, then?

3. Collection as Value

Obviously, using a Collection for every value of our Map would do the job:

Map<String, List<String>> map = new HashMap<>();
List<String> list = new ArrayList<>();
map.put("key1", list);
map.get("key1").add("value1");
map.get("key1").add("value2");
 
assertThat(map.get("key1").get(0)).isEqualTo("value1");
assertThat(map.get("key1").get(1)).isEqualTo("value2");

However, this verbose solution has multiple drawbacks and is prone to errors. It implies that we need to instantiate a Collection for every value, check for its presence before adding or removing a value, delete it manually when no values are left, etc.

From Java 8, we could exploit the compute() methods and improve it:

Map<String, List<String>> map = new HashMap<>();
map.computeIfAbsent("key1", k -> new ArrayList<>()).add("value1");
map.computeIfAbsent("key1", k -> new ArrayList<>()).add("value2");

assertThat(map.get("key1").get(0)).isEqualTo("value1");
assertThat(map.get("key1").get(1)).isEqualTo("value2");

However, we should avoid it unless having a very good reason not to, such as restrictive company policies preventing us from using third-party libraries.

Otherwise, before writing our own custom Map implementation and reinventing the wheel, we should choose among the several options available out-of-the-box.

4. Apache Commons Collections

As usual, Apache has a solution for our problem.

Let’s start by importing the latest release of Common Collections (CC from now on):

<dependency>
  <groupId>org.apache.commons</groupId>
  <artifactId>commons-collections4</artifactId>
  <version>4.5.0-M2</version>
</dependency>

4.1. MultiMap

The org.apache.commons.collections4.MultiMap interface defines a Map that holds a collection of values against each key.

It’s implemented by the org.apache.commons.collections4.map.MultiValueMap class, which automatically handles most of the boilerplate under the hood:

MultiMap<String, String> map = new MultiValueMap<>();
map.put("key1", "value1");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .contains("value1", "value2");

While this class is available since CC 3.2, it’s not thread-safe, and it’s been deprecated in CC 4.1. We should use it only when we can’t upgrade to the newer version.

4.2. MultiValuedMap

The successor of MultiMap is the org.apache.commons.collections4.MultiValuedMap interface. It has multiple implementations ready to be used.

Let’s see how to store our multiple values into an ArrayList, which retains duplicates:

MultiValuedMap<String, String> map = new ArrayListValuedHashMap<>();
map.put("key1", "value1");
map.put("key1", "value2");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value1", "value2", "value2");

Alternatively, we could use a HashSet, which drops duplicates:

MultiValuedMap<String, String> map = new HashSetValuedHashMap<>();
map.put("key1", "value1");
map.put("key1", "value1");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value1");

Both of the above implementations are not thread-safe.

Let’s see how we can use the UnmodifiableMultiValuedMap decorator to make them immutable:

@Test(expected = UnsupportedOperationException.class)
public void givenUnmodifiableMultiValuedMap_whenInserting_thenThrowingException() {
    MultiValuedMap<String, String> map = new ArrayListValuedHashMap<>();
    map.put("key1", "value1");
    map.put("key1", "value2");
    MultiValuedMap<String, String> immutableMap =
      MultiMapUtils.unmodifiableMultiValuedMap(map);
    immutableMap.put("key1", "value3");
}

5. Guava Multimap

Guava is the Google Core Libraries for Java API.

Let’s start by importing Guava on our project:

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>31.0.1-jre</version>
</dependency>

Guava followed the path of multiple implementations since the beginning.

The most common one is the com.google.common.collect.ArrayListMultimap, which uses a HashMap backed by an ArrayList for every value:

Multimap<String, String> map = ArrayListMultimap.create();
map.put("key1", "value2");
map.put("key1", "value1");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value2", "value1");

As always, we should prefer the immutable implementations of the Multimap interface: com.google.common.collect.ImmutableListMultimap and com.google.common.collect.ImmutableSetMultimap.

5.1. Common Map Implementations

When we need a specific Map implementation, the first thing to do is check if it exists because Guava has probably already implemented it.

For example, we can use the com.google.common.collect.LinkedHashMultimap, which preserves the insertion order of keys and values:

Multimap<String, String> map = LinkedHashMultimap.create();
map.put("key1", "value3");
map.put("key1", "value1");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value3", "value1", "value2");

Alternatively, we can use a com.google.common.collect.TreeMultimap, which iterates keys and values in their natural order:

Multimap<String, String> map = TreeMultimap.create();
map.put("key1", "value3");
map.put("key1", "value1");
map.put("key1", "value2");
assertThat((Collection<String>) map.get("key1"))
  .containsExactly("value1", "value2", "value3");

5.2. Forging Our Custom MultiMap

Many other implementations are available.

However, we may want to decorate a Map and/or a List that’s not yet implemented.

Luckily, Guava has a factory method allowing us to do it — the Multimap.newMultimap().

6. Conclusion

We’ve seen how to store multiple values for a key in a Map in all the main existing ways.

We’ve explored the most popular implementations of Apache Commons Collections and Guava, which should be preferred to custom solutions when possible.