14-1 集合并集差集问题

一、背景
《阿里巴巴 Java开发手册》详解专栏 的第 14节，主要讲解了集合去重的正确姿势，对 List 和Set 去重性能差异做了分析，并给出了性能对比的效果。

@慕粉3543028 问了一个编程中可能常见的问题：

请问一个问题：
现在有
List integers = Arrays.asList(1, 2);
List integers2 = Arrays.asList(1, 2,3);
怎么求他们的 差集 和 交集

针对这个问题我主要想谈两点：

• 一个是不是特别推荐用Arrays#asList；
  
• 一个是 List求 差集和交集常见用方式；
  

二、 不推荐用Arrays#asList
阿里手册中有讲到这样的规范：

【强制】使用工具类Arrays.asList()把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。
专栏的 11 节也有重点展开的论述。
如果想要构造不可变 List ,请直接使用

java.util.Collections#unmodifiableList
或者
org.apache.commons.collections4.ListUtils#unmodifiableList
去构造不可修改的 List，这样看到源码更容易明确这是一个不可修改的 LIst。
我猜，你这么写是为了方便，不想创建一个 ArrayList再填充对象，对吧？
要善用工具类，可以用 guava 包
com.google.common.collect.Lists#newArrayList(E…)
写法如下：

自己写个工具类也行啊，对吧…

三、 List求 差集和交集常见用方式
实际开发中去重场景比较多，求交集和并集相对少一点点。
而且希望大家一定一定一定是先思考自己的思路，然后再和答案作对比，否则收获不会太大。
按照咱们专栏的惯例，还是要先思考，而不是直接记忆答案，这点很重要。
3.1 先分析
3.1.1求并集

求并集的逻辑很简单，两个List 的元素加到一起，对吧。
我们可以 list1.addAll(list2)， 可以吧？
这样有啥问题呢？
这样会不符合原始的 list1 的含义，即污染了 list1 集合。
那么怎么办？
不如新建一个空的list 然后分别通过 addAll 添加进去应该可以把？

3.1.2 求交集
求交集就是两个集合重叠的一部分数据，是不是和去重很相似？
是不是可以遍历第一个List ，然后判断第二个List 是否包含当前元素，如果包含则是交集的元素，否则不是。
这样会存在专栏所讲到的性能问题？
是不是应该利用 Set的特性呢？ 怎么利用呢？大家可以想一想。

3.2 参考答案
希望你真正进行了思考，而不是直接跳过前面看到这里。

下面我们用 commons-collections4 工具类实现这个功能。
3.2.1 并集
org.apache.commons.collections4.ListUtils#union

List<Integer> integers1 = Lists.newArrayList(1, 2);
List<Integer> integers2 = Lists.newArrayList(1, 2, 3);
List<Integer> union = ListUtils.union(integers1, integers2);
System.out.println(union);

3.2.2 交集
org.apache.commons.collections4.ListUtils#intersection

List<Integer> integers1 = Lists.newArrayList(1, 2);
List<Integer> integers2 = Lists.newArrayList(1, 2, 3);
List<Integer> intersection = ListUtils.intersection(integers1, integers2);
System.out.println(intersection);

是不是这样就结束了呢？
3.3 Learn More
找到方法其实并不那么值得开心，你更应该因为你懂得其底层实现而开心，所以看源码：

3.3.1 看源码
并集的实现方式：

/**
 * Returns a new list containing the second list appended to the
 * first list.  The {@link List#addAll(Collection)} operation is
 * used to append the two given lists into a new list.
 *
 * @param <E> the element type
 * @param list1  the first list
 * @param list2  the second list
 * @return a new list containing the union of those lists
 * @throws NullPointerException if either list is null
 */
public static <E> List<E> union(final List<? extends E> list1, final List<? extends E> list2) {
    final ArrayList<E> result = new ArrayList<>(list1.size() + list2.size());
    result.addAll(list1);
    result.addAll(list2);
    return result;
}

交集的实现方式：

/**
 * Returns a new list containing all elements that are contained in
 * both given lists.
 *
 * @param <E> the element type
 * @param list1  the first list
 * @param list2  the second list
 * @return  the intersection of those two lists
 * @throws NullPointerException if either list is null
 */
public static <E> List<E> intersection(final List<? extends E> list1, final List<? extends E> list2) {
    final List<E> result = new ArrayList<>();
    List<? extends E> smaller = list1;
    List<? extends E> larger = list2;
    if (list1.size() > list2.size()) {
        smaller = list2;
        larger = list1;
    }
 final HashSet<E> hashSet = new HashSet<>(smaller);
    for (final E e : larger) {
        if (hashSet.contains(e)) {
            result.add(e);
            hashSet.remove(e);
        }
    }
    return result;
}

如果你前面没有想出来，可以看看这里的写法，会有很大收获。

所以本文就这样完美结束了吗？
NO…
3.3.2 那么 List 的差集怎么求呢？
org.apache.commons.collections4.ListUtils#subtract

/**
 * Subtracts all elements in the second list from the first list,
 * placing the results in a new list.
 * <p>
 * This differs from {@link List#removeAll(Collection)} in that
 * cardinality is respected; if <Code>list1</Code> contains two
 * occurrences of <Code>null</Code> and <Code>list2</Code> only
 * contains one occurrence, then the returned list will still contain
 * one occurrence.
 *
 * @param <E> the element type
 * @param list1  the list to subtract from
 * @param list2  the list to subtract
 * @return a new list containing the results
 * @throws NullPointerException if either list is null
 */
public static <E> List<E> subtract(final List<E> list1, final List<? extends E> list2) {
    final ArrayList<E> result = new ArrayList<>();
    final HashBag<E> bag = new HashBag<>(list2);
    for (final E e : list1) {
        if (!bag.remove(e, 1)) {
            result.add(e);
        }
    }
    return result;
}

那么 HashBag 是啥？
org.apache.commons.collections4.bag.HashBag
可以看其注释：
/*
Implements {@code Bag}, using a {@link HashMap} to provide the
data storage. This is the standard implementation of a bag.

A {@code Bag} stores each object in the collection together with a
count of occurrences. Extra methods on the interface allow multiple copies
of an object to be added or removed at once. It is important to read the
interface javadoc carefully as several methods violate the
{@link Collection} interface specification.