FindBugs warning: Inefficient use of keySet iterator instead of entrySet iterator

Question

Please refer to the following method :

public Set<LIMSGridCell> getCellsInColumn(String columnIndex){
    Map<String,LIMSGridCell> cellsMap = getCellsMap();
    Set<LIMSGridCell> cells = new HashSet<LIMSGridCell>();
    Set<String> keySet = cellsMap.keySet();
    for(String key: keySet){
      if(key.startsWith(columnIndex)){
        cells.add(cellsMap.get(key));
      }
    }
    return cells;
  }

FindBugs give this waring message :

"Inefficient use of keySet iterator instead of entrySet iterator This method accesses the value of a Map entry, using a key that was retrieved from a keySet iterator. It is more efficient to use an iterator on the entrySet of the map, to avoid the Map.get(key) lookup."

Answer 1

You are retrieving all the keys (accessing the whole map) and then for some keys, you access the map again to get the value.

You can iterate over the map to get map entries (Map.Entry) (couples of keys and values) and access the map only once.

Map.entrySet() delivers a set of Map.Entrys each one with the key and corresponding value.

for ( Map.Entry< String, LIMSGridCell > entry : cellsMap.entrySet() ) {
    if ( entry.getKey().startsWith( columnIndex ) ) {
        cells.add( entry.getValue() );
    }
}

Note: I doubt that this will be much of an improvement since if you use map entries you will instantiate an object for each entry. I don't know if this is really faster than calling get() and retrieving the needed reference directly.

Answer 2

If somebody is still interested in a detailed and number-backed answer: yes, you should use entrySet() vs. keySet() in case you are iterating over the whole Map. See this Gist for detailed numbers. I run a benchmark with JMH for the default implementations of Map with Oracle JDK8.

The main finding is: it is always a bit slower to iterate over the keySet and re-query for every key. As soon as you have bigger maps, the multiplier can become quite big (e.g., for a ConcurrentSkipListMap it is always 5-10x; while for HashMaps it is not bigger than 2x for up to a million entries).

However, these are still very small numbers. The slowest way to iterate over 1 million entries is with a ConcurrentSkipListMap.keySet(), which is around 500-700 milliseconds; while iterating over over IdentityHashMap.entrySet() is just 25-30 milliseconds with LinkedHashMap.entrySet() just behind with 40-50 milliseconds (not surprising, as it has a LinkedList inside it, which helps with iteration). As an overview from the above linked Gist:

Map type              | Access Type | Δ for 1M entries
----------------------+-------------+-----------------
HashMap               | .entrySet() |     69-72  ms
HashMap               |   .keySet() |     86-94  ms
ConcurrentHashMap     | .entrySet() |     72-76  ms
ConcurrentHashMap     |   .keySet() |     87-95  ms
TreeMap               | .entrySet() |    101-105 ms
TreeMap               |   .keySet() |    257-279 ms
LinkedHashMap         | .entrySet() |     37-49  ms
LinkedHashMap         |   .keySet() |     89-120 ms
ConcurrentSkipListMap | .entrySet() |     94-108 ms
ConcurrentSkipListMap |   .keySet() |    494-696 ms
IdentityHashMap       | .entrySet() |     26-29  ms
IdentityHashMap       |   .keySet() |     69-77  ms

So the bottom line is: it depends on your use-case. While it is definitely faster to iterate over the entrySet() the numbers are not huge, especially for reasonably small Maps. However, if you are iterating over a Map with 1 million entries quite regularly, better use the faster way ;)

The numbers of course are just to compare with each other, not absolutes.

Answer 3

You're getting the set of keys in the map, then using each key to get the value out of the map.

Instead, you can simply iterate through the Map.Entry key/value pairs returned to you via entrySet(). That way you avoid the relatively expensive get() lookup (note the use of the word relatively here)

e.g.

for (Map.Entry<String,LIMSGridCell> e : map.entrySet()) {
   // do something with...
   e.getKey();
   e.getValue();
}