Metode HashSet <T> .removeAll ternyata sangat lambat

Jon Skeet baru-baru ini mengangkat topik pemrograman yang menarik di blognya: "Ada lubang dalam abstraksi saya, Liza sayang, Liza tersayang" (penekanan ditambahkan):

Saya punya satu set - a HashSet, sebenarnya. Saya ingin menghapus beberapa item darinya… dan banyak dari item tersebut mungkin tidak ada. Faktanya, dalam kasus pengujian kami, tidak ada item dalam koleksi "penghapusan" yang akan berada di set asli. Suara ini - dan memang adalah - sangat mudah untuk kode. Bagaimanapun, kita harus Set<T>.removeAllmembantu kita, bukan?

Kami menentukan ukuran kumpulan "sumber" dan ukuran kumpulan "penghapusan" pada baris perintah, dan membangun keduanya. Set sumber hanya berisi bilangan bulat non-negatif; kumpulan penghapusan hanya berisi bilangan bulat negatif. Kami mengukur berapa lama waktu yang dibutuhkan untuk menghapus semua elemen menggunakan System.currentTimeMillis(), yang bukan stopwatch paling akurat di dunia tetapi lebih dari cukup dalam kasus ini, seperti yang akan Anda lihat. Berikut kodenya:

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

Mari kita mulai dengan memberikan pekerjaan mudah: kumpulan sumber 100 item, dan 100 untuk dihapus:

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

Oke, jadi kami tidak menyangka ini akan lambat… jelas kami bisa sedikit meningkatkan. Bagaimana dengan sumber satu juta item dan 300.000 item untuk dihapus?

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

Hmm. Tampaknya masih cukup cepat. Sekarang saya merasa saya sedikit kejam, memintanya untuk melakukan semua itu. Mari membuatnya sedikit lebih mudah - 300.000 item sumber dan 300.000 penghapusan:

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

Permisi? Hampir tiga menit ? Astaga! Tentunya akan lebih mudah untuk menghapus item dari koleksi yang lebih kecil daripada yang kami kelola dalam 38ms?

Adakah yang bisa menjelaskan mengapa ini terjadi? Mengapa HashSet<T>.removeAllmetodenya sangat lambat?

Perilaku tersebut (agak) didokumentasikan di javadoc :

Implementasi ini menentukan mana yang lebih kecil dari set ini dan koleksi yang ditentukan, dengan memanggil metode ukuran pada masing-masing. Jika set ini memiliki lebih sedikit elemen , maka implementasi mengulang set ini, memeriksa setiap elemen yang dikembalikan oleh iterator secara bergiliran untuk melihat apakah itu terdapat dalam koleksi yang ditentukan . Jika isinya begitu, maka akan dihapus dari set ini dengan metode remove iterator. Jika koleksi yang ditentukan memiliki lebih sedikit elemen, implementasi mengulangi koleksi yang ditentukan, menghapus dari set ini setiap elemen yang dikembalikan oleh iterator, menggunakan metode remove set ini.

Artinya dalam praktiknya, saat Anda menelepon source.removeAll(removals);:

• jika removalskoleksi berukuran lebih kecil dari source, removemetode dari HashSetdisebut, yaitu cepat.

• jika removalskoleksi berukuran sama atau lebih besar dari source, maka removals.containsdisebut, yang lambat untuk ArrayList.

Perbaikan cepat:

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

Perhatikan bahwa ada bug terbuka yang sangat mirip dengan yang Anda gambarkan. Intinya tampaknya ini adalah pilihan yang buruk tetapi tidak dapat diubah karena didokumentasikan di javadoc.

Untuk referensi, ini adalah kode removeAll(di Java 8 - belum memeriksa versi lain):

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