Collect into Multimap with order preserved

Question

I have a list of attributes like attr1, attr2, etc. I also have a function that takes an attribute and returns a list of prefixes.

private List<String> getAttributePrefixes(String attribute) {
 //get prefix for attribute
}

I want to create a map whose key is the prefix and value is the attribute. Since the prefix could be repeated, I want to output the result as a multimap.

So, for the example above, the output Multimap will look like:

{ 
  a = [attr1, attr2],
  at = [attr1, attr2],
  att = [attr1, attr2],
  attr = [attr1, attr2],
  attr1 = [attr1],
  attr2 = [attr2]
}

The problem I have with my code is that the order is not preserved. For example, the entries in my map look like this:

a = attr2, attr1 (I call getAttributePrefixes function first for attr1 and then attr2)

I want attr1 to come first and then attr2. Here's my code:

Multimap<String, String> multimap = attributes.stream()
                                              .map(attribute -> new AbstractMap.SimpleEntry<>(attribute, getAttributePrefixes(attribute)))
                                              .flatMap(entry -> entry.getValue()
                                                                     .stream()
                                .map(prefix -> new AbstractMap.SimpleEntry<>(prefix, entry.getKey())))
                                                      .collect(ImmutableListMultimap.toImmutableListMultimap(Map.Entry::getKey, Map.Entry::getValue));

Answer 1

The main issue is that stream usually gives no to little ordering guarantees as it was created with a parallel execution in mind. One simple option is to try out jOOλ as a drop-in replacement that was implemented for single threaded execution. It also has a nice groupBy method for your use case.

If that is not an option/working, you have to perform the grouping manually to get your ordering.

    Map<String, List<String>> multimap = attributes.stream()
        .map(attribute -> new AbstractMap.SimpleEntry<>(attribute, getAttributePrefixes(attribute)))
        .flatMap(entry -> entry.getValue()
            .stream()
            .map(prefix -> new AbstractMap.SimpleEntry<>(prefix, entry.getKey())))
        .collect(Collectors.groupingBy(Map.Entry::getKey, Collectors.mapping(Map.Entry::getValue, Collectors.toList())));

groupingBy is a non-parallel collector so it should work. You'd need to wrap the given map into a multimap though.