Kita tahu bahwa tabel hash adalah struktur data yang sangat efisien, dan desain fungsi hash yang sangat baik dapat membuat penambahan, penghapusan, modifikasi, dan operasi pencarian di dalamnya mencapai level O (1). Java memberi kita struktur hash yang sudah jadi, yaitu kelas hashmap. Dalam artikel sebelumnya, saya memperkenalkan kelas HashMap dan tahu bahwa semua metodenya tidak disinkronkan, sehingga tidak aman di lingkungan multi-threaded. Untuk tujuan ini, Java memberi kita kelas hashtable lain, yang sangat sederhana dan kasar dalam menangani sinkronisasi multi-thread, yaitu, untuk mengunci semua metodenya menggunakan kata kunci yang disinkronkan berdasarkan hashmap. Meskipun metode ini sederhana, itu mengarah pada suatu masalah, yaitu, hanya satu utas yang dapat mengoperasikan tabel hash secara bersamaan. Bahkan jika utas-utas ini hanya membaca operasi, mereka harus antri, yang sangat mempengaruhi kinerja di lingkungan multi-threaded yang sangat kompetitif. Concurrenthashmap yang diperkenalkan dalam artikel ini adalah untuk menyelesaikan masalah ini. Ia menggunakan kunci tersegmentasi untuk membutak-biji kunci, sehingga banyak utas dapat mengoperasikan tabel hash pada saat yang sama, yang sangat meningkatkan kinerja. Gambar berikut adalah diagram skematik dari struktur internalnya.
1. Variabel anggota apa yang dimiliki concurrenthashmap?
// Kapasitas Inisialisasi Default Static Final Int Default_initial_capacity = 16; // Faktor beban default statis float final default_load_factor = 0.75f; // Level konkurensi statis final statis statis intrault_concurrency_level = 16; // setelmora minimal statis statis int static inter maksimum_capacity = 1 << 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; 30; Min_segment_table_capacity = 2; // Jumlah maksimum dari kunci segmen statis int int max_segments = 1 << 16; // jumlah retries sebelum mengunci static final int retries_before_lock = 2; // nilai mask dari segmen final intmmaskask; // segmen segmen segmen final <k, v> [v> [v> [] [v> [v> segments final;
Sebelum membaca artikel ini, saya percaya bahwa pembaca tidak dapat memahami makna dan fungsi spesifik dari variabel anggota ini, tetapi pembaca disarankan untuk membaca dengan sabar. Peran variabel anggota ini akan diperkenalkan satu per satu dalam skenario spesifik nanti. Di sini pembaca hanya perlu meninggalkan tampilan yang akrab pada variabel anggota ini. Namun, masih ada beberapa variabel yang perlu kita ketahui sekarang. Sebagai contoh, array segmen mewakili himpunan kunci segmen, tingkat konkurensi mewakili jumlah kunci segmen (yang juga berarti berapa banyak utas yang dapat beroperasi pada saat yang sama), kapasitas inisialisasi mewakili kapasitas seluruh wadah, dan faktor pemuatan mewakili tingkat seberapa penuh yang dapat dicapai oleh elemen kontainer.
2. Apa struktur internal kunci segmen?
// Segmen Kunci Segmen Kelas Akhir Statis <K, V> memperluas reentrantlock mengimplementasikan serializable {// nomor spin maksimum statis int int max_scan_retries = runtime.getRuntime (). Tersedia processorsorsors ()> 1? 64: 1; // tabel tabel hashentry volatile transien <k, v> [] tabel; // Jumlah total elemen jumlah int transien; // Jumlah modifikasi int transient modcount; // Ambang batas transien elemen ambang batas; // Faktor Muat Final Float Loadfactor; // hilangkan konten berikut ...}Segmen adalah kelas batin statis dari ConcurrenthashMap, Anda dapat melihat bahwa ia mewarisi dari reentrantlock, jadi pada dasarnya itu adalah kunci. Ini memegang array hashentry (tabel hash) secara internal, dan memastikan bahwa semua metode untuk menambah, menghapus, memodifikasi, dan mencari array-aman. Implementasi spesifik akan dibahas nanti. Semua operasi untuk menambah, menghapus, memodifikasi, dan memeriksa concurrhenthmap dapat dipercayakan ke segmen, sehingga ConcurrenthashMap dapat memastikan bahwa itu aman di lingkungan multi-utas. Juga, karena segmen yang berbeda adalah kunci yang berbeda, multithreads dapat mengoperasikan segmen yang berbeda pada saat yang sama, yang berarti bahwa multithreads dapat mengoperasikan ConcurrenthashMap pada saat yang sama, yang dapat menghindari cacat hashtable dan sangat meningkatkan kinerja.
3. Apa yang diinisialisasi Concurrenthashmap?
// core constructor @suppresswarnings ("uncecked") public concurrenthashMap (int initialcapacity, float loadfactor, int concurrencyLevel) {if (! (LoadFactor> 0) || InitialCapacity <0 || concurrencyLevel <= 0) {throw new IllegalArgumentception (); } // Pastikan tingkat konkurensi tidak lebih besar dari batas jika (ConcurrencyLevel> max_segments) {concurrencyLevel = max_segments; } int sshift = 0; int ssize = 1; // Pastikan bahwa SSIZE adalah kekuatan 2, dan merupakan angka terdekat yang lebih besar dari atau sama dengan tingkat konkurensi sementara (ssize <concurrencyLevel) {++ sshift; Ssize << = 1; } // Hitung nilai shift dari kunci segmen this.smentshift = 32 - sshift; // Hitung nilai mask dari kunci segmen this.smentmask = ssize - 1; // Kapasitas awal total tidak dapat lebih besar dari nilai batas jika (initialcapacity> maximum_capacity) {initialcapacity = maximum_capacity; } // Dapatkan kapasitas awal dari setiap kunci segmen int C = InitialCapacity /Ssize; // Jumlah kapasitas kunci tersegmentasi tidak kurang dari kapasitas total awal jika (c * ssize <initialcapacity) {++ c; } int cap = min_segment_table_capacity; // Pastikan tutup adalah kekuatan 2, dan merupakan angka terdekat yang lebih besar dari atau sama dengan c sementara (cap <c) {cap << = 1; } // Buat segmen templat objek segmen baru <k, v> s0 = segmen baru <k, v> (loadfactor, (int) (cap * loadfactor), (hashentry <k, v> []) hashentry baru [cap]); // Buat array kunci segmen baru dari segmen ukuran tertentu <k, v> [] ss = (segmen <k, v> []) segmen baru [ssize]; // Gunakan tidak aman untuk menetapkan elemen ke -0 dari array tidak aman.putorderedObject (ss, sbase, s0); this.segments = ss;}ConcurrenthashMap memiliki banyak konstruktor, tetapi yang diposting di atas adalah konstruktor intinya, dan konstruktor lainnya menyelesaikan inisialisasi dengan menyebutnya. Konstruktor inti perlu lulus dalam tiga parameter, yaitu kapasitas awal, faktor pemuatan dan tingkat konkurensi. Ketika memperkenalkan variabel anggota sebelumnya, kita dapat mengetahui bahwa kapasitas awal default adalah 16, faktor pemuatan adalah 0,75F, dan tingkat konkurensi adalah 16. Sekarang kita melihat kode konstruktor inti. Pertama, kami menghitung SSIZE melalui level concurrency yang masuk. Ssize adalah panjang array segmen. Itu harus dijamin menjadi kekuatan 2. Dengan cara ini, subskrip segmen yang terkunci dalam array dapat dihitung dengan hash & ssize-1. Karena tingkat konkurensi yang masuk tidak dapat dijamin menjadi kekuatan 2, itu tidak dapat digunakan secara langsung sebagai panjang array segmen. Oleh karena itu, kita perlu menemukan kekuatan 2 yang paling dekat dengan tingkat konkurensi dan menggunakannya sebagai panjang array. Jika ConcurrencyLevel = 15 dilewati sekarang, kode di atas dapat menghitung SSIZE = 16 dan SShift = 4. Selanjutnya, Anda dapat segera menghitung SegmentShift = 16 dan Segmentmask = 15. Perhatikan bahwa SegmentShift di sini adalah nilai shift kunci segmen, dan Segmentmask adalah nilai mask dari kunci segmen. Kedua nilai ini digunakan untuk menghitung subskrip kunci segmen di array, yang akan kita bicarakan di bawah ini. Setelah menghitung jumlah kunci segmen SSIZE, kapasitas setiap kunci segmen dapat dihitung berdasarkan total kapasitas masuk, dan nilainya C = InitialCapacity/Ssize. Kapasitas kunci segmen adalah panjang array hashentry, dan juga harus dijamin menjadi kekuatan 2. Nilai C yang dihitung di atas tidak dapat menjamin ini, jadi C tidak dapat digunakan secara langsung sebagai panjang array hashentry. Anda perlu menemukan kekuatan lain dari 2 terdekat dengan C, menetapkan nilai ini untuk ditutup, dan kemudian menggunakan tutup sebagai panjang array hashentry. Sekarang kita memiliki SSIZE dan CAP, kita dapat membuat segmen array kunci segmen baru [] dan elemen array hashentry []. Perhatikan bahwa tidak seperti JDK1.6, hanya array segmen yang dibuat di JDK1.7 dan tidak diinisialisasi. Pengoperasian inisialisasi segmen dibiarkan ke operasi penyisipan.
4. Bagaimana menemukan kunci dan menemukan elemen?
// Dapatkan kunci segmen berdasarkan kode hash @suppresswarnings ("Uncecked") Segmen Pribadi <K, V> SegmentForHash (int h) {long u = (((h >>> SegmentShift) & segmentmask) << sshift) + SBase; return (segmen <k, v>) unsafe.getObjectVolatile (segmen, u);} // dapatkan elemen berdasarkan kode hash @suppresswarnings ("uncecked") static final <k, v> hashentry <k, v> entryforhash (Segmen <K, v> Seg, int h) {hashentry <K, Segment, <K, V> Seg, int H) {hashentry <K, Segment (v; return (seg == null || (tab = seg.table) == null)? null: (hashentry <k, v>) unsafe.getObjectVolatile (tab, ((long) ((tab.length - 1) & h)) << tshift) + tbase);} Dalam JDK1.7, Unsafe digunakan untuk mendapatkan elemen array, jadi berikut adalah beberapa kode lagi untuk menghitung offset elemen array daripada JDK1.6. Kami tidak akan memperhatikan kode -kode ini untuk saat ini. Sekarang kita hanya perlu mengetahui dua poin berikut:
A. Hitung subskrip segmen yang terkunci dalam array melalui kode hash: (h >>> SegmentShift) & Segmentmask.
B. Hitung subskrip elemen dalam array dengan kode hash: (tab.length - 1) & h.
Sekarang mari kita asumsikan bahwa dua parameter yang diteruskan ke konstruktor adalah InitialCapacity = 128, ConcurrencyLevel = 16. Menurut perhitungan, kita dapat memperoleh SSIZE = 16, Sshift = 4, segmentShift = 28, segmentmask = 15. Demikian pula, panjang array hashentry di setiap kunci segmen dihitung menjadi 8, jadi tab.length-1 = 7. Berdasarkan nilai -nilai ini, kami menjelaskan cara menemukan kunci dan elemen segmen berdasarkan kode hash yang sama melalui gambar di bawah ini.
Dapat dilihat bahwa penguncian segmen dan penentuan posisi elemen ditentukan oleh kode hash elemen. Kunci segmen penentuan posisi adalah nilai tinggi dari kode hash (mulai dari 32 bit), dan elemen penentuan posisi adalah nilai rendah dari kode hash. Sekarang ada pertanyaan. Mereka mulai dari ujung kiri 32-bit dan ujung kanan 32-bit. Apakah akan ada konflik di beberapa titik? Kita dapat menemukan maksimum_capacity = 1 << 30, max_segments = 1 << 16 dalam variabel anggota, yang berarti bahwa jumlah total bit yang digunakan untuk penentuan posisi segmen dan elemen penentuan posisi tidak melebihi 30, dan jumlah bit yang digunakan untuk posisi segmen penentuan posisi tidak melebihi 16, sehingga setidaknya ada 2 bit yang tersisa, sehingga tidak akan ada konflik.
5. Bagaimana menemukan elemen secara khusus?
// Dapatkan ValuePublic v Get (Kunci Objek) {Segmen <K, V> S; Hashentry <k, v> [] tab; // Hitung kode hash menggunakan fungsi hash int h = hash (tombol); // Hitung indeks kunci segmen berdasarkan kode hash long u = (((h >>> segmentshift) & segmentmask) << sshift) + sbase; // Dapatkan kunci segmen dan tabel hash yang sesuai if ((s = (segmen <k, v>) tidak aman.getObjectVolatile (segmen, u))! = Null && (tab = s.table)! = Null) {// dapatkan node header dari daftar yang tertaut sesuai dengan kode hash, dan kemudian melintasi daftar yang terhubung ke header (v vershy (v vingy, dan kemudian melintasi daftar header (v v vershy (v v vershy (v v vershy, dan kemudian melintasi daftar header (v v vershy (v v vershy (v v vershy, dan kemudian melintasi daftar header (v v vingy (v v vershy (v v vershy (v v vershy (v v vershy (v v verse, dan kemudian melintasi daftar (v v vershy (v v vershy (v v vershy (v v vershy (v v verse (v ving Uncafe.getObjectVolatile (tab, ((long) ((tab.length - 1) & h)) << tshift) + tbase); // Ikuti nilai elemen yang sesuai sesuai dengan kunci dan hash dan kembalikan nilai if ((k = e.key) == key || (e.hash == h && key.equals (k))) {return e.Value; }}} return null;}Di JDK1.6, metode GET penguncian segmen mengakses elemen array melalui subskrip, sementara di JDK1.7, elemen -elemen dalam array dibaca melalui metode GetObjectVolatile yang tidak aman. Mengapa melakukan ini? Kita tahu bahwa meskipun referensi array hashentry yang dipegang oleh objek segmen adalah tipe volatile, referensi elemen dalam array tidak volatile tipe, sehingga modifikasi multithreading untuk elemen array tidak aman dan mungkin membaca objek yang belum dibangun dalam array. Di JDK1.6, bacaan kunci kedua dijamin aman, dan di JDK1.7, metode bacaan GetObjectVolatile yang tidak aman juga untuk memastikan hal ini. Reading Array Elements Menggunakan GetObjectVolatile Metode membutuhkan terlebih dahulu mendapatkan offset elemen dalam array. Di sini, menurut kode hash, offset kunci segmen di array adalah U, dan kemudian offset U digunakan untuk mencoba membaca kunci segmen. Karena array kunci segmen tidak diinisialisasi selama konstruksi, nilai nol dapat dibacakan, sehingga penilaian diperlukan terlebih dahulu. Setelah mengkonfirmasi bahwa kunci segmen dan tabel hash internalnya tidak kosong, elemen -elemen array hashentry dibacakan melalui kode hash. Menurut diagram struktur di atas, Anda dapat melihat bahwa node header dari daftar tertaut diperoleh saat ini. Kemudian melintasi dan mencari daftar yang ditautkan dari awal hingga akhir. Jika nilai yang sesuai ditemukan, itu akan dikembalikan, jika tidak maka akan dikembalikan nol. Di atas adalah seluruh proses menemukan elemen.
6. Bagaimana cara mengimplementasikan elemen penyisipan?
// Tambahkan pasangan nilai-kunci ke set (ganti jika ada) @suppressWarnings ("Uncecked") public v put (K key, nilai v) {segmen <k, v> s; // Nilai yang berlalu tidak dapat kosong jika (nilai == null) melempar nullpointerException baru (); // Hitung kode hash menggunakan fungsi hash int hash = hash (kunci); // Hitung subskrip kunci segmen berdasarkan kode hash int j = (hash >>> SegmentShift) & segmentmask; // Cobalah untuk mendapatkan kunci segmen berdasarkan subscript if ((s = (segmen <k, v>) unsafe.getObject (segmen, (j << sshift) + sbase)) == null) {// jika kunci segmen yang diperoleh kosong, konstruk a = memastikan bagian (j); } // Panggil metode put dari pengembalian kunci segmen s.put (tombol, hash, value, false);} // Tambahkan pasangan nilai-kunci ke set (tambahkan jika tidak ada) @suppresswarnings ("uncecked") public v putifabsent (Key k, v nilai) {segmen <k, v> s; // Nilai yang berlalu tidak dapat kosong jika (nilai == null) melempar nullpointerException baru (); // Hitung kode hash dengan hash = hash (kunci); // Hitung subskrip kunci segmen berdasarkan kode hash int j = (hash >>> SegmentShift) & segmentmask; // Cobalah untuk mendapatkan kunci segmen berdasarkan subscript if ((s = (segmen <k, v>) unsafe.getObject (segmen, (j << sshift) + sbase)) == null) {// buat s = memastikan bagian (j); } // Kalender Metode put dari pengembalian kunci segmen s.put (tombol, hash, value, true);}Ada dua metode di ConcurrenthashMap untuk menambahkan pasangan nilai kunci. Jika ada, itu akan ditimpa ketika ditambahkan melalui metode put. Metode ifaBSent ditambahkan melalui metode put ifaBsent, itu tidak akan ditimpa. Kedua metode memanggil metode put kunci segmen untuk menyelesaikan operasi, tetapi parameter terakhir yang disahkan masuk berbeda. Dalam kode di atas, kita dapat melihat bahwa pertama -tama, kami menghitung subskrip kunci segmen di array berdasarkan kode hash kunci, dan kemudian menggunakan metode GetObject kelas yang tidak aman untuk membaca kunci segmen sesuai dengan subskrip. Karena elemen -elemen dalam array segmen tidak diinisialisasi saat membangun concurrenthashmap, nilai nol dapat dibaca, dan kunci segmen baru akan dibuat melalui metode penentu. Setelah mendapatkan kunci segmen, hubungi metode putnya untuk menyelesaikan operasi penambahan. Mari kita lihat cara mengoperasikannya.
// Tambahkan nilai kunci pasangan final v put (K key, int hash, nilai v, boolean onlyIfabsent) {// Cobalah untuk mendapatkan kunci, jika gagal, spin hashentry <k, v> node = trylock ()? null: scanandlockforput (kunci, hash, nilai); V oldvalue; coba {hashentry <k, v> [] tab = tabel; // Hitung indeks sub subscript elemen = (tab.length - 1) & hash; // Dapatkan node header dari daftar tertaut berdasarkan hashentry subscript <k, v> first = entryat (tab, index); untuk (hashentry <k, v> e = first ;;) {// transfer daftar yang ditautkan untuk menemukan elemen, dan if (e! = null) {k k; if ((k = e.key) == key || (e.hash == hash && key.equals (k)))) {oldvalue = e.value; // memutuskan apakah akan mengganti nilai lama berdasarkan parameter if (! OnlyIfabSent) {e.value = nilai; ++ modcount; } merusak; } e = E.Next; // Jika tidak ditemukan, tambahkan node ke daftar tertaut} else {// masukkan simpul node ke header daftar tertaut jika (node! = Null) {node.setNext (pertama); } else {node = hashentry baru <k, v> (hash, kunci, nilai, pertama); } // Setelah memasukkan node, selalu tambahkan 1 int c = hitung + 1; // Jika elemen melebihi ambang batas, perluas kapasitas jika (c> threshold && tab.length <maximum_capacity) {rehash (node); // jika tidak, ganti tabel hash yang ditentukan subskrip dengan simpul node} else {setenTyRy (tab, index, node); } ++ modcount; hitung = c; OldValue = null; merusak; }}} akhirnya {buka kunci (); } return oldvalue;}Untuk memastikan keamanan utas, masukkan operasi di kunci tersegmentasi perlu dikunci, sehingga utas akan memperoleh kunci di awal, dan terus mengeksekusi jika akuisisi berhasil. Jika akuisisi gagal, hubungi Metode ScanAndLockForput untuk berputar. Selama proses putaran, pindai tabel hash untuk menemukan kunci yang ditentukan. Jika kunci tidak ada, hashentry baru akan dibuat, sehingga tidak perlu membuatnya lagi setelah mendapatkan kunci. Untuk melakukan beberapa hal sambil menunggu kunci, itu tidak akan membuang waktu dengan sia -sia. Ini menunjukkan niat baik penulis. Kami akan menjelaskan metode putaran spesifik secara rinci nanti. Sekarang, tarik kembali fokus terlebih dahulu. Setelah utas berhasil memperoleh kunci, ia akan mendapatkan elemen dari subskrip yang ditentukan berdasarkan subskrip yang dihitung. Pada saat ini, node header dari daftar tertaut diperoleh. Jika node header tidak kosong, daftar tertaut akan dilalui dan dicari. Setelah menemukannya, putuskan apakah akan menggantinya berdasarkan nilai parameter OnjiFabSent. Jika traversal tidak ditemukan, hashentry baru akan menunjuk ke node header. Pada saat ini, jika hashentry dibuat selama putaran, maka langsung tunjuk di sebelah node header saat ini. Jika putaran tidak dibuat, hashentry baru akan dibuat di sini dan tunjuk ke node header. Setelah menambahkan elemen ke daftar tertaut, periksa apakah jumlah total elemen melebihi ambang batas. Jika melebihi, hubungi Rehash untuk ekspansi. Jika tidak melebihi itu, langsung merujuk ke elemen subskrip yang sesuai dari array ke node yang baru ditambahkan. Metode SetEntryat mengubah referensi elemen array dengan memanggil metode putorderedObject yang tidak aman, yang memastikan bahwa utas lain dapat membaca nilai terbaru saat membaca.
7. Bagaimana menerapkan penghapusan elemen?
// Hapus elemen yang ditentukan (hapus langsung setelah menemukan elemen yang sesuai) public v rape (tombol objek) {// Gunakan fungsi hash untuk menghitung kode hash int hash = hash (tombol); // memperoleh indeks kunci segmen berdasarkan segmen kode hash <k, v> s = segmenforhash (hash); // Calend Metode Hapus Kunci Segmen Pengembalian S == NULL? null: s.remove (kunci, hash, null);} // hapus elemen yang ditentukan (menghapus nilai yang sama dengan nilai yang diberikan) boolean publik hapus (tombol objek, nilai objek) {// Gunakan fungsi hash untuk menghitung kode hash int hash = hash (tombol); Segmen <k, v> s; // Dapat memastikan bahwa kunci segmen tidak kosong sebelum memanggil metode pengembalian metode hapus! = Null && (s = segmentForHash (hash))! = Null && s.remove (tombol, hash, value)! = Null;}ConcurrenthashMap menyediakan dua operasi penghapusan, satu untuk menghapusnya secara langsung setelah menemukannya, dan yang lainnya adalah membandingkannya terlebih dahulu dan kemudian menghapusnya setelah menemukannya. Kedua metode hapus ini adalah untuk menemukan kunci segmen yang sesuai berdasarkan kode hash kunci, dan kemudian menyelesaikan operasi hapus dengan memanggil metode hapus dari kunci segmen. Mari kita lihat metode hapus dari kunci segmen.
// hapus elemen yang ditentukan final v hapus (tombol objek, int hash, nilai objek) {// Cobalah untuk memperoleh kunci, jika gagal, putar if (! Trylock ()) {scanandlock (kunci, hash); } V oldValue = null; coba {hashentry <k, v> [] tab = tabel; // Hitung indeks sub subscript elemen = (tab.length - 1) & hash; // Dapatkan elemen array sesuai dengan subscript (node header daftar tautan) hashentry <k, v> e = entryat (tab, indeks); Hashentry <k, v> pred = null; // Transfer daftar yang ditautkan untuk menemukan elemen yang akan dihapus sementara (e! = Null) {k k; // Poin selanjutnya ke simpul penerus node hashentry saat ini <k, v> next = e.next; // Cari node yang sesuai berdasarkan tombol dan hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {v v = e.value; // Lewati nilai yang dilewati jika tidak sama dengan V, dan hapus dalam kasus lain jika (nilai == null || value == v || value.equals (v)) {// jika pred kosong, itu berarti node yang akan dihapus adalah node header if (pred == null) {// Reset node header dari node tertaut yang tertaut (pred == null) {// Reset node header dari node tertaut yang terhubung } else {// atur suksesi node pred ke simpul berikutnya pred.setNext (next); } ++ modcount; --menghitung; // Catat nilai penghapusan elemen oldValue = v; } merusak; } // Jika e bukan simpul yang Anda cari, arahkan referensi pred ke IT pred = e; // periksa node berikutnya e = selanjutnya; }} akhirnya {buka kunci (); } return oldvalue;}Saat menghapus elemen dalam kunci segmen, Anda perlu mendapatkan kunci terlebih dahulu. Jika akuisisi gagal, hubungi Metode ScanAndlock untuk berputar. Jika akuisisi berhasil, jalankan langkah selanjutnya. Pertama -tama hitung subskrip array dan kemudian dapatkan elemen array hashentry melalui subskrip. Di sini simpul header dari daftar tertaut diperoleh. Selanjutnya, traversal dan cari daftar yang ditautkan. Sebelum ini, gunakan pointer berikutnya untuk merekam simpul penerus node saat ini, dan kemudian bandingkan kunci dan hash untuk melihat apakah itu adalah simpul yang Anda cari. Jika demikian, lakukan penilaian IF berikutnya. Jika nilainya kosong atau nilainya sama dengan nilai saat ini dari node, itu akan memasukkan pernyataan IF untuk penghapusan, jika tidak maka akan dilewati secara langsung. Ada dua situasi saat melakukan operasi penghapusan dalam pernyataan IF. Jika node saat ini adalah node header, maka langsung atur node berikutnya sebagai node header. Jika node saat ini bukan node header, maka atur penerus node pred ke simpul berikutnya. Node pred di sini mewakili pendahulu simpul saat ini. Setiap kali sebelum memeriksa simpul berikutnya, pred diarahkan ke simpul saat ini, yang memastikan bahwa node pred selalu menjadi pendahulu dari node saat ini. Perhatikan bahwa tidak seperti JDK1.6, di JDK1.7, variabel berikutnya dari objek hashentry tidak final, sehingga Anda dapat menghapus elemen dengan secara langsung memodifikasi nilai yang dirujuk oleh Next. Karena variabel berikutnya adalah tipe yang mudah menguap, utas baca dapat segera membaca nilai terbaru.
8. Bagaimana elemen pengganti diterapkan secara khusus?
// Ganti elemen yang ditentukan (operasi CAS) Boolean Public Replace (K key, v OldValue, v NewValue) {// Gunakan fungsi hash untuk menghitung kode hash int hash = hash (key); // Pastikan bahwa OldValue dan NewValue tidak kosong jika (oldValue == null || newValue == null) lempar nullpointerexception baru (); // Dapatkan indeks kunci segmen berdasarkan segmen kode hash <k, v> s = segmenforhash (hash); //Calling the replacement method of the segment lock returns s != null && s.replace(key, hash, oldValue, newValue);}//Replace element operation (CAS operation) final boolean replace(K key, int hash, V oldValue, V newValue) { //Try to acquire the lock, if it fails, spin if (!tryLock()) { scanAndLock(key, hash); } Boolean diganti = false; coba {hashentry <k, v> e; // Cari node header langsung melalui hash dan kemudian lintasi daftar yang ditautkan untuk (e = entryforhash (ini, hash); e! = Null; e = e.next) {k k; // Cari node yang akan diganti berdasarkan tombol dan hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {// Jika nilai saat ini yang ditentukan benar, ganti if (oldvalue.equals (e.Value)) {e.value = newValue; ++ modcount; diganti = true; } // Sebaliknya, jika tidak ada operasi yang dilakukan, return break; }}} akhirnya {buka kunci (); } return diganti;}ConcurrenthashMap juga menyediakan dua operasi penggantian, satu adalah untuk mengganti langsung setelah menemukan, dan yang lainnya adalah membandingkan terlebih dahulu dan kemudian mengganti (operasi CAS). Implementasi kedua operasi ini kira -kira sama, kecuali bahwa operasi CAS memiliki lapisan tambahan operasi perbandingan sebelum diganti, jadi kita hanya perlu memahami secara singkat salah satu operasi. Di sini kami menggunakan operasi CAS untuk analisis, yang masih merupakan rutin lama. Pertama, temukan kunci segmen yang sesuai berdasarkan kode hash kunci, dan kemudian panggil metode ganti. Setelah memasukkan metode ganti di kunci segmen, Anda perlu mendapatkan kunci terlebih dahulu. Jika akuisisi gagal, putar. Jika akuisisi berhasil, lanjutkan ke langkah berikutnya. Pertama, dapatkan simpul header dari daftar yang ditautkan sesuai dengan kode hash, dan kemudian melintasi dan mencari sesuai dengan kunci dan hash. Setelah menemukan elemen yang sesuai, bandingkan apakah OldValue yang diberikan adalah nilai saat ini. Jika tidak, biarkan modifikasi, dan jika demikian, ganti dengan nilai baru. Karena bidang nilai objek hashentry adalah tipe volatile, itu dapat diganti secara langsung.
9. Apa sebenarnya yang Anda lakukan saat berputar?
// berputar menunggu untuk mendapatkan kunci (menempatkan operasi) hashentry pribadi <k, v> scanandlockforput (kunci k, int hash, nilai v) {// Dapatkan node header sesuai dengan kode hash hashentry <k, v> first = entryforhash (ini, hash); Hashentry <k, v> e = pertama; Hashentry <k, v> node = null; int retries = -1; // spin while (! Trylock ()) {hashentry <k, v> f; if (retries <0) {// Jika node header kosong, buat node baru if (e == null) {if (node == null) {node = hashentry baru <k, v> (hash, kunci, nilai, null); } retries = 0; // jika tidak, lintasi daftar yang ditautkan untuk menemukan simpul} lain jika (key.equals (e.key)) {retries = 0; } else {e = e.next; } // coba lagi tambahkan 1 di sini setiap kali dan tentukan apakah itu melebihi nilai maksimum} lain jika (++ retries> max_scan_retries) {lock (); merusak; // Ketika coba lagi adalah angka, tentukan apakah yang pertama telah berubah} lain jika ((retries & 1) == 0 && (f = entryforhash (ini, hash))! = Pertama) {e = pertama = f; retries = -1; }} return node;} // spin menunggu untuk memperoleh kunci (hapus dan ganti operasi) scanandlock pribadi (kunci objek, int hash) {// Dapatkan simpul header dari daftar tertaut sesuai dengan kode hash hashentry <k, v> pertama = entryforhash (ini, hash); Hashentry <k, v> e = pertama; int retries = -1; // spin while (! Trylock ()) {hashentry <k, v> f; if (retries <0) {// Transfer daftar yang ditautkan untuk menemukan simpul if (e == null || key.equals (e.key)) {retries = 0; } else {e = e.next; } // coba lagi tambahkan 1 di sini setiap kali dan tentukan apakah itu melebihi nilai maksimum} lain jika (++ retries> max_scan_retries) {lock (); merusak; // Ketika coba lagi adalah angka, tentukan apakah yang pertama telah berubah} lain jika ((retries & 1) == 0 && (f = entryforhash (ini, hash))! = Pertama) {e = pertama = f; retries = -1; }}}Seperti yang kami sebutkan sebelumnya, letakkan, lepaskan, dan ganti operasi dalam kunci tersegmentasi memerlukan kunci untuk diperoleh terlebih dahulu. Hanya setelah berhasil mendapatkan kunci, operasi berikutnya dapat dilakukan. Jika akuisisi gagal, putaran akan dilakukan. Operasi putaran juga ditambahkan dalam JDK1.7. Untuk menghindari penangguhan dan bangun utas yang sering, dapat meningkatkan kinerja selama operasi bersamaan. Scanandlockforput dipanggil dalam metode put, dan scanandlock dipanggil dalam metode hapus dan ganti. Dua metode putaran kira -kira sama, di sini kami hanya menganalisis metode scanandlockforput. Pertama -tama, Anda harus mendapatkan node header dari daftar tertaut berdasarkan kode hash. Kemudian utas akan masuk ke loop while untuk dieksekusi. Satu -satunya cara untuk keluar dari loop adalah dengan berhasil mendapatkan kunci, dan utas tidak akan ditangguhkan selama periode ini. Ketika loop baru saja dimasukkan, nilai retries adalah -1. Pada saat ini, utas tidak akan mencoba untuk mendapatkan kunci segera. Sebaliknya, pertama -tama akan menemukan simpul yang sesuai dengan kunci (jika tidak ditemukan, yang baru akan dibuat), dan kemudian atur ulang ke 0. Selanjutnya, ia akan mencoba untuk memperoleh kunci lagi dan lagi. Nilai ulang yang sesuai juga akan ditambahkan 1 setiap kali sampai jumlah maksimum upaya melebihi jumlah maksimum upaya. Jika kunci belum diperoleh, metode kunci akan dipanggil untuk memblokir dan memperoleh. Selama upaya untuk memperoleh kunci, ia akan memeriksa apakah node header telah diubah setiap saat (retries genap). Jika diubah, atur ulang ulang kembali ke -1, dan kemudian ulangi prosesnya sekarang. Inilah yang dilakukan utas saat berputar. Perlu dicatat bahwa jika simpul kepala telah terdeteksi untuk diubah selama putaran, waktu putaran utas akan diperpanjang.
10. Operasi apa yang dilakukan saat memperluas tabel hash?
// hash Again @suppresswarnings ("Uncecked") Private Void Rehash (hashentry <k, v> node) {// Dapatkan referensi ke tabel hash hash tua <K, v> [] oldtable = tabel; // Dapatkan kapasitas tabel hash lama int oldcapacity = oldtable.length; // Hitung kapasitas tabel hash baru (2 kali tabel hash lama) int newcapacity = oldcapacity << 1; // Hitung ambang batas elemen baru = (int) (newcapacity * loadFactor); // Buat array hashentry baru hashentry <k, v> [] newtable = (hashentry <k, v> []) hashentry baru [newcapacity]; // menghasilkan nilai mask baru int sizemask = newcapacity - 1; // ketenangan melalui semua elemen tabel lama untuk (int i = 0; i <oldcapacity; i ++) {// Dapatkan simpul header dari daftar tertaut hashentry <k, v> e = oldtable [i]; if (e! = null) {hashentry <k, v> next = e.next; // Hitung indeks elemen dalam tabel baru int idx = e.hash & sizemask; // Berikutnya kosong untuk menunjukkan bahwa hanya ada satu node dalam daftar tertaut jika (NEXT == NULL) {// Masukkan node langsung ke tabel baru yang baru [idx] = e; } else {hashentry <k, v> lastrun = e; int lastidx = idx; // Posisikan simpul lastrun dan langsung masukkan simpul setelah lastrun ke tabel baru untuk (hashentry <k, v> last = next; last! = Null; last = last.next) {int k = last.hash & sizemask; if (k! = lastIdx) {lastIdx = k; lastrun = terakhir; }} newtable [lastIdx] = lastrun; // Transipasi elemen sebelum simpul lastrun dari daftar yang ditautkan, salin ke tabel baru secara bergantian (hashentry <k, v> p = e; p! = Lastrun; p = p.next) {v v = p.value; int h = p.hash; int k = h & sizemask; Hashentry <k, v> n = newtable [k]; newtable [k] = hashentry baru <k, v> (h, p.key, v, n); }}}}} // Hitung subskrip dari simpul yang masuk dalam tabel baru int nodeIndex = node.hash & sizemask; // Tambahkan node yang masuk ke node header dari daftar tertaut node.setNext (newtable [nodeIndex]); // Sukihkan elemen subskrip yang ditentukan tabel baru dengan node newtable yang masuk [nodeIndex] = node; // Poin referensi tabel hash ke tabel tabel baru = newtable;}Metode pengulangan dipanggil dalam metode put. Kita tahu bahwa ketika metode put diadakan, elemen baru akan dibuat dan ditambahkan ke array hash. Semakin besar kemungkinan konflik hash terjadi, semakin besar kinerja tabel hash juga akan menurun. Oleh karena itu, setiap kali operasi put, ia akan memeriksa apakah jumlah total elemen melebihi ambang batas. Jika melebihi ambang batas, metode pengulangan akan dipanggil untuk memperluas kapasitas. Karena panjang array tidak dapat lagi diubah setelah ditentukan, array baru perlu dibuat untuk mengganti array asli. Dari kode, Anda dapat mengetahui bahwa array yang baru dibuat adalah dua kali lipat dari array asli (Oldcapacity << 1). After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.