Производительность removeAll() в HashSet

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 .