HashMap Interenal Working

A HashMap egy olyan adatstruktúra, amely az adatokat (Key, Value) párokban tárolja, hasonlóan a Dictionary-hez pythonban, ha érdekel!

A Hashmap belső működésének megértéséhez ismerkedjünk meg a következő fogalmakkal:

HASHING:
Hashing az a folyamat, amikor egy adott kulcsot egy képlet alapján egy függvény segítségével egy másik értékké alakítunk. A hash-függvényt arra használjuk, hogy egy matematikai algoritmus alapján létrehozzuk az új értéket. A hash-függvény eredményét hash-értéknek vagy egyszerűen hash-nek nevezzük. Ezt használják az elemek indexelésére és visszakeresésére, valamint
titkosítási algoritmusokhoz.

Egy valódi hash-függvénynek ezt a szabályt kell követnie –

“A hash-függvénynek minden egyes alkalommal ugyanazt a hash-kódot kell visszaadnia, amikor a függvényt azonos vagy egyenlő objektumokra alkalmazzák. Más szóval, két egyenlő objektumnak következetesen ugyanazt a hash-kódot kell produkálnia.”

A Java-ban minden objektum örökli az Object osztályban definiált hashCode() függvény alapértelmezett implementációját.

COLLISIONS :
Ne feledjük, hogy két kulcs ugyanazt a hash-t generálhatja, ami ugyanahhoz a címhez vezethet. Ezt a jelenséget ütközésnek nevezzük.

HashMap függvények

1. Public V get(Object key) : azaz a kulcs alapján egy érték lekérdezése a leképezésből.
2. Public V put(K key, V value) : azaz egy kulcs , érték pár beszúrása a leképezésbe.

Megjegyzés: Általában szükséges a hashCode() metódus felülírása minden alkalommal, amikor az equals() metódus felülírása történik, hogy a hashCode() metódusra vonatkozó általános szerződést fenntartsuk, amely szerint az egyenlő objektumoknak egyenlő hash-kódokkal kell rendelkezniük.

HashMap in JAVA

Ways to instantiate a HashMap in java:
1. Konstruál egy üres HashMapot a megadott kezdeti
kapacitással és terhelési tényezővel.

public HashMap(int initialCapacity, float loadFactor)

2. Konstruál egy üres HashMapot a megadott kezdeti
kapacitással és az alapértelmezett terhelési tényezővel (0,75).

public HashMap(int initialCapacity)

3. Üres HashMapot konstruál az alapértelmezett kezdeti kapacitással (16) és az alapértelmezett terhelési tényezővel (0.75).

public HashMap()

Load Factor and Initial Capacity.

A HashMap példányának két paramétere van, amelyek befolyásolják a teljesítményét:
1. Kezdeti kapacitás
2. Terhelési tényező.

Kezdeti kapacitás :
A kapacitás a hash-táblában lévő vödrök száma, a kezdeti kapacitás pedig egyszerűen a hash-tábla létrehozásakor meglévő kapacitás.

Leterhelési tényező:
A terhelési tényező azt méri, hogy a hash-tábla mennyire telhet meg, mielőtt a kapacitása automatikusan megnő. Amikor a hash-táblában lévő bejegyzések száma meghaladja a terhelési tényező és az aktuális kapacitás szorzatát, a hash-tábla újratöltődik (azaz a belső adatstruktúrák újjáépülnek), így a hash-tábla körülbelül kétszer annyi vödörrel rendelkezik.

MEGJEGYZÉS:

Az alapértelmezett terhelési tényező (.75) általános szabályként jó kompromisszumot kínál az idő- és helyköltségek között. A magasabb értékek csökkentik a helyterhelést, de növelik a keresési költségeket (ami a HashMap osztály legtöbb műveletében tükröződik, beleértve a get és put műveleteket is.

A kezdeti kapacitás beállításakor figyelembe kell venni a map várható bejegyzésszámát és a terhelési tényezőt, hogy minimalizáljuk az újrakeresési műveletek számát. Ha a kezdeti kapacitás nagyobb, mint a bejegyzések maximális száma osztva a terhelési tényezővel, akkor soha nem kerül sor rehash műveletekre.

HashMap in Java 8

A HashMap(a java 8-tól) az adatokat több bejegyzésből álló singly linked listába vagy több Red BlacK Trees-be vagy a kettő keverékébe tárolja , a küszöbértéktől függően, más néven bucket vagy bins.

Az összes listát/fát egy Entry tömbben (Entry<K,V> táblázat) regisztráljuk, és ennek a belső tömbnek az alapértelmezett kapacitása 16.

Egy HashMapban minden egyes rekordot vagy a Kulcs és érték egyetlen párját Entry<Key,Value>-nak nevezzük.

Entry

A HashMapok egy belső osztályt használnak az adatok tárolására: az Entry<K,V>-t. A HashMapok egy belső osztályt használnak.
Ez a bejegyzés egy egyszerű kulcs-érték pár két további értékkel, amelyek a következők:

1. Hivatkozás egy másik Entry-re, így a HashMap a bejegyzéseket úgy tárolhatja, mint egyenként összekapcsolt listákat, vagy mint Tree-t bal és jobb csomópontokkal a jobb keresés biztosítása érdekében.

2. Egy hash-érték, amely a kulcs hash-értékét képviseli. Ezt a hash-értéket azért tároljuk, hogy elkerüljük a hash kiszámítását minden alkalommal, amikor a HashMap-nek szüksége van rá.

A bejegyzés a java 8-ban 2 típusú LinkedList Node vagy RedBlack Tree Node lehet.

*mérete a fent tárgyaltak szerint vagy a példányosítás során kerül meghatározásra, vagy alapértelmezett 16-os. A terhelési tényező alapján a korábbi méret kétszeresére nő, hogy további bejegyzéseket tudjon befogadni.

tranzitív Node<K,V> táblázat; //tartalmazza az összes bejegyzést.

A táblázatban minden index vagy egy LinkedList vagy egy RedBlackTree Node-ja.
A bejegyzés hierarchiája így néz ki:

Térkép.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; //egy LinkedList fenntartásához.
Node(int hash, K kulcs, V érték, Node<K,V> next) {
this.hash = hash;
this.key = kulcs;
this.value = érték;
this.next = next;
}

TreeNode:

HashMap, a java 8-ban , bizonyos TREEIFY_THRESHOLD(alapértelmezett érték 8) néven ismert küszöbérték után RedBlackTree-t használ, mivel a legrosszabb esetben O(log n) időbonyolultságot ad, szemben a LinkedListtel, amely O(n) alatt adja a keresést.

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // szükséges, hogy törléskor feloldjuk a következő hivatkozását
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

HashMap függvények működése

1. Ellenőrzi, hogy a kulcs null-e vagy sem . Megjegyezzük, hogy a HashMapban csak egy null kulcs lehet.Ha a kulcs null , akkor a null kulcsok mindig a hash 0-hoz, tehát a táblázat 0 indexéhez tartoznak.
2. Ha a kulcs nem null, akkor a módszer meghívja a hashCode() metódust a kulcsobjektumon (a felhasználó felülírja a megfelelő kulcsosztályban), és a visszaadott hashValue-t a saját statikus hash függvényére alkalmazza, hogy megtalálja a vödör helyét (háttértömb), ahol a kulcsok és értékek tárolódnak egy Entry nevű, egymásba ágyazott osztály formájában.
A vödör helye az Entry táblázat indexe.

MEGJEGYZÉS: a hash értéket ismét a hash(hashValue) segítségével számítjuk ki, mivel ez véd a rossz minőségű hash függvény ellen.

3. A végső hash értéket arra használjuk, hogy megtaláljuk azt a vödörhelyet, ahol az Entry objektum tárolódik.
A get() és put() bonyolultsága O(1) ,feltételezve, hogy a hash függvény megfelelően eloszlatja az elemeket a vödrök között.

Megjegyzés: Mivel most már tudjuk, hogy hash ütközés esetén a entry objektumok egy csomópontként vannak tárolva egy linkelt listában és az equals() módszert használjuk a kulcsok összehasonlítására. Ez az összehasonlítás a helyes kulcs megtalálására egy összekapcsolt listában lineáris művelet, így legrosszabb esetben a komplexitás O(n) lesz.
A probléma megoldására a Java 8 hash-elemek egy bizonyos küszöbérték elérése után összekapcsolt listák helyett kiegyensúlyozott fákat használnak. Ami azt jelenti, hogy a HashMap úgy indul, hogy az Entry objektumokat linkelt listában tárolja, de miután a hash elemeinek száma nagyobb lesz egy bizonyos küszöbértéknél, a hash átvált linkelt lista használatáról kiegyensúlyozott fára, ami a legrosszabb esetben a teljesítményt O(n)-ről O(log n)-re javítja.

Mi van akkor, ha két különböző kulcsnak ugyanaz a hashkódja?

4. Egy indexnél több érték is lehet, mivel a hashelésben ütközések lehetnek. Ahhoz, hogy kitaláljuk, melyikre van szükségünk, a HashMap az equals() segítségét veszi igénybe.

A megoldás, az equals() metódus jön a segítségünkre. Mivel a bucket egy, és két azonos hash kódú objektumunk van .

A kulcs indexének lekérdezése után tehát lekérdezi az indexen lévő első csomópontot. Az első csomópontot ezután összehasonlítja a kulccsal az equals() segítségével, Ha ez a kívánt csomópont ,közvetlenül innen adja vissza az értéket.
Első esetben kideríti a Node példányát, hogy kiderítse, hogy az ebben az indexben tárolt, tartalmazó adatok linkelt lista vagy RedBlack fa formátumban vannak-e.

Amikor ezt kiderítettük,végigjárjuk a LinkedList-et vagy a Tree-t , összehasonlítva a kulcsokat minden egyes bejegyzésben a keys.equals() segítségével, amíg igazat nem ad vissza. Ezután a megfelelő bejegyzés objektum értékét adjuk vissza .

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; //reprezentálja a bejegyzés tömbjét
Node<K,V> first, e;
int n; K k;

/* Annak ellenőrzése, hogy a táblázatban vannak-e bejegyzések .*/
/* Továbbá az index megtalálása az előző lépésekben kiszámított hash alapján, ahol a bejegyzés vagy listaként vagy facsomóként van tárolva.*/

if ((tab = táblázat) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*A hash alapján kapott index első csomópontjának lekérése.*/
if (first.hash == hash && /*mindig az első csomópont ellenőrzése*/
((k = first.key) == key||(key != null && key.equals(k))))
return first;

/*Ha az index első csomópontja nem a keresett érték ,akkor megy a traversing.*/
if ((e = first.next) != null) {
if (first instance of TreeNode)
/*Fetching from Red Black Tree if starting Node on the index if of TreeNode .*/

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

/*Hívás LinkedListből, ha a kezdő csomópont Node típusú és nem 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. Ellenőrzi, hogy a kulcs null-e vagy sem .Ha a kulcs null , akkor a null kulcsok mindig a hash 0-hoz, tehát a táblázat 0 indexéhez tartoznak.
2. Ha a kulcs nem null, a módszer meghívja a hashCode() metódust a kulcs objektumon (a felhasználó által felülírva a megfelelő Key osztályban) és a visszaadott hashValue-t a saját statikus hash függvényére alkalmazza, hogy megtalálja a vödör helyét(backing array), ahol a kulcsokat és az értékeket kell tárolni egy Entry nevű beágyazott osztály formájában.A vödör helye az Entry indexe, nevezetesen a táblázatban.
3. A végső hash-értéket arra használjuk, hogy megtaláljuk a vödör helyét, ahol az Entry objektumot tárolni kell. Ezután a Kulcsokat a get()-ben leírt módon keressük, hogy ellenőrizzük, létezik-e már a kulcs, ha létezik, akkor az értéket az új értékkel helyettesítjük.
Emelyik esetben a lista mérete kerül ellenőrzésre,
Ha meghaladja a TREEIFY_THRESHOLD(alapértelmezett 8) értéket, akkor a csomópontok átstrukturálódnak RedBlackTree-be, és az új kulcsot a benne lévő értékkel együtt tároljuk.
Ha a küszöbértéket nem lépjük túl, akkor az új Entry létrejön a megfelelő kulcs-értékkel, és tárolásra kerül.

public V put(K kulcs, V érték) {
return putVal(hash(kulcs), kulcs, érték, false, true);}

final V putVal(int hash, K kulcs, V érték, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing mint a 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, kulcs, érték);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*A TREEIFY_THRESHOLD túllépésének ellenőrzése.*/

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) { /* meglévő leképezés a kulcshoz*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}}

++modCount;

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