HashMap vs LinkedHashMap在迭代中的性能（） [英] HashMap vs LinkedHashMap performance in iteration over values()

问题描述

HashMap 和 LinkedHashMap 之间是否存在通过 values（） c> $ c> > Iterator

中的优越 nextEntry

这是为什么：

让我们从 values 实现。

HashMap 实现 values 就是这样： p>



  public Collection< V> values（）{
 Collection< V> vs = value; 
 return（vs！= null？vs：（values = new Values（）））; 
} 
  

LinkedHashMap 从 HashMap 并继承相同的实现。

区别在于 。 code>它扩展自 java.util.HashMap.HashIterator

  private final class ValueIterator extends HashIterator< V> {
 public V next（）{
 return nextEntry（）。value; 
} 
} 
  



它扩展自 java.util.LinkedHashMap.LinkedHashIterator

  private class ValueIterator extends LinkedHashIterator< V> {
 public V next（）{return nextEntry（）。value; } 
} 
  

因此差异本质上归结为 nextEntry 实现。

对于 LinkedHashMap .after其中e是 Entry ，
但是 HashMap 有一些工作涉及遍历 Entry [] 数组以查找下一个。

UPDATE ：< c $ c> nextEntry（）在 HashMap

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

Entry []不是连续的存储。 （中间可能有空值）。如果你看看上面的代码，它做的是在当前点旁边，通过迭代Entry []来找到下一个。

但是我认为这种性能增益将以插入为代价。在两个类中查看 addEntry 方法。

Is there any performance difference between HashMap and LinkedHashMap for traversal through values() function?

解决方案

I think the LinkedHashMap has to be faster in traversal due to a superior nextEntry implementation in its Iterator

Here is why :

Let us go step by step from the values implementation.
The HashMap implementation of values is this :

   public Collection<V> values() {
        Collection<V> vs = values;
        return (vs != null ? vs : (values = new Values()));
    }

The LinkedHashMap extends from HashMap and inherits the same implementation.

The difference is in the Iterator implementation for the Values in both.

for HashMap it extends from java.util.HashMap.HashIterator

  private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }

but for LinkedHashMap it extends from java.util.LinkedHashMap.LinkedHashIterator

 private class ValueIterator extends LinkedHashIterator<V> {
        public V next() { return nextEntry().value; }
    }

so the difference essentially boils down to nextEntry implementation.

For LinkedHashMap it is just calling e.after where e is the Entry , but for HashMap there is some work involved in traversing the Entry[] array to find the next next.

UPDATE : Code for nextEntry() in HashMap

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

The Entry[] is not a contiguous store. (There could be null values in between). If you take a look at the above code, what it does is point next to current and find the next next by iterating over the Entry[] .

But I think this performance gain will come at the cost of insertion. Check out the addEntry method in both classes as an exercise.

这篇关于HashMap vs LinkedHashMap在迭代中的性能（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！