19

我有一个Map在应用程序启动期间填充的。它在应用程序执行期间不会更改。稍后此映射仅用于迭代其中的所有元素。我应该选择哪个具体实现Map？HashMap或TreeMap或LinkedHashMap?
更新
插入顺序无关紧要。唯一重要的是所有元素的快速迭代（比如 6000 个元素）。

4

7 回答 7

12

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

如果地图在初始化后不会更改，您可能需要使用ImmutableMap或UnmodifiableMap

于 2013-07-28T16:49:16.823 回答
8

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

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

但是，如果您可以避免创建保存数据的对象并仅使用原始值数组，那么真正的、令人惊叹的改进将会实现。当然，这高度依赖于您的用例。

于 2013-07-28T17:43:51.513 回答
6

我不会使用地图。如果您想要的只是遍历条目，则创建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

于 2013-07-28T18:05:35.863 回答
3

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

于 2013-07-28T16:53:21.533 回答
1

我同意 Zim-Zam 的回答，并补充一点：如果您需要在迭代期间同时访问键和值，最快的方法是使用该entrySet()方法，如此处所述。

现在，如果您确定地图永远不会改变，为什么不使用单独的数据结构进行迭代呢？例如：在完成的地图上迭代一次并用它的内容填充几个数组，一个带有键，另一个带有值，在相同的相应位置。然后遍历这些数组将尽可能快。

于 2013-07-28T16:51:38.907 回答
1

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

于 2019-03-26T18:54:53.097 回答
-2

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;
    }
}
于 2016-06-14T00:05:42.297 回答