大量数据的集合去重-->效率

作者：巧克力er

坐标：江苏 南京

场景：
有两个数据量很大的集合 list1， list2，现在需要去掉两个集合中都存在的数据。

方法一：一个最常见的方法

public class Collex {
    public static void main(String[] args) {
        int max_len = 50000;
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        for (int i=0; i<max_len; i++) {
            list1.add((int)(Math.random()*max_len));
            list2.add((max_len/2)+(int)(Math.random()*max_len));
        }
         
        System.out.printf("list1:%d, list2:%d\n", list1.size(), list2.size());
        long start = System.currentTimeMillis();
        
        List<Integer> list1Copy = new ArrayList<Integer>(list1);
        list1.removeAll(list2);
        list2.removeAll(list1Copy);
        long end = System.currentTimeMillis();
        System.out.printf("list1 clean:%d, list2 clean:%d\n", list1.size(), list2.size());
        System.out.printf("time spent : %dms\n", end-start);
    }
}

方法一结果展示：

list1:50000, list2:50000
list1 clean:34004, list2 clean:34063
time spent : 12346ms

方法二：

public class CollectionCompire {

    public static void main(String[] args) {
        int max_len = 50000;
        ArrayList<Integer> list1 = new ArrayList<Integer>();
        ArrayList<Integer> list2 = new ArrayList<Integer>();
        for (int i=0; i<max_len; i++) {
            list1.add((int)(Math.random()*max_len));
            list2.add((max_len/2)+(int)(Math.random()*max_len));
        }
         
        System.out.printf("list1:%d, list2:%d\n", list1.size(), list2.size());
        long start = System.currentTimeMillis();
         
        HashSet<Integer> set_all = new HashSet<Integer>();
        for (int i=0; i<list1.size(); i++) {
            set_all.add(list1.get(i));
        }
        HashSet<Integer> set_dup = new HashSet<Integer>();
        ArrayList<Integer> list2_clean = new ArrayList<Integer>();
        for (int i=0; i<list2.size(); i++) {
            if (set_all.add(list2.get(i))) {  //in list2 but not in list1
                list2_clean.add(list2.get(i));
            } else {
                set_dup.add(list2.get(i));  //in list2 and also in list1
            }
        }
        ArrayList<Integer> list1_clean = new ArrayList<Integer>();
        for (int i=0; i<list1.size(); i++) {
            if (set_dup.add(list1.get(i))) {  //in list1 but not in the duplicated set
                list1_clean.add(list1.get(i));
            }
        }
         
        long end = System.currentTimeMillis();
        System.out.printf("list1 clean:%d, list2 clean:%d\n", list1_clean.size(), list2_clean.size());
        System.out.printf("time spent : %dms\n", end-start);
    }
}

方法二结果展示：

list1:50000, list2:50000
list1 clean:21709, list2 clean:21613
time spent : 67ms

这里可以看出看来当集合的数据量达到50000的时候，方法一的耗时要远远大于方法二。