Jika ada yang membiarkan saya menggambarkan mekanisme kerja peta hash, saya akan menjawab dengan sederhana: "aturan berbasis hash". Kalimat ini sangat sederhana, tetapi sebelum memahami kalimat ini, kita harus terlebih dahulu memahami apa itu, bukan?
Apa itu Beh
Hash hanyalah string unik yang diperoleh setelah atribut variabel/objek diterapkan pada algoritma tertentu, dan string ini digunakan untuk menentukan keunikan variabel/objek. Fungsi hash yang benar harus mematuhi kriteria ini.
Ketika fungsi hash diterapkan ke objek yang sama atau objek yang sama, setiap eksekusi harus mengembalikan nilai yang sama. Dengan kata lain, dua objek yang sama harus memiliki kode hash yang sama.
Catatan: Semua objek Java mewarisi metode hashcode default () dari kelas objek. Metode ini mengembalikan alamat objek dalam memori sebagai integer.
Satu Pengantar Kelas Entri
Definisi peta adalah: objek dari kunci pemetaan ke nilai. Sangat sederhana, bukan?
Oleh karena itu, harus ada mekanisme tertentu dalam hashmap untuk menyimpan pasangan nilai -nilai kunci ini. Buat HashMap memiliki entri kelas internal, yang terlihat seperti ini.
Entri kelas statis <K, V> mengimplementasikan peta.
Tentu saja, kelas entri memiliki atribut untuk menyimpan nilai -nilai kunci. Kunci ditandai dengan final. Selanjutnya kami mencoba memahami arti dari variabel -variabel ini.
Apa sebenarnya metode put ()?
Sebelum melihat implementasi metode put, perlu untuk melihat penyimpanan instance entri dalam array.
/ ** * Tabel, ubah ukurannya. /*** mengaitkan nilai yang ditentukan dengan kunci yang ditentukan dalam peta ini.* Jika peta yang sebelumnya berisi kunci, nilai* lama adalah CED. Nilai nilai yang akan dikaitkan dengan tombol spesifik* @return nilai sebelumnya yang terkait dengan </tt>, atau* <tt> null </tt> Jika theer e /tt>.* (a <tt> null </tt> Pengembalian juga dapat menunjukkan bahwa peta* asosiasi sebelumnya <tt> null </tt> key </tt>.)*/Public v put (K key, value) {if (key == null) return putfornullKey (value); int hash = memiliki (key.hashcode ()); && (k = e.key) == Key || key.equals (k)) {v oldValue = E.Value; , kunci, semua); Mari kita tonton langkah demi langkah
Pertama -tama, periksa apakah kuncinya adalah nol.
Selanjutnya, nilai hash kunci ini dihitung melalui metode hashcode kunci (), yang digunakan untuk menghitung posisi dalam array objek entri. Perancang JDK mengasumsikan bahwa beberapa orang mungkin menulis metode hashcode () yang sangat buruk, dan akan ada beberapa nilai hash yang sangat besar atau sangat kecil. Untuk mengatasi masalah ini, mereka memperkenalkan fungsi hash lain untuk menerima kode hashcode () dari objek dan mengubahnya ke kapasitas array.
Berikutnya adalah metode indexfor (hash, tabel, panjang), yang menghitung lokasi akurat dari penyimpanan objek entri.
Berikutnya adalah bagian utama.
Jawabannya adalah LinkedList. Jika Anda ingat, kelas entri memiliki variabel berikutnya, variabel ini selalu menunjuk ke variabel berikutnya dalam rantai, yang sepenuhnya memenuhi karakteristik daftar yang ditautkan.
Oleh karena itu, ketika sebuah tabrakan, objek entri akan disimpan dalam bentuk daftar yang ditautkan. Objek entri saat ini digunakan sebagai simpul objek entri berikutnya yang telah disimpan.
Bagaimana jika kita menyimpan kunci yang ada dalam nilai lain? Secara logis, nilai lama akan diganti. Setelah mendeteksi posisi penyimpanan objek entri, HashMap akan melintasi daftar entri yang ditautkan di posisi itu. Jika Anda menemukan bahwa metode yang sama sama, penggantian dilakukan.
Dengan cara ini, HashMap dapat memastikan keunikan kunci.
Mekanisme kerja metode get
Sekarang kami telah mempelajari mekanisme penyimpanan -berpasangan di hashmap. Pertanyaan selanjutnya adalah: bagaimana menanyakan hasil dari hashmap.
Bahkan, logikanya sama dengan put.
/*** Mengembalikan nilai di mana tombol spesifik dipetakan,* atau {@code null} Jika peta ini tidak mengandung pemetaan untuk kunci. * {@code k} ke nilai {@code v} sedemikian rupa sehingga {@code (key == null? k == null:* key.equals (k)}, maka metode ini mengembalikan {@code v}; o Theerwise* mengembalikan {@code null}. Digunakan untuk* membedakan dua kasus. ); = kunci ||.Kode di atas terlihat mirip dengan metode put (), kecuali jika (e.hash == hash && ((k = e.key) == key || key.equals (k))).
Memperhatikan