FindBugs警告：使用keySet迭代器而不是entrySet迭代器效率低下。

Question

请参考以下方法：

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 给出以下警告信息：

"使用 keySet 迭代器而不是 entrySet 迭代器时效率低下 此方法访问了一个 Map 条目的值，使用了从 keySet 迭代器检索到的键。 更有效的方法是在 map 的 entrySet 上使用迭代器，以避免 Map.get(key) 操作."

- Geek

---

如果Map是一个哈希表，它是否更高效仍有争议，因为查找是*O(1)，否则必须是TreeMap，其中查找是(O log N)*。这几乎不会产生太大差异。这里纯粹是吹毛求疵。 - user207421

Answer 1

你正在检索所有的键（访问整个映射），然后对于某些键，你再次访问映射以获取值。

你可以迭代地遍历映射以获取映射条目（Map.Entry）（键和值的一对），并仅访问映射一次。 Map.entrySet() 返回一组Map.Entry，每个条目都有对应的键和值。

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

注意：我怀疑这并不会有太大的改进，因为如果您使用映射条目，您将为每个条目实例化一个对象。我不知道这是否比直接调用“get（）”并检索所需引用更快。

- Matteo

---

但是 hashMap 的 get() 方法不是 O(1) 吗？ - Geek

@Geek：是的。请看我的附加说明。我怀疑FindBugs的建议是否真的有意义。实例化和get()都是O(1)。 - Matteo

地图可以存储Entry（例如Sun的HashMap实现），因此无需实例化。而get()可能会超过O(1)，例如TreeMap或哈希函数不好的HashMap。但是你是正确的，在大多数情况下，这不会产生明显的差异。 - TimK

@Matteo，你能否请审核一下我的答案？如果有任何意见，请告诉我。 - Kanagavelu Sugumar

“如果您使用映射条目，您将为每个条目实例化一个对象”—并非如此。大多数映射实现已经是条目的映射。特别是在迭代HashMap时，条目实例与内部存储的条目对象相同。因此，在Entry上调用getValue（以及类似地调用setValue）直接访问该值，而在映射上调用get意味着在键上调用hashCode，计算数组索引，并至少调用一次键上的equals，以到达使用entrySet()时已经存在的同一条目对象。 - Holger

@Matteo，你能否请看一下我的问题 https://stackoverflow.com/questions/67880418/getdetailsstring-makes-inefficient-use-of-keyset-iterator-instead-of-entryset - Gen

Answer 2

如果有人仍然对详细且基于数字的答案感兴趣：是的，如果您正在遍历整个映射表，应该使用 entrySet() 而不是 keySet()。请参见此 Gist以获取详细的数字。我使用JMH为Oracle JDK8的默认实现运行了一个基准测试。

主要发现是：遍历 keySet 并为每个键重新查询总是稍微慢一些。一旦您拥有更大的映射表，乘数就会变得相当大（例如，对于 ConcurrentSkipListMap，它始终是5-10倍；而对于HashMap，在高达100万个条目之前乘数不会超过2倍）。

然而，这些数字仍然非常小。遍历100万个条目最慢的方法是使用ConcurrentSkipListMap.keySet()，大约需要500-700毫秒；而使用IdentityHashMap.entrySet() 进行遍历只需25-30毫秒，LinkedHashMap.entrySet()紧随其后，只需要40-50毫秒（毫不奇怪，因为它内部有一个 LinkedList，这有助于迭代）。总之，以上链接的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

因此，最重要的是：它取决于您的用例。尽管使用 entrySet（） 进行迭代肯定会更快，但对于相当小的 Maps 来说，这些数字并不是很大。然而，如果您经常遍历具有 100 万个条目的 Map，则最好使用更快的方法 ;)

当然，这些数字只是相互比较，而不是绝对值。

- D. Kovács

Answer 3

你正在获取地图中的键集，然后使用每个键从地图中获取值。

相反，你可以通过 entrySet() 迭代返回给你的 Map.Entry 键/值对。这样你就避免了相对昂贵的 get() 查找（请注意这里使用了“相对”的词）。

例如：

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

- Brian Agnew

---

在这种情况下，map的实现是HashMap。难道HashMap的get()不是O(1)吗？ - Geek

@Geek：是的，但使用entrySet()可以完全避免调用get()。 - user330315

O(1)并没有指定所需的时间长度，仅表示其是恒定的。 - Brian Agnew

他并不通过get()访问每一个值，只有那些键与条件匹配的才会被使用。我认为没有一般规则可以偏向哪种方式，这取决于符合条件的键所占比例。显然，FindBugs无法检查这一点。 - Heiko Schmitz

Answer 4

这是建议，不是真正回答你的问题。 当你使用ConcurrentHashMap时，在javadoc中提到了迭代器行为，如下所示：

视图的迭代器是一个“弱一致性”迭代器，永远不会抛出ConcurrentModificationException，并保证遍历元素与迭代器构造时相同，并且可能（但不保证）反映构造后的任何修改。

因此，如果您使用EntrySet迭代器，则可能包含过期的键/值对；因此最好从keySet iterator()获取键，并检查集合中的值。这将确保您从集合中获取最新的更改。

如果您可以接受故障安全迭代器，则可以检查link；它指出使用entrySet可以稍微提高性能。

- Kanagavelu Sugumar

Answer 5

在键集中，你需要获取所有键，然后在集合中搜索每个键。

此外，循环遍历entrySet更快，因为你不需要为每个键查询两次映射。

如果你只需要Map的键或值，则使用keySet()或values()。

- Chetan Laddha