Invert a Map with redundant values to produce a multimap

Question

Given a map such as this where we have a frequency count per day-of-week for a year:

Map.of(
    DayOfWeek.MONDAY , 52 ,
    DayOfWeek.TUESDAY , 52 ,
    DayOfWeek.WEDNESDAY, 53 ,
    DayOfWeek.THURSDAY , 53 ,
    DayOfWeek.FRIDAY , 52 ,
    DayOfWeek.SATURDAY , 52 ,
    DayOfWeek.SUNDAY , 52 
)

…or as text:

{MONDAY=52, TUESDAY=52, WEDNESDAY=53, THURSDAY=53, FRIDAY=52, SATURDAY=52, SUNDAY=52}

…how can I invert to produce a multimap of distinct numbers each leading to a collection (list? set?) of the DayOfWeek which owned that number?

The result should be equivalent to the result of this code:

Map.of(
    53 , List.of( DayOfWeek.WEDNESDAY , DayOfWeek.THURSDAY ) ,
    52 , List.of( DayOfWeek.MONDAY , DayOfWeek.TUESDAY , DayOfWeek.FRIDAY , DayOfWeek.SATURDAY , DayOfWeek.SUNDAY ) 
)

I would like to produce the resulting multimap using straight Java without extra libraries such as Eclipse Collections or Google Guava. Those libraries might make this easier, but I am curious to see if a solution using only built-in Java is possible. Otherwise, my Question here is the exact same Question as Guava: construct a Multimap by inverting a Map. Given new streams and multimap features in modern Java, I expect this is possible now while it was not then.

I saw various existing Questions similar to this. But none fit my situation, which seems like a rather common situation. For example, this Question neglects the issue of the original values being redundant/multiple, thus necessitating a multimap as a result. Others such as this or this involve Google Guava.

This might help https://stackoverflow.com/questions/53986939/collectors-groupby-for-mapstring-liststring — Marc, Dec 28 '20 at 07:26

Donald Raab · Accepted Answer · 2020-12-28T23:20:05.423

The following works using Java 9 or above:

@Test
void invertMap()
{
    Map<DayOfWeek, Integer> map = Map.of(
            DayOfWeek.MONDAY, 52,
            DayOfWeek.TUESDAY, 52,
            DayOfWeek.WEDNESDAY, 53,
            DayOfWeek.THURSDAY, 53,
            DayOfWeek.FRIDAY, 52,
            DayOfWeek.SATURDAY, 52,
            DayOfWeek.SUNDAY, 52
    );

    Map<Integer, Set<DayOfWeek>> flipped = new TreeMap<>();
    map.forEach((dow, count) ->
            flipped.computeIfAbsent(count, (key) ->
                    EnumSet.noneOf(DayOfWeek.class)).add(dow));

    Map<Integer, Set<DayOfWeek>> flippedStream = map.entrySet().stream()
           .collect(Collectors.groupingBy(
                    Map.Entry::getValue, 
                    TreeMap::new,
                    Collectors.mapping(
                            Map.Entry::getKey,
                            Collectors.toCollection(
                                    () -> EnumSet.noneOf(DayOfWeek.class)))));

    Map<Integer, Set<DayOfWeek>> expected = Map.of(
            53, EnumSet.of(
                    DayOfWeek.WEDNESDAY, 
                    DayOfWeek.THURSDAY),
            52, EnumSet.of(
                    DayOfWeek.MONDAY, 
                    DayOfWeek.TUESDAY, 
                    DayOfWeek.FRIDAY, 
                    DayOfWeek.SATURDAY, 
                    DayOfWeek.SUNDAY)
    );
    Assert.assertEquals(expected, flipped);
    Assert.assertEquals(expected, flippedStream);
}

If you are open to using a third-party library, the following code will work with Eclipse Collections:

@Test
void invertEclipseCollectionsMap()
{
    MutableMap<DayOfWeek, Integer> map =
            Maps.mutable.<DayOfWeek, Integer>empty()
                    .withKeyValue(DayOfWeek.MONDAY, 52)
                    .withKeyValue(DayOfWeek.TUESDAY, 52)
                    .withKeyValue(DayOfWeek.WEDNESDAY, 53)
                    .withKeyValue(DayOfWeek.THURSDAY, 53)
                    .withKeyValue(DayOfWeek.FRIDAY, 52)
                    .withKeyValue(DayOfWeek.SATURDAY, 52)
                    .withKeyValue(DayOfWeek.SUNDAY, 52);

    SetMultimap<Integer, DayOfWeek> flipped = map.flip();

    Assert.assertEquals(flipped.get(52), Set.of(
            DayOfWeek.MONDAY,
            DayOfWeek.TUESDAY,
            DayOfWeek.FRIDAY,
            DayOfWeek.SATURDAY,
            DayOfWeek.SUNDAY));
    Assert.assertEquals(flipped.get(53), Set.of(
            DayOfWeek.WEDNESDAY,
            DayOfWeek.THURSDAY));
}

Note: I am a committer for Eclipse Collections.

Good stuff. Two points: (a) `new TreeMap<>()` works a bit better than `new HashMap<>()` since it puts the numbers (the new keys) in order. (b) Is there a way to use [`EnumSet`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/EnumSet.html) rather than `HashSet` since [`DayOfWeek`](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/time/DayOfWeek.html) is an enum? The problem is that `EnumSet` class does not offer a constructor. I tried `EnumSet.noneOf` but got error "method noneOf in class EnumSet cannot be applied to given types;". — Basil Bourque, Dec 28 '20 at 07:30
Good enough, thanks. I was just curious about trying to shoehorn the `EnumSet` factory methods into streams syntax. — Basil Bourque, Dec 28 '20 at 07:42
I'm working on a stream example for this, mostly out of my own curiosity now because I know it's possible. I am the creator of the Eclipse Collections framework, which also has methods to flip Map to Multimap built in, so doing this in plain Java code is a good Streams refresher for me. — Donald Raab, Dec 28 '20 at 07:47
I thought your name was familiar. But I didn't recognize you with the mask on. Feel free to append an example of the *Eclipse Collections* solution. I'm not against Google Guava or Eclipse Collections, I was just curious if a bulit-in Java solution is possible. — Basil Bourque, Dec 28 '20 at 07:56
I added the Stream version so you can compare. I changed the Map from HashMap to TreeMap and included EnumSet in both solutions. I'll see if I can find some time tomorrow to append an Eclipse Collections solution. — Donald Raab, Dec 28 '20 at 08:04

chrylis -cautiouslyoptimistic- · Answer 2 · 2020-12-28T07:35:10.020

1

With streams, you can split a map into its entries, then flip the entries and group:

numberOfDaysInYear.entrySet().stream()
  .collect(groupingBy(Map.Entry::getValue), mapping(Map.Entry::getKey, toList()));

Based on your updated comments asking for optimization not actually in your original question,

numberOfDaysInYear.entrySet().stream()
  .collect(groupingBy(
    Map.Entry::getValue,
    TreeMap::new,
    mapping(Map.Entry::getKey, toCollection(() -> EnumSet.of(DayOfWeek.class)))
  ));

edited Dec 28 '20 at 07:35

answered Dec 28 '20 at 07:28

chrylis -cautiouslyoptimistic-

75,269
21
115
152

Actually, the original Question specifically states that the multimap value could be any collection, list or set. So both your solutions work. Thanks. – Basil Bourque Dec 28 '20 at 07:49

score 1 · Answer 3 · edited Jan 02 '21 at 19:15

`Collectors.toMap`

In this case you can use method Collectors.toMap(keyMapper,valueMapper,mergeFunction) and produce multimap where the value can be a list or a set:

Multimap value is a List:

Map<Integer, List<DayOfWeek>> inverted = map.entrySet().stream()
        .collect(Collectors.toMap(
                // key of the new map
                entry -> entry.getValue(),
                // value of the new map
                entry -> List.of(entry.getKey()),
                // merging two values, i.e. lists
                (list1, list2) -> {
                    List<DayOfWeek> list = new ArrayList<>();
                    list.addAll(list1);
                    list.addAll(list2);
                    return list;
                }));

Multimap value is a Set:

Map<Integer, Set<DayOfWeek>> inverted = map.entrySet().stream()
        .collect(Collectors.toMap(
                // key of the new map
                entry -> entry.getValue(),
                // value of the new map
                entry -> Set.of(entry.getKey()),
                // merging two values, i.e. sets
                (set1, set2) -> {
                    Set<DayOfWeek> set = new HashSet<>();
                    set.addAll(set1);
                    set.addAll(set2);
                    return set;
                }));

^{See also: Collect a list of ids based on multiple fields}

score 0 · Answer 4 · edited Jan 03 '21 at 12:49

Please refer below code:

@Test
void testMap() {
    Map<DayOfWeek, Integer> map = new HashMap<>();
    map.put(DayOfWeek.MONDAY, 52);
    map.put(DayOfWeek.TUESDAY, 52);
    map.put(DayOfWeek.WEDNESDAY, 53);
    map.put(DayOfWeek.THURSDAY, 53);
    map.put(DayOfWeek.FRIDAY, 52);
    map.put(DayOfWeek.SATURDAY, 52);
    map.put(DayOfWeek.SUNDAY, 52);

    Map<Integer, List<DayOfWeek>> result = new HashMap<>();

    for (Map.Entry<DayOfWeek, Integer> entry : map.entrySet()) {
        if (result.containsKey(entry.getValue())) {
            List list = result.get(entry.getValue());
            list.add(entry.getKey());
            result.put(entry.getValue(), list);
        } else {
            List list = new ArrayList();
            list.add(entry.getKey());
            result.put(entry.getValue(), list);
        }
    }
    System.out.println(result);
}

Invert a Map with redundant values to produce a multimap

4 Answers4

`Collectors.toMap`

Linked