哈希集和数组列表性能

我已经实现了一种方法,它只是循环使用一组CSV文件,这些文件包含许多不同模块上的数据。然后,这会将“模块名称”添加到哈希集中。(代码如下所示)

我使用了一个hashSet,因为它保证没有重复项入,而不是ArrayList,ArrayList必须使用reclude()方法并循环访问列表以检查它是否已经存在。

我相信使用哈希集比数组列表具有更好的性能。我这样说是对的吗?

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

  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; 
    

    }


答案 1

我的实验表明,这比从包含3个元素的集合开始更快。HashSetArrayList

完整的结果表

| 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

答案 2

他们是完全不同的阶级,所以问题是:你想要什么样的行为?

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


推荐