Bagaimanakah HashMap berfungsi dalam Java

Kebanyakan anda akan bersetuju bahawa HashMaphari ini, adalah topik yang paling digemari untuk perbincangan semasa temu duga. Kadang-kadang saya mengadakan perbincangan yang sama dengan rakan sekerja saya dan ia sangat membantu. Sekarang saya akan mengadakan perbincangan sedemikian dengan anda. Saya menganggap bahawa jika anda berminat dengan dalaman dan cara kerja HashMap, maka anda sudah biasa dengan asas HashMap , jadi saya akan melangkau bahagian itu. Tetapi jika anda baharu dalam hal ini, saya cadangkan anda pergi ke tapak Java Docs . Sebelum kita meneruskan, saya sangat mengesyorkan anda menyemak artikel saya sebelum ini: Bekerja dengan hashCode dan kaedah yang sama dalam Java. Kandungan artikel ini:

1. Satu-satunya jawapan yang mungkin.
2. Apa itu Hashing.
3. Sedikit tentang kelas Entry.
4. Apa yang put().
5. Bagaimana kaedah itu berfungsi get().
6. Nota

Satu-satunya jawapan yang mungkin

Jika sesiapa meminta saya menerangkan " Bagaimanakah HashMap berfungsi?" ", saya hanya akan menjawab: " Mengikut prinsip Hashing ." Ia tidak boleh menjadi lebih mudah. Untuk memahami perkara ini dan mendapatkan jawapan lanjutan, anda perlu memastikan anda mengetahui asas Hashing. Betul ke?

Apa itu Hashing

Hashing dalam bentuk termudah ialah cara menukar mana-mana pembolehubah/objek kepada kod unik selepas menggunakan sebarang formula/algoritma pada sifatnya. Fungsi cincang benar mesti mengikut peraturan berikut: Fungsi cincang mesti mengembalikan kod cincang yang sama apabila ia digunakan pada objek yang sama atau sama. Dalam erti kata lain, dua objek yang sama mesti mengembalikan kod cincang yang sama pada gilirannya. Anda boleh membaca lebih lanjut tentang ini di sini: Bekerja dengan hashCode dan kaedah sama dalam Java

Sedikit tentang kelas Kemasukan

Mengikut definisi, peta ialah "objek yang menyimpan nilai dan kunci secara berpasangan." Cukup mudah, bukan? Jadi, mesti ada beberapa jenis mekanisme dalam HashMap yang menyimpan pasangan Nilai dan Kunci? Jawapan - Ya. HashMapmempunyai kelas dalaman Entryyang kelihatan seperti ini:

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

Sememangnya, kelas Entrymempunyai Kunci dan Nilai yang disimpan sebagai atribut. Kunci ditandakan sebagai finaldan kami juga melihat dua medan tambahan: nextdan hash. Kami akan cuba memahami tujuan medan ini semasa artikel berlangsung.

Apakah yang dilakukan oleh kaedah Java put()?

Sebelum kita menyelami pelaksanaan kaedah put(), adalah sangat penting untuk memahami bahawa kejadian kelas Entrydisimpan dalam tatasusunan. Kelas HashMap mentakrifkan pembolehubah ini sebagai:

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

Sekarang lihat kod pelaksanaan kaedah 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 fikirkan langkah demi langkah:

• Pertama sekali, kami menyemak sama ada kunci itu wujud. Jika kunci tidak wujud ( null), nilai diletakkan dalam jadual pada kedudukan sifar kerana kod cincang untuk nilai ialah null, это – всегда 0.


• Dalam langkah seterusnya, nilai cincang dikira menggunakan kod cincang kunci yang diperoleh dengan memanggil kaedah hashCode(). Nilai cincang ini digunakan untuk mengira kedudukan dalam tatasusunan di mana objek akan diletakkan Entry. Pereka JDK mengandaikan bahawa fungsi bertulis yang buruk hashCode()boleh mengembalikan nilai cincang yang terlalu tinggi atau terlalu rendah. Untuk menyelesaikan masalah ini, mereka memperkenalkan hash()fungsi lain dan menghantar nilai cincang objek ke dalamnya untuk menjadikan nilai cincang sepadan dengan saiz tatasusunan.


• Sekarang fungsi dipanggil indexFor(hash, table.length)untuk mengira kedudukan tepat di mana objek akan diletakkan Entry.


• Di sinilah bahagian utama bermula. Sekarang, berdasarkan apa yang kita tahu bahawa dua objek yang tidak sama boleh mempunyai kod cincang yang sama, kita bertanya soalan: Adakah dua objek berbeza akan diletakkan pada kedudukan yang sama dalam tatasusunan [baldi]? Jawapannya ialah LinkedList. Jika anda masih ingat, kelas Entrymempunyai atribut " next". Atribut ini sentiasa menunjuk ke objek seterusnya dalam rantai. Beginilah perangainya LinkedList.

Jadi, objek Entrydisimpan dalam bentuk LinkedList. Apabila objek Entryhendak diletakkan di lokasi tertentu, HashMap menyemak untuk melihat sama ada sudah ada entri di lokasi tersebut. Jika tiada kemasukan, maka objek diletakkan pada kedudukan ini. Jika, walau bagaimanapun, sudah ada objek pada kedudukan ini, atribut seterusnya ditandakan. Jika ia kembali nulldan objek semasa Entrymenjadi pautan seterusnya dalam LinkedList. Jika pembolehubah seterusnya tidak null, prosedur diulang untuk pembolehubah seterusnya sehingga ia menemui null. Bagaimana jika kita meletakkan objek lain dengan nilai yang berbeza tetapi dengan kunci yang sama seperti sebelumnya? Secara logiknya ini sepatutnya menyebabkan nilai lama diganti. Bagaimana ini berlaku? Secara umum, selepas menentukan kedudukan objek Entry, semasa merentasi LinkedListke kedudukan yang dikira, HashMapia memanggil kaedah perbandingan utama untuk setiap objek Entry. Semua Entryobjek ini LinkedListmungkin mempunyai kod cincang yang serupa, tetapi kaedah itu equals()akan menyemak persamaan sebenar. Ini hanya akan menggantikan nilai dalam Entry. Oleh itu, HashMap menjamin keunikan semua kunci.

Bagaimanakah kaedah Java get() berfungsi?

Sekarang kita mempunyai idea tentang cara pasangan nilai kunci disimpan dalam HashMap. Soalan besar seterusnya ialah: Apa yang berlaku apabila objek dihantar dari HashMap ke kaedah get()? Bagaimanakah nilai sesuatu objek ditentukan? Kita sepatutnya sudah tahu jawapannya, kerana cara keunikan sesuatu kunci ditentukan dalam kaedah put()mempunyai logik yang sama dengan kaedah yang digunakan get(). Sebaik sahaja HashMapia menentukan kunci objek yang diluluskan sebagai hujah, ia hanya mengembalikan nilai Entry. Jika tiada padanan ditemui, kaedah get()akan kembali null. Mari kita lihat kod:

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;
}

Kod di atas adalah serupa dengan kaedah put()sehingga ke tahap ini if (e.hash == hash && ((k = e.key) == key || key.equals(k))). Selepas itu ia hanya mengembalikan nilai objek.

Nota

• Struktur data yang akan disimpan dalam objek Entryialah tatasusunan dengan nama tabledan jenis Entry.
• Setiap kedudukan individu dalam tatasusunan dipanggil baldi kerana ia boleh mengandungi elemen pertama LinkedListobjek Entry.
• hashCode()Kunci diperlukan untuk mengira kedudukan objek Entry.
• equals()Kekunci digunakan untuk menyemak keunikan kunci dalam peta( map).
• hashCode()dan equals()Nilai tidak digunakan dalam kaedah get()dan set()dalam HashMap.
• Kod cincang untuk kunci dengan nilai nullsentiasa 0. Dan objek sedemikian Entryakan sentiasa disimpan dalam kedudukan sifar tatasusunan.

Saya harap saya menyampaikan fikiran saya dengan betul dalam artikel ini. Jika anda mendapati ralat atau mempunyai soalan, sila tinggalkan mereka dalam ulasan. Selamat belajar!