HashSet与ArrayList包含性能

Question

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

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

类似于"转储"列表中集的内容.我通常这样做,因为我添加的元素通常包含我要删除的重复项,这似乎是一种删除它们的简单方法.

只考虑到这个目标(避免重复),我也可以写:

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

因此无需将该集"转储"到列表中.但是,在插入每个元素之前我会做一个小的检查(我假设HashSet也这样做)

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

Answer 1

该集合将提供更好的性能(O(n)与O(n^2)列表相比),这是正常的,因为集合成员资格(contains操作)是集合的目的.

对于包含HashSet被O(1)比较O(n)的清单,因此,你不应该使用一个列表,如果你经常需要运行contains.

Answer 2

在ArrayList使用用于存储数据的数组.这 ArrayList.contains将具有O(n)复杂性.因此,基本上一次又一次地搜索数组将具有O(n^2)复杂性.

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

Answer 3

我做了一个测试,所以请检查结果:

对于HashSet,TreeSet,ArrayList和LinkedList中的SAME STRING项,以下是结果

1. 50.000 UUID
   • 搜索项目:e608c7d5-c861-4603-9134-8c636a05a42b(索引25.000)
   • hashSet.contains(item)？TRUE 0 ms
   • treeSet.contains(item)？TRUE 0 ms
   • arrayList.contains(item)？是2毫秒
   • linkedList.contains(item)？TRUE 3毫秒
2. 5.000.000 UUID
   • 搜索项目:61fb2592-3186-4256-a084-6c96f9322a86(索引25.000)
   • hashSet.contains(item)？TRUE 0 ms
   • treeSet.contains(item)？TRUE 0 ms
   • arrayList.contains(item)？是1毫秒
   • linkedList.contains(item)？是2毫秒
3. 5.000.000 UUID
   • 搜索项目:db568900-c874-46ba-9b44-0e1916420120(索引号2.500.000)
   • hashSet.contains(item)？TRUE 0 ms
   • treeSet.contains(item)？TRUE 0 ms
   • arrayList.contains(item)？TRUE 33毫秒
   • linkedList.contains(item)？是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");
    }

Answer 4

如果您不需要列表，则只使用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）。