Tandai, dan pada saat yang sama, Anda dapat menggabungkan metode hashcode () dan sama dengan () dengan baik. HashCode () tidak sama, harus berbeda juga untuk dapat menyimpulkan setara ();
Karena ketika hashmap mendapatkan, pertama bandingkan kode hash, lalu bandingkan sama, hashCode == && setara, keduanya benar, jadi itu dianggap sebagai kunci yang sama
1. Ikhtisar HashMap:
HashMap adalah implementasi asinkron dari antarmuka peta berdasarkan tabel hash. Implementasi ini menyediakan semua operasi pemetaan opsional dan memungkinkan penggunaan nilai nol dan kunci nol. Kelas ini tidak menjamin urutan pemetaan, terutama tidak menjamin bahwa pesanan akan bertahan.
2. Struktur Data Hashmap:
Dalam bahasa pemrograman Java, ada dua struktur dasar, satu adalah array dan yang lainnya adalah penunjuk simulasi (referensi). HashMap sebenarnya adalah struktur data "daftar tertaut", yaitu kombinasi array dan daftar tertaut.
Seperti yang dapat dilihat dari gambar di atas, lapisan hashmap yang mendasari adalah struktur array, dan setiap item dalam array adalah daftar tertaut lainnya. Ketika hashmap baru dibuat, array akan diinisialisasi.
Kode sumber adalah sebagai berikut:
/ ** Tabel, diubah ukurannya. Value;
Dapat dilihat bahwa entri adalah elemen dalam array.
3. Implementasi Akses HashMap:
1) Penyimpanan:
public v put (key k, nilai v) {// hashmap memungkinkan tombol nol dan nilai nol. // Ketika kunci adalah nol, panggil metode putfornullkey dan tempatkan nilai pada posisi pertama array. if (key == null) return putfornullkey (nilai); int hash = hash (key.hashcode ()); // Cari indeks nilai hash yang ditentukan dalam tabel yang sesuai. int i = indexfor (hash, table.length); // Jika entri pada indeks I tidak nol, terus melintasi elemen berikutnya dari elemen E melalui loop. untuk (entri <k, v> e = tabel [i]; e! = null; e = e.next) {objek k; | i. Bahwa ini belum ada entri. ModCount ++; // Tambahkan Kunci dan Nilai ke Indeks I. addentry (hash, kunci, nilai, i); Dari kode sumber di atas, kita dapat melihat bahwa ketika kita memasukkan elemen ke dalam hashmap, pertama -tama kita menghitung ulang nilai hash berdasarkan kode hash kunci, dan sesuai dengan nilai hash, posisi elemen ini dalam array (mis., Subskrip ), jika array ada elemen lain yang sudah disimpan di posisi tersebut, sehingga elemen pada posisi ini akan disimpan dalam bentuk daftar yang ditautkan, yang baru ditambahkan ditempatkan di kepala rantai, dan yang pertama ditambahkan yang ditempatkan di ujung rantai. Jika tidak ada elemen pada posisi ini dalam array, letakkan elemen langsung pada posisi ini di array.
Metode addentry (hash, kunci, nilai, i) menempatkan pasangan nilai kunci pada indeks i dari tabel array berdasarkan nilai hash yang dihitung. AddEntry adalah metode izin akses paket yang disediakan oleh HashMap, kodenya adalah sebagai berikut:
void addEntry (int hash, k kunci, v nilai, int bucketindex) {// Dapatkan entri di entri indeks bucketindex yang ditentukan <k, v> e = tabel [bucketindex]; indeks dan biarkan titik masuk baru ke tabel entri asli [bucketindex] = entri baru <k, v> (hash, kunci, nilai, e); (size ++> = threshold) // Perluas panjang objek tabel menjadi dua kali yang asli. Ubah Ulang (2 * Table.Length); Ketika sistem memutuskan untuk menyimpan pasangan nilai kunci dalam hashmap, nilai dalam entri tidak dipertimbangkan sama sekali, dan itu hanya menghitung dan menentukan lokasi penyimpanan setiap entri berdasarkan kunci. Kami dapat sepenuhnya memperlakukan nilai dalam pengumpulan peta sebagai lampiran ke kunci.
Metode hash (int h) menghitung ulang hash sekali berdasarkan kode hash dari kunci. Algoritma ini menambah perhitungan bit tinggi untuk mencegah konflik hash yang disebabkan ketika bit rendah tetap tidak berubah dan ketika perubahan bit tinggi.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); Kita dapat melihat bahwa untuk menemukan elemen dalam hashmap, kita perlu menemukan posisi yang sesuai dalam array berdasarkan nilai hash kunci. Cara menghitung posisi ini adalah algoritma hash. Seperti yang disebutkan sebelumnya, struktur data hashmap adalah kombinasi array dan daftar yang terhubung, jadi tentu saja kami berharap bahwa posisi elemen dalam hashmap ini harus didistribusikan secara merata sebanyak mungkin, sehingga jumlah elemen pada setiap posisi hanya pertama. Efisiensi kueri.
Untuk objek yang diberikan, selama nilai pengembalian hashcode () adalah sama, nilai kode hash yang dihitung dengan program yang memanggil metode hash (int h) selalu sama. Hal pertama yang kami pikirkan adalah memodulo nilai hash ke panjang array, sehingga distribusi elemen relatif seragam. Namun, operasi "modulo" banyak mengkonsumsi, dan ini dilakukan dalam hashmap: panggil Metode indexfor (int h, int length) untuk menghitung indeks mana objek harus disimpan dalam array tabel.
Metode Kode Indeks untuk (int h, int int) adalah sebagai berikut:
indeks int statis untuk (int h, panjang int) {return h & (length-1);Metode ini sangat pintar. ketentuan kecepatan. Dalam konstruktor hashmap, ada kode berikut:
Kapasitas int = 1;
Kode ini memastikan bahwa kapasitas hashmap selalu berada pada kekuatan N 2 selama inisialisasi, yaitu, panjang array yang mendasarinya selalu pada kekuatan N 2.
Ketika panjang selalu dengan daya N 2, operasi H & (panjang-1) setara dengan panjang modulo, yaitu, panjang H %, tetapi & memiliki efisiensi yang lebih tinggi dari %.
Ini terlihat sangat sederhana, tetapi sebenarnya cukup misterius.
Dengan asumsi bahwa panjang array adalah 15 dan 16, dan kode hash yang dioptimalkan masing -masing adalah 8 dan 9, kemudian hasilnya setelah & operasi adalah sebagai berikut:
H & (TABLE.Length-1) Hash Table.length-1
8 & (15-1): 0100 & 1110 = 0100
9 & (15-1): 0101 & 1110 = 0100
-------------------------------------------------- -------------------------------------------------- ---------------------------- ---------------------- -------------------------------------------------- -------------------------------------------------- ------ --------------------------------------------- -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- -------------------------------------------------- ------------
8 & (16-1): 0100 & 1111 = 0100
9 & (16-1): 0101 & 1111 = 0101
Seperti dapat dilihat dari contoh di atas: ketika mereka "sebagai" dengan 15-1 (1110), hasil yang sama dihasilkan, yaitu, mereka akan diposisikan pada posisi yang sama dalam array, yang menciptakan tabrakan, 8 dan 9 akan ditempatkan pada posisi yang sama dalam array untuk membentuk daftar yang ditautkan. Pada saat yang sama, kita juga dapat menemukan bahwa ketika panjang array adalah 15, nilai hash akan "sebagai" dengan 15-1 (1110), maka bit terakhir akan selalu 0, dan 0001, 0011, 0101, 1001 , 1011, 0111, 0111, 1101 tidak pernah dapat menyimpan elemen, dan ruang itu cukup banyak terbuang. Peluang tabrakan semakin meningkat dan efisiensi kueri yang lambat! Ketika panjang array adalah 16, yaitu, ketika itu ke kekuatan N 2, nilai pada setiap bit dari angka biner yang diperoleh 2n-1 adalah 1, yang membuat bit rendah dari jumlah hash asli ketika Ini & pada bit rendah, sehingga bit rendah dari jumlah hash yang diperoleh adalah sama, ditambah dengan metode hash (int h) lebih lanjut mengoptimalkan kode hash dari kunci dan menambahkan perhitungan bit tinggi, sehingga hanya dua nilai Dari nilai hash yang sama akan ditempatkan pada posisi yang sama dalam array untuk membentuk daftar yang ditautkan.
Oleh karena itu, ketika panjang array adalah kekuatan N 2, probabilitas bahwa tombol yang berbeda dapat menghitung indeks yang sama lebih kecil, sehingga data akan didistribusikan secara merata pada array, yang berarti bahwa probabilitas tabrakan kecil, relatif, kueri di Kali ini, Anda tidak perlu melintasi daftar yang ditautkan di lokasi tertentu, sehingga efisiensi kueri akan lebih tinggi.
Menurut kode sumber metode put di atas, ketika program mencoba untuk memasukkan pasangan nilai kunci ke dalam hashmap, program pertama-tama menentukan lokasi penyimpanan entri berdasarkan nilai pengembalian hashcode () dari kunci: jika pada Kunci dari dua entri nilai pengembalian hashcode () adalah sama, dan lokasi penyimpanannya sama. Jika kunci dari dua entri ini kembali benar melalui perbandingan yang sama, nilai entri yang baru ditambahkan akan mengesampingkan nilai entri asli dalam koleksi, tetapi kunci tidak akan mengganti. Jika kunci dari dua entri ini mengembalikan False melalui perbandingan Equals, entri yang baru ditambahkan akan membentuk rantai entri dengan entri asli dalam koleksi, dan entri yang baru ditambahkan terletak di kepala rantai entri - detail terus dilihat untuk dilihat deskripsi metode addentry ().
2) Baca:
Public V Get (Kunci Objek) {if (key == null) return getFornullKey (); Panjangnya)]; mengembalikan E. Dengan algoritma hash yang disimpan di atas sebagai dasar, mudah untuk memahami kode ini. Dari kode sumber di atas, kita dapat melihat bahwa ketika mendapatkan elemen dalam hashmap, pertama -tama hitung kode hash dari kunci, temukan elemen pada posisi yang sesuai dalam array, dan kemudian temukan elemen yang diperlukan dalam daftar yang ditautkan dari posisi yang sesuai Melalui metode Equals dari kunci.
3) Untuk meringkas, hashmap memproses nilai kunci secara keseluruhan di bagian bawah, dan keseluruhan ini adalah objek entri. Hashmap yang mendasarinya menggunakan array entri [] untuk menyimpan semua pasangan nilai kunci. Metode yang sama.
4. Ubah Ukuran Hashmap (Rehash):
Karena semakin banyak elemen dalam hashmap, peluang konflik hash semakin tinggi dan lebih tinggi, karena lamanya array sudah diperbaiki. Oleh karena itu, untuk meningkatkan efisiensi kueri, array hashmap harus diperluas. Muncul: Data dalam array asli harus dihitung ulang dan ditempatkan di array baru, yang diubah ukurannya.
Jadi kapan hashmap akan diperluas? Ketika jumlah elemen dalam hashmap melebihi ukuran array *Loadfactor, array diperluas. Artinya, secara default, ukuran array adalah 16. Kemudian ketika jumlah elemen dalam hashmap melebihi 16*0,75 = 12, ukuran array diperluas menjadi 2*16 = 32, yaitu, dua kali lipat ukurannya, dua kali dan kemudian menghitung ulang. .
5. Parameter Kinerja Hashmap:
HashMap berisi konstruktor berikut:
HashMap (): Bangun hashmap dengan kapasitas awal 16 dan faktor beban 0,75.
HashMap (int initialcapacity): Bangun hashmap dengan kapasitas awal dan faktor beban 0,75.
HashMap (int initialcapacity, float loadfactor): Membuat hashmap dengan kapasitas awal yang ditentukan dan faktor beban yang ditentukan.
Konstruktor dasar HashMap, HashMap (int initialcapacity, float loadfactor), memiliki dua parameter, mereka adalah kapasitas awal kapasitas kapasitas dan factor loadfactor loadfactor.
Kapasitas awal: Kapasitas maksimum hashmap, yaitu, panjang array yang mendasarinya.
LoadFactor: Load Factor LoadFactor didefinisikan sebagai: jumlah aktual elemen tabel hash (n)/kapasitas tabel hash (m).
Faktor beban mengukur tingkat penggunaan ruang tabel hash. Semakin besar faktor beban, semakin tinggi faktor beban, dan sebaliknya. Untuk tabel hash menggunakan metode daftar yang ditautkan, waktu rata -rata untuk menemukan elemen adalah O (1+A) Faktor beban terlalu kecil, maka data tabel hash akan terlalu jarang, menyebabkan pemborosan ruang yang serius.
Dalam implementasi hashmap, kapasitas maksimum hashmap ditentukan oleh bidang ambang:
Salinan kode adalah sebagai berikut:
threshold = (int) (kapasitas * loadfactor);
Berdasarkan rumus definisi dari faktor beban, dapat dilihat bahwa ambang batas adalah jumlah maksimum elemen yang diizinkan sesuai dengan loadfactor dan kapasitas. Faktor beban default 0,75 adalah pilihan seimbang untuk efisiensi spasial dan temporal. Ketika kapasitas melebihi kapasitas maksimum ini, kapasitas hashmap yang diubah ukurannya dua kali kapasitas:
if (size ++> = threshold) mengubah ukuran (2 * tabel.length);
6. Mekanisme gagal-cepat:
Kita tahu bahwa java.util.hashmap tidak aman, jadi jika utas lain memodifikasi peta selama proses penggunaan iterator, concurrentModificationException akan dilemparkan, yang disebut strategi gagal-cepat.
Strategi ini diimplementasikan dalam kode sumber melalui bidang ModCount. Iterator yang diharapkan MODCount.
Hashiterator () {diharapkanmodcount = modcount; ;}} Selama proses iterasi, tentukan apakah ModCount dan yang diharapkan MODCount sama.
Perhatikan bahwa MODCount dinyatakan sebagai volatile, memastikan visibilitas modifikasi antara utas.
entri akhir <k, v> nextEntry () {if (modcount! = diharapkan modcount) lempar concurrentModificationException (); Dalam API Hashmap, dinyatakan:
Iterator yang dikembalikan oleh "Metode Tampilan Koleksi" dari semua kelas HashMap gagal dengan cepat: setelah iterator dibuat, jika pemetaan dimodifikasi dari struktur, kecuali jika dilewatkan melalui metode hapus iterator sendiri, dengan cara lain Lemparkan ConcurrentModificationException jika modifikasi dibuat. Oleh karena itu, dalam menghadapi modifikasi bersamaan, iterator akan segera gagal sepenuhnya tanpa mempertaruhkan perilaku yang tidak pasti sewenang -wenang pada waktu yang tidak pasti di masa depan.
Perhatikan bahwa perilaku kegagalan cepat dari iterator tidak dapat dijamin. Iterator Gagal Cepat Melempar ConcurrentModificationException saat bekerja paling baik. Oleh karena itu, adalah salah untuk menulis program yang bergantung pada pengecualian ini, dan cara yang benar adalah: perilaku kegagalan cepat dari iterator harus digunakan hanya untuk mendeteksi kesalahan program.