Java迭代哈希表vs ArrayList速度

我正在写一个简单的3D SW渲染引擎。我有一个默认的ArrayList<Object3D>包含整个场景。现在，我希望能够按照名称添加，删除和选择对象，就像3D编辑器一样（因为它比鼠标选择更简单，但在作业中仍然看起来不错））。Java迭代哈希表vs ArrayList速度

因此，我认为的第一件事情是Hashtable的名称和索引到现场ArrayList。但是，然后我想我可以直接使用Hashtable直接保存场景，并通过它使用迭代器进行渲染。

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

来源

2011-12-14 B.Gen.Jack.O.Neill

首先，我建议你使用一个HashMap代替Hashtable，出于同样的原因，ArrayList比Vector一个更好的选择：更少的开销，由于没用同步。

我的猜测是通过迭代ArrayList会比通过由Hashtable的（或HashMap的）entrySet()方法返回的Set迭代更快。但要知道的唯一方法是配置文件。

显然，对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; 
    } 
}

，这里是结果的一个典型运行：在一个HashMap

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

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

作为参考，这是在Intel 1.6GHz四核Windows机器上使用Java 1.6.0_26（64位JVM）完成的，该机器拥有充足的可用内存。

来源

2011-12-14 22:10:49

Absolutelly完美的答案，谢谢大的时候:) – 2011-12-15 01:18:24

我相当肯定，迭代通过ArrayList将比迭代Hashtable更快。但是，不确定这种区别有多大 - 可能是（拇指吸）2倍于实际的内部逻辑，但这并不多。

但请注意，除非您需要多线程同步，否则应该使用HashMap而不是Hashtable。这里有一些表现。

来源

2011-12-14 22:11:21

有需要同步的大多数应用中，哈希表的方法级的同步几乎总是错的，您就可以最终做更高级别的同步。我不推荐Hashtable作为处理多线程同步的一种方式。 – 2011-12-14 22:23:13

在从不同线程随机更新表的情况下，Hashtable非常有用。不是你想要“同步”线程的地方，而是为了避免出现像HashMap一样的损坏表。 – 2011-12-15 04:48:55

是的，这是一个超出我评论中“最”的情况。我只是觉得应用程序需要在线程之间共享一个映射是不常见的，但除了确保映射没有被破坏所需的同步以外不需要任何同步。 – 2011-12-15 05:33:23

A）请勿使用Hashtable，请使用HashMap。 Hashtable已被非正式弃用

B）这取决于应用程序。在HashMap中查找会更快，迭代将可能与内部使用数组相同。（但是HashMap中的阵列有间隙，所以可能会给ArrayList带来一些小优势）。哦，如果你想保持迭代的固定顺序，使用LinkedHashMap（通过插入排序）或TreeMap（按自然顺序进行排序）

来源

2011-12-14 22:11:43

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

来源

2011-12-14 22:11:49

实际上，我看着目前的HashMap实施（首选超过Hashtable大家指出）。对值进行迭代看起来像只是遍历一个底层数组。

所以，速度可能会与迭代ArrayList相当，尽管可能会有一些时间跳过HashMap的底层阵列。

所有说，分析才是王道。

来源

2011-12-14 22:22:53 rfeak

前面已经说过，这是更好地使用HashMap。关于迭代，理论上，ArrayList必须更快，原因有两个。首先是数据结构更简单，访问时间更短。第二是ArrayList可以通过索引而不创建Iterator对象，其中，在大量使用的情况下，产生较少的垃圾，因此较少GC进行迭代。在实践中 - 你可能没有注意到差异，取决于你将使用它有多沉重。

来源

2011-12-14 22:22:57 Stas

Java迭代哈希表vs ArrayList速度

回答

相关问题