Bagaimana cara kerja HashMap di Java

Sebagian besar dari Anda pasti setuju bahwa HashMaphari ini adalah topik paling favorit untuk didiskusikan saat wawancara. Kadang-kadang saya melakukan diskusi serupa dengan rekan-rekan saya dan itu sangat membantu. Sekarang saya akan berdiskusi dengan Anda. Saya berasumsi jika Anda tertarik dengan internal dan cara kerja HashMap, maka Anda sudah familiar dengan dasar-dasar HashMap , jadi saya akan melewatkan bagian itu. Namun jika Anda baru dalam hal ini, saya sarankan Anda mengunjungi situs Java Docs . Sebelum kita melanjutkan, saya sangat menyarankan Anda membaca artikel saya sebelumnya: Bekerja dengan kode hash dan metode yang sama di Java. Isi artikel ini:

1. Satu-satunya jawaban yang mungkin.
2. Apa itu Hashing.
3. Sedikit tentang kelas Entry.
4. Apa yang dimaksud dengan put().
5. Bagaimana metode ini bekerja get().
6. Catatan

Satu-satunya jawaban yang mungkin

Jika ada yang meminta saya menjelaskan " Bagaimana cara kerja HashMap?" ", Saya hanya akan menjawab:" Sesuai dengan prinsip Hashing ." Ini sangat sederhana. Untuk memahami hal ini dan mendapatkan jawaban yang lebih luas, Anda harus yakin bahwa Anda mengetahui dasar-dasar Hashing. Benar?

Apa itu Hashing

Hashing dalam bentuknya yang paling sederhana adalah cara mengubah variabel/objek apa pun menjadi kode unik setelah menerapkan rumus/algoritma apa pun ke propertinya. Fungsi hash yang sebenarnya harus mengikuti aturan berikut: Fungsi hash harus mengembalikan kode hash yang sama setiap kali diterapkan pada objek yang sama atau setara. Dengan kata lain, dua objek identik harus mengembalikan kode hash yang sama secara bergantian. Anda dapat membaca lebih lanjut tentang ini di sini: Bekerja dengan kode hash dan metode yang sama di Java

Sedikit tentang kelas Entry

Menurut definisi, peta adalah “objek yang menyimpan nilai dan kunci secara berpasangan.” Cukup sederhana, bukan? Jadi, di HashMap pasti ada semacam mekanisme yang menyimpan pasangan Values ​​dan Keys? Jawaban - Ya. HashMapmemiliki kelas dalam Entryyang terlihat seperti ini:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

Secara alami, kelas Entrymemiliki Kunci dan Nilai yang disimpan sebagai atribut. Kuncinya ditandai sebagai finaldan kita juga melihat dua bidang tambahan: nextdan hash. Kami akan mencoba memahami tujuan bidang ini seiring berjalannya artikel.

Apa yang dilakukan metode Java put()?

Sebelum kita mendalami implementasi metode ini put(), sangat penting untuk memahami bahwa instance suatu kelas Entrydisimpan dalam array. Kelas HashMap mendefinisikan variabel ini sebagai:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Sekarang lihat kode implementasi metode put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

Mari kita lihat langkah demi langkah:

• Pertama-tama, kami memeriksa apakah kuncinya ada. Jika kunci tidak ada ( null), nilai ditempatkan pada tabel pada posisi nol karena kode hash untuk nilai tersebut adalah null, это – всегда 0.


• Pada langkah berikutnya, nilai hash dihitung menggunakan kode hash dari kunci yang diperoleh dengan memanggil metode tersebut hashCode(). Nilai hash ini digunakan untuk menghitung posisi dalam array dimana objek akan ditempatkan Entry. Perancang JDK berasumsi bahwa fungsi yang ditulis dengan buruk hashCode()dapat mengembalikan nilai hash yang terlalu tinggi atau terlalu rendah. Untuk mengatasi masalah ini, mereka memperkenalkan hash()fungsi lain dan meneruskan nilai hash suatu objek ke dalamnya untuk membuat nilai hash sesuai dengan ukuran array.


• Sekarang fungsi tersebut dipanggil indexFor(hash, table.length)untuk menghitung posisi pasti dimana objek akan ditempatkan Entry.


• Di sinilah bagian utama dimulai. Sekarang, berdasarkan apa yang kita ketahui bahwa - dua objek yang tidak sama dapat memiliki kode hash yang sama, kita mengajukan pertanyaan: Akankah dua objek berbeda ditempatkan pada posisi yang sama dalam array [bucket]? Jawabannya adalah LinkedList. Jika Anda ingat, kelas tersebut Entrymemiliki atribut " next". Atribut ini selalu menunjuk ke objek berikutnya dalam rantai. Inilah tepatnya perilakunya LinkedList.

Jadi, benda Entrydisimpan dalam bentuk LinkedList. Ketika suatu objek Entryakan ditempatkan di lokasi tertentu, HashMap memeriksa apakah sudah ada entri di lokasi tersebut. Jika tidak ada entri, maka benda ditempatkan pada posisi ini. Namun, jika sudah ada objek pada posisi ini, atribut berikutnya akan dicentang. Jika ia kembali nulldan objek saat ini Entrymenjadi tautan berikutnya di file LinkedList. Jika variabel berikutnya tidak null, prosedur diulangi untuk variabel berikutnya sampai ditemukan null. Bagaimana jika kita meletakkan objek lain dengan nilai berbeda tetapi dengan kunci yang sama seperti sebelumnya? Logikanya ini akan mengakibatkan nilai lama diganti. Bagaimana ini bisa terjadi? Secara umum, setelah menentukan posisi suatu objek Entry, saat melintasi LinkedListke posisi terhitung, HashMapmetode perbandingan kunci akan dipanggil untuk setiap objek Entry. Semua Entryobjek ini LinkedListmungkin memiliki kode hash yang serupa, namun metode ini equals()akan memeriksa kesamaan sebenarnya. Ini hanya akan menggantikan nilai di dalam Entry. Dengan demikian, HashMap menjamin keunikan semua kunci.

Bagaimana cara kerja metode get() Java?

Sekarang kita memiliki gambaran tentang bagaimana pasangan nilai kunci disimpan di HashMap. Pertanyaan besar berikutnya adalah: Apa yang terjadi ketika sebuah objek diteruskan dari HashMap ke suatu metode get()? Bagaimana nilai suatu benda ditentukan? Kita seharusnya sudah mengetahui jawabannya, karena cara penentuan keunikan suatu kunci dalam suatu metode put()memiliki logika yang sama dengan yang diterapkan oleh metode tersebut get(). Setelah HashMapmenentukan kunci objek yang diteruskan sebagai argumen, ia hanya mengembalikan nilai yang sesuai Entry. Jika tidak ditemukan kecocokan, metode get()akan kembali null. Mari kita lihat kodenya:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

Kode di atas mirip dengan metode put()sampai saat ini if (e.hash == hash && ((k = e.key) == key || key.equals(k))), setelah itu hanya mengembalikan nilai objek.

Catatan

• Struktur data yang akan disimpan dalam suatu objek Entryadalah array dengan nama tabledan tipe Entry.
• Setiap posisi individu dalam array disebut bucket karena dapat berisi elemen pertama LinkedListdari objek Entry.
• hashCode()Kuncinya diperlukan untuk menghitung posisi benda Entry.
• equals()Kuncinya digunakan untuk memeriksa keunikan kunci di peta ( map).
• hashCode()dan equals()Nilai tidak digunakan dalam metode get()dan set()dalam HashMap.
• Kode hash untuk kunci dengan nilai nullselalu 0. Dan objek seperti itu Entryakan selalu disimpan di posisi nol dalam array.

Saya harap saya menyampaikan pemikiran saya dengan benar di artikel ini. Jika Anda menemukan kesalahan atau memiliki pertanyaan, silakan tinggalkan di komentar. Selamat belajar!