java-map-duplicate-keys
How to Store Duplicate Keys in a Map in Java?
1. Overview
2. Standard Maps
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
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
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
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");
5.2. Forging Our Custom MultiMap
However, we may want to decorate a Map and/or a List not yet implemented.
Luckily, Guava has a factory method allowing us to do it: the Multimap.newMultimap().
6. Conclusion
We’ve explored the most popular implementations of Apache Commons Collections and Guava, which should be preferred to custom solutions when possible.
As always, the full source code is available over on Github.