CODEWITHSUNDEEP
javahashmapsetjava-streamjava-11
Aman
Aman

Reputation: 127

Finding common set of elements from a Map with Set values using Java streams

Let's say I've a HashMap which contains key as a String and value as a Set of Integers (Map<String, Set<Integer>>). 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? e.g.: In this case, the common set of values across all keys is Set.of(3,7).

Upvotes: 1

Views: 1389

Answers (9)

M. Justin
M. Justin

Reputation: 21114

This can be solved using Stream.reduce:

Set<Integer> commonElements = map.values().stream()
        .reduce((s1, s2) -> s1.stream()
                .filter(s2::contains)
                .collect(Collectors.toUnmodifiableSet()))
        .orElseThrow(NoSuchElementException::new);

Each step of the reduction will create a new Set containing only the elements in common between the two sets.

One easy optimization that I haven't made here (in the name of simplicity for the example) would be to conditionally swap s1 and s2 such that the smaller set is being streamed over, since that occurs in linear time based on the size of the set, but each contains check occurs in constant time.

Upvotes: 1

Alexander Ivanchenko
Alexander Ivanchenko

Reputation: 28978

That could be done by utilizing the collect() operation.

The logic behind this approach is to get a random set from the collection of values, wrap it with a new set to avoid mutating existing data, and then combine all sets using retainlAll() method one by one.

Even if values are represented by immutable sets (like in the example in the question) that will not be an issue because this approach guarantees that a map passed as an argument will be preserved intact. The only collection that will be mutated is a locally created set.

Stream-based implementation might look like:

public static <K, V> Set<V> getIntersection(Map<K, Set<V>> map) {

    return map.values().stream()
        .collect(
            () -> getFirstSet(map),
            Set::retainAll,
            Set::retainAll
        );
}

Method get getFirstSet() is responsible for retrieving a random set from the collection of values. In the case of an empty map it'll return an empty set, otherwise, it'll yield a new set containing the elements of the first set in the stream.

public static <K, V> Set<V> getFirstSet(Map<K, Set<V>> map) {
    
    return map.values().stream()
        .map(HashSet::new) // create a new Set with the same contents to avoid modifying existing one
        .findFirst()
        .orElseGet(HashSet::new);
}

The same logic could be implemented iteratively:

public static <K, V> Set<V> getIntersection(Map<K, Set<V>> map) {
    Set<V> intersection = getFirstSet(map);
    for (Set<V> next: map.values()) {
        intersection.retainAll(next);
    }
    return intersection;
}

Usage example:

public static void main(String[] args) {
    Map<String, Set<Integer>> map =
            Map.of("key1", Set.of(1,3,4,6,7),
                   "key2", Set.of(2,3,4,5,7),
                   "key3", Set.of(1,2,3,5,7));
    
    System.out.println(getIntersectionStream(map));
    System.out.println(getIntersectionLoop(map));
}

Output:

[3, 7]
[3, 7]

Upvotes: 3

frascu
frascu

Reputation: 828

In my opinion, this is the best solution:

map.values().stream().reduce((s1, s2) -> {
    Set<Integer> s3 = new HashSet<>(s2);
    s3.retainAll(s1);
    return s3;
}).orElse(new HashSet<>());

It is a stream on map values reduced by intersecting the sets.

Upvotes: 2

WJS
WJS

Reputation: 40034

I would first recommend to not use streams and just do it simply as shown below. This does remove one element of the map. You could just do map.get("w1") and do one redundant retainAll.

Notice since you used Map.of which creates an immutable set I had to make a copy to allow result to be modified.

Set<Integer> result = new HashSet<>(map.remove("w1"));
for (Set<Integer> set : map.values()) {
            result.retainAll(set);
}

Here is a stream solution.

To avoid having to use an initializer for a reduce operation I would use the reducing Collector. This collector returns an Optional so orElse had to be used to retrieve the set and allow for an empty map.

Set<Integer> result = map.values().stream()
        .collect(Collectors.reducing((a, b) -> {
            a.retainAll(b);
            return a;
        }))..orElse(new HashSet<>());

System.out.println(result);

Both of the above would print

[3, 7]

The solutions shown presume a properly populated Map. A full solution would include checks for

Upvotes: 0

DuncG
DuncG

Reputation: 15136

This simple version uses stream with set operations to populate intersections by finding one of the members and retainAll to match all the others:

Set<Integer> intersection = new HashSet<>();
map.values().stream().limit(1).forEach(intersection::addAll);
map.values().stream().forEach(intersection::retainAll);

Upvotes: 0

geanakuch
geanakuch

Reputation: 972

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());

Upvotes: 2

MikeFHay
MikeFHay

Reputation: 9013

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;
}

Upvotes: 2

Lino
Lino

Reputation: 19926

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.

Upvotes: 0

Andronicus
Andronicus

Reputation: 26046

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.

Upvotes: 3

Related Questions