Map的keySet（）和entrySet（）的性能注意事项 [英] Performance considerations for keySet() and entrySet() of Map

问题描述

全部，

任何人都可以让我知道2之间的性能问题是什么？网站： CodeRanch 简要概述了需要的内部通话当使用keySet（）和get（）。但是，如果任何人都可以提供关于使用keySet（）和get（）方法的流程的详细信息，这将是巨大的。

解决方案

首先，这完全取决于您使用的地图类型使用。但是由于JavaRanch线程谈论HashMap，我假设这是你所指的实现。让我们假设你正在谈论Sun / Oracle的标准API实现。

其次，如果你在迭代哈希映射时关注性能，建议您查看 LinkedHashMap 。从文档：

在LinkedHashMap的集合视图上迭代需要与地图大小成正比的时间其容量。 HashMap上的迭代可能更昂贵，需要与其容量成比例的时间。

HashMap.entrySet

此实现的源代码可用。实现基本上只是返回一个新的 HashMap.EntrySet 。类如下：

 私有最终类EntrySet扩展AbstractSet< Map.Entry< K，V& {
 public Iterator< Map.Entry< K，V> iterator（）{
 return newEntryIterator（）; //返回一个HashIterator ... 
} 
 // ... 
} 
  

b $ b

和 HashIterator 看起来像

  class HashIterator< E>实现迭代器< E> {
 Entry< K，V>下一个; //下一个条目返回
 int expectedModCount; // For fast-fail 
 int index; // current slot 
 Entry< K，V>当前; //当前条目
 
 HashIterator（）{
 expectedModCount = modCount; 
 if（size> 0）{//进入第一个条目
 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（）

在这里，你首先需要获取一组键。这需要与地图的 capacity 成正比的时间（而不是LinkedHashMap的 size ）。完成后，您为每个键调用 get（）一次。当然，在平均情况下，有一个好的hashCode实现这需要不断的时间。然而，它不可避免地需要大量的 .hashCode 和 .equals 调用，这显然需要更多的时间， a entry.value（）调用。

All,

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.

解决方案

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.

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

Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

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...
    }
    // ...
}

and a HashIterator looks like

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;
    }

    // ...
}

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.

HashMap.keySet() and .get()

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屋！