Tinjauan 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.
Struktur data HashMap
Dalam bahasa pemrograman Java, ada dua struktur dasar, satu adalah array dan yang lainnya adalah pointer simulasi (referensi). Semua struktur data dapat dibangun menggunakan dua struktur dasar ini, dan hashmap tidak terkecuali. HashMap sebenarnya adalah struktur data "daftar tertaut", yaitu struktur array dan daftar tertaut, tetapi di JDK1.8
Implementasi pohon merah dan hitam ditambahkan. Ketika panjang daftar yang ditautkan lebih besar dari 8, ia dikonversi menjadi struktur pohon merah dan hitam.
Seperti yang dapat dilihat dari gambar di atas, HashMap menggunakan metode alamat rantai di Java. Metode alamat tautan, sederhananya, adalah kombinasi dari array dan daftar tertaut. Ada struktur daftar tertaut pada setiap elemen array. Ketika data hash, subskrip array diperoleh dan data ditempatkan pada daftar tertaut dari elemen subskrip yang sesuai.
*/ Node kelas statis <K, V> mengimplementasikan peta.entry <k, v> {final int hash; // Digunakan untuk menemukan posisi kunci Kunci K Final Indeks Array; Nilai v; Node <k, v> next; // node berikutnya di node daftar tertaut (int hash, k tombol, v nilai, node <k, v> next) {this.hash = hash; this.key = key; this.value = nilai; this.next = next; }Node adalah kelas internal hashmap, yang mengimplementasikan antarmuka MAP.Entry, yang pada dasarnya adalah peta (pasangan nilai kunci).
Terkadang dua tombol diposisikan ke posisi yang sama, menunjukkan tabrakan hash terjadi. Tentu saja, semakin seragam hasil perhitungan algoritma hash, semakin kecil probabilitas tabrakan hash, dan semakin tinggi efisiensi akses peta.
Ada bidang yang sangat penting di kelas hashmap, yang merupakan tabel node [], yaitu, array ember hash. Ini jelas merupakan array node.
Jika array ember hash besar, bahkan algoritma hash yang miskin akan lebih tersebar. Jika array array hash ember array kecil, bahkan algoritma hash yang baik akan memiliki lebih banyak tabrakan, jadi perlu untuk menimbang biaya ruang dan biaya waktu. Bahkan, itu adalah untuk menentukan ukuran array hash ember berdasarkan situasi aktual, dan atas dasar ini, algoritma hash yang dirancang akan mengurangi tabrakan hash. Jadi bagaimana kita bisa mengontrol peta untuk membuat probabilitas tabrakan hash kecil, dan hash ember array (node [] tabel) mengambil lebih sedikit ruang? Jawabannya adalah algoritma hash yang bagus dan mekanisme ekspansi kapasitas.
Sebelum memahami proses hash dan ekspansi, kita perlu memahami beberapa bidang hashmap. Dari kode sumber konstruktor default HashMap, dapat dilihat bahwa konstruktor menginisialisasi bidang -bidang berikut, kode sumber adalah sebagai berikut:
ambang batas int; // Nilai kunci yang dapat ditampung adalah Ultimate Float Loadfactor; // Faktor Muat Int ModCount; ukuran int;
Pertama, panjang inisialisasi dari tabel node [] (nilai default adalah 16), faktor beban adalah faktor beban (nilai default adalah 0,75), dan ambang batas adalah jumlah simpul (pasangan nilai kunci) dari jumlah data maksimum yang dapat ditampung hashmap. ambang = panjang * faktor beban. Dengan kata lain, setelah array telah menentukan panjangnya, semakin besar faktor beban, semakin banyak pasangan nilai kunci yang dapat ditampung.
Berdasarkan rumus definisi dari faktor beban, dapat dilihat bahwa ambang batas adalah jumlah maksimum elemen yang diizinkan sesuai dengan faktor dan panjang beban ini (panjang array). Jika nomor ini melebihi ini, ubah ukurannya (perbesar kapasitas). Kapasitas hashmap yang diperluas adalah dua kali kapasitas sebelumnya. Faktor beban default 0,75 adalah pilihan seimbang untuk efisiensi ruang dan waktu. Dianjurkan agar Anda tidak memodifikasinya kecuali dalam hal waktu dan ruang khusus, jika ada banyak ruang memori dan persyaratan efisiensi waktu yang tinggi, nilai faktor beban beban dapat dikurangi; Sebaliknya, jika ruang memori ketat dan persyaratan efisiensi waktu tidak tinggi, nilai faktor beban beban dapat ditingkatkan, yang dapat lebih besar dari 1.
Bidang ukuran sebenarnya mudah dimengerti, itu adalah jumlah pasangan nilai kunci yang benar-benar ada di hashmap. Perhatikan perbedaan antara panjang tabel dan jumlah ambang yang mengakomodasi pasangan nilai kunci maksimum. Bidang ModCount terutama digunakan untuk mencatat jumlah perubahan dalam struktur internal hashmap, dan terutama digunakan untuk kegagalan iterasi yang cepat. Untuk menekankan, perubahan dalam struktur internal merujuk pada perubahan dalam struktur, seperti menempatkan pasangan nilai kunci baru, tetapi nilai yang sesuai dengan kunci ditimpa dan bukan milik perubahan struktural.
Pada hashmap, panjang tabel array hash ember harus dalam kekuatan N 2 (harus bilangan komposit). Ini adalah desain yang tidak konvensional. Desain konvensionalnya adalah merancang ukuran ember sebagai bilangan prima. Secara relatif, probabilitas konflik yang disebabkan oleh bilangan prima lebih kecil dari bilangan komposit. Untuk bukti tertentu, silakan merujuk ke //www.vevb.com/article/100911.htm. Hashtable menginisialisasi ukuran bucket ke 11, yang merupakan aplikasi ukuran ember yang dirancang sebagai bilangan prima (hashtable tidak dapat dijamin menjadi bilangan prima setelah ekspansi). HashMap mengadopsi desain yang tidak konvensional ini, terutama untuk mengoptimalkan ketika modulo dan ekspansi. Pada saat yang sama, untuk mengurangi konflik, HashMap juga menambahkan proses partisipasi tinggi dalam komputasi saat menemukan posisi indeks hash bucket.
Ada masalah di sini. Bahkan jika faktor beban dan algoritma hash dirancang secara wajar, pasti akan ada situasi di mana ritsleting terlalu panjang. Setelah ritsleting terlalu lama, itu akan sangat mempengaruhi kinerja hashmap. Oleh karena itu, dalam versi JDK1.8, struktur data dioptimalkan lebih lanjut dan pohon merah dan hitam diperkenalkan. Ketika panjang daftar yang ditautkan terlalu panjang (standarnya lebih dari 8), daftar tertaut diubah menjadi pohon merah dan hitam. Karakteristik penambahan cepat pohon merah dan hitam, penghapusan, modifikasi dan pencarian akan digunakan untuk meningkatkan kinerja hashmap. Penyisipan, penghapusan, dan pencarian pohon merah dan hitam akan digunakan untuk memasukkan, menghapus, dan mencari algoritma seperti pohon merah dan hitam.
Tentukan posisi indeks array ember hash
Implementasi Kode:
// Metode 1: hash int static final (kunci objek) {//jdk1.8 & jdk1.7 int h; // h = key.hashCode () Mendapat nilai kode hash untuk langkah pertama // h ^ (h >>> 16) berpartisipasi dalam pengoperasian pengembalian langkah kedua (key == null)? 0: (h = key.HashCode ()) ^ (h >>> 16);} // Metode 2: indeks int statis untuk (int h, panjang int) {//jdk1.7 Kode sumber, JDK1.8 tidak memiliki metode ini, tetapi prinsip implementasi adalah pengembalian yang sama H & (panjang-1); // Langkah ketiga mengambil operasi modulus}Algoritma hash di sini pada dasarnya adalah tiga langkah: mengambil nilai kode hash dari operasi kunci, bit tinggi, dan operasi modulus.
Untuk objek yang diberikan, selama nilai pengembalian hashcode () adalah sama, kode hash yang dihitung dengan metode panggilan program, seseorang selalu sama. Hal pertama yang kami pikirkan adalah memodulo nilai hash ke panjang array, sehingga distribusi elemen relatif seragam. Namun, konsumsi operasi modulus relatif besar. Ini dilakukan di HashMap: Metode Panggilan Dua untuk menghitung indeks mana objek harus disimpan dalam array tabel.
Metode ini sangat pintar. Ini memperoleh bit yang disimpan dari objek melalui h & (tabel.length -1), dan panjang array hashmap yang mendasari selalu ke n -power dari 2, yang merupakan optimalisasi hashmap dalam hal kecepatan. 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 %.
Dalam implementasi JDK1.8, algoritma untuk operasi bit tinggi dioptimalkan, dan implementasi hashcode ()-16-bit-bit-16-bit (h = k.hashcode ()) ^ (h >>> 16), yang terutama dipertimbangkan dari kecepatan, efisiensi, dan kualitas. Ini dapat memastikan bahwa ketika panjang tabel array relatif kecil, ia juga dapat memastikan bahwa bit terlibat dalam perhitungan hash dengan mempertimbangkan rendah-rendah, dan tidak akan ada overhead yang berlebihan.
Berikut adalah contohnya, N adalah panjang tabel.
Hashmap menempatkan implementasi metode
Gagasan umum dari fungsi put adalah:
Kode spesifik diimplementasikan sebagai berikut:
public v put (key k, nilai v) {return putval (hash (kunci), kunci, nilai, false, true); } / ***Metode untuk menghasilkan hash hash* / static final int hash (kunci objek) {int h; return (key == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); } final v putval (int hash, k kunci, v nilai, boolean onlyifabsent, boolean eVict) {node <k, v> [] tab; Node <k, v> p; int n, i; // menilai apakah tabel kosong, if ((tab = tabel) == null || (n = tab.length) == 0) n = (tab = ubah ukuran ()). Panjang; // Buat array tabel baru dan dapatkan panjang array // Hitung nilai hash ke indeks array yang dimasukkan i sesuai dengan kunci nilai kunci. Jika tabel [i] == null, langsung buat simpul baru dan tambahkan if ((p = tab [i = (n - 1) & hash]) == null) tab [i] = newNode (hash, kunci, nilai, null); else {// jika simpul yang sesuai memiliki simpul <k, v> e; K K; // menilai apakah elemen pertama tabel [i] sama dengan kunci, jika sama, langsung menimpa nilai jika (p.hash == hash && ((k = p.key) == key || (key! = Null && key.equals (k)))) e = p; // menilai apakah tabel [i] adalah treenode, yaitu, apakah tabel [i] adalah pohon merah-hitam. Jika itu adalah pohon merah-hitam, langsung masukkan pasangan nilai kunci di pohon lain jika (p instance dari treenode) e = ((treenode <k, v>) p) .puttreeval (ini, tab, hash, kunci, nilai); // Rantai ini adalah daftar lain yang ditautkan {// Transipate melalui Tabel [i] untuk menentukan apakah panjang daftar yang ditautkan lebih besar dari Treeify_Threshold (nilai defaultnya adalah 8). Jika lebih besar dari 8, ubah daftar yang ditautkan menjadi pohon merah-hitam dan lakukan operasi penyisipan di pohon merah-hitam. Kalau tidak, operasi penyisipan daftar tertaut dilakukan; Jika ditemukan bahwa kunci sudah memiliki nilai timpa langsung selama proses traversal; untuk (int bincount = 0;; ++ bincount) {if ((e = p.next) == null) {p.next = newNode (hash, kunci, nilai, null); if (Bincount> = Treey_threshold - 1) // -1 untuk 1st TreeyBin (tab, hash); merusak; } if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) break; p = e; }} // tulis if (e! = Null) {// pemetaan yang ada untuk kunci v oldvalue = e.value; if (! OnlyIfabSent || oldValue == null) e.value = nilai; sore hari (e); Kembalikan OldValue; }} ++ modcount; // Setelah penyisipan berhasil, tentukan apakah jumlah aktual pasangan nilai kunci melebihi ambang kapasitas maksimum. Jika melebihi kapasitas, perluas if (++ size> threshold) ubah ukuran (); sore hari (penggusuran); kembali nol; }Hashmap get metode implementasi
Idenya adalah sebagai berikut:
1. Node pertama dalam ember, tekan langsung;
2. Jika ada konflik, gunakan kunci.Equals (k) untuk menemukan entri yang sesuai
Jika itu adalah pohon, maka cari di pohon melalui kunci.
Jika itu adalah daftar yang ditautkan, maka cari melalui key.equals (k) dalam daftar tertaut, o (n).
public v get (tombol objek) {node <k, v> e; return (e = getNode (hash (key), key)) == null? NULL: E.Value; } node akhir <k, v> getNode (int hash, tombol objek) {node <k, v> [] tab; Node <k, v> pertama, e; int n; K K; if ((tab = tabel)! = null && (n = tab.length)> 0 && (first = tab [(n - 1) & hash])! = null) {// tekan langsung jika (first.hash == hash && // setiap kali diperiksa node pertama ((k = first.key) == key || (KEY! = TULAN & NULL / TOULE (K = K = First.Key) == KUNCI || // melewatkan if ((e = first.next)! = Null) {// dapatkan if (instance pertama dari treenode) return ((treenode <k, v>) pertama) .gettreenode (hash, key); // dapatkan do {if (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) return e; } while ((e = e.next)! = null); }} return null; }Mekanisme ekspansi kapasitas
Ubah ukuran berarti menghitung ulang kapasitas dan terus -menerus menambahkan elemen ke objek hashmap. Ketika array di dalam objek hashmap tidak dapat memuat lebih banyak elemen, objek perlu memperluas panjang array sehingga lebih banyak elemen dapat dimuat. Tentu saja, array di Java tidak dapat diperluas secara otomatis. Metode ini adalah menggunakan array baru alih -alih array yang ada dengan kapasitas kecil, sama seperti kami menggunakan ember kecil untuk mengisi air. Jika kita ingin mengisi lebih banyak air, kita harus menggantinya dengan ember besar.
Kami menganalisis kode sumber mengubah ukuran. Mengingat bahwa JDK1.8 mengintegrasikan pohon merah dan hitam, itu lebih rumit. Untuk memfasilitasi pemahaman, kami masih menggunakan kode JDK1.7, yang lebih mudah dipahami. Ada sedikit perbedaan dalam esensi. Mari kita bicara tentang perbedaan spesifik nanti.
void mengubah ukuran (int newcapacity) {// jeda entri kapasitas baru [] oldtable = tabel; // referensi array entri sebelum ekspansi int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) {// Jika ukuran array sebelum ekspansi telah mencapai ambang maksimum (2^30) = integer.max_value; // Ubah ambang batas ke nilai maksimum int (2^31-1), sehingga kapasitas tidak akan diperluas di pengembalian di masa depan; } Entri [] newtable = entri baru [newcapacity]; // inisialisasi transfer array entri baru (NewTable); //! Lai Mentransfer data ke tabel array entri baru = newtable; // Atribut tabel HashMap mengacu pada ambang array entri baru = (int) (newcapacity * loadFactor); // Ubah ambang}Di sini kami menggunakan array dengan kapasitas yang lebih besar alih -alih array yang ada dengan kapasitas yang lebih kecil. Metode transfer () menyalin elemen -elemen dari array masuk asli ke array entri baru.
void transfer (entri [] newtable) {entri [] src = tabel; // src mengacu pada array entri lama int newcapacity = newtable.length; untuk (int j = 0; j <src.length; j ++) {// ketenangan melalui entri array entri lama <k, v> e = src [j]; // Dapatkan setiap elemen dari array entri lama jika (e! = Null) {src [j] = null; // Lepaskan referensi objek dari array entri lama (setelah loop for, array entri lama tidak lagi mengacu pada objek apa pun) lakukan {entri <k, v> next = e.next; int i = indexfor (e.hash, newcapacity); //! Lai Hitung ulang posisi setiap elemen dalam array e.next = newtable [i]; // Tag [1] Newtable [i] = e; // Letakkan elemen pada array e = selanjutnya; // akses elemen pada rantai entri berikutnya} while (e! = Null); }}}Referensi ke Newtable [i] ditugaskan ke E.Next, yang berarti bahwa metode penyisipan header dari satu daftar tertaut digunakan. Elemen -elemen baru pada posisi yang sama akan selalu ditempatkan di kepala daftar yang ditautkan; Dengan cara ini, elemen -elemen yang ditempatkan pada indeks pada akhirnya akan ditempatkan pada akhir rantai masuk (jika konflik hash terjadi). Ini berbeda dari JDK1.8, yang dijelaskan secara rinci di bawah ini. Elemen pada rantai masuk yang sama dalam array lama dapat ditempatkan pada posisi yang berbeda dalam array baru setelah menghitung ulang posisi indeks.
Berikut adalah contoh untuk menggambarkan proses ekspansi kapasitas. Asumsikan bahwa algoritma hash kami hanya menggunakan mod kunci untuk mendapatkan ukuran tabel (yaitu, panjang array). Ukuran tabel array hash ember = 2, sehingga kunci = 3, 7, 5, dan urutan put adalah 5, 7, dan 3. Setelah mod 2, konflik ada pada tabel [1]. Di sini, diasumsikan bahwa factor loadfactor load = 1, yaitu, ketika ukuran sebenarnya dari pasangan nilai kunci lebih besar dari ukuran tabel yang sebenarnya, diperluas. Tiga langkah berikutnya adalah proses mengubah ukuran array hash ember menjadi 4, dan kemudian mengulangi semua node.
Mari kita jelaskan optimisasi apa yang telah dibuat di JDK1.8. Setelah observasi, kita dapat menemukan bahwa kita menggunakan kekuatan dua ekspansi (mengacu pada panjang dua kali yang asli), sehingga posisi elemen baik dalam posisi asli atau menggerakkan posisi kekuatan dua lagi pada posisi asli. Melihat gambar di bawah ini, Anda dapat memahami arti dari kalimat ini. n adalah panjang meja. Gambar (a) merupakan contoh posisi indeks dari dua tombol yang menentukan posisi indeks dari KEY1 dan KEY2 sebelum ekspansi. Gambar (b) merupakan contoh posisi indeks dari Key1 dan Key2 setelah ekspansi. Di mana hash1 adalah hash dan hasil operasi bit tinggi yang sesuai dengan key1.
Setelah elemen menghitung ulang hash, karena n menjadi 2 kali, kisaran topeng N-1 adalah 1 bit (merah) pada titik tinggi, sehingga indeks baru akan berubah seperti ini:
Oleh karena itu, ketika kami memperluas hashmap, kami tidak perlu menghitung ulang hash seperti implementasi JDK1.7. Kita hanya perlu melihat apakah bit yang ditambahkan ke nilai hash asli adalah 1 atau 0. Jika 0, indeks belum berubah. Jika 1, indeks menjadi "indeks asli + oldcap". Anda dapat melihat angka berikut sebagai diagram ubah ukuran dengan 16 ekspansi ke 32:
Desain ini memang sangat pintar, yang tidak hanya menghemat waktu untuk menghitung ulang nilai hash, tetapi juga, karena 1bit yang baru ditambahkan adalah 0 atau 1, itu dapat dianggap acak, sehingga proses mengubah ukuran secara merata mendistribusikan node yang bertentangan sebelumnya ke ember baru. Ini adalah titik optimisasi baru yang ditambahkan oleh JDK1.8. Ada sedikit perhatian pada perbedaannya. Ketika Rehash di JDK1.7, ketika daftar lama yang ditautkan memigrasikan daftar tertaut baru, jika posisi indeks array dari tabel baru adalah sama, elemen daftar tertaut akan dibalik, tetapi seperti yang dapat dilihat dari gambar di atas, JDK1.8 tidak akan dibalik. Siswa yang tertarik dapat mempelajari kode sumber ubah ukuran JDK1.8, yang sangat bagus, sebagai berikut:
node akhir <k, v> [] mengubah ukuran () {node <k, v> [] oldtab = tabel; int oldcap = (oldtab == null)? 0: oldtab.length; int oldthr = ambang; int newcap, newThr = 0; if (oldcap> 0) {// Jika nilai maksimum melebihi, itu tidak akan lagi diperluas, jadi saya harus bertabrakan dengan Anda jika (oldcap> = maximum_capacity) {threshold = integer.max_value; kembali oldtab; } // Jika nilai maksimum tidak terlampaui, itu akan diperluas ke 2 kali ifer asli ((newcap = oldcap << 1) <maximum_capacity && oldcap> = default_initial_capacity) newThr = oldthThr << 1; // ambang ganda} lain jika (oldthr> 0) // kapasitas awal ditempatkan di ambang batas newcap = oldthr; else {// nol ambang batas awal menandakan menggunakan default newcap = default_initial_capacity; newThr = (int) (default_load_factor * default_initial_capacity); } // Hitung ubah ukuran baru batas atas jika (newThr == 0) {float ft = (float) newcap * loadFactor; newThr = (newcap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: integer.max_value); } threshold = newThr; @SuppressWarnings ({"RawTypes", "Uncecked"}) node <k, v> [] newtab = (node <k, v> []) node baru [newcap]; tabel = newtab; if (oldtab! = null) {// pindahkan setiap ember ke ember baru untuk (int j = 0; j <oldcap; ++ j) {node <k, v> e; if ((e = oldtab [j])! = null) {oldtab [j] = null; if (e.next == null) newtab [e.hash & (newcap - 1)] = e; lain jika (e instance dari treenode) ((treenode <k, v>) e) .split (ini, newtab, j, oldcap); else {// simpan simpul pesanan <k, v> loHead = null, lotail = null; Node <k, v> hime = null, hitail = null; Node <k, v> selanjutnya; do {next = e.next; // indeks asli if ((e.hash & oldcap) == 0) {if (lOTAIL == null) lohead = e; selain itu lOatail.next = e; LOTAIL = E; } // indeks asli + oldcap else {if (hitail == null) hyhead = e; lain hitail.next = e; HITAIL = E; }} while ((e = next)! = null); // Masukkan indeks asli ke dalam ember if (lobail! = Null) {lOTAIL.next = null; newtab [j] = lohead; } // Masukkan indeks asli + oldcap ke dalam ember if (HITAIL! = NULL) {HITAIL.NEXT = NULL; newtab [j + oldcap] = hyhead; }}}}} return newtab;}Meringkaskan
Kita sekarang dapat menjawab beberapa pertanyaan di awal untuk memperdalam pemahaman kita tentang hashmap:
1. Kapan hashmap akan digunakan? Apa karakteristiknya?
Ini didasarkan pada implementasi antarmuka peta. Saat menyimpan pasangan nilai kunci, ia dapat menerima nilai-nilai kunci nol, yang asinkron. HashMap Stores Entry (hash, kunci, nilai, berikutnya) Objek.
2. Tahukah Anda cara kerja hashmap?
Melalui metode hash, objek disimpan dan diperoleh melalui put dan dapatkan. Saat menyimpan objek, ketika kita meneruskan K/V ke metode put, itu memanggil kode hash untuk menghitung hash untuk mendapatkan lokasi ember dan menyimpannya lebih lanjut. HashMap akan secara otomatis menyesuaikan kapasitas sesuai dengan pekerjaan ember saat ini (jika melebihi beban facotr, ubah ukurannya dua kali lipat asli). Saat mendapatkan objek, kami melewati K untuk mendapatkan, yang memanggil kode hash untuk menghitung hash untuk mendapatkan posisi ember, dan lebih lanjut memanggil metode Equals () untuk menentukan pasangan nilai kunci. Jika terjadi tabrakan, HashMap mengatur elemen -elemen yang menghasilkan konflik tabrakan melalui daftar yang ditautkan. Di Java 8, jika elemen yang bertabrakan dalam ember melebihi batas tertentu (standarnya adalah 8), pohon merah dan hitam digunakan untuk mengganti daftar yang ditautkan untuk meningkatkan kecepatan.
3. Apakah Anda tahu prinsip -prinsip Get and Pat? Apa fungsi Equals () dan HashCode ()?
Dengan hashing hashcode () dari kunci dan menghitung subskrip (n-1 & hash), posisi ember diperoleh. Jika terjadi tabrakan, gunakan metode key.equals () untuk mencari node yang sesuai dalam daftar atau pohon yang ditautkan
4. Apakah Anda tahu implementasi hash? Mengapa saya perlu melakukan ini?
Dalam implementasi Java 1.8, ini diimplementasikan melalui hashCode 16-bit 16-bit tinggi 16-bit (): (h = k.hashcode ()) ^ (h >>> 16), yang terutama dipertimbangkan dari kecepatan, efisiensi, dan kualitas. Ini dapat memastikan bahwa ketika N dari ember relatif kecil, ia juga dapat memastikan bahwa kedua bit tinggi dan rendah terlibat dalam perhitungan hash, dan tidak akan ada overhead yang berlebihan.
5. Bagaimana jika ukuran hashmap melebihi kapasitas yang ditentukan oleh faktor beban?
Jika faktor beban terlampaui (default 0,75), hashmap dengan dua kali panjang asli akan diubah ukurannya dan metode hash akan dipanggil lagi.
Lembar cheat tentang koleksi java digambarkan sebagai berikut:
Array hash ember yang diimplementasikan dengan array entri [], dan nilai hash dari kunci dapat digunakan untuk mendapatkan subskrip array.
Saat memasukkan elemen, jika dua tombol jatuh ke dalam ember yang sama (misalnya, setelah nilai hash 1 dan 17 adalah Modulo 16, keduanya milik ember hash pertama), entri menggunakan properti berikutnya untuk mengimplementasikan beberapa entri dalam daftar tertaut satu arah, dan entri yang memasuki titik ember di sebelah entri ember saat ini.
Saat mencari kunci dengan nilai hash 17, pertama temukan ember hash pertama, kemudian beralih melalui semua elemen dalam ember dengan daftar tertaut, dan bandingkan nilai -nilai kunci mereka satu per satu.
Ketika jumlah entri mencapai 75% dari ember (banyak artikel mengatakan bahwa jumlah ember yang digunakan mencapai 75%, tetapi menurut kode, array ember akan diperluas secara eksponensial dan semua entri asli akan dipindahkan, jadi sebaiknya memiliki nilai yang diperkirakan di sini.
Operasi bit (hash & (arraylength-1)) akan lebih cepat, sehingga ukuran array selalu ke daya n 2. Jika Anda memberikan nilai awal seperti 17, itu akan dikonversi menjadi 32. Nilai awal default ketika elemen pertama ditempatkan adalah 16.
Iterator () melintasi di sepanjang array hash ember, yang terlihat seperti rusak.
6. Apa yang terjadi ketika kode hash dua objek sama?
Karena kode hash adalah sama, posisi ember mereka sama, dan 'tabrakan' akan terjadi. Karena HashMap menggunakan daftar tertaut untuk menyimpan objek, entri ini (objek MAP.Entry yang berisi pasangan nilai kunci) disimpan dalam daftar tertaut.
7. Jika kode hash dua tombol sama, bagaimana Anda mendapatkan objek nilai?
Setelah menemukan lokasi bucket, metode Keys.equals () akan dipanggil untuk menemukan simpul yang benar dalam daftar tertaut, dan akhirnya menemukan objek nilai yang dapat ditemukan. Oleh karena itu, ketika merancang jenis utama hashmap, jika objek yang tidak dapat diubah dinyatakan sebagai final dan metode setara () dan hashcode () yang sesuai digunakan, terjadinya tabrakan akan dikurangi dan efisiensi akan ditingkatkan. Ketidakmampuan dapat men -cache hashcodes untuk tombol yang berbeda, yang akan meningkatkan kecepatan mendapatkan seluruh objek. Menggunakan kelas pembungkus seperti string dan interger sebagai kunci adalah pilihan yang sangat baik.
8. Bagaimana jika ukuran hashmap melebihi kapasitas yang ditentukan oleh faktor beban?
Ukuran faktor beban default adalah 0,75. Artinya, ketika peta mengisi 75% ember, seperti kelas koleksi lainnya (seperti arraylist, dll.), Array ember yang dua kali ukuran hashmap asli akan dibuat untuk mengubah ukuran peta dan memasukkan objek asli ke dalam array ember baru. Proses ini disebut Rephashing karena memanggil metode hash untuk menemukan lokasi ember baru
9. Apakah Anda mengerti apa yang salah dengan mengubah ukuran hashmap?
Ketika mengubah ukuran hashmap, memang ada persaingan bersyarat, karena jika kedua utas menemukan bahwa hashmap perlu diubah ukurannya, mereka akan mencoba mengubah ukuran pada saat yang sama. Selama proses mengubah ukuran, urutan elemen yang disimpan dalam daftar yang ditautkan akan dibalik, karena ketika pindah ke posisi ember baru, HashMap tidak menempatkan elemen -elemen di akhir daftar yang ditautkan, tetapi di kepala, yaitu untuk menghindari melintasi ekor. Jika persaingan bersyarat terjadi, maka ada lingkaran setan. Oleh karena itu, dalam lingkungan yang bersamaan, kami menggunakan CurrentHashMap untuk menggantikan HashMap
10. Mengapa kelas pembungkus seperti string dan interger cocok sebagai kunci?
Karena string tidak dapat diubah dan final, dan sama () dan metode hashcode () telah ditulis ulang. Kelas pembungkus lainnya juga memiliki fitur ini. Keabadian diperlukan karena untuk menghitung kode hashcode (), Anda harus mencegah nilai kunci berubah. Jika nilai kunci mengembalikan kode hash yang berbeda saat memasukkan dan mendapatkan, Anda tidak dapat menemukan objek yang Anda inginkan dari hashmap. Ketidakmampuan memiliki keunggulan lain seperti keamanan utas. Jika Anda dapat menjamin bahwa kode hash tidak berubah hanya dengan menyatakan bidang sebagai final, maka silakan lakukan. Karena metode Equals () dan HashCode () digunakan saat mendapatkan objek, sangat penting untuk menulis ulang kedua metode ini dengan benar. Jika dua objek yang tidak setara mengembalikan kode hash yang berbeda, kemungkinan tabrakan akan lebih kecil, yang akan meningkatkan kinerja hashmap
Terima kasih telah membaca, saya harap ini dapat membantu Anda. Terima kasih atas dukungan Anda untuk situs ini!