Java 集合操作之交集、并集和差集-蒲公英云

在 Java 编程中，经常需要对集合进行一些操作，比如取两个集合的交集、并集和差集。本文将介绍如何使用 Java 集合框架中的方法来实现这些集合操作，并通过源码解析来深入了解其实现原理。

先上代码

import lombok.extern.slf4j.Slf4j;
import java.util.*;
@Slf4j
public class Test
{
    public static void main(String[] args) {
        System.out.println("===============Set=================");
        Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5, 6));
        // 交集
        Set<Integer> intersectionSet = new HashSet<>(set1);
        intersectionSet.retainAll(set2);
        System.out.println("交集：" + intersectionSet);
        // 并集
        Set<Integer> unionSet = new HashSet<>(set1);
        unionSet.addAll(set2);
        System.out.println("并集：" + unionSet);
        // 差集
        Set<Integer> differenceSet = new HashSet<>(set1);
        differenceSet.removeAll(set2);
        System.out.println("差集：" + differenceSet);
        System.out.println("===============List=================");
        List<Integer> list1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
        List<Integer> list2= new ArrayList<>(Arrays.asList(3, 4, 5, 6));
        // 交集
        List<Integer> intersectionList = new ArrayList<>(list1);
        intersectionList.retainAll(list2);
        System.out.println("交集：" + intersectionSet);
        // 并集
        List<Integer> unionList = new ArrayList<>(list1);
        unionList.addAll(list2);
        System.out.println("并集：" + unionList);
        // 差集
        List<Integer> differenceList = new ArrayList<>(list1);
        differenceList.removeAll(list2);
        System.out.println("差集：" + differenceList);
    }
}

执行结果

===============Set=================
交集：[3, 4]
并集：[1, 2, 3, 4, 5, 6]
差集：[1, 2]
===============List=================
交集：[3, 4]
并集：[1, 2, 3, 4, 3, 4, 5, 6]
差集：[1, 2]

此处各操作会改动原始集合，所以此处的操作都是创建了一个新的集合来执行操作

交集（Intersection）：

交集是指两个集合中共有的元素集合。在 Java 中，可以使用 retainAll 方法来实现两个集合的交集操作。retainAll 方法会修改调用该方法的集合，使其只包含与指定集合共有的元素

源码解析：

在AbstractCollection的 retainAll 方法的内部实现中，通常会遍历调用该方法的集合，并逐个判断元素是否存在于指定集合中。如果元素不存在于指定集合，则通过迭代器的 remove 方法将其从集合中删除。这样就实现了只保留共有元素的操作。

public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                it.remove();
                modified = true;
            }
        }
        return modified;
    }

ArrayList

public boolean retainAll(Collection<?> c) {

    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

并集（Union）：
并集是指将两个集合中的所有元素合并到一个新的集合中。在 Java 中，可以使用 addAll 方法来实现两个集合的并集操作。addAll 方法会将指定集合中的所有元素添加到调用该方法的集合中。
- Set

addAll 方法的内部实现会遍历指定集合，并逐个将元素添加到调用该方法的集合中。如果被添加的元素已经存在于集合中，则不会重复添加。

public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

ArrayList

public boolean addAll(Collection<? extends E> c) {

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

差集（Difference）：
差集是指从一个集合中移除另一个集合中相同的元素后的剩余元素集合。在 Java 中，可以使用 removeAll 方法来实现两个集合的差集操作。removeAll 方法会修改调用该方法的集合，移除与指定集合相同的元素。

Set
在 removeAll 方法的内部实现中，通常会遍历指定集合，并逐个判断元素是否存在于调用该方法的集合中。如果元素存在于调用的集合中，则通过迭代器的 remove 方法将其从集合中移除。这样就实现了移除与指定集合相同元素的操作。

public boolean removeAll(Collection<?> c) {

    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

ArrayList

public boolean removeAll(Collection<?> c) {

    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
/**
 * Retains only the elements in this list that are contained in the
 * specified collection.  In other words, removes from this list all
 * of its elements that are not contained in the specified collection.
 *
 * @param c collection containing elements to be retained in this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (<a href="Collection.html#optional-restrictions">optional</a>),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}