java - Hash Set 和 Array List 的表现

Question

我已经实现了一种方法，它简单地循环一组包含许多不同模块上的数据的 CSV 文件。然后将“moduleName”添加到 hashSet 中。（代码如下所示）

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

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

另外，有人可以向我解释一下：

如果使用每个数据结构的性能如何？

使用大 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;

}

score 53 · Accepted Answer

我的实验表明，这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

score 26 · Accepted Answer

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

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

score 22 · Accepted Answer

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

有很多（无论是什么意思）条目，是的。但是，对于较小的数据大小，原始线性搜索可能比散列更快。盈亏平衡点在哪里，你必须衡量。我的直觉是，如果元素少于 10 个，线性查找可能会更快；超过 100 个元素的散列可能更快，但这只是我的感觉......

如果元素的 hashCode 实现是健全的，从 HashSet 中查找是恒定的时间，O(1)。从列表中线性查找是线性时间，O(n)。

score 5 · Accepted Answer

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

您将数据存储在中HashSet，并且对于您的情况，存储HashSet比ArrayList（因为您不希望重复条目）更好。但仅仅存储并不是通常的意图。

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

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

访问特定元素HashSet的时间复杂度为 O (1)，如果您使用ArrayList它，它会是 O (N)，正如您自己指出的那样，您必须iterate通过列表查看该元素是否不存在。

java - Hash Set 和 Array List 的表现

4 回答 4

Related

Reference