Merging, sorting and limit Map streams using Java 8

Question

I have two maps Map<String, Long>. I want to merge both maps, sort in descending order, and get top 5. In case of duplicate keys in merge I need to sum the values. I have the following code that works:

Map<String, Long> topFive = (Stream.concat(map1.entrySet().stream(), 
                                           map2.entrySet().stream())
                                   .collect(Collectors.toMap(Map.Entry::getKey, 
                                                             Map.Entry::getValue,
                                                             Long::sum)))
                                   .entrySet()
                                   .stream()
                                   .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                                   .limit(5)
                                   .collect(Collectors.toMap(Map.Entry::getKey,
                                                             Map.Entry::getValue,
                                                            (v1, v2) -> v1,
                                                            LinkedHashMap::new));

But I would like to know if there is a better solution.

Answer 1

If you mean better in terms of performance, and you have large collections, and only need few top elements you can avoid sorting the entire map, given the n*log(n) complexity.

If you already have Guava, you can use MinMaxPriorityQueue to store only the best N results. And then just sort this few constant N elements.

Comparator<Entry<String, Long>> comparator = Entry.comparingByValue(reverseOrder());

Map<String, Long> merged = Stream.of(map1, map2)
        .map(Map::entrySet)
        .flatMap(Set::stream)
        .collect(Collectors.toMap(Map.Entry::getKey, 
                Map.Entry::getValue, 
                Long::sum));

MinMaxPriorityQueue<Entry<String, Long>> tops = MinMaxPriorityQueue.orderedBy(comparator)
        .maximumSize(5)
        .create(merged.entrySet());

Map<String, Long> sorted = tops.stream()
        .sorted(comparator)
        .collect(Collectors.toMap(Map.Entry::getKey, 
                Map.Entry::getValue,
                (m1, m2) -> m1,
                LinkedHashMap::new));

If you don't have/want to use Guava, you can simulate the MinMaxPriorityQueue by using a custom TreeMap (Also a class that receives the max size in constructor can be created, if you don't want to use an anonymous class [this is to show the functionality]).

Set<Entry<String, Long>> sorted = new TreeSet<Entry<String, Long>>(comparator) {
    @Override
    public boolean add(Entry<String, Long> entry) {
        if (size() < 5) { // 5 can be constructor arg in custom class
            return super.add(entry);
        } else if (comparator().compare(last(), entry) > 0) {
            remove(last());
            return super.add(entry);
        } else {
            return false;
        }
    }
};

And add all the elements to the set with top.

sorted.addAll(merged);

You can also change the merge function, to use something similar to the merge mentioned by Federico.

Map<String, Long> merged = new HashMap<>(map1);
map2.forEach((k, v) -> merged.merge(k, v, Long::sum));

This tends to be faster that using streams, and after that, once you have the merged map, you can select the top N elements with MinMaxPriorityQueue or TreeSet, avoiding again the unnecessary need of sorting the entire collection.