intersection of map values and set

Question

I have a hypothetical map - HashMap<String,List<String>> mapteachertostudents.
There is a separate set - Set<String> giftedstudents.
The ask is simply print out the common students using java 1.7

mapteachertostudents { 'A':'a,b,c';'B':'b,e';'C':'b,c,f'}
giftedstudents ['b','c','e']
expected output ['b']

Is there a more efficient routine than iterating each teacher and maintaining state,considering that this comparison has to be run over 10000+ maps each.

So the "common students" are those who are in giftedstudents and in each list of the map? Something else? What? — JB Nizet, Jul 01 '18 at 13:59
With `mapteachertostudents.keySet()` you can retrieve the set of keys from the map. Then it see the captioned answer — Daniele, Jul 01 '18 at 14:04
Checkout this answer as well for map intersection : https://stackoverflow.com/a/13180552/48136 — bric3, Oct 03 '22 at 07:28

score 4 · Accepted Answer · answered Jul 01 '18 at 14:07

Every possible algorithm is going to involve iterating over all the teachers and checking each teacher's students, there is no way around that. As far as efficiency goes, I think retainAll should be the most efficient way to derive set intersections in Java.

public static <T> Set<T> intersect(
        Collection<? extends Collection<T>> sets) {
    if (sets.isEmpty()) return Collections.emptySet();

    Iterator<? extends Collection<T>> it = sets.iterator();
    Set<T> intersect = new HashSet<>(it.next());
    while (it.hasNext()) {
        intersect.retainAll(it.next());
    }
    return intersect;
}

This allows you to then do

Set<String> commonStudents = intersect(mapteachertostudents.values());

The generics make the method general-purpose, so it isn't restricted to just HashMap<String,List<String>>, you can use it to intersect any collection of collections.

intersection of map values and set

1 Answers1