Java迭代HashTable与ArrayList速度

Question

我正在编写一个简单的3D SW渲染引擎.我有一个默认ArrayList<Object3D>包含整个场景.现在,我希望能够按名称添加,删除和选择对象,就像3D编辑一样(因为它比鼠标选择更简单,但在家庭作业中仍然看起来很好:)).

所以,我想到的第一件事就是拥有Hashtable名称和场景索引ArrayList.但是,我认为我可以Hashtable直接使用直接保存场景,然后使用迭代器进行渲染.

所以我想问一下,在3D引擎中,什么是速度优先？因为与选择对象相比,我将每秒多次循环场景.是ArrayList比任何更快iterated Hashtable？谢谢.

Answer 1

首先,我建议您使用a HashMap而不是a Hashtable,出于同样的原因,这ArrayList是一个更好的选择而不是Vector:由于无用的同步而导致的开销减少.

我的猜测是迭代通过一个ArrayList将比Set通过一个Hashtable(或HashMap's)entrySet()方法返回的迭代更快.但唯一要知道的方法就是剖析.

显然,对显示列表的更改(除了追加或切断最后一个元素)对于a而言HashMap要比对a更快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是一个很大的胜利(比3-4倍)优于HashMap,至少对于我通过HashMap迭代的风格.我怀疑数组迭代器比数组下标慢的原因是需要创建然后进行垃圾收集的所有迭代器对象.

作为参考,这是在具有大量可用内存的Intel 1.6GHz四核Windows机器上使用Java 1.6.0_26(64位JVM)完成的.