Waktu berjalan yang tidak terduga untuk kode HashSet

Jadi awalnya, saya punya kode ini:

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

Butuh sekitar 4s untuk menjalankan loop bersarang di komputer saya dan saya tidak mengerti mengapa butuh waktu lama. Loop luar berjalan 100.000 kali, bagian dalam untuk loop harus berjalan 1 kali (karena nilai hashSet tidak akan pernah -1) dan menghapus item dari HashSet adalah O (1), sehingga harus ada sekitar 200.000 operasi. Jika biasanya ada 100.000.000 operasi dalam satu detik, kenapa kode saya bisa berjalan 4s?

Selain itu, jika baris hashSet.remove(i);dikomentari, kode hanya membutuhkan waktu 16 ms. Jika bagian dalam untuk loop dikomentari (tetapi tidak hashSet.remove(i);), kode hanya membutuhkan 8 ms.

Anda telah membuat kasus penggunaan marjinal HashSet, di mana algoritma menurun ke kompleksitas kuadratik.

Inilah loop sederhana yang memakan waktu sangat lama:

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

async-profiler menunjukkan bahwa hampir semua waktu dihabiskan di dalam java.util.HashMap$HashIterator()konstruktor:

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

Garis yang disorot adalah loop linier yang mencari ember non-kosong pertama di tabel hash.

Karena Integermemiliki trivial hashCode(yaitu kode hash sama dengan angka itu sendiri), ternyata bilangan bulat berturut-turut sebagian besar menempati ember berurutan dalam tabel hash: angka 0 pergi ke ember pertama, angka 1 pergi ke ember pertama, angka 1 pergi ke ember kedua, dll.

Sekarang Anda menghapus angka berurutan dari 0 hingga 99999. Dalam kasus paling sederhana (ketika ember berisi satu kunci) penghapusan kunci diimplementasikan sebagai meniadakan elemen yang sesuai dalam larik bucket. Perhatikan bahwa tabel tidak dipadatkan atau diulang setelah dilepas.

Jadi, semakin banyak kunci yang Anda hapus dari awal susunan bucket, semakin lama HashIteratorkebutuhan untuk menemukan bucket non-kosong pertama.

Cobalah untuk menghapus kunci dari ujung yang lain:

hashSet.remove(100_000 - i);

Algoritma akan menjadi lebih cepat secara dramatis!