how to write this more elegantly to merge a list of maps

[Jeanne Boyarsky]

I have a bunch of Maps that map a String key to a List of Integers. I want to merge them so that I have one map with String key and the union of all those integers.

For example, suppose I have these two maps in my list:
map 1:
{
"a": [1],
"b" : [2, 3]
}

map 2:
{
"b" : [3, 4],
"c" : [5]
}

The result would be
{
"a": [1],
"b" : [2, 3,3, 4],
"c" : [5]
}


And the method signature is:

public static Map<String, List<Integer>> merge(List<Map<String, List<Integer>>> list) {
		
}

I have working code that involves two loops and the Map's compute() method.

This feels inelegant though. Is there a better way?

[Piet Souris]

A possible way, but also not very elegant, is:

public class Boyarski {
    public static void main(String... args) {
        Map<String, List<Integer>> map1 = new HashMap<>();
        map1.put("a", new ArrayList<>(List.of(1, 2, 3, 4)));
        map1.put("b", new ArrayList<>(List.of(5)));
        map1.put("c", new ArrayList<>(List.of(1,2)));
        Map<String, List<Integer>> map2 = Map.of("c", List.of(10, 11));
        List<Map<String, List<Integer>>> maps = new ArrayList<>();
        maps.add(map2);
        maps.forEach(map -> 
            map.forEach(
                (k, v) -> map1.merge(k, v, (l1, l2) -> {l1.addAll(l2); return l1;})
            )
        );
        map1.entrySet().forEach(System.out::println);
    }    
}

Beware of using the 'of' versions of Map and List: these lead to immutable lists and maps, so methods like 'merge' fail.

[salvin francis]

I did this :

public class Main {
    public static void main(String[] args) {
        Map<String, List<Integer>> m1 = new HashMap<>();
        Map<String, List<Integer>> m2 = new HashMap<>();

        m1.put("a", new ArrayList<Integer>(Arrays.asList(1)));
        m1.put("b", new ArrayList<Integer>(Arrays.asList(2, 3)));
        m2.put("b", new ArrayList<Integer>(Arrays.asList(3, 4)));
        m2.put("c", new ArrayList<Integer>(Arrays.asList(5)));

        System.out.println(m1);
        System.out.println(m2);

        Map<String, List<Integer>> merge = merge(m1, m2);
        System.out.println(merge);

    }

    public static Map<String, List<Integer>> merge(Map<String, List<Integer>> item1, Map<String, List<Integer>> item2) {
        Map<String, List<Integer>> mergedMap = new HashMap<>();

        List<Entry<String, List<Integer>>> list = new ArrayList<>();
        list.addAll(item1.entrySet());
        list.addAll(item2.entrySet());

        list.stream()
            .forEach(entry -> {
                String key = entry.getKey();
                List<Integer> value = entry.getValue();

                mergedMap.computeIfAbsent(key, K -> {
                    return value;
                });
                mergedMap.computeIfPresent(key, (K, V) -> {
                    return mergeList(value, V);
                });
            });

        return mergedMap;

    }

    private static List<Integer> mergeList(List<Integer> item1, List<Integer> item2) {
        Set<Integer> set1 = new LinkedHashSet<>();
        set1.addAll(item1);
        set1.addAll(item2);
        return new ArrayList<>(set1);
    }

}

[salvin francis]

My colleague suggested that if you are okay to modify the original map, here's a solution that changes the first map:

public class Main {
    public static void main(String[] args) {
        Map<String, List<Integer>> m1 = new HashMap<>();
        Map<String, List<Integer>> m2 = new HashMap<>();

        m1.put("a", new ArrayList<Integer>(Arrays.asList(1)));
        m1.put("b", new ArrayList<Integer>(Arrays.asList(2, 3)));
        m2.put("b", new ArrayList<Integer>(Arrays.asList(3, 4)));
        m2.put("c", new ArrayList<Integer>(Arrays.asList(5)));

        System.out.println(m1);
        System.out.println(m2);

        m2.forEach((K, V) -> {
            m1.merge(K, V, (list1, list2) -> {
                list1.addAll(list2);
                return list1;
            });
        });
        System.out.println("Merged: \n"+m1);

    }
}

[Rob Spoor]

salvin francis wrote:

public class Main {
        List<Entry<String, List<Integer>>> list = new ArrayList<>();
        list.addAll(item1.entrySet());
        list.addAll(item2.entrySet());

        list.stream()

If you want to merge to streams, you can use Stream.concat:

Stream.concat(item1.entrySet().stream(), item2.entrySet().stream())

That saves you the memory usage of the list and the time needed to add all map entries. It might not be a significant gain if your maps are small, but if they're large - oh boy!
And if you have more than two streams, you can use Stream.of, Arrays.stream or Collection.stream to create a Stream of Streams, and then flatMap it using Function.identity().

And you should consider using a Collector. I think that groupingBy in combination with the right (possibly custom) downstream Collector will give the correct results.

[Piet Souris]

I did consider (and used) a Collector. And although 'de gustibus non est disputandem', I found my merge solution more elegant. I had this: (assuming 'maps' is Jeanne's List<Map<String, List<Integer>>>)

List<Entry<String, List<Integer>>> flup = maps.stream().collect(
    () -> new ArrayList<>(), 
    (list, map) -> list.addAll(map.entrySet()), 
    (list1, list2) -> list1.addAll(list2)
);
// flup.forEach(System.out::println);
var result = flup.stream().collect(
    toMap(Entry::getKey, Entry::getValue, (a1, a2) -> {a1.addAll(a2); return a1;})
);

Interesting is that if you write 'var flup = maps.stream()...' then you get a Compiler error that Entry::getKey is incorect, and you may get a Runtime error if your maps contain unmodifiable elements (for instance if you use List.of(1, 2, 3). The errors are such that it takes a long time to figure out what is going on.

@Salvin
in your first code snippet, take care that there may be more than only two maps involved

[Michael Billiot]

Jeanne,

This was a fun exercise and very challenging. Below is what I came up with. I don't know if it is much more elegant but I finally got it to output what you were looking for.
Hopefully it would be some use to you.

The BiFunction (mergeList) at the beginning of the method is used to merge the lists if there is a duplicate key.

public class Test {

    public static Map<String, List<Integer>> merge(List<Map<String, List<Integer>>> maps) {
        BiFunction<List<Integer>, List<Integer>, List<Integer>> mergeList
                = (list_a, list_b) -> {
                    list_a.addAll(list_b);
                    return list_a;
                };
        return maps.stream().flatMap(m -> m.entrySet().stream())
                .collect(Collectors.toMap(entry -> entry.getKey(),
                        entry -> entry.getValue()
                                .stream().collect(Collectors.toList()),
                        (list_a, list_b) -> mergeList.apply(list_a, list_b)));
    }

    public static void main(String[] args) {
        Map<String, List<Integer>> map1 = new HashMap<>();
        map1.put("A", Arrays.asList(1));
        map1.put("B", Arrays.asList(2, 3));

        List<Map<String, List<Integer>>> maps = new ArrayList<>();
        maps.add(map1);
        map1 = new HashMap<>();
        map1.put("B", Arrays.asList(3, 4));
        map1.put("C", Arrays.asList(5));
        maps.add(map1);
        Map<String, List<Integer>> m = merge(maps);
        m.forEach((k, v) -> System.out.println(k + " : " + v));

    }

}

[Jeanne Boyarsky]

Thanks all. While I'm sticking with my original code*, I learned a lot here!

I find it interesting that Piet's is most similar to mine. I used traditional lists instead of forEach() because I was wary of side effects in the stream. OVerall,  of the solutions are things I didn't think of making this quite educational!

* This needs to be readable for my teammates who are less comfortable with advanced streams.

[Junilu Lacar]

Late to the party...  

The Map#compute documentation seems to suggests that Map#merge is simpler so I gave it a shot:

import java.util.*;

class Main {

  public static void main(String[] args) {
    List<Map<String, List<Integer>>> testData = new ArrayList<>();
    Map<String, List<Integer>> m;
    
    m = new HashMap<>();
    m.put("a", Arrays.asList(1));
    m.put("b", Arrays.asList(2, 3));
    testData.add(m);

    m = new HashMap<>();
    m.put("b", Arrays.asList(3, 4));
    m.put("c", Arrays.asList(5));
    testData.add(m);

    m = merge(testData);
    for (String k : m.keySet()) {
      System.out.printf("%s -> %s%n", k, m.get(k));
    }
  }

  public static Map<String, List<Integer>> merge(List<Map<String, List<Integer>>> maps) {
    Map<String, List<Integer>> result = new HashMap<>();

    for (Map<String, List<Integer>> m : maps) {
      for (String key : m.keySet())
        result.merge(key, m.get(key), (t, u) -> {
          List<Integer> r = new ArrayList<>(t);
          r.addAll(u);
          return r;
        });
    }
    return result;
  }
 
}

I don't know if that's necessarily more elegant or even simpler than what you came up with, Jeanne.

You can test this code here: https://repl.it/@jlacar/ListMerge

EDIT: Got some code review feedback (Thanks, Rob!). Also added version that used .forEach() like Piet did but I opted to avoid side effects. The code using .forEach() looks cleaner to me.

 private static Map<String, List<Integer>> merge(List<Map<String, List<Integer>>> maps) {    Map<String, List<Integer>> result = new HashMap<>();    for (Map<String, List<Integer>> m : maps) {      for (Map.Entry<String, List<Integer>> e : m.entrySet()) {        result.merge(e.getKey(), e.getValue(), (t, u) -> {          List<Integer> r = new ArrayList<>(t);          r.addAll(u);          return r;        });      }    }    return result;  }  private static Map<String, List<Integer>> fnMerge(List<Map<String, List<Integer>>> maps) {    Map<String, List<Integer>> result = new HashMap<>();    maps.forEach(m ->      m.forEach((key, value) ->        result.merge(key, value, (t, u) -> {          List<Integer> r = new ArrayList<>(t);          r.addAll(u);          return r;        })      )    );    return result;  }

[Aleksandr Shitov]

What do you think about that?

    public static Map<String, List<Integer>> merge(List<Map<String, List<Integer>>> maps) {
        return maps.stream()
                .flatMap(map -> map.entrySet().stream())
                .collect(Collectors.toMap(
                        Map.Entry::getKey,
                        Map.Entry::getValue,
                        (l1, l2) -> Stream.concat(l1.stream(), l2.stream()).collect(Collectors.toList())));
    }

[Stephan van Hulst]

Welcome to CodeRanch Alex!

You can probably simplify your collection step with a groupingBy(), rather than a toMap().

[Aleksandr Shitov]

Stephan van Hulst wrote:Welcome to CodeRanch Alex!

You can probably simplify your collection step with a groupingBy(), rather than a toMap().

Won't be work unfortunately, because there is no appropriate mapper for groupingBy function to flat grouped lists to one.

[Piet Souris]

Many different solutions! It shows that the Java 8(+) streams and lambdas are a lot of fun to use.

@Jeanne
I found this remrk interesting:

Jeanne Boyarsky wrote:* This needs to be readable for my teammates who are less comfortable with advanced streams.

Can you tell me in how far the java 8(+) streams and lambdas are used in practice, compared to the java < 8 ways?

[Rob Spoor]

Junilu Lacar wrote:      for (String key : m.keySet())
       result.merge(key, m.get(key), (t, u) -> {[/code]

Whenever I see someone looping over the key set and then using get, I am forced to tell them to use entrySet instead...

[Junilu Lacar]

Rob Spoor wrote:

Junilu Lacar wrote:      for (String key : m.keySet())
       result.merge(key, m.get(key), (t, u) -> {[/code]

Whenever I see someone looping over the key set and then using get, I am forced to tell them to use entrySet instead...

Yes, that's a good point.  

I made the appropriate modifications to the code on repl.it

[Piet Souris]

Alex Shitov wrote:

Stephan van Hulst wrote:Welcome to CodeRanch Alex!

You can probably simplify your collection step with a groupingBy(), rather than a toMap().

Won't be work unfortunately, because there is no appropriate mapper for groupingBy function to flat grouped lists to one.

Well, it CAN be done, but it is not the most simple solution...

public class JavaRanch16 {

    /**
     * @param args the command line arguments
     */
    public static void main(String... args) {
        var map1 = Map.of("a", List.of(1, 2, 3));
        var map2 = Map.of("a", List.of(2, 3, 4));
        var mapTotal = List.of(map1, map2);
        var result = compressMap(mapTotal);
        result.entrySet().forEach(System.out::println);
    }
    
    public static <T, S> Map<T, List<S>> compressMap(List<Map<T, List<S>>> maps) {
        Map<T, List<S>> result = maps.stream()
            .flatMap(map -> map.entrySet().stream())
            .collect(Collectors.toList())
            .stream()
            .collect(
                Collectors.groupingBy(
                    Entry::getKey, 
                    mapping(
                        Entry::getValue, 
                        Collectors.reducing(
                            new ArrayList<>(), 
                            (a1, a2) -> {a1.addAll(a2); return a1;}
                        )
                    )
                )
            )      
        ;
        return result;
    }
}

I tried to indent it so, that parts that go together are nicely grouped.

Of course I did try to make this more generic, something like

public static <T, X extends Collection<? extends T>, Y extends Collection<?  extends X>> List<T> compressMap(Y maps) {...}

but for the time being I get a load of errors....

[Piet Souris]

Hmmm, I start to belive that Alex Shitov is right, after all. My above code does not work; I added a third Map, and the reducing reduced the complete value Collection of all Maps, no matter what key it was.
Does anyone know what I am doing wrong?

public class JavaRanch16 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        var map1 = Map.of("a", List.of(1, 2, 3));
        var map2 = Map.of("a", List.of(2, 3, 4));
        var map3 = Map.of("a", List.of(3, 4, 5), "b", List.of(10));
        var mapTotal = List.of(map1, map2, map3);
        Map<String, List<Integer>> result = compressMap2(mapTotal);
        System.out.println("****** the final map, incorrect ************");
        result.entrySet().forEach(System.out::println);
    }
    
    public static <T, S> Map<T, List<S>> compressMap2(List<Map<T, List<S>>> maps) {
        List<Entry<T, List<S>>> temp = maps.stream().collect(
            () -> new ArrayList<>(), 
            (list, map) -> list.addAll(map.entrySet()), 
            (list1, list2) -> list1.addAll(list2)
        );
        System.out.println("******** The combined listt of the entries************");
        temp.forEach(System.out::println);
        System.out.println("******************************************************");
        Map<T, List<S>> result = temp.stream()
            .collect(
                groupingBy(
                    Entry::getKey, 
                    mapping(
                        Entry::getValue,
                        Collectors.reducing(
                            new ArrayList<>(),
                            (list1, list2) -> {list1.addAll(list2); return list1;}
                        )
                    )
                )
            )    
        ;
        return result;
    }
}

Output:

******** The combined listt of the entries************
a=[1, 2, 3]
a=[2, 3, 4]
b=[10]
a=[3, 4, 5]
******************************************************
****** the final map, incorrect ************
a=[1, 2, 3, 2, 3, 4, 10, 3, 4, 5]
b=[1, 2, 3, 2, 3, 4, 10, 3, 4, 5]

[Jeanne Boyarsky]

I like that Alex's attempt doesn't use a loop!

Piet Souris wrote:@Jeanne

Jeanne Boyarsky wrote:* This needs to be readable for my teammates who are less comfortable with advanced streams.

Can you tell me in how far the java 8(+) streams and lambdas are used in practice, compared to the java < 8 ways?

They are good with the basics: stream/filter/map/collect. But writing a custom Collector goes way to far. Also, if it isn't simpler than the loop solution...

[Aleksandr Shitov]

Piet Souris wrote:Hmmm, I start to belive that Alex Shitov is right, after all. My above code does not work; I added a third Map, and the reducing reduced the complete value Collection of all Maps, no matter what key it was.
Does anyone know what I am doing wrong?

public class JavaRanch16 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        var map1 = Map.of("a", List.of(1, 2, 3));
        var map2 = Map.of("a", List.of(2, 3, 4));
        var map3 = Map.of("a", List.of(3, 4, 5), "b", List.of(10));
        var mapTotal = List.of(map1, map2, map3);
        Map<String, List<Integer>> result = compressMap2(mapTotal);
        System.out.println("****** the final map, incorrect ************");
        result.entrySet().forEach(System.out::println);
    }
    
    public static <T, S> Map<T, List<S>> compressMap2(List<Map<T, List<S>>> maps) {
        List<Entry<T, List<S>>> temp = maps.stream().collect(
            () -> new ArrayList<>(), 
            (list, map) -> list.addAll(map.entrySet()), 
            (list1, list2) -> list1.addAll(list2)
        );
        System.out.println("******** The combined listt of the entries************");
        temp.forEach(System.out::println);
        System.out.println("******************************************************");
        Map<T, List<S>> result = temp.stream()
            .collect(
                groupingBy(
                    Entry::getKey, 
                    mapping(
                        Entry::getValue,
                        Collectors.reducing(
                            new ArrayList<>(),
                            (list1, list2) -> {list1.addAll(list2); return list1;}
                        )
                    )
                )
            )    
        ;
        return result;
    }
}

Output:

******** The combined listt of the entries************
a=[1, 2, 3]
a=[2, 3, 4]
b=[10]
a=[3, 4, 5]
******************************************************
****** the final map, incorrect ************
a=[1, 2, 3, 2, 3, 4, 10, 3, 4, 5]
b=[1, 2, 3, 2, 3, 4, 10, 3, 4, 5]

This is because ArrayList in Collectors.reducing(new ArrayList<>(), ...) is created only once and used for each grouped key as initial(zero-size) list. Fixed version of compressMap2(...):

    public static <T, S> Map<T, List<S>> compressMap2(List<Map<T, List<S>>> maps) {
        List<Map.Entry<T, List<S>>> temp = maps.stream().collect(
                () -> new ArrayList<>(),
                (list, map) -> list.addAll(map.entrySet()),
                (list1, list2) -> list1.addAll(list2)
        );
        System.out.println("******** The combined listt of the entries************");
        temp.forEach(System.out::println);
        System.out.println("******************************************************");
        Map<T, List<S>> result = temp.stream()
                .collect(
                        Collectors.groupingBy(
                                Map.Entry::getKey,
                                mapping(
                                        Map.Entry::getValue,
                                        Collectors.reducing(
                                                new ArrayList<>(), //this list is used as initial list for each grouping key, Collections.emptyList() could be used instead
                                                (list1, list2) -> {
                                                    List<S> combined = new ArrayList<>(list1); //it is not memory efficient, only to show how to fix it
                                                    combined.addAll(list2);
                                                    return combined;
                                                }
                                        )
                                )
                        )
                );
        return result;
    }

Thanks for evaluation)

[Junilu Lacar]

Seeing all these variations is great from a learning standpoint but I can see why Jeanne is deciding to stick with her two-loop (and probably) more imperative version. Given my own attempt at a solution, I think I would prefer that over the more "streamy" solutions suggested. I also like the conciseness of Alex's solution but the flatmap() method is something that always seems to twist my brain in knots whenever I encounter it, which isn't that often to begin with.

[Stephan van Hulst]

.flatMap(map -> map.entrySet().stream()
  .flatMap(entry -> entry.getValue().stream().map(
    value -> new SimpleImmutableEntry<K,V>(entry.getKey(), value))))
.collect(groupingBy(
  Entry::getKey,
  mapping(Entry::getValue, toList())));

Alex' version may be preferable, because it creates a new stream object per list, while my version creates a new entry object per list element.

[Jeanne Boyarsky]

Junilu Lacar wrote:Seeing all these variations is great from a learning standpoint but I can see why Jeanne is deciding to stick with her two-loop (and probably) more imperative version.

Yup. I'm glad I posted for learning though!