HashMap Interenal Working

HashMap on tietorakenne, joka tallentaa tiedot (Avain, Arvo) -pareina, samanlainen kuin Dictionary pythonissa, jos olet kiinnostunut siitä!

Ymmärtääksemme Hashmapin sisäistä toimintaa, tutustutaan seuraaviin termeihin:

HASHING:
Hashing on prosessi, jossa annettu avain muunnetaan toiseksi arvoksi kaavan perusteella funktiota käyttäen. Hash-funktiota käytetään uuden arvon tuottamiseen matemaattisen algoritmin mukaisesti. Hash-funktion tulosta kutsutaan hash-arvoksi tai yksinkertaisesti hashiksi. Sitä käytetään kohteiden indeksointiin ja hakuun sekä
salausalgoritmeihin.

Todellisen hash-funktion on noudatettava tätä sääntöä –

”Hash-funktion on palautettava sama hash-koodi joka kerta, kun funktiota sovelletaan samoihin tai samankaltaisiin objekteihin. Toisin sanoen, kahden samanarvoisen objektin on tuotettava johdonmukaisesti sama hash-koodi.”

Kaikki Javan objektit perivät Object-luokassa määritellyn hashCode()-funktion oletustoteutuksen.

KOKONAISUUDET :
Pitäkää mielessä, että kaksi avainta voi tuottaa saman hash-koodin, joka voi johtaa samaan osoitteeseen. Tätä ilmiötä kutsutaan törmäykseksi.

HashMap-funktiot

1. Public V get(Object key) : eli haetaan arvo mapista avaimen perusteella.
2. Public V put(K key, V value) : eli lisätään avain , arvo pari mapiin.

Huomautus: On yleensä tarpeen ohittaa hashCode()-metodi aina, kun equals()-metodi ohitetaan, jotta säilytetään hashCode()-metodin yleinen sopimus, jonka mukaan yhtäläisillä objekteilla on oltava yhtäläiset hash-koodit.

HashMap in JAVA

Tapoja, joilla HashMap voidaan instanttisoida javassa:
1. Konstruoi tyhjän HashMapin määritetyllä alku
kapasiteetilla ja kuormituskertoimella.

public HashMap(int initialCapacity, float loadFactor)

2. Konstruoi tyhjän HashMapin määritetyllä alku
kapasiteetilla ja oletusarvoisella kuormituskertoimella (0,75).

public HashMap(int initialCapacity)

3. Konstruoi tyhjän HashMapin, jossa on oletusarvoinen alkukapasiteetti (16) ja oletuskuormituskerroin (0.75).

public HashMap()

Kuormituskerroin ja alkukapasiteetti.

HashMapin instanssilla on kaksi parametria, jotka vaikuttavat sen suorituskykyyn:
1. Alkuperäinen kapasiteetti
2. Kuormituskerroin.

Alkuperäinen kapasiteetti :
Kapasiteetti on hash-taulukon ämpäreiden lukumäärä, ja alkukapasiteetti on yksinkertaisesti kapasiteetti hash-taulukon luontihetkellä.

Load Factor:
Kuormituskerroin on mitta, kuinka täyteen hash-taulu saa täyttyä ennen kuin sen kapasiteettia lisätään automaattisesti. Kun hash-taulukon merkintöjen määrä ylittää kuormituskertoimen ja senhetkisen kapasiteetin tulon, hash-taulukko täytetään uudelleen (eli sisäiset tietorakenteet rakennetaan uudelleen) niin, että hash-taulukossa on noin kaksi kertaa enemmän ämpäreitä.

Huomautus:

Yleissääntönä voidaan sanoa, että oletusarvoinen kuormituskerroin (.75) tarjoaa hyvän kompromissin aikakustannusten ja tilakustannusten välillä. Suuremmat arvot pienentävät tilakustannuksia, mutta lisäävät hakukustannuksia (mikä näkyy useimmissa HashMap-luokan operaatioissa, mukaan lukien get ja put.

Kartan odotettavissa oleva merkintöjen määrä ja kuormituskerroin tulisi ottaa huomioon, kun asetetaan kartan alkuperäistä kapasiteettia, jotta uudelleenkäsittelyoperaatioiden määrä olisi mahdollisimman pieni. Jos alkukapasiteetti on suurempi kuin merkintöjen maksimimäärä jaettuna kuormituskertoimella, uudelleenkäsittelyoperaatioita ei koskaan tapahdu.

HashMap in Java 8

HashMap(java 8:sta) tallentaa datan useisiin singly linked list of entries tai useisiin Red BlacK Trees tai molempien sekoitukseen , riippuen kynnysarvosta, joita kutsutaan myös ämpäreiksi (buckets) tai bins.

Kaikki listat/puut rekisteröidään Entry-matriisiin (Entry<K,V>-taulukko) ja tämän sisäisen matriisin oletuskapasiteetti on 16.

Jokaista yksittäistä tietuetta tai yksittäistä avaimen ja arvon paria HashMapissa kutsutaan nimellä Entry<Key,Value>.

Entry

HashMapit käyttävät tietojen tallentamiseen sisäistä luokkaa: Entry<K,V>.
Tämä Entry on yksinkertainen avain-arvopari, jossa on kaksi lisäarvoa, jotka ovat seuraavat:

1. Viittaus toiseen Entryyn, jotta HashMap voi tallentaa merkintöjä kuten yksittäin linkitettyjä listoja tai Puuna, jossa on vasen ja oikea solmu paremman haun tarjoamiseksi.

2. Hash-arvo, joka edustaa avaimen hash-arvoa. Tämä hash-arvo tallennetaan, jotta hash-arvoa ei tarvitsisi laskea joka kerta, kun HashMap tarvitsee sitä.

Entry java 8:ssa voi olla 2 tyyppiä LinkedList Node tai RedBlack Tree Node.

*size tämän kuten edellä on käsitelty joko määritellään instantioinnin yhteydessä tai oletusarvo 16. Kuormituskertoimen perusteella se kasvaa kaksinkertaiseksi aiempaan verrattuna, jotta siihen mahtuu lisää merkintöjä.

transientti Node<K,V> taulukko; //sisältää kaikki merkinnät.

Taulukossa kukin indeksi on joko LinkedList- tai RedBlackTree-solmu.
Tietueiden hierarkia menee näin:

Map.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>

LinkedList Node:

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //LinkitetynListan ylläpitämiseen.
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

TreeNode:

HashMap, java 8:ssa , käyttää RedBlackTree:ta tietyn kynnysarvon jälkeen, joka tunnetaan nimellä TREEIFY_THRESHOLD (oletusarvo 8), koska se antaa pahimmassa tapauksessa O(log n):n aikakompleksisuuden verrattuna LinkedListiin, joka antaa haun O(n):ssa.

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // punamusta puu linkit
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // tarvitaan seuraavan linkin poistamiseen poiston yhteydessä
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

HashMap-funktioiden toiminta

1. Se tarkistaa, onko avain null vai ei . Huomaa, että HashMapissa voi olla vain yksi nolla-avain.Jos avain on nolla , niin nolla-avaimet kohdistuvat aina hashiin 0, siis taulukon indeksiin 0.
2. Jos avain ei ole nolla, metodi kutsuu hashCode()-metodia avainobjektille (käyttäjä ohittaa sen vastaavassa Key-luokassa) ja soveltaa palautettua hashValue-arvoa omaan staattiseen hash-funktioonsa löytääkseen ämpäripaikan (backing array), johon avaimet ja arvot on tallennettu sisäkkäisen luokan nimeltä Entry muodossa.
Umpio-paikka on nimittäin Entry-taulukon indeksi.

Huomautus: laskemme hash-arvon uudelleen käyttämällä hash(hashValue) -funktiota, koska se suojaa huonolaatuista hash-funktiota vastaan.

3. Lopullista hash-arvoa käytetään etsimään ämpäripaikka, johon Entry-objekti on tallennettu.
Get():n ja put():n monimutkaisuus on O(1) ,olettaen, että hash-funktio jakaa elementit oikein ämpäreiden kesken.

Huomautus: Kuten nyt tiedämme, että hash-törmäyksen sattuessa Entry-objektit tallennetaan solmuna linkitettyyn listaan ja avainten vertailuun käytetään menetelmää equals(). Tuo vertailu oikean avaimen löytämiseksi linkitetystä listasta on lineaarinen operaatio, joten pahimmassa tapauksessa monimutkaisuudesta tulee O(n).
Tämän ongelman ratkaisemiseksi Java 8:n hash-elementit käyttävät tasapainotettuja puita linkitettyjen listojen sijasta tietyn kynnysarvon saavuttamisen jälkeen. Mikä tarkoittaa, että HashMap aloittaa tallentamalla Entry-objekteja linkitettyyn listaan, mutta kun hash-elementtien määrä kasvaa yli tietyn kynnysarvon, hash muuttuu linkitetyn listan käytöstä tasapainotettuun puuhun, mikä parantaa pahimman tapauksen suorituskykyä O(n):stä O(log n):iin.

Mitä jos kahdella eri avaimella on sama hash-koodi?

4. Indeksin kohdalla meillä voi olla useampia arvoja, koska hash:issa voi esiintyä törmäyksiä. Selvittääksemme, kumpaa tarvitsemme, HashMap käyttää apuna equals()-metodia.

Ratkaisu, equals()-metodi tulee apuun. Koska ämpäri on yksi ja meillä on kaksi objektia, joilla on sama hash-koodi .

Siten avaimen indeksin hakemisen jälkeen se hakee ensimmäisen solmun, joka on kyseisessä indeksissä. Ensimmäistä solmua verrataan sitten avaimeen käyttäen equals(), Jos tämä on haluttu solmu ,se palauttaa arvon suoraan täältä.
Muussa tapauksessa se selvittää Noden instanssin selvittääkseen, onko tähän indeksiin tallennettu sisältävä data linkitetyn listan tai RedBlack-puun muodossa.

Kun se on selvinnyt,käymme läpi linkitetyn listan tai puun , vertailemalla avaimia kussakin merkinnöissä käyttäen keys.equals() kunnes se palauttaa true. Sitten palautetaan vastaava entry-objekti Value .

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab; //esittää Array of Entry
Node<K,V> first, e;
int n; K k;

/* Tarkistetaan, onko taulukossa entryjä .*/
/* Myös indeksin etsiminen edellisissä vaiheissa lasketun hashin perusteella, jossa merkintä on tallennettu joko listana tai puun solmuna.*/

if ((tab = taulukko) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Ensimmäisen solmun nouto hakeminen hashin perusteella saatuun indeksiin.*/
if (first.hash == hash && /* Tarkistetaan aina ensimmäinen solmu*/
((k = first.key) == key||| (key != null && key.equals(k))))
palauta first;

/*Jos tuon indeksin ensimmäisenä solmuna ei ole etsimäämme arvoa ,mennään läpi.*/
if ((e = first.next) != null) {
if (first instance of TreeNode)
/*Nouto punamustasta puusta, jos aloitussolmu indeksillä if of TreeNode .*/

return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {

/*Nouto LinkedLististä, jos aloitussolmu on tyyppiä Node eikä Tree.*/

if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
while ((e = e.next) != null);
}}
return null;
}

PUT:

1. Se tarkistaa, että onko avain nolla vai ei .Jos avain on nolla , niin nolla avaimet aina mapata hash 0, siis indeksi 0 taulukon.
2. Jos avain ei ole nolla, metodi kutsuu hashCode()-metodia avain-objektin (Overriden käyttäjän toimesta vastaavassa Key-luokassa) ja soveltaa palautettua hashValue omaan staattiseen hash-funktioonsa löytääkseen ämpäripaikan (backing array), johon avaimet ja arvot tallennetaan sisäkkäisen luokan muodossa nimeltään Entry.Kauhan sijainti on Entryn indeksi eli taulukko.
3. Lopullista hash-arvoa käytetään etsimään kauhan sijainti, johon Entry-objekti on tallennettava. Tämän jälkeen avaimet käydään läpi samalla tavalla kuin get():ssa on kuvattu, jotta voidaan tarkistaa, onko avain jo olemassa, jos se on olemassa, arvo korvataan uudella arvolla.
Ellei, listan koko tarkistetaan,
Jos se ylittää TREEIFY_THRESHOLD(oletus 8), solmut järjestetään uudelleen RedBlackTree:ksi ja uusi avain tallennetaan siihen sisältyvällä arvolla.
Jos kynnysarvoa ei ylitetä, uusi Entry luodaan vastaavalla avain-arvolla ja tallennetaan.

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = taulukko) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*Tarkistetaan, onko TREEIFY_THRESHOLD ylitetty vai ei.*/

if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 for 1st*/
treeifyBin(tab, hash);
break;}

if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}}

if (e != null) { /* olemassa oleva kartoitus avaimelle*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}}

++modCount;

if (++size > kynnysarvo)
resize();
afterNodeInsertion(evict);
return null;}