HashMap与LinkedHashMap在values（）迭代中的性能

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 []找到下一个next。

但是 我认为这种性能提升将以插入为代价。addEntry在练习中检查这两个类中的方法。