Find Map Keys with Duplicate Values in Java

1. Overview

Map is an efficient structure for key-value storage and retrieval.

In this tutorial, we’ll explore different approaches to finding map keys with duplicate values in a Set. In other words, we aim to transform a Map<K, V> to a Map<V, Set<K>>.

2. Preparing the Input Examples

Let’s consider a scenario where we possess a map that stores the association between developers and the operating systems they primarily work on:

Map<String, String> INPUT_MAP = Map.of(
  "Kai", "Linux",
  "Eric", "MacOS",
  "Kevin", "Windows",
  "Liam", "MacOS",
  "David", "Linux",
  "Saajan", "Windows",
  "Loredana", "MacOS"
);

Now, we aim to find the keys with duplicate values, grouping different developers that use the same operating system in a Set:

Map<String, Set<String>> EXPECTED = Map.of(
  "Linux", Set.of("Kai", "David"),
  "Windows", Set.of("Saajan", "Kevin"),
  "MacOS", Set.of("Eric", "Liam", "Loredana")
);

While we primarily handle non-null keys and values, it’s worth noting that HashMap allows both null values and one null key. Therefore, let’s create another input based on INPUT_MAP to cover scenarios involving null keys and values:

Map<String, String> INPUT_MAP_WITH_NULLS = new HashMap<String, String>(INPUT_MAP) {{
    put("Tom", null);
    put("Jerry", null);
    put(null, null);
}};

As a result, we expect to obtain the following map:

Map<String, Set<String>> EXPECTED_WITH_NULLS = new HashMap<String, Set<String>>(EXPECTED) {{
    put(null, new HashSet<String>() {{
        add("Tom");
        add("Jerry");
        add(null);
    }});
}};

We’ll address various approaches in this tutorial. Next, let’s dive into the code.

3. Prior to Java 8

In our first idea to solve the problem, we  initialize an empty HashMap<V, Set<K>> and populate it using in a classic for-each loop:

static <K, V> Map<V, Set<K>> transformMap(Map<K, V> input) {
    Map<V, Set<K>> resultMap = new HashMap<>();
    for (Map.Entry<K, V> entry : input.entrySet()) {
        if (!resultMap.containsKey(entry.getValue())) {
            resultMap.put(entry.getValue(), new HashSet<>());
        }
        resultMap.get(entry.getValue())
          .add(entry.getKey());
    }
    return resultMap;
}

As the code shows, transformMap() is a generic method. Within the loop, we use each entry’s value as the key for the resultant map and collect values associated with the same key into a Set.

transformMap() does the job no matter whether the input map contains null keys or values:

Map<String, Set<String>> result = transformMap(INPUT_MAP);
assertEquals(EXPECTED, result);
 
Map<String, Set<String>> result2 = transformMap(INPUT_MAP_WITH_NULLS);
assertEquals(EXPECTED_WITH_NULLS, result2);

4. Java 8

Java 8 brought forth a wealth of new capabilities, simplifying collection operations with tools like the Stream API. Furthermore, it enriched the Map interface with additions such as computeIfAbsent().

In this section, we’ll tackle the problem using the functionalities introduced in Java 8.

4.1. Using Stream with groupingBy()

The groupingBy() collector, which ships with the Stream API, allows us to group stream elements based on a classifier function, storing them as lists under corresponding keys in a Map.

Hence, we can construct a stream of Entry<K, V> and employ groupingBy() to collect the stream into a Map<V, List<K>>. This aligns closely with our requirements. The only remaining step is converting the List<K> into a Set<K>.

Next, let’s implement this idea and see how to convert List<K> to a Set<K>:

Map<String, Set<String>> result = INPUT_MAP.entrySet()
  .stream()
  .collect(groupingBy(Map.Entry::getValue, mapping(Map.Entry::getKey, toSet())));
assertEquals(EXPECTED, result);

As we can see in the above code, we used the mapping() collector to map the grouped result (List) to a different type (Set).

Compared to our transformMap() solution, the groupingBy() approach is easier to read and understand. Furthermore, as a functional solution, this approach allows us to apply further operations fluently.

However, the groupingBy() solution raises NullPointerException when it transforms our INPUT_MAP_WITH_NULLS input:

assertThrows(NullPointerException.class, () -> INPUT_MAP_WITH_NULLS.entrySet()
  .stream()
  .collect(groupingBy(Map.Entry::getValue, mapping(Map.Entry::getKey, toSet()))));

This is because groupingBy() cannot handle null keys:

public static <T, K, D, A, M extends Map<K, D>> 
  Collector<T, ?, M> groupingBy(Function<? super T, ? extends K> classifier,...){
...
    BiConsumer<Map<K, A>, T> accumulator = (m, t) -> {
        K key = Objects.requireNonNull(classifier.apply(t), "element cannot be mapped to a null key");
...
}

Next, let’s see if we can build a solution for both non-null and nullable keys or values.

4.2. Using forEach() and computeIfAbsent()

Java 8’s forEach() provides a concise way to iterate collections. computeIfAbsent() computes a new value for a specified key if the key is not already associated with a value or is mapped to null.

Next, let’s combine these two methods to solve our problem:

Map<String, Set<String>> result = new HashMap<>();
INPUT_MAP.forEach((key, value) -> result.computeIfAbsent(value, k -> new HashSet<>())
  .add(key));
assertEquals(EXPECTED, result);

This solution follows the same logic as transformMap(). However, with the power of Java 8, the implementation is more elegant and compact.

Furthermore, the forEach() + computeIfAbsent() solution works with maps containing null keys or values:

Map<String, Set<String>> result2 = new HashMap<>();
INPUT_MAP_WITH_NULLS.forEach((key, value) -> result2.computeIfAbsent(value, k -> new HashSet<>())
  .add(key));
assertEquals(EXPECTED_WITH_NULLS, result2);

5. Leveraging Guava Multimap

Guava, a widely used library, offers the Multimap interface, enabling the association of a single key with multiple values.

Now, let’s develop solutions based on Multimaps to address our problem.

5.1. Using Stream API and a Multimap Collector

We’ve seen how the Java Stream API empowers us to craft compact, concise, and functional implementations. Guava provides Multimap collectors, such as Multimaps.toMultimap(), that allow us to collect elements from a stream into a Multimap conveniently.

Next, let’s see how to combine a stream and Multimaps.toMultimap() to solve the problem:

Map<String, Set<String>> result = INPUT_MAP.entrySet()
  .stream()
  .collect(collectingAndThen(Multimaps.toMultimap(Map.Entry::getValue, Map.Entry::getKey, HashMultimap::create), Multimaps::asMap));
assertEquals(EXPECTED, result);

The toMultimap() method takes three arguments:

• A Function to get key
• A Function to get value
• Multimap Supplier – Provide a Multimap object. In this example, we used HashMultimap to obtain a SetMultimap.

Thus, toMultimap() collect Map.Entry<K, V> objects into a SetMultimap<V, K>. Then, we employed collectingAndThen() to perform Multimaps.asMap() to convert the collected SetMultimap<V, K> to a Map<V, Set<K>>.

This approach works with maps holding null keys or values:

Map<String, Set<String>> result2 = INPUT_MAP_WITH_NULLS.entrySet()
  .stream()
  .collect(collectingAndThen(Multimaps.toMultimap(Map.Entry::getValue, Map.Entry::getKey, HashMultimap::create), Multimaps::asMap));
assertEquals(EXPECTED_WITH_NULLS, result2);

5.2. Using invertFrom() and forMap()

Alternatively, we can use Multimaps.invertFrom() and Multimaps.forMap() to achieve our goal:

SetMultimap<String, String> multiMap = Multimaps.invertFrom(Multimaps.forMap(INPUT_MAP), HashMultimap.create());
Map<String, Set<String>> result = Multimaps.asMap(multiMap);
assertEquals(EXPECTED, result);
 
SetMultimap<String, String> multiMapWithNulls = Multimaps.invertFrom(Multimaps.forMap(INPUT_MAP_WITH_NULLS), HashMultimap.create());
Map<String, Set<String>> result2 = Multimaps.asMap(multiMapWithNulls);
assertEquals(EXPECTED_WITH_NULLS, result2);

The forMap() method returns a Multimap<K, V> view of the specified Map<K, V>. Subsequently, as the name implies, invertFrom() converts the Multimap<K, V> view to a Multimap<V, K> and transfers it to the target Multimap provided as the second argument. Finally, we use Multimaps.asMap() again to convert Multimap<V, K> to Map<V, Set<K>>.

Also, as we can see, this approach works maps with null keys or values.

6. Conclusion

In this article, we’ve explored various ways to find map keys with duplicate values in a Set, including a classic loop-based solution, Java 8-based solutions, and approaches using Guava.