Home > OS >  Finding common set of elements from a Map whose value is a collection in Java using streams
Finding common set of elements from a Map whose value is a collection in Java using streams

Time:03-03

Let's say I've a HashMap which contains key as a String and value as a Set of Integers (Map<String, Set>). And say that the map is populated with following values:

Map<String, Set<Integer>> map = new HashMap<>();
map.put("w1", Set.of(1,3,4,6,7));
map.put("w2", Set.of(2,3,4,5,7));
map.put("w3", Set.of(1,2,3,5,7));

How can I find common set of values across all keys using Streams in Java? eg: In this case, the common set of values across all keys is Set.of(3,7)

CodePudding user response:

First note that using stream is not always the cleanest way.

My idea would be to get the first set and iterate over the rest to check if all of them contain it:

Set<Integer> res = map.values().iterator().next().stream()
            .filter(item -> map.values().stream().allMatch(set -> set.contains(item)))
            .collect(Collectors.toSet());

This is a concise solution but it checks the first set twice. You can also add a check to see if the map contains any entries.

CodePudding user response:

My approach is to first group the different values and count them. Then only keep those whose count is equal to the number of entries in the map. That works because each set can only contains the value once.

map.values().stream().flatMap(Set::stream)
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
    .entrySet().stream().filter(e -> e.getValue() == map.size())
    .map(Map.Entry::getKey).collect(Collectors.toSet());

CodePudding user response:

A generic and potentially efficient solution could be:

public static <T> Set<T> retain(Map<?, Set<T>> map) {
    Iterator<Set<T>> it = map.values().iterator();
    if (!it.hasNext()) {
        return new HashSet<>();
    }
    Set<T> result = new HashSet<>(it.next());
    while (it.hasNext() && !result.isEmpty()) {
        result.retainAll(it.next());
    }
    return result;
}

Note the !result.isEmpty() which is an early-exit condition. I.e. if the result is empty, then the sets have no elements in common.

Note: this was inspired by the answer of MikeFHay.


If you really want to use streams, and can guarantee that the Sets are mutable, then you may also use the reduce() terminal operation:

public static <T> Set<T> retain(Map<?, Set<T>> map) {
    return map.values().stream()
        .reduce((a, b) -> {
            a.retainAll(b);
            return a;
        })
        .orElse(Set.of());
}

But be aware that this modifies and returns the first set in the map.

CodePudding user response:

Set<Integer> commonValues(Map<String, Set<Integer>> map) {
    if (map.isEmpty()) {
       return new HashSet<>();
    }

    Set<Integer> intersection = new HashSet<>(map.values().iterator().next());
    map.values().forEach(v -> intersection.retainAll(v));
    return intersection;
}
  • Related