Efficient way to find if map contains any of the keys from a list/iterable

Question

I need to check if a map contains any of the keys from a list, and if it does then return the first matching value. The naive approach that comes to mind is to do it in two nested loops:

Map<String, String> fields = new HashMap<String, String>();
fields.put("a", "value a");
fields.put("z", "value z");
String[] candidates = "a|b|c|d".split("|");
for (String key : fields.keySet()){
    for (String candidate : candidates) {
        if (key.equals(candidate)){
            return fields.get(key);
        }
    }
}

Is there a nicer and more efficient way, possibly one relying on the Java standard library?

NimChimpsky · Answer 1 · 2012-12-28T11:15:34.847

26

for(String candidate : candidates) {
 if(fields.containsKey(candidate)) {
  return fields.get(candidate)
 }
}

the best way if null values are possibly in map, and if only the first detected key is required.

edited Dec 28 '12 at 11:15

answered Dec 28 '12 at 11:04

NimChimpsky

46,453
60
198
311

Brian Agnew · Accepted Answer · 2012-12-28T11:14:15.113

24

Surely something like:

for (String candidate : candidates) {
     String result = fields.get(key);
     if (result != null) {
         return result;
     }
}

The above only performs one map lookup per candidate key. It avoids the separate test for presence plus extraction, since extracting a non-existant key will simply give you a null. Note (thanks Slanec) that a null value for a valid key is indistinguishable from a non-existant key for this solution.

I don't quite understand why you're performing the case conversion, btw.

edited Dec 28 '12 at 11:14

answered Dec 28 '12 at 11:05

Brian Agnew

268,207
37
334
440

9

This is as efficient as it can get, but it may get tricky if `null` is a permitted value in the `Map`. – Petr Janeček Dec 28 '12 at 11:09
4

Interesting... Do I understand it correctly that the idea is to only use `map.get()` once instead of `map.contains() + map.get()` because that would avoid a second lookup? That's neat! – ccpizza Dec 28 '12 at 11:11
3

@NimChimpsky retainAll is descructive. – Peter Lawrey Dec 28 '12 at 11:12
2

@ccpizza - that's correct. Note Slanec's caveat re. null values in the map, though – Brian Agnew Dec 28 '12 at 11:13
@BrianAgnew: Got it! I don't worry about null's since the keys in the map are already validated for `null`. – ccpizza Dec 28 '12 at 11:16
@ccpizza As a side note, if you'll ever need the `null` values and maximize performance (hopefully after a check with a profiler), you can overcome it by inserting a dummy object instead of `null`s. That way, you can still do a single lookup and if `null` is returned, you'll know the key wasn't there. If your dummy object is returned, you'll return `null`. – Petr Janeček Dec 28 '12 at 11:20
@Slanec: Thanks, this is good to know. Still, I don't see why would anyone want to store `null` keys in a map. Did you encounter a real-life use case for `null` keys? – ccpizza Dec 28 '12 at 11:24
2

@ccpizza Actually, yes, once, I think. In an application where we didn't have explicit control over the hashmap's content as it was user's configuration and we needed to capture a case where a setting was accessed (but not changed) or was reset to default. [Anyway, there is a SO question for this.](http://stackoverflow.com/questions/3622007/why-is-it-useful-to-have-null-values-or-null-keys-in-hash-maps) – Petr Janeček Dec 28 '12 at 11:31

score 22 · Answer 3 · answered Jan 19 '17 at 13:43

In Java 8 you can have this:

boolean exists = Arrays.stream(candidates).anyMatch(fields::containsKey);

If you just want to know if any of candidates is key to the map.

If you want to know the first or any you can use:

Arrays.stream(candidates).filter(fields::containsKey).findAny();

or

Arrays.stream(candidates).filter(fields::containsKey).findFirst();

As per @Klapsa2503 answer above

score 7 · Answer 4 · answered Dec 28 '12 at 11:04

My take:

Map<String, String> fields = new HashMap<String, String>();
fields.put("a", "value a");
fields.put("z", "value z");
String[] candidates = "a|b|c|d".split("|");
for (String candidate : candidates) {
    if (fields.containsKey(candidate)) {
        return fields.get(candidate);
    }
}

score 7 · Answer 5 · answered Nov 18 '16 at 09:35

7

In Java 8 you can use this:

return candidates.stream()
            .filter(fields::containsKey)
            .findFirst()
            .map(fields::get)
            .orElse(null);

answered Nov 18 '16 at 09:35

Klapsa2503

829
10
33

score 5 · Answer 6 · answered Dec 28 '12 at 11:09

5

Try

Set<String> keySet = new HashSet<String>(fields.keySet());    
keySet.retainAll(list);

so keySet is supposed to have all keys from HashMap which are mentioned in the list

answered Dec 28 '12 at 11:09

Nikolay Kuznetsov

9,467
12
55
101

2

This is, I believe, the shortest way. However, it may be not the fastest one since the looping ends at the first found result, but this continues its work till the end. – Petr Janeček Dec 28 '12 at 11:12
3

@Slanec, yes it depends whether OP wants to get all keys or just first one. – Nikolay Kuznetsov Dec 28 '12 at 11:13

Evgeniy Dorofeev · Answer 7 · 2012-12-28T11:13:57.637

2

Try as

    List list= Arrays.asList(1, 2, 3);
    HashMap map = new HashMap();
    map.put(1, 1);
    map.put(3, 3);
    Set set = new HashSet(map.keySet());
    set.retainAll(list);
    System.out.println(set);
    Object e = set.isEmpty() ? null : set.iterator().next();
    System.out.println(e);

output

[1, 3]
1

edited Dec 28 '12 at 11:13

answered Dec 28 '12 at 11:06

Evgeniy Dorofeev

133,369
30
199
275

score 1 · Answer 8 · answered Dec 28 '12 at 11:05

1

Map<String, String> fields = new HashMap<String, String>();
fields.put("a", "value a");
fields.put("z", "value z");
String[] candidates = "a|b|c|d".split("|");
List<String> canList = Arrays.asList(candidates );
for (String key : fields.keySet()){

if (canList .contains(key)) {
return fields.get(key);
}

}

answered Dec 28 '12 at 11:05

NPKR

5,368
4
31
48

1

**Note** : canList.contains is linear in time. – Srinivas Dec 28 '12 at 11:06

score 1 · Answer 9 · answered Dec 28 '12 at 11:10

1

You can use a single loop if you assume the key of the map are already in lower case, in the same way you assume the lookup values are in lower case.

answered Dec 28 '12 at 11:10

Peter Lawrey

525,659
79
751
1,130

Efficient way to find if map contains any of the keys from a list/iterable

9 Answers9

Linked

Related