Tiempos de ejecución inesperados para el código HashSet

Entonces, originalmente, tenía este código:

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));
    }
}

Se necesitan alrededor de 4 segundos para ejecutar los bucles anidados en mi computadora y no entiendo por qué tardó tanto. El bucle externo se ejecuta 100,000 veces, el bucle interno debe ejecutarse 1 vez (porque cualquier valor de hashSet nunca será -1) y la eliminación de un elemento de un HashSet es O (1), por lo que debería haber alrededor de 200,000 operaciones. Si normalmente hay 100,000,000 operaciones en un segundo, ¿cómo es que mi código tarda 4 segundos en ejecutarse?

Además, si la línea hashSet.remove(i);está comentada, el código solo tarda 16 ms. Si el bucle for interno está comentado (pero no hashSet.remove(i);), el código solo tarda 8 ms.

Ha creado un caso de uso marginal de HashSet, donde el algoritmo se degrada a la complejidad cuadrática.

Aquí está el ciclo simplificado que lleva tanto tiempo:

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

async-profiler muestra que casi todo el tiempo se gasta dentro del java.util.HashMap$HashIterator()constructor:

    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);
        }
    }

La línea resaltada es un bucle lineal que busca el primer depósito no vacío en la tabla hash.

Dado que Integertiene el trivial hashCode(es decir, hashCode es igual al número en sí), resulta que los enteros consecutivos ocupan principalmente los cubos consecutivos en la tabla hash: el número 0 va al primer cubo, el número 1 va al segundo cubo, etc.

Ahora elimina los números consecutivos de 0 a 99999. En el caso más simple (cuando el depósito contiene una sola clave), la eliminación de una clave se implementa como la anulación del elemento correspondiente en la matriz del depósito. Tenga en cuenta que la tabla no se compacta ni se vuelve a colocar después de quitarla.

Por lo tanto, cuantas más claves elimine desde el comienzo de la matriz de cubetas, más tiempo HashIteratornecesitará encontrar la primera cubeta no vacía.

Intenta eliminar las llaves del otro extremo:

hashSet.remove(100_000 - i);

¡El algoritmo será dramáticamente más rápido!