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速度

回答

相關問題