Kisah Dua Iterator: Strategi Modifikasi Kompetitif di Java

Penulis catatan ini adalah Grzegorz Mirek, seorang pengembang perangkat lunak dari Krakow (Polandia). Ia mulai berkembang di Jawa sekitar 6 tahun yang lalu, saat masih kuliah, dan sejak saat itu ia tanpa kenal lelah terus mengasah kemampuannya di bidang tersebut. Dia sangat tertarik pada kinerja dan pengoptimalan JVM, yang terutama dia tulis di blognya . Beberapa pertanyaan wawancara Java yang paling populer meliputi: Apa perbedaan antara iterator fail-fast dan fail-safe? Jawaban paling sederhana untuk ini adalah: Iterator fail-fast memunculkan ConcurrentModificationException jika koleksi berubah selama iterasi, namun iterator fail-safe tidak. Meskipun hal ini terdengar cukup bermakna, masih belum jelas apa yang dimaksud oleh pewawancara dengan kata aman dari kegagalan? Spesifikasi Bahasa Java tidak mendefinisikan istilah ini sehubungan dengan iterator. Namun, ada empat strategi modifikasi kompetitif.

Modifikasi kompetitif

Pertama, mari kita definisikan apa itu modifikasi kompetitif (atau paralel). Katakanlah kita memiliki koleksi dan ketika iterator aktif, terjadi beberapa perubahan yang tidak berasal dari iterator ini. Dalam hal ini, kami mendapatkan modifikasi kompetitif. Biarkan saya memberi Anda sebuah contoh sederhana: katakanlah kita memiliki beberapa thread. Thread pertama diulang, dan thread kedua menyisipkan atau menghapus elemen dari koleksi yang sama. Namun, kita bisa mendapatkan ConcurrentModificationException saat dijalankan di lingkungan single-thread:

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);
 
Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Gagal-cepat

Fragmen kode di atas adalah contoh iterator gagal-cepat . Seperti yang Anda lihat, ConcurrentModificationException dilempar saat mencoba mengambil elemen kedua dari iterator . Bagaimana iterator mengetahui bahwa koleksi telah dimodifikasi sejak dibuat? Misalnya, koleksi mungkin memiliki cap tanggal/waktu, misalnya lastModified . Saat membuat iterator, Anda harus menyalin bidang ini dan menyimpannya di objek iterator. Kemudian, setiap kali Anda memanggil metode next() , Anda cukup membandingkan nilai lastModified dari koleksi dengan salinan dari iterator. Pendekatan yang sangat mirip digunakan, misalnya, dalam implementasi kelas ArrayList . Ia memiliki variabel instan modCount yang menyimpan berapa kali daftar telah diubah:

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

Penting untuk dicatat bahwa iterator fail-fast beroperasi pada basis terbaik, artinya tidak ada jaminan bahwa ConcurrentModificationException akan dilempar jika terjadi modifikasi bersamaan. Jadi Anda tidak boleh bergantung pada mereka - sebaliknya, mereka harus digunakan untuk mendeteksi kesalahan. Kebanyakan koleksi yang tidak bersamaan menyediakan iterator yang cepat gagal .

Konsistensi Lemah

Kebanyakan koleksi serentak dalam paket java.util.concurrent (seperti ConcurrentHashMap dan sebagian besar Queue ) menyediakan iterator yang kurang konsisten. Arti istilah ini dijelaskan dengan sangat baik dalam dokumentasi :

• Mereka dapat diproses bersamaan dengan operasi lainnya
• Mereka tidak pernah melempar ConcurrentModificationException
• Mereka dijamin untuk melintasi elemen yang ada pada saat iterator dibuat tepat satu kali, dan dapat (tetapi tidak diharuskan) mencerminkan modifikasi selanjutnya.

Foto

Dengan strategi ini, iterator dikaitkan dengan keadaan koleksi pada saat pembuatannya - ini adalah cuplikan dari koleksi. Setiap perubahan yang dilakukan pada koleksi asli akan menghasilkan pembuatan versi baru dari struktur data yang mendasarinya. Hal ini membuat snapshot kita tidak berubah, sehingga tidak mencerminkan perubahan pada koleksi yang terjadi setelah iterator dibuat. Ini adalah teknik copy-on-write (COW) lama yang bagus . Ini sepenuhnya menyelesaikan masalah modifikasi bersamaan, sehingga ConcurrentModificationException tidak dihasilkan dengan pendekatan ini. Selain itu, iterator tidak mendukung operasi yang mengubah elemen. Koleksi copy-on-write cenderung terlalu mahal untuk digunakan, namun masuk akal untuk menggunakannya jika perubahan lebih jarang terjadi dibandingkan traversal iterator. Contohnya adalah kelas CopyOnWriteArrayList dan CopyOnWriteArraySet .

Perilaku tidak terdefinisi

Anda mungkin menemukan perilaku tidak terdefinisi pada tipe koleksi lama seperti Vector dan Hashtable . Keduanya memiliki iterator cepat gagal standar , tetapi selain itu, mereka mengizinkan penggunaan implementasi antarmuka Enumeration , dan mereka tidak tahu bagaimana harus berperilaku jika terjadi modifikasi bersamaan. Anda mungkin menemukan beberapa elemen diulang atau hilang, atau bahkan beberapa pengecualian aneh. Lebih baik tidak bermain-main dengan mereka!