散列集和数组列表性能

Question

我已经实现了一种方法,它只是循环一组包含许多不同模块数据的CSV文件.然后将'moduleName'添加到hashSet中.(代码如下所示)

我使用了一个hashSet,因为它保证不会插入重复项而不是ArrayList,它必须使用contains()方法并遍历列表以检查它是否已存在.

我相信使用哈希集具有比数组列表更好的性能.我说的是正确的吗？

还有,有人可以向我解释一下:

1. 如果使用,如何处理每个数据结构的性能？

2. 使用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; 
   

   }

Answer 1

我的实验表明,HashSet比起ArrayList包含3个元素的集合更快.

完整的结果表

| 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

Answer 2

它们是完全不同的类,所以问题是:你想要什么样的行为？

HashSet确保没有重复项,为您提供O(1)contains()方法但不保留顺序.
ArrayList不确保没有重复,contains()是O(n)但您可以控制条目的顺序.

Answer 3

我相信使用哈希集具有比数组列表更好的性能.我说的是正确的吗？

有很多(无论它意味着)条目,是的.但是,对于较小的数据大小,原始线性搜索可能比散列更快.确切地说,收支平衡就在哪里,你只需要衡量.我的直觉是,只需少于10个元素,线性查找可能更快; 有超过100个元素散列可能更快,但这只是我的感觉......

来自HashSet的查找是常量时间O(1),前提是元素的hashCode实现是理智的.列表中的线性查找是线性时间O(n).

Answer 4

这取决于数据结构的用法。

您正在将数据存储在中HashSet，并且对于您而言，存储数据HashSet要比ArrayList（因为您不希望重复输入）更好。但是，仅仅存储并不是通常的意图。

这取决于您希望如何读取和处理存储的数据。如果您想要顺序访问或基于随机索引的访问，则ArrayList更好，或者排序无关紧要，则HashSet更好。

如果订购很重要，但是您想进行很多修改（添加和删除），则LinkedList会更好。

访问特定元素的HashSet时间复杂度为O（1），如果您曾经使用过，则您将ArrayList被指定为O（N），就像您自己指出的那样，您将必须iterate遍历列表并查看该元素是否不存在。