问题描述

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

我认为 LinkedHashMap 的遍历速度必须更快，因为它的 nextEntry 实现在其 <代码>迭代器

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

原因如下:

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

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

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

The LinkedHashMap extends from HashMap and inherits the same implementation.

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

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

对于 HashMap 它从 java.util.HashMap.HashIterator

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

但对于 LinkedHashMap 它是从 java.util.LinkedHashMap.LinkedHashIterator 扩展而来的

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

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

所以区别本质上归结为nextEntry实现.

so the difference essentially boils down to nextEntry implementation.

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

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

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[] .

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

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 与 LinkedHashMap 在值迭代中的性能()的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！