Неожиданное время выполнения кода HashSet

Итак, изначально у меня был этот код:

import java.util.*;

public class sandbox {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < 100_000; i++) {
            hashSet.add(i);
        }

        long start = System.currentTimeMillis();

        for (int i = 0; i < 100_000; i++) {
            for (Integer val : hashSet) {
                if (val != -1) break;
            }

            hashSet.remove(i);
        }

        System.out.println("time: " + (System.currentTimeMillis() - start));
    }
}

Для запуска вложенных циклов for на моем компьютере требуется около 4 секунд, и я не понимаю, почему это заняло так много времени. Внешний цикл выполняется 100 000 раз, внутренний цикл for должен выполняться 1 раз (поскольку любое значение hashSet никогда не будет равно -1), а удаление элемента из HashSet равно O (1), поэтому должно быть около 200 000 операций. Если в секунду обычно выполняется 100 000 000 операций, почему мой код запускается за 4 секунды?

Кроме того, если строка hashSet.remove(i);закомментирована, код занимает всего 16 мс. Если внутренний цикл for закомментирован (но не закомментирован hashSet.remove(i);), код занимает всего 8 мс.

Вы создали предельный вариант использования HashSet, при котором алгоритм ухудшается до квадратичной сложности.

Вот упрощенный цикл, который занимает так много времени:

for (int i = 0; i < 100_000; i++) {
    hashSet.iterator().next();
    hashSet.remove(i);
}

async-profiler показывает, что почти все время тратится внутри java.util.HashMap$HashIterator()конструктора:

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
--->        do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

Выделенная строка представляет собой линейный цикл, который выполняет поиск первого непустого сегмента в хэш-таблице.

Так как Integerимеет тривиальное значение hashCode(т. Е. HashCode равен самому числу), оказывается, что последовательные целые числа в основном занимают последовательные сегменты в хеш-таблице: число 0 идет в первый сегмент, номер 1 - во второй.

Теперь вы удаляете последовательные числа от 0 до 99999. В простейшем случае (когда корзина содержит один ключ) удаление ключа осуществляется как обнуление соответствующего элемента в массиве корзины. Обратите внимание, что таблица не сжимается или перефразируется после удаления.

Таким образом, чем больше ключей вы удалите из начала массива сегментов, тем дольше будет HashIteratorнеобходимо найти первое непустое поле.

Попробуйте удалить ключи с другого конца:

hashSet.remove(100_000 - i);

Алгоритм станет значительно быстрее!