HashSet的removeAll()方法性能何如？

1. 引言

HashSet是 Java 集合 Set 的一个实现类，Set 是一个接口，其实现类除 HashSet 之外，还有 TreeSet ，并继承了Collection，HashSet 集合很常用。本篇文章中，我们将讨论下 java.util.HashSet 类中 removeAll() 方法 的性能。

2. HashSet.removeAll()

removeAll 方法删除集合 中包含的所有元素：

Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);
set.add(4);

Collection<Integer> collection = new ArrayList<Integer>();
collection.add(1);
collection.add(3);

set.removeAll(collection);

Integer[] actualElements = new Integer[set.size()];
Integer[] expectedElements = new Integer[] { 2, 4 };
assertArrayEquals(expectedElements, set.toArray(actualElements));

结果，元素 1 和 3 将会从集合中移除。

3. 内部实现及其时间复杂度

removeAll() 方法通过调用 size()方法来确定上述代码中的set和collection 哪个更小。

如果 collection的元素少于 set， 则遍历 collection， 遍历的时间复杂度为 O(n) ，同时检查遍历的元素是否存在 时间复杂度为 O(1) 的 set 中。如果元素存在，将调用 set 的 remove() 方法将其从 set 中移除，时间复杂度仍然为O(1)。所以总的时间复杂度仍然为O(n)。

如果 set中的元素少于 collection， 那就遍历set， 遍历的时间复杂度为 O(n)。然后，通过调用 contains() 方法来检查 collection 中是否存在这个元素。如果存在这样一个元素，那么该元素就会从 set 中移除。所以时间复杂度取决于contains()方法的时间复杂度。

在本例中，如果collection的实例是 ArrayList，那么 contains()方法的时间复杂度为O(m)，所以从set中移除 ArrayList 中所有元素的总时间复杂度是O(n*m）。

如果collection 实例仍然是 HashSet，则 contains() 方法的时间复杂度为O(1)。所以从set中移除HashSet中所有元素的总时间复杂度是 O(n) 。

4. 性能

为了查看以上三种情况之间的性能差异，让我们编写一个简单的JMH基准测试。

对于第一种情况，我们将初始化 set 和 collection，其中 set 中的元素多于 collection 中的元素。

在第二种情况下，我们同样将初始化 set和 collection，其中 collection 中的元素多于 set 中的元素。

在第三种情况下，我们将初始化两个 set，其中第二个set比第一个 set 拥有更多的元素：

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class HashSetBenchmark {

    @State(Scope.Thread)
    public static class MyState {
        private Set employeeSet1 = new HashSet<>();
        private List employeeList1 = new ArrayList<>();
        private Set employeeSet2 = new HashSet<>();
        private List employeeList2 = new ArrayList<>();
        private Set<Employee> employeeSet3 = new HashSet<>();
        private Set<Employee> employeeSet4 = new HashSet<>();

        private long set1Size = 60000;
        private long list1Size = 50000;
        private long set2Size = 50000;
        private long list2Size = 60000;
        private long set3Size = 50000;
        private long set4Size = 60000;

        @Setup(Level.Trial)
        public void setUp() {
            // populating sets
        }
    }
}

之后，我们添加基准测试：

@Benchmark
public boolean given_SizeOfHashsetGreaterThanSizeOfCollection_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {
    return state.employeeSet1.removeAll(state.employeeList1);
}

@Benchmark
public boolean given_SizeOfHashsetSmallerThanSizeOfCollection_whenRemoveAllFromHashSet_thenBadPerformance(MyState state) {
    return state.employeeSet2.removeAll(state.employeeList2);
}

@Benchmark
public boolean given_SizeOfHashsetSmallerThanSizeOfAnotherHashSet_whenRemoveAllFromHashSet_thenGoodPerformance(MyState state) {
    return state.employeeSet3.removeAll(state.employeeSet4);
}

结果如下：

Benchmark                                              Mode  Cnt            Score            Error  Units
HashSetBenchmark.testHashSetSizeGreaterThanCollection  avgt   20      2700457.099 ±     475673.379  ns/op
HashSetBenchmark.testHashSetSmallerThanCollection      avgt   20  31522676649.950 ± 3556834894.168  ns/op
HashSetBenchmark.testHashSetSmallerThanOtherHashset    avgt   20      2672757.784 ±     224505.866  ns/op

我们可以看到，当 HashSet 的元素少于 Collection，collection 作为参数传递给 removeAll() 方法时，HashSet.removeAll() 的性能表现很差。但是，当removeAll() 方法的参数为 HashSet 时，则性能表现良好。

5. 总结

在本文中，我们探讨了 HashSet 中 removeAll() 方法的性能。当 set 的元素少于 collection 时，removeAll() 的性能取决于 collection 的 contains() 方法的时间复杂度。