HashMap interne werking

HashMap is een gegevensstructuur die de gegevens opslaat in (Sleutel, Waarde) paren, vergelijkbaar met Dictionary in python als je daarmee vertrouwd bent!

Om de interne werking van Hashmap te begrijpen, moeten we vertrouwd raken met de volgende termen:

HASHING:
Hashing is het proces van het omzetten van een gegeven sleutel in een andere waarde op basis van een formule met behulp van een functie. Een hashfunctie wordt gebruikt om de nieuwe waarde te genereren volgens een wiskundig algoritme. Het resultaat van een hashfunctie staat bekend als een hashwaarde of kortweg, een hash. Het wordt gebruikt om items te indexeren en terug te vinden en voor
encryptie-algoritmen.

Een echte hash-functie moet aan deze regel voldoen –

“Een hash-functie moet telkens dezelfde hash-code teruggeven wanneer de functie wordt toegepast op dezelfde of gelijke objecten. Met andere woorden, twee gelijke objecten moeten consistent dezelfde hash-code opleveren.”

Alle objecten in Java erven een standaardimplementatie van de functie hashCode() die is gedefinieerd in de klasse Object.

COLLISIES :
Bedenk dat twee sleutels dezelfde hash kunnen genereren die tot hetzelfde adres kan leiden. Dit fenomeen staat bekend als een collision.

HashMap Functies

1. Public V get(Object key) : d.w.z. om een waarde op te halen uit de map op basis van de sleutel.
2. Public V put(K key, V value) : of om een sleutel , waarde paar in de map in te voegen.

Opmerking: Het is in het algemeen nodig om de hashCode() methode te overschrijven telkens wanneer de equals() methode wordt overschreven, om het algemene contract voor de hashCode() methode te behouden, dat stelt dat gelijke objecten gelijke hashcodes moeten hebben.

HashMap in JAVA

manieren om een HashMap te instantiëren in java:
1. Construeert een lege HashMap met de opgegeven initiële
capaciteit en belastingsfactor.

public HashMap(initialCapacity, float loadFactor)

2. Construeert een lege HashMap met de opgegeven initiële
capaciteit en de standaardbelastingsfactor (0,75).

public HashMap(initialCapacity)

3. Construeert een lege HashMap met de standaardinitiële capaciteit (16) en de standaardbelastingsfactor (0.75).

public HashMap()

Laadfactor en initiële capaciteit.

Een instantie van HashMap heeft twee parameters die de prestaties ervan beïnvloeden:
1. Initial capacity
2. Load factor.

Initial Capacity :
De capaciteit is het aantal emmers in de hashtabel, en de initial capacity is eenvoudigweg de capaciteit op het moment dat de hashtabel wordt aangemaakt.

Load Factor:
De belastingfactor is een maat voor hoe vol de hashtabel mag worden voordat de capaciteit automatisch wordt verhoogd. Wanneer het aantal ingangen in de hashtabel groter is dan het product van de belastingsfactor en de huidige capaciteit, wordt de hashtabel opnieuw gehasht (dat wil zeggen dat interne gegevensstructuren opnieuw worden opgebouwd), zodat de hashtabel ongeveer tweemaal zoveel emmers heeft.

NOOT:

In het algemeen biedt de standaardbelastingsfactor (.75) een goede afweging tussen tijd- en ruimtekosten. Hogere waarden verlagen de ruimteoverhead, maar verhogen de opzoekkosten (die worden weerspiegeld in de meeste bewerkingen van de HashMap-klasse, waaronder get en put.

Het verwachte aantal items in de map en de belastingsfactor moeten in aanmerking worden genomen bij het instellen van de initiële capaciteit, zodat het aantal herhalingsbewerkingen tot een minimum wordt beperkt. Als de initiële capaciteit groter is dan het maximum aantal entries gedeeld door de load factor, zullen er nooit rehash operaties optreden.

HashMap in Java 8

Een HashMap (uit java 8) slaat gegevens op in meerdere enkelvoudig gekoppelde lijsten van entries of meerdere Red BlacK Trees of mengsel van beide , afhankelijk van de drempel, ook wel buckets of bins genoemd.

Alle lijsten/bomen worden geregistreerd in een array van Entry (Entry<K,V> tabel) en de standaard capaciteit van deze binnen array is 16.

Elk van de Enkele record of een enkel paar van Sleutel en een waarde in een HashMap wordt Entry<Key,Value> genoemd.

Entry

HashMaps gebruiken een binnenklasse om gegevens op te slaan: de Entry<K, V>.
Deze entry is een eenvoudig sleutel-waardepaar met twee extra waarden die als volgt zijn:

1. Een verwijzing naar een andere ingang, zodat een HashMap ingangen kan opslaan als enkelvoudig gekoppelde lijsten, of als een boom met linker- en rechterknooppunten voor beter zoeken.

2. Een hashwaarde die de hashwaarde van de sleutel weergeeft. Deze hashwaarde wordt opgeslagen om te voorkomen dat de hash moet worden berekend telkens wanneer de HashMap deze nodig heeft.

Entry in java 8 kan van 2 typen zijn LinkedList Node of RedBlack Tree Node.

*size hiervan wordt, zoals hierboven besproken, ofwel gedefinieerd tijdens de instantiatie ofwel standaard 16. Op basis van de belastingsfactor neemt deze toe tot tweemaal de vorige grootte om meer entries te kunnen bevatten.

transient Node<K,V> tabel; //bevat alle entries.

In de tabel is elke index een Node van ofwel een LinkedList ofwel een RedBlackTree.
De hiërarchie van Entry gaat als volgt:

Map.Entry<K,V> → implementeert → Node<K,V> → breidt uit → TreeNode<K,V>

LinkedList Node:

static class Node<K,V> implementeert Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //voor het onderhouden van een LinkedList.
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, in java 8 , gebruikt RedBlackTree na een bepaalde drempel die bekend staat als TREEIFY_THRESHOLD (standaardwaarde 8), omdat dit een worst-case tijdcomplexiteit geeft van O(log n), in vergelijking met LinkedList die het zoeken in O(n) geeft.

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // rood-zwarte boomkoppelingen
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // nodig om volgende te ontkoppelen bij verwijdering
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

Werking van HashMap-functies

1. Er wordt gecontroleerd of de sleutel al dan niet null is. Merk op dat er slechts één nulsleutel in de HashMap kan zijn. Als de sleutel null is, worden nulsleutels altijd toegewezen aan hash 0, dus index 0 van de tabel.
2. Als sleutel is niet null dan, methode roept hashCode() methode op de sleutel object (Overriden door de gebruiker in de respectieve sleutel-klasse) en past teruggegeven hashValue aan zijn eigen statische hash-functie om een emmer locatie (backing array) waar sleutels en waarden worden opgeslagen in de vorm van een geneste klasse genaamd Entry.
De emmer locatie is een index van de Entry namelijk tabel.

NOOT: we berekenen de hash waarde opnieuw met behulp van hash(hashValue) als het verdedigt tegen slechte kwaliteit hash functie.

3. Uiteindelijke hash waarde wordt gebruikt om de emmer locatie te vinden waar de Entry object is opgeslagen.
De complexiteit van get() en put() is O(1), aangenomen dat de hash-functie de elementen goed over de emmers verdeelt.

Note: Zoals we nu weten, worden in geval van hash-botsing entry-objecten opgeslagen als een node in een linked-list en wordt de methode equals() gebruikt om sleutels te vergelijken. Die vergelijking om de juiste sleutel in een gelinkte lijst te vinden is een lineaire operatie, dus in het ergste geval wordt de complexiteit O(n).
Om dit probleem op te lossen, gebruiken Java 8 hash-elementen gebalanceerde bomen in plaats van gelinkte lijsten nadat een bepaalde drempel is bereikt. Dat betekent dat HashMap begint met het opslaan van Entry-objecten in linked list, maar nadat het aantal items in een hash groter wordt dan een bepaalde drempel, zal de hash veranderen van een linked list naar een balanced tree, waardoor de worst-case performance verbetert van O(n) naar O(log n).

Wat als twee verschillende sleutels dezelfde hashcode hebben?

4. Op een index kunnen we meerdere waarden hebben omdat we botsingen kunnen hebben bij het hashen. Om erachter te komen welke we nodig hebben, gebruikt HashMap de hulp van equals().

Oplossing, equals() methode komt tot redding. Aangezien de emmer één is en we twee objecten met dezelfde hash-code hebben.

Dus na het ophalen van de index van de sleutel, wordt de eerste node opgehaald die op die index aanwezig is. De eerste node wordt dan vergeleken met de sleutel met behulp van equals(), Als dit de gewenste node, het retourneert de waarde direct van hier.
Else, het vindt de instantie van de Node, om uit te vinden of de gegevens die zijn opgeslagen in deze index is in het formaat van de gekoppelde lijst of RedBlack tree.

Zodra we erachter komen dat, gaan we door de LinkedList of Tree, het vergelijken van sleutels in elke inzendingen met behulp van keys.equals() totdat het waar retourneert. Dan wordt het overeenkomstige ingangsobject Waarde teruggegeven.

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

final Node<K,V> getNode(hash, Object key) {
Node<K,V> tab; //vertegenwoordigt de array van Entry
Node<K,V> first, e;
int n; K k;

/*Controleren of de tabel entries heeft .*/
/* Ook het vinden van de index op basis van de berekende hash in voorgaande stappen, waarbij de entry is opgeslagen als List of Tree Node.*/

if ((tab = tabel) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Halen van de eerste node in de index die is verkregen op basis van de hash.*/
if (first.hash == hash && /* controleer altijd eerste node*/
((k = first.key) == key|(key != null && key.equals(k))))
return first;

/*Als eerste node van die index niet de waarde is die we zoeken, dan gaat het om traverseren.*/
if ((e = first.next) != null) {
if (eerste instantie van TreeNode)
/*Halen uit Rood Zwarte boom als beginnende Node op de index if van TreeNode .*/

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

/*Opgehaald uit LinkedList als de startnode van het type Node is en niet van Tree.*/

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

PUT:

1. Het controleert of de sleutel null is of niet. Als de sleutel null is, dan gaan null sleutels altijd naar hash 0, dus index 0 van de tabel.
2. Als de sleutel niet null is, roept de methode hashCode() op het sleutelobject (Overriden door de gebruiker in de respectievelijke sleutel klasse) en past de geretourneerde hashValue toe op zijn eigen statische hash functie om een emmer locatie (backing array) te vinden waar sleutels en waarden moeten worden opgeslagen in de vorm van een geneste klasse genaamd Entry.De bucket locatie is een index van de Entry namelijk de tabel.
3. De uiteindelijke hash waarde wordt gebruikt om de bucket locatie te vinden waar het Entry object moet worden opgeslagen. Dan, worden de Sleutels doorlopen op dezelfde manier als beschreven in de get(), om te controleren of de sleutel al bestaat als het bestaat de waarde wordt vervangen door de nieuwe waarde.
Else, de grootte van de lijst wordt gecontroleerd,
Als het de TREEIFY_THRESHOLD (standaard 8) overschrijdt, worden de nodes geherstructureerd in RedBlackTree en de nieuwe sleutel wordt opgeslagen met de waarde erin.
Als de drempel niet wordt overschreden, wordt de nieuwe Entry aangemaakt met de respectievelijke sleutel-waarde, en wordt deze opgeslagen.

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 = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traverseren zoals 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);
/*Om te controleren of de TREEIFY_THRESHOLD is overschreden of niet.*/

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

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

if (e != null) { /* bestaande mapping voor key*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}

++modCount;

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