«1. Обзор

HashSet — это коллекция для хранения уникальных элементов.

В этом руководстве мы обсудим производительность метода removeAll() в классе java.util.HashSet.

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() для набора и коллекции.

Если в коллекции меньше элементов, чем в наборе, то выполняется итерация по указанной коллекции с временной сложностью O(n). Он также проверяет, присутствует ли элемент в наборе с временной сложностью O(1). И если элемент присутствует, он удаляется из набора с помощью метода remove() набора, который снова имеет временную сложность O(1). Таким образом, общая временная сложность равна O(n).

Если в наборе меньше элементов, чем в коллекции, то он выполняет итерацию по этому набору, используя O (n). Затем он проверяет, присутствует ли каждый элемент в коллекции, вызывая метод contains(). И если такой элемент присутствует, то элемент удаляется из набора. Так что это зависит от временной сложности метода contains().

Теперь в этом случае, если коллекция является ArrayList, временная сложность метода contains() равна O(m). Таким образом, общая временная сложность удаления всех элементов, присутствующих в ArrayList, из набора составляет O (n * m).

Если коллекция снова представляет собой HashSet, временная сложность метода contains() равна O(1). Таким образом, общая временная сложность удаления всех элементов, присутствующих в HashSet, из набора составляет O (n).

4. Производительность

Чтобы увидеть разницу в производительности между тремя вышеприведенными случаями, давайте напишем простой тест производительности JMH.

В первом случае мы инициализируем набор и коллекцию, где у нас больше элементов в наборе, чем в коллекции. Во втором случае мы инициализируем набор и коллекцию, где у нас больше элементов в коллекции, чем в наборе. И в третьем случае мы инициализируем 2 набора, где у нас будет 2-й набор с большим количеством элементов, чем 1-й: 

@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.removeAll() работает очень плохо, когда HashSet содержит меньше элементов, чем Collection, которая передается в качестве аргумента в метод removeAll(). Но когда другой коллекцией снова является HashSet, то производительность хорошая.

5. Заключение

В этой статье мы рассмотрели производительность removeAll() в HashSet. Когда в наборе меньше элементов, чем в коллекции, производительность removeAll() зависит от временной сложности метода contains() коллекции.

Как обычно, полный код этой статьи доступен на GitHub.