HashMap与LinkedHashMap在值迭代中的性能()

Question

遍历功能HashMap和LinkedHashMap遍历values()功能之间是否存在性能差异？

Answer 1

我认为LinkedHashMap由于其优越的nextEntry实现,遍历必须更快Iterator

原因如下:

让我们从values实施步骤一步步走.
该HashMap实施values是这样的:

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

在LinkedHashMap 从扩展HashMap和继承相同的实现.

区别在于两者的Iterator实施Values.

因为HashMap它延伸自 java.util.HashMap.HashIterator

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

但LinkedHashMap它延伸自java.util.LinkedHashMap.LinkedHashIterator

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

所以差异基本上归结为nextEntry实施.

因为LinkedHashMap它只是调用e.after,其中e是Entry,但是因为HashMap有一些工作涉及遍历Entry[]数组以找到下一个.

UPDATE:用于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 []不是连续的商店.(两者之间可能存在空值).如果您查看上面的代码,它的作用是指向current旁边,并通过迭代Entry []找到下一个代码.

但我认为这种性能提升将以插入成本为代价.查看addEntry两个类中的方法作为练习.

Answer 2

我写了一个小的分析程序,创建了100万个键(Integer)和Boolean.TRUE,重复了100次.找到以下内容:

HashMap:-
Create:  3.7sec
Iterate: 1.1sec
Access:  1.5sec
Total:   6.2sec

LinkedHashMap:-
Create:  4.7sec   (30% slower)
Iterate: 0.5sec   (50% faster)
Access:  0.8sec   (50% faster)
Total :  6.0sec

垃圾收集没有这样做有点污染数字,但我认为LinkedHashMap优于HashMap,我将在未来的代码中使用它.

Answer 3

几乎没有关系。问题是：您需要什么。如果元素的顺序相关，则必须使用LinkedHashMap。否则，您只是不需要它，请使用HashMap。