ArrayList和HashSet的插入性能測試結果讓我困惑

我WIRTE類測試的ArrayList和HashSet的之間的插入性能，如我所料，HashSet中插入性能會比ArrayList的好很多（也許這本書欺騙了我），但測試結果讓我很困惑ArrayList和HashSet的插入性能測試結果讓我困惑

HashSet<String> hashSet = new HashSet<String>(); 

    long start = System.currentTimeMillis(); 
    for (int i = 0; i < 900000; i++) { 
     hashSet.add(String.valueOf(i)); 
    } 

    System.out.println("Insert HashSet Time: " + (System.currentTimeMillis() - start)); 


    ArrayList<String> arrayList = new ArrayList<String>(); 

    start = System.currentTimeMillis(); 

    for (int i = 0; i < 900000; i++) { 
     arrayList.add(String.valueOf(i)); 
    } 
    System.out.println("Insert ArrayList Time: " + (System.currentTimeMillis() - start)); 

result: 
Insert HashSet Time: 978 
Insert ArrayList Time: 287

我運行這個主梅託德很多次，結果沒有這個之間有更多的不同，插入ArrayList的時間比插入HashSet的時間任何人可以解釋這個怪異的結果要短得多。

來源

2013-02-25 Gospel

可能會有字符串緩存進行字符串。例如。花費時間爲HashSet創建字符串，然後在ArrayList中對其進行緩存和重用。如果您顛倒順序，您會得到什麼結果（例如，先填充ArrayList，再填充HashSet第二個）？ – 2013-02-25 15:22:27

數據結構和算法的精確性能特徵非常依賴於機器和實現。但是，對於我來說ArrayList插入會比插入一個常數因子要快。要插入到ArrayList中，只需要在數組中的某個特定索引處設置一個值。要插入散列集，您需要計算插入項的散列碼並將其映射到數組索引，檢查該索引並根據所找到的內容執行某些操作，最後插入數組。此外HashSet將有更糟的內存位置，所以你會更經常地得到緩存未命中。

還有一個數組大小調整的問題，兩個數據結構都需要這樣做，但兩個數據結構都需要調整大約相同的速率（並且哈希表調整大小可能會因恆定因子而更加昂貴，由於重新哈哈哈）。

這兩種算法都是恆定的（預計）時間，但是哈希表的數量比數組列表要多得多。所以不會因爲一個不變因素而變慢就不奇怪了。（同樣，確切的區別高度依賴於機器和實現。）

來源

2013-02-25 15:28:44 jacobm

哈希集和列表是不同類型的數據結構。所以你應該在選擇之前思考你想要做什麼。

HashSet的

更長的插入時間

上的元素

列表

快速追加時間

朗接入T快速訪問時間上的元素IME

名單是更快，因爲它只需在列表的末尾添加元素，HashSet中已找到在哪裏插入，然後進行元素accessable，這是更多的工作（時間）將其添加到列表的末尾。

來源

2013-02-25 15:18:47 Peter

謝謝，我記得哈希碼在元素插入之前使用了哈希碼去掉元素位置哦，我想我應該更仔細地閱讀本書~~謝謝你這麼多 – Gospel 2013-02-25 15:27:52

列表有一個快速*追加*時間; *插入*時間取決於他們如何在內部實施。 – 2013-02-26 13:32:30

HashSet中插入性能會比ArrayList的

你從哪裏得到這個想法好很多？
HashSet將在搜索即超越ArrayList：get()。
但插入他們有相當的表現。其實ArrayList甚至更快，如果你是陣列範圍之內（不調整大小需要）和散列功能不好

來源

2013-02-25 15:24:06 Cratylus

HashSet的是通過哈希表支持。如果你知道散列表，你會知道有一個散列函數。還有碰撞處理（如果有碰撞），當你添加新的元素時。那麼哈希集不處理衝突，只是如果散列相同覆蓋舊值。但是，如果容量達到，它需要調整大小，並可能重新哈希。它會很慢。

的ArrayList只是對象追加到列表的末尾。如果大小達到，它確實調整大小。

來源

2013-02-25 15:24:31 Kent

其實，你正在得到正確的結果。另外，正如在上面的答案中指出的那樣，這些是不同類型的數據結構。比較它們就像比較自行車和汽車的速度。我認爲在HashSet中插入的時間必須多於在ArrayList中插入的時間，因爲HashSet不允許重複鍵。所以我假設插入之前必須有一些類型的檢查插入前的重複鍵和如何處理它們，這使得它們比ArrayList稍慢。

來源

2013-02-25 15:25:14 TheRookierLearner

ArrayList和HashSet的插入性能測試結果讓我困惑

回答

相關問題