HashSet vs ArrayList 包含性能

Question

在处理大量数据时，我经常发现自己在做以下事情：

HashSet<String> set = new HashSet<String> ();
//Adding elements to the set
ArrayList<String> list = new ArrayList<String> (set);

类似于"dumping"列表中集合的内容。我通常这样做是因为我添加的元素经常包含我想删除的重复项，这似乎是删除它们的简单方法。

仅考虑 objective（避免重复）我也可以写：

ArrayList<String> list = new ArrayList<String> ();
// Processing here
if (! list.contains(element)) list.add(element);
//More processing here

因此不需要将 "dumping" 设置到列表中。但是，我会在插入每个元素之前做一个小检查（我假设 HashSet 也这样做）

这两种可能性中的任何一种明显更有效吗？

Answer 1

ArrayList使用数组来存储数据。 ArrayList.contains 的复杂度为 O(n)。因此，本质上一次又一次地在数组中搜索将具有 O(n^2) 的复杂性。

虽然HashSet使用散列机制将元素存储到各自的桶中。 HashSet 的操作对于长值列表会更快。它将到达 O(1).

中的元素

Answer 2

集合会提供更好的性能（O(n) vs O(n^2) 对于列表），这是正常的，因为集合成员（contains 操作）是 非常有用 一组。

HashSet 的包含与列表的 O(n) 相比是 O(1)，因此如果您经常需要运行 [=12]，则永远不要使用列表=].

Answer 3

如果您不需要列表，我会使用 Set，如果顺序无关紧要并且您想忽略重复项，这就是使用的自然集合。

如果您需要一个没有重复项的列表，则两者都可以。

private Set<String> set = new HashSet<>();
private List<String> list = new ArrayList<>();


public void add(String str) {
    if (set.add(str))
        list.add(str);
}

这样列表将只包含唯一值，原始插入顺序被保留并且操作是 O(1)。

Answer 4

您可以向列表本身添加元素。然后，去重 -

HashSet<String> hs = new HashSet<>(); // new hashset
hs.addAll(list); // add all list elements to hashset (this is the dedup, since addAll works as a union, thus removing all duplicates)
list.clear(); // clear the list
list.addAll(hs); // add all hashset elements to the list

如果您只需要一个带有去重的集合，您也可以在不同的集合上使用 addAll()，这样它就只有唯一值。

Answer 5

我已经做了测试，请检查结果：

对于 HashSet、TreeSet、ArrayList 和 LinkedList 中的 SAME STRING 项目，以下是

的结果

50.000 个 UUID
- 搜索的项目：e608c7d5-c861-4603-9134-8c636a05a42b（索引 25.000）
- hashSet.contains（项目）？真 0 毫秒
- treeSet.contains（项目）？真 0 毫秒
- arrayList.contains（项目）？真 2 毫秒
- linkedList.contains（项目）？真 3 毫秒
5.000.000 个 UUID
- 搜索的项目：61fb2592-3186-4256-a084-6c96f9322a86（索引 25.000）
- hashSet.contains（项目）？真 0 毫秒
- treeSet.contains（项目）？真 0 毫秒
- arrayList.contains（项目）？真 1 毫秒
- linkedList.contains（项目）？真 2 毫秒
5.000.000 个 UUID
- 搜索的项目：db568900-c874-46ba-9b44-0e1916420120（索引 2.500.000）
- hashSet.contains（项目）？真 0 毫秒
- treeSet.contains（项目）？真 0 毫秒
- arrayList.contains（项目）？真 33 毫秒
- linkedList.contains（项目）？真 65 毫秒

根据以上结果，使用数组列表与集合没有太大区别。也许您可以尝试修改此代码并将 String 替换为您的 Object 然后查看差异...

    public static void main(String[] args) {
        Set<String> hashSet = new HashSet<>();
        Set<String> treeSet = new TreeSet<>();
        List<String> arrayList = new ArrayList<>();
        List<String> linkedList = new LinkedList<>();

        List<String> base = new ArrayList<>();

        for(int i = 0; i<5000000; i++){
            if(i%100000==0) System.out.print(".");
            base.add(UUID.randomUUID().toString());
        }

        System.out.println("\nBase size : " + base.size());
        String item = base.get(25000);
        System.out.println("SEARCHED ITEM : " + item);

        hashSet.addAll(base);
        treeSet.addAll(base);
        arrayList.addAll(base);
        linkedList.addAll(base);

        long ms = System.currentTimeMillis();
        System.out.println("hashSet.contains(item) ? " + (hashSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
        System.out.println("treeSet.contains(item) ? " + (treeSet.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
        System.out.println("arrayList.contains(item) ? " + (arrayList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
        System.out.println("linkedList.contains(item) ? " + (linkedList.contains(item)? "TRUE " : "FALSE") + (System.currentTimeMillis()-ms) + " ms");
    }

HashSet vs ArrayList 包含性能

HashSet vs ArrayList contains performance

java

arraylist

hashset