How to Store Duplicate Keys in a Map in Java?

Last updated: January 8, 2024

Written by: Andrea Ligios

Java Map

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Distributed systems often come with complex challenges such as service-to-service communication, state management, asynchronous messaging, security, and more.

Dapr (Distributed Application Runtime) provides a set of APIs and building blocks to address these challenges, abstracting away infrastructure so we can focus on business logic.

In this tutorial, we'll focus on Dapr's pub/sub API for message brokering. Using its Spring Boot integration, we'll simplify the creation of a loosely coupled, portable, and easily testable pub/sub messaging system:

>> Flexible Pub/Sub Messaging With Spring Boot and Dapr

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