Метод HashSet <T> .removeAll на удивление медленный

Джон Скит недавно поднял интересную тему программирования в своем блоге: «В моей абстракции есть дыра, дорогая Лиза, дорогая Лиза» (курсив мой ):

У меня есть набор - собственно HashSetговоря. Я хочу удалить из него некоторые элементы… а многие из них могут не существовать. Фактически, в нашем тестовом примере ни один из элементов в коллекции «удаления» не будет в исходном наборе. Звучит - и это действительно так - кодировать очень легко. В конце концов, мы ведь должны Set<T>.removeAllнам помочь, верно?

Мы указываем размер «исходного» набора и размер «удаленной» коллекции в командной строке и строим их оба. Исходный набор содержит только неотрицательные целые числа; набор удалений содержит только отрицательные целые числа. Мы измеряем, сколько времени требуется для удаления всех элементов, используя System.currentTimeMillis()секундомер, который не является самым точным в мире, но, как вы увидите, в данном случае более чем достаточно. Вот код:

import java.util.*;
public class Test 
{ 
    public static void main(String[] args) 
    { 
       int sourceSize = Integer.parseInt(args[0]); 
       int removalsSize = Integer.parseInt(args[1]); 
        
       Set<Integer> source = new HashSet<Integer>(); 
       Collection<Integer> removals = new ArrayList<Integer>(); 
        
       for (int i = 0; i < sourceSize; i++) 
       { 
           source.add(i); 
       } 
       for (int i = 1; i <= removalsSize; i++) 
       { 
           removals.add(-i); 
       } 
        
       long start = System.currentTimeMillis(); 
       source.removeAll(removals); 
       long end = System.currentTimeMillis(); 
       System.out.println("Time taken: " + (end - start) + "ms"); 
    }
}

Начнем с легкой работы: исходный набор из 100 элементов и 100 элементов для удаления:

c:UsersJonTest>java Test 100 100
Time taken: 1ms

Итак, мы не ожидали, что это будет медленно ... очевидно, что мы можем немного ускорить процесс. Как насчет того, чтобы удалить один миллион элементов и 300 000 элементов?

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

Хм. Это все еще кажется довольно быстрым. Теперь я чувствую, что был немного жесток, прося его удалить все это. Давайте сделаем это немного проще - 300 000 исходных элементов и 300 000 удалений:

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

Прошу прощения? Почти три минуты ? Ой! Конечно, должно быть проще удалить элементы из меньшей коллекции, чем та, которую мы обработали за 38 мс?

Может кто-нибудь объяснить, почему это происходит? Почему HashSet<T>.removeAllметод такой медленный?

Поведение (отчасти) задокументировано в javadoc :

Эта реализация определяет меньшее из этого набора и указанной коллекции, вызывая метод размера для каждого из них. Если в этом наборе меньше элементов , то реализация выполняет итерацию по этому набору, проверяя каждый элемент, возвращаемый итератором, по очереди, чтобы увидеть , содержится ли он в указанной коллекции . Если он так содержится, он удаляется из этого набора с помощью метода remove итератора. Если в указанной коллекции меньше элементов, то реализация выполняет итерацию по указанной коллекции, удаляя из этого набора каждый элемент, возвращенный итератором, с помощью метода remove этого набора.

Что это означает на практике, когда вы звоните source.removeAll(removals);:

• если removalsразмер коллекции меньше, чем source, вызывается removeметод HashSet, который выполняется быстро.

• если removalsразмер коллекции равен или больше, чем у source, то removals.containsвызывается, что медленно для ArrayList.

Быстрая починка:

Collection<Integer> removals = new HashSet<Integer>();

Обратите внимание, что есть открытая ошибка , очень похожая на то, что вы описываете. Суть в том, что это, вероятно, плохой выбор, но его нельзя изменить, потому что он задокументирован в javadoc.

Для справки это код removeAll(в Java 8 - другие версии не проверял):

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;

    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}