Map 的 keySet() 和 entrySet() 的性能考虑 [英] Performance considerations for keySet() and entrySet() of Map

问题描述

全部，

谁能让我确切知道两者之间的性能问题是什么?该站点:CodeRanch 提供了内部的简要概述使用 keySet() 和 get() 时需要的调用.但是，如果有人可以提供有关使用 keySet() 和 get() 方法时的流程的确切详细信息，那就太好了.这将帮助我更好地了解性能问题.

Can anyone please let me know exactly what are the performance issues between the 2? The site : CodeRanch provides a brief overview of the internal calls that would be needed when using keySet() and get(). But it would be great if anyone can provide exact details about the flow when keySet() and get() methods are used. This would help me understand the performance issues better.

推荐答案

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

First of all, this depends entirely on which type of Map you're using. But since the JavaRanch thread talks about HashMap, I'll assume that that's the implementation you're referring to. And lets assume also that you're talking about the standard API implementation from Sun/Oracle.

其次，如果您在遍历哈希映射时担心性能，我建议您查看 LinkedHashMap.来自文档:

Secondly, if you're concerned about performance when iterating through your hash map, I suggest you have a look at LinkedHashMap. From the docs:

对 LinkedHashMap 的集合视图进行迭代所需的时间与地图的大小成正比，而不管其容量如何.对 HashMap 进行迭代可能更昂贵，需要与其容量成正比的时间.

HashMap.entrySet()

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

HashMap.entrySet()

The source-code for this implementation is available. The implementation basically just returns a new HashMap.EntrySet. A class which looks like this:

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 时会发生什么的代码.它遍历与地图容量一样长的整个数组.

So there you have it... Thats the code dictating what will happen when you iterate through an entrySet. It walks through the entire array which is as long as the maps capacity.

在这里，您首先需要掌握一组密钥.这花费的时间与地图的容量(相对于 LinkedHashMap 的大小)成正比.完成此操作后，您为每个键调用一次 get().当然，在一般情况下，一个好的 hashCode 实现需要固定的时间.然而，它不可避免地需要大量的 .hashCode 和 .equals 调用，这显然比仅仅做一个 entry.value() 需要更多的时间> 打电话.

Here you first need to get hold of the set of keys. This takes time proportional to the capacity of the map (as opposed to size for the LinkedHashMap). After this is done, you call get() once for each key. Sure, in the average case, with a good hashCode-implementation this takes constant time. However, it will inevitably require lots of .hashCode and .equals calls, which will obviously take more time than just doing a entry.value() call.

这篇关于Map 的 keySet() 和 entrySet() 的性能考虑的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！