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

Question

HashMap和LinkedHashMap通过values()函数进行遍历有性能差异吗？

Answer 1

我认为 LinkedHashMap 的遍历速度必须更快，因为其 Iterator

中的 nextEntry 实现更好

原因如下:

让我们从 values 实现一步一步来。
values 的 HashMap 实现是这样的:

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

LinkedHashMap 扩展自 HashMap 并继承相同的实现。

区别在于两者中 Values 的 Iterator 实现。

对于 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 : HashMap

中 nextEntry() 的代码

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[] 不是连续存储。 (两者之间可能有空值)。如果你看一下上面的代码，它的作用是指向当前的 next 并通过遍历 Entry[] 来找到下一个。

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