Paano gumagana ang HashMap sa Java

Karamihan sa inyo ay sasang-ayon na HashMap, ngayon, ang pinakapaboritong paksa para sa talakayan sa panahon ng mga panayam. Minsan nagkaroon ako ng mga katulad na talakayan sa aking mga kasamahan at talagang nakatulong ito. Ngayon ay magkakaroon ako ng ganoong talakayan sa iyo. Ipinapalagay ko na kung interesado ka sa mga panloob at gawain ng HashMap, alam mo na ang mga pangunahing kaalaman ng HashMap , kaya laktawan ko ang bahaging iyon. Ngunit kung bago ka dito, iminumungkahi kong magtungo ka sa site ng Java Docs . Bago tayo magpatuloy, lubos kong inirerekumenda na tingnan mo ang aking nakaraang artikulo: Paggawa gamit ang hashCode at ang katumbas na pamamaraan sa Java. Mga nilalaman ng artikulong ito:

1. Ang tanging posibleng sagot.
2. Ano ang Hashing.
3. Medyo tungkol sa klase Entry.
4. Ano ang ginagawa ng put().
5. Paano gumagana ang pamamaraan get().
6. Mga Tala

Ang tanging posibleng sagot

Kung may humihiling sa akin na ipaliwanag " Paano gumagana ang HashMap?" ", Sasagot lang ako: " Ayon sa mga prinsipyo ng Hashing ." Hindi ito maaaring maging mas simple. Upang maunawaan ito at makakuha ng pinahabang sagot, kailangan mong tiyaking alam mo ang mga pangunahing kaalaman sa Hashing. tama?

Ano ang Hashing

Ang pag-hash sa pinakasimpleng anyo nito ay isang paraan ng pag-convert ng anumang variable/object sa isang natatanging code pagkatapos maglapat ng anumang formula/algorithm sa kanilang mga katangian. Ang isang tunay na hash function ay dapat sumunod sa sumusunod na panuntunan: Ang isang hash function ay dapat magbalik ng parehong hash code sa tuwing ito ay inilapat sa pareho o pantay na mga bagay. Sa madaling salita, dapat ibalik ng dalawang magkaparehong bagay ang parehong mga hash code. Maaari kang magbasa ng higit pa tungkol dito: Paggawa gamit ang hashCode at katumbas na pamamaraan sa Java

Medyo tungkol sa Entry class

Sa pamamagitan ng kahulugan, ang mapa ay "isang bagay na nag-iimbak ng mga halaga at susi nang magkapares." Medyo simple, tama? Kaya, dapat mayroong ilang uri ng mekanismo sa HashMap na nag-iimbak ng mga pares ng Mga Halaga at Susi? Sagot - Oo. HashMapay may panloob na klase Entryna ganito ang hitsura:

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

Naturally, ang klase Entryay may Key at Value na nakaimbak bilang mga katangian. Ang susi ay minarkahan bilang finalat nakikita rin namin ang dalawang karagdagang field: nextat hash. Susubukan naming maunawaan ang layunin ng mga larangang ito habang umuusad ang artikulo.

Ano ang ginagawa ng Java put() method?

Bago tayo sumisid sa pagpapatupad ng method put(), napakahalagang maunawaan na ang mga instance ng isang klase Entryay nakaimbak sa isang array. Tinutukoy ng klase ng HashMap ang variable na ito bilang:

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

Ngayon tingnan ang code ng pagpapatupad ng pamamaraan 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;
}

Alamin natin ito nang hakbang-hakbang:

• Una sa lahat, sinusuri namin kung umiiral ang susi. Kung ang susi ay hindi umiiral ( null), ang halaga ay inilalagay sa talahanayan sa posisyong zero dahil ang hash code para sa halaga ay null, это – всегда 0.


• Sa susunod na hakbang, ang halaga ng hash ay kinakalkula gamit ang hash code ng key na nakuha sa pamamagitan ng pagtawag sa pamamaraan hashCode(). Ang hash value na ito ay ginagamit upang kalkulahin ang posisyon sa array kung saan ilalagay ang object Entry. Ipinapalagay ng mga taga-disenyo ng JDK na ang isang hindi magandang nakasulat na function hashCode()ay maaaring magbalik ng hash value na masyadong mataas o masyadong mababa. Upang malutas ang problemang ito, nagpakilala sila ng isa pang hash()function at ipinasa dito ang hash value ng isang bagay upang gawing tumugma ang hash value sa laki ng array.


• Ngayon ang function ay tinatawag indexFor(hash, table.length)upang kalkulahin ang eksaktong posisyon kung saan ang bagay ay ilalagay Entry.


• Dito nagsisimula ang pangunahing bahagi. Ngayon, batay sa kung ano ang alam namin na - dalawang hindi pantay na mga bagay ay maaaring magkaroon ng pantay na hash code, itatanong namin ang tanong: Ang dalawang magkaibang mga bagay ay ilalagay sa parehong posisyon sa [bucket] array? Ang sagot ay LinkedList. Kung naaalala mo, ang klase Entryay may katangian na " next". Palaging tumuturo ang katangiang ito sa susunod na bagay sa chain. Ganito talaga ang ugali LinkedList.

Kaya, ang mga bagay Entryay naka-imbak sa form LinkedList. Kapag ang isang bagay Entryay ilalagay sa isang partikular na lokasyon, ang HashMap ay tumitingin upang makita kung mayroon nang entry sa lokasyong iyon. Kung walang entry, kung gayon ang bagay ay inilalagay sa posisyong ito. Kung, gayunpaman, mayroon nang isang bagay sa posisyong ito, ang susunod na katangian ay susuriin. Kung ito ay bumalik nullat ang kasalukuyang bagay Entryay magiging susunod na link sa LinkedList. Kung ang susunod na variable ay hindi null, ang pamamaraan ay paulit-ulit para sa susunod na isa hanggang sa ito ay mahanap null. Paano kung maglagay tayo ng isa pang bagay na may ibang halaga ngunit may parehong susi tulad ng dati? Sa lohikal na paraan, dapat itong magresulta sa pagpapalit ng lumang halaga. Paano ito nangyayari? Sa pangkalahatan, pagkatapos matukoy ang posisyon ng isang bagay Entry, habang binabagtas LinkedListang kinakalkula na posisyon, HashMaptinatawag nito ang key compare method para sa bawat object Entry. Ang lahat ng Entrymga bagay na ito LinkedListay maaaring may magkatulad na hash code, ngunit equals()susuriin ng pamamaraan ang tunay na pagkakapareho. Papalitan lamang nito ang halaga sa loob ng Entry. Kaya, ginagarantiyahan ng HashMap ang pagiging natatangi ng lahat ng mga susi.

Paano gumagana ang Java get() method?

Ngayon ay mayroon na tayong ideya kung paano iniimbak ang mga pares ng key-value sa HashMap. Ang susunod na malaking tanong ay: Ano ang mangyayari kapag ang isang bagay ay naipasa mula sa isang HashMap patungo sa isang pamamaraan get()? Paano natutukoy ang halaga ng isang bagay? Dapat na alam na natin ang sagot, dahil ang paraan kung saan natutukoy ang pagiging natatangi ng isang susi sa pamamaraan put()ay may parehong lohika na nalalapat sa pamamaraan get(). Kapag HashMapnatukoy na nito ang susi ng bagay na ipinasa bilang argumento, ibinabalik lamang nito ang halaga ng katumbas na Entry. Kung walang mahanap na tugma, get()babalik ang paraan null. Tingnan natin ang code:

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

Ang code sa itaas ay katulad ng pamamaraan put()hanggang sa puntong ito if (e.hash == hash && ((k = e.key) == key || key.equals(k))). Pagkatapos nito ay ibinabalik lamang nito ang halaga ng bagay.

Mga Tala

• Ang istraktura ng data na maiimbak sa isang bagay Entryay isang array na may pangalan tableat isang uri Entry.
• Ang bawat indibidwal na posisyon sa array ay tinatawag na bucket dahil maaari itong maglaman ng unang elemento LinkedListng mga bagay Entry.
• hashCode()Ang susi ay kinakailangan upang makalkula ang posisyon ng bagay Entry.
• equals()Ang susi ay ginagamit upang suriin ang pagiging natatangi ng susi sa mapa( map).
• hashCode()at equals()Ang mga halaga ay hindi ginagamit sa mga pamamaraan get()at set()sa HashMap.
• Ang hash code para sa mga key na may value nullay palaging 0. At ang naturang object Entryay palaging iimbak sa zero na posisyon ng array.

Sana naihatid ko nang tama ang aking mga saloobin sa artikulong ito. Kung makakita ka ng mga error o may mga tanong, mangyaring iwanan ang mga ito sa mga komento. Maligayang pag-aaral!