散列集和數組列表性能

我已經實現了一個方法，它只是圍繞一組包含多個不同模塊上的數據的CSV文件進行循環。然後將這個'moduleName'添加到hashSet中。（代碼如下）散列集和數組列表性能

我已經使用了一個hashSet，因爲它保證不會插入重複項而不是ArrayList，它必須使用contains（）方法並遍歷列表來檢查它是否已經存在。

我相信使用哈希集具有比數組列表更好的性能。我說得對嗎？如果使用

如何工作的每一個數據結構中的表現：

此外，有人可以解釋一下嗎？

使用big-O符號的複雜性是什麼？

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

for (File f: marksheetFiles){ 
    try { 
     csvFileReader = new CSVFileReader(f); 
     csvReader = csvFileReader.readFile(); 
     csvReader.readHeaders(); 

     while(csvReader.readRecord()){ 
      String moduleName = csvReader.get("Module"); 

      if (!moduleName.isEmpty()){ 
       modulesUploaded.add(moduleName); 
      } 
     } 

    } catch (IOException e) { 
     e.printStackTrace(); 
    } 

    csvReader.close(); 
} 
return modulesUploaded;

}

來源

2012-04-17 user1339335

您可能希望將您正在使用的語言作爲其中一個標籤（您必須消除其中一個標籤，但語言幾乎無疑更重要）。 – 2012-04-17 17:54:03

他們是完全不同的類，所以問題是：你想要什麼樣的行爲？

HashSet確保沒有重複，給你一個O（1）方法，但不保留順序。
ArrayList不確保沒有重複，是O（n）但您可以控制條目的順序。

來源

2012-04-17 18:07:42 biziclop

我相信使用哈希集具有比數組列表更好的性能。我說得對嗎？

有很多（不管是什麼意思）條目，是的。然而，對於小數據量的原始線性搜索可能比哈希算法更快。盈虧平衡點在哪裏，你只需要衡量一下。我的直覺是，只有不到10個元素，線性查找可能更快;有超過100個元素散列可能更快，但這只是我的感覺...

從HashSet查找恆定時間O（1），前提是元素的hashCode實現是理智的。從列表中線性查找是線性時間O（n）。

來源

2012-04-17 18:10:33

My experiment顯示HashSet比包含3個元素的集合開始的ArrayList更快。

一個完整的結果表

| Boost | Collection Size | 
| 2x |  3 elements | 
| 3x |  10 elements | 
| 6x |  50 elements | 
| 12x |  200 elements | <= proportion 532-12 vs 10.000-200 elements 
| 532x | 10.000 elements | <= shows linear lookup growth for the ArrayList

來源

2013-11-07 16:19:08

它取決於數據結構的使用。

您正在將數據存儲在HashSet中，對於您的案例來說，存儲HashSet要好於ArrayList（因爲您不需要重複條目）。但只是存儲不是通常的意圖。

這取決於您希望如何讀取和處理存儲的數據。如果您想要順序訪問或基於隨機索引的訪問，那麼ArrayList更好，或者如果排序並不重要，那麼HashSet就更好。

如果排序很重要，但您想進行大量修改（添加和刪除），則LinkedList更好。

爲了訪問特定的元素HashSet將有時間複雜度爲O（1），如果你要使用ArrayList這本來是O（N）爲你自己所指出的那樣，你將不得不iterate在列表中看到如果元素不存在。

來源

2016-03-05 12:55:36

散列集和數組列表性能

回答

相關問題