《手册》详解 14节 集合去重的正确姿势学员并集差集问题解答

一、背景

《阿里巴巴 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<Integer> integers1 = Lists.newArrayList(1, 2);

List<Integer> integers2 = Lists.newArrayList(1, 2, 3);

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

三、 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.
 * <p>
 * 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.
 * </p>
 *
 * @param <E> the type of elements in this bag
 * @since 3.0 (previously in main package v2.0)
 */
public class HashBag<E> extends AbstractMapBag<E> implements Serializable {

// 省略
}

使用 HashMap 来提供数据存储，实现包的结构。此类是包的标准实现方式。

包存储集合中的每个元素和出现的次数。

还提供了对象添加和移除的方法。

看到这里再结合差集的概念，是不是就突然懂了呢，哈哈。

如果想深入了解自行查看和学习源码。

当然可能还有其他工具类能实现此功能，而此工具类还提供了更多List 相关工具函数，大家后续自行探索。

四、总结

本问针对学员的课后提问进行了全面的解答。

通过本文的讲解，希望大家能够明白很多人学习不深入的原因，本质上是方法和态度的问题。

很多人根本不会意识到：学习的习惯和意识才是拉开差距的根本原因之一。

希望大家能够通体会到专栏所希望大家学习的不止是知识点而是学习的方法和研究问题的态度。

希望大家在未来的一段时间，能够通过专栏的一系列讲解和学习，将学习问题的方法当做习惯，能够通过一个知识点学到更多的知识，这也是专栏的最大价值之一。

想了解更多《手册》详解的更多内容，想学习更多开发和避坑技巧，少走弯路，请关注《阿里巴巴Java 开发手册》详解专栏。

大家购买前有啥疑问或者想和其他读者交流可以用base64算法解密以下内容： 5re75Yqg5b6u5L+hICBmZW5neWVsaWFvemhhaSAg5bm255WZ6KiA77ya5Yqg5YWl44CK5omL5YaM44CL6K+m6Kej5LiT5qCP6K+76ICF5Lqk5rWB576k44CC

如果本文或者专栏对你有帮助，欢迎介绍给身边的同学、朋友，你的支持是我持续创作的最大动力。