HashMap或TreeMap或LinkedHashMap哪一个迭代更快？

Question

我有一个Map在应用程序启动期间填满的.在执行应用程序期间,它不会在以后更改.之后,此映射仅用于迭代其中的所有元素.Map我应该选择哪种具体实施方案？HashMap或TreeMap或LinkedHashMap？
更新广告
订单无关紧要.唯一重要的是快速迭代所有元素(比如6000个元素).

Answer 1

HashMap一般将最快的,因为它具有最佳的缓存行为(HashMap直接迭代背衬阵列,而TreeMap和LinkedHashMap遍历链接的数据结构).

如果地图初始化后不会改变,您可能希望使用ImmutableMap或UnmodifiableMap

Answer 2

这里没有其他答案考虑到CPU缓存的影响,当涉及迭代时,这可能是巨大的.

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

但是,如果您可以避免创建保存数据的对象并仅使用原始值数组,那么将实现真正的,尖锐的改进.当然,这很大程度上取决于您的使用案例.

Answer 3

我不会使用地图。如果您只想遍历所有条目，请重新编写ArrayList所需的内容并使用它-您不可能比ArrayListfor迭代更快。

// 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的建议更改LinkedList为ArrayList。