How to Store Duplicate Keys in a Map in Java?

Table of Contents

1. Overview
2. Standard Maps
3. Collection as Value
4. Apache Commons Collections
- 4.1. MultiMap
- 4.2. MultiValuedMap
5. Guava Multimap
- 5.1. Common Map Implementations
- 5.2. Forging Our Custom MultiMap
6. Conclusion

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 which 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, etcetera.

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");

While this is something worth knowing, we should avoid it unless having a very good reason not to, like restrictive company policies preventing us from using third-party libraries.

Otherwise, before writing our own custom Map implementation and reinvent 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.1</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.

The com.google.common.collect.Multimap interface is there since version 2. At the time of writing the latest release is the 25, but since after version 23 it’s been split in different branches for jre and android (25.0-jre and 25.0-android), we’ll still use version 23 for our examples.

Let’s start by importing Guava on our project:

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>23.0</version>
</dependency>

Guava followed the path of the 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 probably Guava has 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");