Saat menerapkan HashMap di lingkungan multi-utas Java, opsi utamanya adalah sebagai berikut: Gunakan java.util.Hashtable yang aman untuk thread sebagai alternatif. Gunakan metode java.util.Collections.synchronizedMap untuk membungkus objek HashMap yang ada sebagai utas -aman. Gunakan kelas java.util.concurrent.ConcurrentHashMap sebagai alternatif, yang memiliki kinerja sangat baik.
Semua metode di atas menggunakan kunci mutex kurang lebih dalam detail implementasi yang spesifik. Kunci mutex akan menyebabkan pemblokiran ulir, mengurangi efisiensi pengoperasian, dan dapat menyebabkan serangkaian masalah seperti kebuntuan dan pembalikan prioritas.
CAS (Bandingkan Dan Tukar) adalah fungsi yang disediakan oleh perangkat keras yang mendasarinya, yang dapat melakukan atomisasi operasi penilaian dan perubahan nilai.
Operasi atom di Jawa
Dalam paket java.util.concurrent.atomic, Java memberi kita banyak tipe atom yang mudah digunakan, yang seluruhnya didasarkan pada operasi CAS.
Misalnya, jika kita ingin menerapkan penghitung publik global, kita dapat:
Copy kode kodenya sebagai berikut:
penghitung privateAtomicInteger =newAtomicInteger(3);
publicvoidaddCounter() {
untuk(;;) {
intoldValue = counter.get();
intnewValue = nilai lama +1;
if(counter.compareAndSet(oldValue, newValue))
kembali;
}
}
Diantaranya, metode CompareAndSet memeriksa apakah nilai counter yang ada adalah oldValue. Jika demikian, maka disetel ke nilai baru newValue. Operasi berhasil dan true dikembalikan;
Saat menghitung nilai penghitung baru, jika thread lain mengubah nilai penghitung, perbandinganDanSwap akan gagal. Pada titik ini kita hanya perlu menambahkan lapisan perulangan di luar dan terus mencoba proses ini, maka pada akhirnya kita akan berhasil meningkatkan nilai penghitung sebesar 1. (Faktanya, AtomicInteger telah mendefinisikan metode incrementAndGet dan decrementAndGet untuk operasi +1/-1 yang umum digunakan. Kita hanya perlu memanggilnya di masa mendatang)
Selain AtomicInteger, paket java.util.concurrent.atomic juga menyediakan tipe AtomicReference dan AtomicReferenceArray, yang masing-masing mewakili referensi atom dan array referensi atom (array referensi).
Penerapan daftar tertaut bebas kunci
Sebelum menerapkan HashMap bebas kunci, pertama-tama mari kita lihat metode implementasi yang relatif sederhana dari daftar tertaut bebas kunci.
Ambil operasi penyisipan sebagai contoh:
Pertama kita perlu mencari node A di depan posisi yang akan disisipkan dan node B di belakangnya.
Kemudian buat node C baru dan arahkan pointer selanjutnya ke node B. (Lihat Gambar 1)
Terakhir, buatlah penunjuk berikutnya dari node A menunjuk ke node C. (Lihat Gambar 2)
Namun selama operasi, ada kemungkinan thread lain langsung menyisipkan beberapa node di A dan B (diasumsikan D). Jika kita tidak mengambil keputusan, hal itu dapat menyebabkan hilangnya node yang disisipkan oleh thread lain. (Lihat Gambar 3) Kita dapat menggunakan operasi CAS untuk menentukan apakah penunjuk berikutnya dari node A masih menunjuk ke B saat memberikan nilai. Jika penunjuk berikutnya dari node A berubah, coba lagi seluruh operasi penyisipan. Perkiraan kodenya adalah sebagai berikut:
Copy kode kodenya sebagai berikut:
privatevoidlistInsert(Kepala simpul, Node c) {
untuk(;;) {
Node a = findInsertionPlace(head), b = a.next.get();
c.next.set(b);
if(a.next.compareAndSwap(b,c))
kembali;
}
}
(Bidang berikutnya dari kelas Node bertipe AtomicReference<Node>, yang merupakan referensi atom yang menunjuk ke tipe Node)
Operasi pencarian daftar tertaut bebas kunci tidak berbeda dengan operasi pencarian daftar tertaut biasa. Operasi penghapusan memerlukan pencarian node A di depan node yang akan dihapus dan node B di belakangnya, serta menggunakan operasi CAS untuk memverifikasi dan memperbarui penunjuk berikutnya dari node A sehingga menunjuk ke node B.
Kesulitan dan terobosan HashMap bebas kunci
HashMap pada dasarnya memiliki empat operasi dasar: penyisipan, penghapusan, pencarian, dan ReHash. Implementasi HashMap pada umumnya menggunakan array, dan setiap elemen array adalah daftar node yang tertaut. Untuk daftar tertaut ini, kita dapat menggunakan metode operasi yang disebutkan di atas untuk melakukan operasi penyisipan, penghapusan, dan pencarian, tetapi operasi ReHash lebih sulit.
Seperti yang ditunjukkan pada Gambar 4, selama proses ReHash, operasi yang umum dilakukan adalah melintasi setiap node di tabel lama, menghitung posisinya di tabel baru, dan kemudian memindahkannya ke tabel baru. Selama periode ini kita perlu memanipulasi pointer tiga kali:
Penunjuk titik A selanjutnya ke D
Penunjuk titik B selanjutnya ke C
Penunjuk titik C selanjutnya ke E
Ketiga operasi penunjuk ini harus diselesaikan pada saat yang sama untuk memastikan atomisitas operasi pemindahan. Namun tidak sulit untuk melihat bahwa operasi CAS hanya dapat memastikan bahwa nilai satu variabel diverifikasi dan diperbarui secara atom pada satu waktu, dan tidak dapat memenuhi kebutuhan untuk memverifikasi dan memperbarui tiga petunjuk pada saat yang bersamaan.
Jadi sebaiknya kita mengubah pemikiran kita. Karena pengoperasian node yang bergerak sangat sulit, kita dapat menjaga semua node dalam keadaan teratur setiap saat, sehingga menghindari operasi perpindahan. Dalam implementasi HashMap yang khas, panjang array selalu tetap 2i, dan proses pemetaan nilai Hash ke subskrip array hanya melakukan operasi modulo pada panjang array (yaitu, hanya i bit terakhir dari biner Hash yang dipertahankan). Saat ReHash, panjang array digandakan menjadi 2i+1, dan setiap node dalam daftar kalung ke-j dari array lama akan dipindahkan ke item ke-j di array baru, atau dipindahkan ke item ke-j+2i item dalam larik baru, dan Perbedaannya hanya terletak pada bit ke-i+1 dari nilai Hash (jika bit ke-i+1 adalah 0, itu tetap merupakan item ke-j, jika tidak maka item ke-j+2).
Seperti yang ditunjukkan pada Gambar 5, kami mengatur semua node dalam urutan menaik sesuai dengan urutan nilai Hash yang terbalik (seperti 1101->1011). Jika ukuran lariknya 8, 2 dan 18 berada dalam satu grup; Di awal setiap kelompok, sebuah simpul sentinel dimasukkan untuk memudahkan operasi selanjutnya. Untuk mengatur node sentinel di depan grup dengan benar, kami menetapkan bit tertinggi dari node normal Hash (yang menjadi bit terendah setelah dibalik) ke 1, sedangkan node sentinel tidak menyetel bit ini.
Ketika array diperluas menjadi 16 (lihat Gambar 6), grup kedua dipecah menjadi grup yang hanya berisi 3 dan grup berisi 11 dan 27, tetapi urutan relatif antar node tidak berubah. Dengan cara ini, kita tidak perlu memindahkan node selama ReHash.
Detail implementasi
Karena penyalinan array memakan banyak waktu selama perluasan, di sini kita mengadopsi metode membagi seluruh array menjadi blok-blok dan dengan malas membuatnya. Dengan cara ini, ketika subskrip tertentu diakses, hanya perlu dinilai apakah blok tempat subskrip tersebut berada sudah ditetapkan (jika belum, buatlah).
Selain itu, ukuran didefinisikan sebagai rentang subskrip yang digunakan saat ini, dan nilai awalnya adalah 2. Ketika array diperluas, ukurannya hanya perlu digandakan; hitungan ditentukan untuk mewakili jumlah total node yang saat ini disertakan dalam HashMap ( tidak termasuk node sentinel).
Awalnya, semua item dalam array kecuali item ke-0 adalah null. Item 0 menunjuk ke daftar tertaut dengan hanya satu node sentinel, yang mewakili titik awal dari keseluruhan rantai. Gambaran lengkap awal ditunjukkan pada Gambar 7, di mana warna hijau muda mewakili rentang subskrip yang saat ini tidak digunakan, dan panah putus-putus mewakili blok yang secara logis ada tetapi sebenarnya tidak terbentuk.
Inisialisasi operasi subskrip
Item kosong dalam array dianggap dalam keadaan tidak diinisialisasi. Menginisialisasi subskrip tertentu berarti membuat node sentinel yang sesuai. Inisialisasi dilakukan secara rekursif, yaitu jika subskrip induknya tidak diinisialisasi maka subskrip induknya diinisialisasi terlebih dahulu. (Subskrip induk dari suatu subskrip adalah subskrip yang diperoleh dengan menghilangkan bit biner tertinggi.) Perkiraan kodenya adalah sebagai berikut:
Copy kode kodenya sebagai berikut:
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
jika(getBucket(parentIdx) ==null)
inisialisasiBucket(parentIdx);
Node tiruan =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
Diantaranya, getBucket adalah metode yang dienkapsulasi untuk mendapatkan konten subskrip tertentu dalam array, dan setBucket juga sama. listInsert akan memasukkan node yang diberikan ke posisi yang sesuai mulai dari posisi yang ditentukan. Jika sebuah node dengan hash yang sama sudah ada di daftar tertaut, ia akan mengembalikan node yang ada, jika tidak, ia akan mengembalikan node yang baru dimasukkan.
operasi penyisipan
Pertama, gunakan ukuran HashMap untuk memodulasi kode hash kunci untuk mendapatkan subskrip array yang harus dimasukkan.
Kemudian tentukan apakah subskripnya nol, dan jika nol, inisialisasi subskripnya.
Bangun node baru dan masukkan ke posisi yang sesuai. Perhatikan bahwa nilai hash dalam node harus menjadi nilai kode hash asli setelah bit dibalik dan atur posisi terendah ke 1.
Tambahkan 1 ke penghitung nomor node. Jika node terlalu banyak setelah menambahkan 1, Anda hanya perlu mengubah ukurannya menjadi size*2, yang berarti memperluas array (ReHash).
Temukan operasi
Temukan indeks node yang akan ditemukan dalam array.
Tentukan apakah subskripnya nol. Jika nol, kegagalan pencarian akan dikembalikan.
Masukkan daftar tertaut dari posisi yang sesuai dan cari secara berurutan hingga simpul yang ditemukan ditemukan atau melebihi jangkauan kelompok simpul ini.
operasi penghapusan
Temukan indeks node dalam array yang harus dihapus.
Tentukan apakah subskripnya nol, dan jika nol, inisialisasi subskripnya.
Temukan node yang akan dihapus dan hapus dari daftar tertaut. (Perhatikan bahwa karena keberadaan node sentinel, elemen normal apa pun hanya direferensikan oleh satu-satunya node pendahulunya. Tidak ada situasi di mana elemen tersebut direferensikan oleh node pendahulu dan penunjuk dalam array pada saat yang bersamaan, jadi ada tidak perlu mengubah beberapa petunjuk secara bersamaan.)
Kurangi penghitung nomor node sebesar 1.