HashMap、TreeMap和LinkedHashMap，哪一个迭代速度最快？

Question

我有一个Map，在应用程序启动时填充。在应用程序执行过程中不会更改此映射表。稍后，此地图仅用于迭代其中的所有元素。我应该选择哪个具体实现的Map？HashMap、TreeMap还是LinkedHashMap？
更新
插入顺序并不重要。唯一重要的是快速迭代所有元素（比如6000个元素）。

- Mac

---

插入顺序不重要。唯一重要的是快速迭代所有元素（比如6000个元素）。 - Mac

请考虑编辑您的帖子，而不是在其上添加评论，因为很容易被忽视。 - Marconius

请发布您的个人资料结果。 - trashgod

@trashgod：我不太明白你的意思，请再解释一下。 - Mac

Answer 1

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

如果地图在初始化后不会改变，则可以使用ImmutableMap或UnmodifiableMap。

- Zim-Zam O'Pootertoot

---

这个故事并不简单。你应该加上来自HashMap Javadoc的以下引用：“遍历集合视图需要的时间与HashMap实例（桶的数量）的“容量”以及其大小（键值对映射的数量）成正比。因此，如果迭代性能很重要，就非常重要不要将初始容量设置得太高（或负载因子太低）。” - Marko Topolnik

@MarkoTopolnik，你在Javadoc中发布的最后一行让我重新考虑盲目使用HashMap的决定。你对这种情况有什么建议？ - Mac

Answer 2

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

改进的一种方法是仅使用一个交错键值数组（偶数索引处为键，奇数索引处为值）。这将紧密地组合这些数据项并最大限度地利用缓存，至少对于引用来说是如此。

但是，如果您可以避免创建保存数据的对象并仅使用原始值数组，则真正的、显著的改进将会实现。这自然取决于您的用例。

- Marko Topolnik

---

在我的情况下，我将一个整数类型的“ID”作为键，以及某个用户定义的数据类型的“对象”作为值进行存储。因此，我认为我不能使用单个数组来实现这个目的，因为“键”和“值”的数据类型是不同的。 - Mac

如果您不知道值类型，那么除了优化键和值引用的访问之外，您几乎无能为力。为键和值分别使用一个单独的原始 int[] 可能会产生回报。如果您真的想要最后一点性能，您将不得不对这些替代方案进行基准测试。 - Marko Topolnik

没有人能给出终极答案：您必须进行基准测试。当您这样做时，请使用像Google Caliper或Oracle jmh这样的微基准工具。否则，您几乎肯定会得到不恰当的结果。是的，性能是一个艰难的主题，需要大量的知识、经验和直觉。它没有捷径可走。 - Marko Topolnik

关于Iterator中的CPU缓存，你是想表达Iterator在迭代之前会在CPU寄存器中内部缓存key-value对吗？还是我理解错了？ - Mac

我根本不会使用迭代器，因为没有必要。重点是，当你进行迭代时，你访问连续的 RAM 地址而不是散布你的请求。所有 CPU 缓存架构都是基于下一次访问将在当前访问之后的假设进行优化的。 - Marko Topolnik

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

- OldCurmudgeon

---

数组迭代由于元素的非常、非常密集的打包而显然快得多。 - Marko Topolnik

好观点Marko - 因此，如果可以从ArrayList获得观察到的加速，则使用它，但是您将占用更多内存。 LinkedList将添加最小的内存开销。 - OldCurmudgeon

不，实际上 LinkedList 是最浪费的：它为每个列表节点分配一个完整的对象。ArrayList 只有一个数组，自然地，如果您正在从现有映射转换，可以将其大小调整到合适的大小。但是我的建议是使用普通数组而不是 ArrayList。对于固定列表，你真的不会从 ArrayList 获得任何好处。 - Marko Topolnik

@MarkoTopolnik - 你是对的 - 我发帖后意识到了这一点。我会修改我的帖子。有时候我还在用C语言思考。 - OldCurmudgeon

Answer 4

如果您的地图仅用于遍历元素并且迭代速度很重要，那么将地图转换为ArrayList并对其进行迭代将是最快的方法。

- Evgeniy Dorofeev

---

如何将HashMap转换为ArrayList？一个ArrayList如何存储HashMap的键值对？ - Mac

@radai，那个类已经存在了，它是在Map内部使用的Map.Entry。 - Óscar López

@ÓscarLópez - 在任何不是Map的上下文中使用Map.Entry（例如如果他从map切换到list）都是非常丑陋的。 - radai

@radai 但这会导致在内存中创建6000个额外的对象！我认为这是不可取的。 - Mac

@Mac - 如果你删掉这个映射，它就不会了。 - radai

Answer 5

我同意Zim-Zam的回答，并补充一点：如果在迭代过程中需要同时访问keys和values，最快的方法是使用entrySet() 方法，如此处所讨论。

现在，如果你确定该映射永远不会改变，为什么不使用单独的数据结构进行迭代呢？例如：对已完成的映射进行一次迭代，并在相应位置上用其内容填充两个数组，一个包含keys，另一个包含values。然后遍历这些数组将尽可能快。

- Óscar López

---

这是否意味着通过Hashmap的entrySet()方法获得的集合的Iterator比TreeMap的更快？我知道在Hashmap中进行插入和搜索比Treemap更快，但我想了解它们两者的Iterator性能。 - Mac

@Mac 不，这意味着如果使用entrySet()返回的集合，遍历Map会更快。另一件事是，遍历HashMap可能比遍历TreeMap更快。 - Óscar López

д»ҺHashMapзљ„entrySet()иҺ·еЏ–зљ„IteratorеЏҮиѓҢдәљж›өеү«пәЊе› дёғе®ѓењЁе†…йѓЁе®һзҺ°зљ„ж–№еәЏдёҚеђЊгЂ‚ - Óscar López

你使用了“可能会”。但是，我能否确信HashMap的性能会更快？ - Mac

你应该运行一个分析器并亲自查看，这是确保的唯一方法。我基于对类内部的了解估计了相对速度，但很多因素影响速度-不要仅凭我的话，进行一些测量。 - Óscar López

Answer 6

从Java 10开始，您可以使用Map.of()重载方法之一或Map.copyOf()创建一个不可修改的Map。由于这些方法返回的地图不支持向地图中添加任何新条目，因此现有的键/值以交替模式存储，如此答案所述。这应该为您的用例提供最佳性能。

- jippiee

Answer 7

Map.forEach(BiConsumer) 几乎总是比迭代器更快，有时速度差距很大。例如，如果您正在对值进行求和：

public class TestForStackOverflow {
    int sum = 0;

    // Or whatever Map you are using
    Map<Object, Integer> map = new HashMap();

    static class C implements BiConsumer<Object, Integer> {
        int sum = 0;

        @Override
        public void accept(Object k, Integer v) {
            sum += v;
        }
    }

    public int getSum(Map map) {
        C c = new C();
        map.forEach(c);
        return c.sum;
    }

    public int getSum2(Map map) {
        map.forEach((k, v) -> sum += v);
        return sum;
    }
}

- hamom1968