Map的keySet()和entrySet()的性能考虑

Question

大家好，

请问有人能够告诉我使用keySet()和get()方法之间的性能差异吗？网站：CodeRanch提供了一个简要概述，介绍了在使用这两种方法时所需的内部调用。但如果有人能够提供关于使用keySet()和get()方法时流程的确切细节，那就太好了。这将帮助我更好地理解性能问题。

- name_masked

Answer 1

使用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的情况下，这要求评估key对象的hashCode()和equals()方法以查找关联的值。而在第一种情况下，这个额外的工作是被省略掉了。

编辑：如果考虑到TreeMap，情况甚至更糟。在TreeMap中，调用get方法的时间复杂度是O(log(n))，也就是说比较器可能需要运行log2(n)次（n为Map的大小）才能找到关联的值。

有些Map实现在调用hashCode()和equals()之前会进行内部优化来检查对象的身份。

- Michael Barker

---

另外，如果该地图是TreeMap而不是HashMap，则get()操作是一个O(log(n))的操作。 - ILMTitan

@ILMIian和Michael：为什么TreeMap和HashMap之间有区别？ - name_masked

TreeMap和HashMap是不同的数据结构，TreeMap基于红/黑树。HashMap是一种桶和链表哈希表。在两种情况下，调用get()都不是免费的，其成本取决于数据结构类型。 - Michael Barker

Java 8（及以上版本）中的HashMap的值实现为二叉搜索树，而不是LinkedList。请参见http://openjdk.java.net/jeps/180 - Novice User

只是一个小问题，但“其中调用get的时间复杂度为O(log2(n))，即比较器for可能需要运行log2(n)次”应该改为“其中调用get的时间复杂度为O(log(n))，即比较器for可能需要运行log2(n)次”。简单对数的底数与大O符号无关，因为所有对数增长都相差一个常数因子。（在计算机科学中，“lg”通常表示基数2，由于它是最常见的一种出现，所以我们只要在没有指数或其他不常见情况下使用“lg”即可。） - Trixie Wolf

Answer 2

首先，这完全取决于您使用的Map类型。但由于JavaRanch线程谈论了HashMap，我假设您指的是该实现。同时假设您也在谈论来自Sun/Oracle的标准API实现。

其次，如果您关心迭代哈希映射的性能，建议您查看LinkedHashMap。从文档中可以得知：

迭代LinkedHashMap的集合视图需要与地图大小成比例的时间，而不管其容量如何。迭代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

---

在LinkedHashMap的集合视图上进行迭代需要与地图大小成比例的时间，而不管其容量如何。在HashMap上进行迭代可能更昂贵，需要与其容量成比例的时间。 - metdos

但是，如果你只需要访问Map的键或者值之一，那么最好迭代keySet()返回的Set和values()返回的Collection。另外，keySet()返回的Set和values()返回的Collection都由原始Map支持。也就是说，如果你在它们里面做了任何修改，这些修改将反映在Map中。但是，它们不支持add()和addAll()方法，也就是说你不能向Set添加新的键，也不能向Collection中添加新的值。 - sactiw

@aioobe，你写道：“这就是在迭代entrySet时发生的事情。它遍历整个数组，其长度与map的容量一样。”难道不应该是“...其长度与map的大小一样”吗？ - Sumit Kumar Saha

好的好答案。我总是更喜欢参考源代码，因为它是真相的最终来源。 - ACV

Answer 3

这篇文章比较了entrySet(), keySet(), 和 values()三种方法并提供了相关建议，适用场景不同使用时需要注意。

显然，只要您不需要通过Map.get()方法获取值，使用keySet()会更快（除了更方便）。

- Stefan L

---

你在那篇文章中说：“使用keySet或values而不是entrySet的方法比entrySet迭代略快（大约快10%），更加清晰。”请问您是如何得出“10%”这个数值的？您没有展示任何测量数据或外部数据来支持此数值。 - dantuch

@dantuch 我不是Sergiy，但我认为这篇文章很有道理。不过这篇文章比较旧，是2008年的。如果你感到好奇，你可以使用Google的Caliper创建一个微基准测试，例如针对最新的JDK，请发布结果。 - Stefan L