Pertama -tama mari kita lihat pertanyaan wawancara:
Serangkaian pasangan nilai kunci yang disimpan dalam hashmap, di mana kuncinya adalah jenis tertentu yang kami sesuaikan. Setelah memasukkan hashmap, kami mengubah atribut kunci secara eksternal, dan kemudian kami menggunakan kunci ini untuk menghapus elemen dari hashmap. Apa yang akan dikembalikan hashmap saat ini?
Kode sampel dan jawaban telah diberikan dalam artikel, tetapi tidak ada penjelasan yang diberikan tentang prinsip hashmap.
1. Fitur
Kita dapat menggunakan kelas apa pun sebagai kunci hashmap, tetapi apa pembatasan pada kelas -kelas ini? Mari kita lihat kode berikut:
orang kelas publik {nama string privat; orang publik (nama string) {this.name = name; }} Peta <Person, String> testMap = new HashMap <> (); testmap.put (orang baru ("halo"), "dunia"); testmap.get (orang baru ("halo")); // ---> nullSaya awalnya ingin mendapatkan nilai kelas orang dengan nilai bidang yang sama, tetapi hasilnya nol. Siapa pun yang memiliki sedikit pengetahuan tentang hashmap dapat melihat bahwa kelas orang tersebut tidak memiliki metode kode hash override, yang mengarah pada warisannya terhadap kode hash objek (pengembalian adalah alamat memori). Ini juga merupakan alasan mengapa kelas invarian seperti string (atau integer, dll.) Biasanya digunakan sebagai kunci hashmap. Jadi, bagaimana hashmap menggunakan kode hash untuk dengan cepat mengindeks kunci?
2. Prinsip
Pertama, mari kita lihat solusi implementasi hashmap sederhana dalam "Thinking in Java":
//: wadah/simpleHashMap.java // Demonstrasi hashed map.import java.util.*; impor net.mindview.util.*; kelas publik SimpleHashMap <K, V> memperluas abstrak <K, v> {// Pilih bilangan prima untuk ukuran tabel hash, untuk mencapai distribusi yang seragam: Static: Static: Static = 9; // Anda tidak dapat memiliki serangkaian obat generik fisik, tetapi Anda dapat diatur ke satu: @suppressWarnings ("Uncecked") LinkedList <MapEntrry <K, V >> [] Buckets = Daftar LinkedList baru [ukuran]; public v put (key k, nilai v) {v oldValue = null; int index = math.abs (key.hashcode ()) % ukuran; if (buckets [index] == null) bucket [index] = new LinkedList <MapEntry <K, v >> (); LinkedList <MapEntry <K, V >> Bucket = Buckets [Index]; MapEntry <K, V> pair = MapEntry baru <K, V> (key, value); boolean ditemukan = false; ListIterator <MapEntry <K, V >> it = bucket.listiterator (); while (it.hasnext ()) {MapEntry <k, v> ipair = it.next (); if (ipair.getKey (). Equals (key)) {oldValue = ipair.getValue (); It.set (pasangan); // ganti lama dengan found baru = true; merusak; }} if (! Ditemukan) bucket [index] .add (pair); Kembalikan OldValue; } public v get (tombol objek) {int index = math.abs (key.HashCode ()) % ukuran; if (bucket [index] == null) return null; untuk (MapEntry <K, V> IPAIR: Buckets [index]) if (ipair.getKey (). Equals (key)) mengembalikan ipair.getValue (); kembali nol; } set publik <map.entry <k, v >> entryset () {set <map.entry <k, v >> set = hashset baru <map.entry <k, v >> (); untuk (LinkedList <MapEntry <K, V >> Bucket: Bucket) {if (bucket == null) Lanjutkan; untuk (MapEntry <K, V> MPAIR: Bucket) Set.Add (MPAIR); } return set; } public static void main (String [] args) {SimpleHashMap <String, String> m = new SimpleHashMap <String, String> (); M.PutAll (Negara -negara. Kapital (25)); System.out.println (m); System.out.println (m.get ("Eritrea")); System.out.println (m.entryset ()); }}SimpleHashMap membuat meja hash untuk menyimpan kunci. Fungsi hash adalah Modulus Operation Math.ABS (Key.HashCode ()) %, dan konflik hash diselesaikan dengan menggunakan metode daftar tertaut; Setiap slot bucket menyimpan peta. Acara dengan nilai indeks yang sama (hash), seperti yang ditunjukkan pada gambar di bawah ini:
Prinsip implementasi hashmap JDK mirip dengan itu, yang menggunakan tabel hash alamat rantai untuk menyimpan peta.
/*** Tabel, diubah ukurannya seperlunya. Panjang harus selalu menjadi kekuatan dua. */entri transien <k, v> [] tabel = (entri <k, v> []) kosong_table; entri kelas statis <k, v> mengimplementasikan peta.entry <k, v> {kunci k final; Nilai v; Entri <k, v> berikutnya; int hash; …}Indeks peta. Entri diperoleh dengan hashing kode hash dari kunci. Ketika Anda ingin mendapatkan nilai yang sesuai dengan kunci, hitung indeksnya untuk kunci, dan kemudian keluarkan peta. Acara dalam tabel untuk mendapatkannya. Untuk detailnya, lihat kodenya:
public v get (kunci objek) {if (key == null) return getFornullKey (); Entri <k, v> entri = getEntry (key); return null == entri? null: entry.getValue ();} entri akhir <k, v> getEntry (tombol objek) {if (size == 0) {return null; } int hash = (key == null)? 0: hash (kunci); untuk (entri <k, v> e = tabel [indexfor (hash, table.length)]; e! = null; e = e.next) {objek k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e; } return null;}Dapat dilihat bahwa kode hash secara langsung mempengaruhi efisiensi fungsi hash hashmap - kode hash yang baik akan sangat mengurangi konflik hash dan meningkatkan kinerja kueri. Pada saat yang sama, ini juga menjelaskan dua pertanyaan yang diajukan pada awalnya: jika kelas kustom melakukan kunci hashmap, perhitungan kode hash harus mencakup semua bidang konstruktor, jika tidak dimungkinkan untuk mendapatkan nol.