Getting common values from entries of a map in an efficient way

Question

Suppose there is map as show below:

    Map<String, List<String>> myMap =     
     {   
        k1: [ v1, v2, v3, v3],  
        k2: [ v1, v2],  
        k3: [ v1, v2, v6, v7]
      }

I want to find values which are common for all the keys.

 List<String> commonValues = {v1,v2}

I want to understand the efficient way of doing it using java 8. I am able to achieve the same using for loops in java 5, but I am sure Java 8 is having better ways of doing it.

@sleepToken thank you for pointing out, I corrected the data — AkashSharma, Jan 28 '20 at 12:56
Dont use static initialization, recommended. Moreover i dont think your initialisation is even correct. — Vishwa Ratna, Jan 28 '20 at 13:35
@VishwaRatna I was just intending to show how the map is, wasn't initializing it — AkashSharma, Jan 28 '20 at 14:00

Lino · Accepted Answer · 2020-01-28T13:13:14.140

6

You may use something like this:

List<String> commonValues = myMap.values().stream()
    .reduce((a, b) -> {
        a.retainAll(b);
        return a;
    })
    .orElse(Collections.emptyList());

From the doc of retainAll:

Retains only the elements in this collection that are contained in the specified collection (optional operation). In other words, removes from this collection all of its elements that are not contained in the specified collection.

In case you're working with multiple threads or collections which are immutable:

List<String> commonValues = myMap.values().stream()
    .reduce((a, b) -> {
        List<String> c = new ArrayList<>(a);
        c.retainAll(b);
        return c;
    })
    .orElse(Collections.emptyList());

Though this solution creates a new copy every iteration.

Another way would be somewhat more hacky:

List<String> commonValues = myMap.values().stream()
    .reduce(null, (a, b) -> {
        if(a == null) return new ArrayList<>(b);
        a.retainAll(b);
        return a;
    });

But this time, commonValues may be null, so you'd have to check for that

edited Jan 28 '20 at 13:13

answered Jan 28 '20 at 13:03

Lino

19,604
6
47
65

2

I believe this raises an `UnsupportedOperationException` for the example data OP provided. – sleepToken Jan 28 '20 at 13:07
1

@sleepToken but only if the underlying `list` is immutable – Lino Jan 28 '20 at 13:13
agreed after your edit - am I wrong for thinking that a HashMap in java is mutable? – sleepToken Jan 28 '20 at 13:17
1

@sleepToken , `Arrays.asList() `, will surely be immutable. – Vishwa Ratna Jan 28 '20 at 13:22
2

@sleepToken since the OP didn’t provide valid Java code, we don’t know which actual type the collections will have. But using reduction with a function which modifies the input is broken anyway. Especially with the Stream API, which requires the function to be associative, so it doesn’t even allow to predict, which of the input collections will end up modified, if they support modifications… – Holger Jan 28 '20 at 16:56

Getting common values from entries of a map in an efficient way

1 Answers1