Map的keySet()和entrySet()的性能注意事项

Question

全部，

任何人都可以让我确切知道两者之间的性能问题是什么吗？站点： CodeRanch 简要概述了使用 keySet() 和 get() 时所需的内部调用。但是，如果有人可以提供有关使用 keySet() 和 get() 方法时流程的确切细节，那就太好了。这将帮助我更好地理解性能问题。

原文由 name_masked 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

首先，这完全取决于您使用的是哪种类型的 Map 。但是由于 JavaRanch 线程谈论 HashMap ，我假设这就是您所指的实现。我们还假设您正在谈论来自 Sun/Oracle 的标准 API 实现。

其次，如果您担心遍历哈希映射时的性能，我建议您看一下 LinkedHashMap 。从文档：

迭代 a LinkedHashMap 的集合视图需要的时间与地图的大小成正比，无论其容量如何。迭代 a HashMap 可能更昂贵，需要与其容量成正比的时间。

HashMap.entrySet()

此实现的源代码可用。该实现基本上只返回一个新的 HashMap.EntrySet 。一个看起来像这样的类：

 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator(); // returns a HashIterator...
    }
    // ...
}

和 HashIterator 看起来像

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;    // next entry to return
    int expectedModCount;   // For fast-fail
    int index;      // current slot
    Entry<K,V> current; // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null);
        }
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null);
        }
        current = e;
        return e;
    }

    // ...
}

所以你有它……这就是当你迭代 entrySet 时指示会发生什么的代码。它遍历整个阵列，与地图的容量一样长。

HashMap.keySet() 和 .get()

在这里，您首先需要掌握一组密钥。这花费的时间与地图的 容量 成正比（与 LinkedHashMap 的 大小 相反）。完成后，您为每个密钥调用一次 get() 一次。当然，在一般情况下，通过良好的 hashCode 实现，这需要恒定的时间。然而，它不可避免地需要大量的 hashCode() 和 equals() 调用，这显然比只调用 entry.value() -- 调用要花费更多的时间。

原文由 aioobe 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

使用 entrySet 优于 keySet 的最常见情况是当您遍历 Map 中的所有键/值对时。

这样效率更高：

 for (Map.Entry entry : map.entrySet()) {
    Object key = entry.getKey();
    Object value = entry.getValue();
}

比：

 for (Object key : map.keySet()) {
    Object value = map.get(key);
}

因为在第二种情况下，对于 keySet 中的每个键，都会调用 map.get() 方法，在 HashMap 的情况下，这需要 hashCode() 和 equals() 评估关键对象的方法以找到关联的值*。在第一种情况下，额外的工作被消除了。

编辑：如果你考虑一个 TreeMap，情况会更糟，其中对 get 的调用是 O(log(n))，即比较器可能需要运行 log2(n) 次（n = Map 的大小）才能找到关联的价值。

*某些 Map 实现具有内部优化，可在调用 hashCode() 和 equals() 之前检查对象的身份。

原文由 Michael Barker 发布，翻译遵循 CC BY-SA 4.0 许可协议