Java迭代HashTable与ArrayList速度

Question

我正在编写一个简单的 3D SW 渲染引擎。我有一个包含整个场景的默认 ArrayList。现在，我希望能够按名称添加、删除和选择对象，就像 3D 编辑器所做的那样（因为它比鼠标选择简单得多，但在家庭作业中仍然看起来不错:)）。

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

所以我想问一下，在3D引擎中，什么是速度优先？因为与选择对象相比，我每秒会多次循环场景。 ArrayList 比迭代哈希表 快吗？谢谢。

Answer 1

首先，我建议您使用 HashMap 而不是 Hashtable，同样的原因，ArrayList 是比 Vector 更好的选择：由于无用的同步而导致的开销更少。

我的猜测是，迭代 ArrayList 比迭代 Hashtable（或 HashMap）返回的 Set 更快。 /code> 的) entrySet() 方法。但了解的唯一方法是进行分析。

显然，HashMap 的显示列表更改（除了追加或删除最后一个元素之外）比 ArrayList 更快。

编辑
所以我遵循了自己的建议并进行了基准测试。这是我使用的代码：

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

显然，使用 ArrayList 比 HashMap 取得了巨大的胜利（3-4 倍），至少对于我迭代 HashMap 的风格来说是这样。我怀疑数组迭代器比数组下标慢的原因是所有迭代器对象都需要创建然后进行垃圾收集。

作为参考，这是在具有大量可用内存的 Intel 1.6GHz 四核 Windows 计算机上使用 Java 1.6.0_26（64 位 JVM）完成的。

Answer 2

我相当确定迭代ArrayList会比迭代Hashtable更快。不过，不确定差异有多大——在实际的内部逻辑中可能是（拇指吸）2 倍，但这并不多。

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

Answer 3

实际上，我查看了当前的 HashMap 实现（正如大家指出的那样，优于 Hashtable）。迭代值看起来就像简单地迭代底层数组。

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

总而言之，分析为王。

Answer 4

A) 不要使用Hashtable，使用HashMap。 Hashtable 已被非正式弃用

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

Answer 5

正如已经说过的，最好使用HashMap。关于迭代，理论上，ArrayList 必须更快，原因有两个。首先，数据结构更简单，访问时间更少。第二个是 ArrayList 可以通过索引进行迭代，而无需创建 Iterator 对象，在大量使用的情况下，产生的垃圾更少，因此 gc 也更少。
在实践中 - 您可能不会注意到差异，这取决于您要使用它的重量。

Answer 6

如果不需要检索同步，请使用 java.util.HashMap 而不是 java.util.Hashtable。