List取交集、并集、差集

突然被面试官问到这样一个问题，List怎么取交集。我想了一会后说道双重循环？
自己都觉得面试官想要的答案应该不是这个，效率太低了。
后面问面试官答案，面试官告诉我可以将其中一个llist转成一个map或set，再遍历第二个list的时候判断，map/set中是否存在该元素，这样就可以求出交集。可以省去很多比较，速度是绝对快很多。

public static void main(String[] args) {
        List<String> listA = new ArrayList<String>();
        List<String> listB = new ArrayList<String>();
        listA.add("A");
        listA.add("B");
        listA.add("C");
        listA.add("D");
        listB.add("B");
        listB.add("C");
        listB.add("D");
        listB.add("E");
        Set map = new HashSet();
        for (String tmp: listA) {
            map.add(tmp);
        }
        for (String tmp: listB) {
            if(map.contains(tmp)){
                System.out.println(tmp);
            }

        }
    }

运行结果如下

后来我又想有没有别的方法呢，于是又去网上搜了一波。然后我竟然发现ArrayList本身就提供了取交集的方法。

public static void main(String[] args) {
        List<String> listA = new ArrayList<String>();
        List<String> listB = new ArrayList<String>();
        listA.add("A");
        listA.add("B");
        listA.add("C");
        listA.add("D");
        listB.add("B");
        listB.add("C");
        listB.add("D");
        listB.add("E");
        listA.retainAll(listB);
        System.out.println("交集："+listA);
    }

运行结果：

好奇之下我点进去看了源码

ArrayList对此方法进行了重写，先对传入的参数进行了非空判断

然后调用了batchRemove方法执行取交集逻辑

 final Object[] elementData = this.elementData;

这里要注意的是这样赋值，elementData引用还是指向this.elementData，所以后面直接操作elementData改变的会是this。
对自身进行了遍历，在遍历的过程中判断传进来的集合中是否包含当前元素，如果包含，则按顺序写入当前集合中。
finally中的第一个判断有点没懂，我理解的是执行完循环后r是必=size的，有大佬看懂了可以留言告诉我。
第二个判断就是将交集后面多余的元素去除。

并集

先去掉A中并集，再将B集合中元素放入A元素

public static void main(String[] args) {
        List<String> listA = new ArrayList<String>();
        List<String> listB = new ArrayList<String>();
        listA.add("B");
        listA.add("C");
        listA.add("D");
        listB.add("E");
        listB.add("B");
        listB.add("C");
        listB.add("D");
        listA.removeAll(listB);
        listA.addAll(listB);
        System.out.println(listA);
    }

运行结果：

差集

removeAll是去掉并集，这里求差集需要注意得在长集合中去掉并集。
否则可能出现集合A有B、C。集合B有B、C、D。此时listA.removeAll(listB)，集合A中全是并集被全部移除，输出[]的情况。

public static void main(String[] args) {
        List<String> listA = new ArrayList<String>();
        List<String> listB = new ArrayList<String>();
        listA.add("B");
        listA.add("C");
        listA.add("D");
        listB.add("E");
        listB.add("B");
        listB.add("C");
        listB.add("D");
        if(listB.size() >= listA.size()){
            listB.removeAll(listA);
            System.out.println(listB);
        }else{
            listA.removeAll(listB);
            System.out.println(listA);
        }
    }

运行结果

参考：List集合取交集、并集、去除重复数据等