HashMap、TreeMap或LinkedHashMap哪个迭代最快？

Question

我有一个Map，它是在启动应用程序时填充的。在以后的应用程序执行过程中，它不会改变。稍后，这个映射只用于迭代它中的所有元素。我应该选择哪个Map的具体实现？HashMap还是TreeMap还是LinkedHashMap？

更新

插入顺序并不重要。唯一重要的是所有元素(比如6000元素)的快速迭代。

Answer 1

这里没有任何其他答案考虑到CPU缓存的影响，当涉及迭代时，CPU缓存可以是巨大的。

改善这种情况的一种方法是只使用一个交错键和值的数组(偶数索引处的键，奇数的值)。这将将这些数据项紧密地组合在一起，并最大限度地利用缓存，至少对引用是这样。

但是，如果您能够避免创建保存数据的对象，并且只使用原始值数组，那么真正的、令人尖叫的改进就会实现。这很自然地高度依赖于您的用例。

Answer 2

HashMap通常是最快的，因为它具有最好的缓存行为(HashMap直接在支持数组上迭代，而TreeMap和LinkedHashMap迭代链接的数据结构)。

如果映射在初始化后不会更改，则可能需要使用ImmutableMap或UnmodifiableMap

Answer 3

我不会用地图的。如果您想要的只是迭代这些条目，那么就需要创建一个新的ArrayList并使用它--对于迭代，您不能比ArrayList更快。

// Which map you use only chooses the order of the list.
Map<Key,Value> map = new HashMap<>();
// The list to iterate for maximum speed.
List<Map.Entry<Key,Value>> list = new ArrayList<>(map.entrySet());

这样，您就可以在条目集中迭代一次来构建列表。从那时起，您将一次又一次地遍历列表--这肯定是接近最优的。

根据Marko的建议，Note从LinkedList改为ArrayList。