Java迭代哈希表与ArrayList的速度对比

Question

我正在编写一个简单的三维软件渲染引擎。我有一个默认的ArrayList<Object3D>，其中包含整个场景。现在，我想能够通过名称添加、删除和选择对象，就像3D编辑器一样（因为这比鼠标选择简单得多，但在作业中看起来仍然很好 :)）。

所以，我首先想到的是使用Hashtable来存储名称和场景ArrayList的索引。但是，后来我想，我可以直接使用Hashtable保存场景，并使用迭代器遍历它进行渲染。

所以我想问，在一个3D引擎中，哪种方法更快？因为我会每秒钟多次for循环场景，而不是选择对象。是ArrayList比iterated Hashtable更快吗？谢谢。

- B.Gen.Jack.O.Neill

Answer 1

首先，建议您使用HashMap而不是Hashtable，原因与使用ArrayList比使用Vector相同：由于无用的同步，开销更小。

我猜遍历ArrayList比遍历Hashtable（或HashMap）的entrySet()方法返回的Set更快。但唯一知道的方法是进行分析。

显然，对于HashMap，除了附加或削减最后一个元素之外，对显示列表的更改将更快。 编辑 所以我遵循了自己的建议并进行了基准测试。这是我使用的代码：

import java.util.*;

public class IterTest {
    static class Thing {
        Thing(String name) { this.name = name; }
        String name;
    }

    static class ArrayIterTest implements Runnable {
        private final ArrayList<Thing> list;
        ArrayIterTest(ArrayList<Thing> list) {
            this.list = list;
        }
        public void run() {
            int i = 0;
            for (Thing thing : list) {
                ++i;
            }
        }
    }

    static class ArraySubscriptTest implements Runnable {
        private final ArrayList<Thing> list;
        ArraySubscriptTest(ArrayList<Thing> list) {
            this.list = list;
        }
        public void run() {
            int i = 0;
            int n = list.size();
            for (int j = 0; j < n; ++j) {
                Thing thing = list.get(j);
                ++i;
            }
        }
    }

    static class MapIterTest implements Runnable {
        private final Map<String, Thing> map;
        MapIterTest(Map<String, Thing> map) {
            this.map = map;
        }
        public void run() {
            int i = 0;
            Set<Map.Entry<String, Thing>> set = map.entrySet();
            for (Map.Entry<String, Thing> entry : set) {
                ++i;
            }
        }
    }

    public static void main(String[] args) {
        final int ITERS = 10000;
        final Thing[] things = new Thing[1000];
        for (int i = 0; i < things.length; ++i) {
            things[i] = new Thing("thing " + i);
        }
        final ArrayList<Thing> arrayList = new ArrayList<Thing>();
        Collections.addAll(arrayList, things);
        final HashMap<String, Thing> hashMap = new HashMap<String, Thing>();
        for (Thing thing : things) {
            hashMap.put(thing.name, thing);
        }
        final ArrayIterTest t1 = new ArrayIterTest(arrayList);
        final ArraySubscriptTest t2 = new ArraySubscriptTest(arrayList);
        final MapIterTest t3 = new MapIterTest(hashMap);
        System.out.println("t1 time: " + time(t1, ITERS));
        System.out.println("t2 time: " + time(t2, ITERS));
        System.out.println("t3 time: " + time(t3, ITERS));
    }

    private static long time(Runnable runnable, int iters) {
        System.gc();
        long start = System.nanoTime();
        while (iters-- > 0) {
            runnable.run();
        }
        return System.nanoTime() - start;
    }
}

以下是典型运行的结果：

t1 time: 41412897
t2 time: 30580187
t3 time: 146536728

显然，对于我的HashMap迭代方式来说，使用ArrayList比HashMap更优（优势为3-4倍）。我猜测数组迭代器比数组下标访问慢的原因是因为需要创建并回收许多迭代器对象。

参考信息：这是在Java 1.6.0_26（64位JVM）上，在一台拥有充足空闲内存的英特尔1.6 GHz四核Windows计算机上完成的。

- Ted Hopp

Answer 2

我相当确定通过迭代 ArrayList 比迭代 Hashtable 更快。不过，我不确定差异有多大，也许（粗略估计）在实际内部逻辑中会快两倍，但这并不算太多。

但请注意，除非您需要多线程同步，否则应该使用 HashMap 而不是 Hashtable。这里可以获得一些性能提升。

- Hot Licks

---

对于大多数需要同步的应用程序，Hashtable 的方法级同步几乎总是错误的，最终你还是会进行更高级别的同步。我不建议使用 Hashtable 处理多线程同步。 - Ted Hopp

Hashtable在表格从不同的线程随机更新时非常有用。它并不一定需要与线程“同步”，而是仅仅避免出现HashMap可能发生的损坏表格。 - Hot Licks

是的，这是一个例外情况，不符合我评论中的“大多数”情况。我只是认为，一个应用程序需要在线程之间共享地图，但除了确保地图不被破坏所必需的同步之外，不需要其他同步的情况并不常见。 - Ted Hopp

当我在维护 iSeries JVM 时，我们收到了很多来自人们（实际上是银行等）的投诉，称他们从 HashMap 中得到了“损坏”的错误，其实是因为他们在做多线程处理。 - Hot Licks

从HashMap切换到Hashtable将消除不正确同步的症状，但我猜测可能会在其他地方出现不同的症状。当（如果）应用程序开发人员最终找出如何正确同步线程时，使用Hashtable的需求可能就消失了。就像我说的，这只是一个猜测。 :) - Ted Hopp

Answer 3

A) 不要使用 Hashtable，而要使用 HashMap。因为 Hashtable 已经被非正式地弃用了。

B) 这取决于应用程序。在 HashMap 中查找会更快，迭代可能与两者都使用内部数组相同（但是 HashMap 中的数组有间隙，所以这可能会给 ArrayList 带来轻微的优势）。哦，如果你想保持迭代的固定顺序，请使用 LinkedHashMap（按插入排序）或 TreeMap（按自然排序）。

- Sean Patrick Floyd

Answer 4

如果您不需要检索同步，使用java.util.HashMap代替java.util.Hashtable。

- Wojciech Owczarczyk

---

也许您可以在这个答案上再详细解释一下？ - NullUserException

Answer 5

实际上，我查看了当前的HashMap实现（优先于大家指出的Hashtable）。遍历值似乎只是在遍历底层数组。

因此，速度可能与遍历ArrayList相当，尽管在HashMap底层数组中跳过间隙可能需要一些时间。

总之，性能分析至关重要。

- rfeak

---

该数组是一个桶的数组。每个桶包含一系列条目，也必须遍历这些条目。无论如何，您都必须使用LinkedHashMap来保留顺序，而LinkedHashMap使用一系列条目而不是数组进行迭代。 - JB Nizet

Answer 6

正如已经提到的那样，最好使用 HashMap。关于迭代，在理论上，由于两个原因，ArrayList 应该更快。首先，数据结构更简单，因此访问时间更少。其次，ArrayList 可以通过索引进行迭代，而不必创建 Iterator 对象，在强烈使用的情况下，可以产生较少的垃圾，因此也会产生较少的 gc。在实践中，您可能注意不到差异，这取决于您使用它的程度。

- Stas