HashMap Interenal Working

HashMap ist eine Datenstruktur, die die Daten in (Key, Value) Paaren speichert, ähnlich wie Dictionary in Python, wenn Sie sich dafür interessieren!

Um die interne Funktionsweise von Hashmap zu verstehen, sollten wir uns mit folgenden Begriffen vertraut machen:

HASHING:
Hashing ist der Prozess der Umwandlung eines gegebenen Schlüssels in einen anderen Wert auf der Grundlage einer Formel unter Verwendung einer Funktion. Eine Hash-Funktion wird verwendet, um den neuen Wert nach einem mathematischen Algorithmus zu erzeugen. Das Ergebnis einer Hash-Funktion wird als Hash-Wert oder einfach als Hash bezeichnet. Er wird zum Indizieren und Abrufen von Elementen und für
Verschlüsselungsalgorithmen verwendet.

Eine echte Hash-Funktion muss diese Regel befolgen –

„Eine Hash-Funktion sollte jedes Mal den gleichen Hash-Code zurückgeben, wenn die Funktion auf gleiche oder gleiche Objekte angewendet wird. Mit anderen Worten, zwei gleiche Objekte müssen konsistent den gleichen Hash-Code liefern.“

Alle Objekte in Java erben eine Standardimplementierung der Funktion hashCode(), die in der Klasse Object definiert ist.

COLLISIONS :
Denken Sie daran, dass zwei Schlüssel denselben Hash erzeugen können, der zur selben Adresse führen kann. Dieses Phänomen wird als Kollision bezeichnet.

HashMap Funktionen

1. Public V get(Object key) : d.h. einen Wert aus der Map auf der Basis des Schlüssels holen.
2. Public V put(K key, V value) : oder ein Schlüssel , Wertpaar in die Map einfügen.

Hinweis: Es ist im Allgemeinen notwendig, die Methode hashCode() zu überschreiben, wenn die Methode equals() überschrieben wird, um den allgemeinen Vertrag für die Methode hashCode() beizubehalten, der besagt, dass gleiche Objekte gleiche Hashcodes haben müssen.

HashMap in JAVA

Wie man eine HashMap in Java instanziert:
1. Konstruiert eine leere HashMap mit der angegebenen initialen
Kapazität und dem Lastfaktor.

public HashMap(int initialCapacity, float loadFactor)

2. Konstruiert eine leere HashMap mit der angegebenen initialen
Kapazität und dem Standardlastfaktor (0,75).

public HashMap(int initialCapacity)

3. Konstruiert eine leere HashMap mit der Standard-Anfangskapazität (16) und dem Standard-Lastfaktor (0.75).

public HashMap()

Lastfaktor und Anfangskapazität.

Eine Instanz von HashMap hat zwei Parameter, die ihre Leistung beeinflussen:
1. Anfängliche Kapazität
2. Lastfaktor.

Anfängliche Kapazität :
Die Kapazität ist die Anzahl der Buckets in der Hashtabelle, und die anfängliche Kapazität ist einfach die Kapazität zum Zeitpunkt der Erstellung der Hashtabelle.

Lastfaktor:
Der Auslastungsfaktor ist ein Maß dafür, wie voll die Hash-Tabelle werden darf, bevor ihre Kapazität automatisch erhöht wird. Wenn die Anzahl der Einträge in der Hash-Tabelle das Produkt aus Lastfaktor und aktueller Kapazität übersteigt, wird die Hash-Tabelle neu gepuffert (d.h. die internen Datenstrukturen werden neu aufgebaut), so dass die Hash-Tabelle ungefähr die doppelte Anzahl von Buckets hat.

HINWEIS:

In der Regel bietet der Standard-Lastfaktor (.75) einen guten Kompromiss zwischen Zeit- und Platzkosten. Höhere Werte verringern den Platzbedarf, erhöhen aber die Suchkosten (was sich in den meisten Operationen der Klasse HashMap, einschließlich get und put, widerspiegelt.

Die erwartete Anzahl von Einträgen in der Map und ihr Lastfaktor sollten bei der Festlegung ihrer Anfangskapazität berücksichtigt werden, um die Anzahl der Rehash-Operationen zu minimieren. Wenn die Anfangskapazität größer ist als die maximale Anzahl der Einträge geteilt durch den Lastfaktor, werden niemals Rehash-Operationen auftreten.

HashMap in Java 8

Eine HashMap (aus Java 8) speichert Daten in mehrere einfach verknüpfte Listen von Einträgen oder mehrere Red BlacK Trees oder eine Mischung aus beiden, je nach Schwellenwert, auch Buckets oder Bins genannt.

Alle Listen/Trees werden in einem Array von Entry (Tabelle Entry<K,V>) registriert und die Standardkapazität dieses inneren Arrays ist 16.

Jeder einzelne Datensatz oder ein einzelnes Paar aus Schlüssel und Wert in einer HashMap wird als Entry<Key,Value> bezeichnet.

Entry

HashMaps verwenden eine innere Klasse, um Daten zu speichern: die Entry<K, V>.
Dieser Eintrag ist ein einfaches Schlüssel-Wert-Paar mit zwei zusätzlichen Werten, die wie folgt lauten:

1. Ein Verweis auf einen anderen Eintrag, so dass eine HashMap Einträge wie einzeln verknüpfte Listen oder als Baum mit linken und rechten Knoten für eine bessere Suche speichern kann.

2. Ein Hash-Wert, der den Hash-Wert des Schlüssels darstellt. Dieser Hash-Wert wird gespeichert, um die Berechnung des Hash-Wertes jedes Mal zu vermeiden, wenn die HashMap ihn benötigt.

Eintrag in Java 8 kann von 2 Typen LinkedList Node oder RedBlack Tree Node sein.

*Größe dieser wie oben besprochen wird entweder während der Instanzierung oder Standard 16 definiert. Aufgrund des Lastfaktors erhöht sie sich auf das Doppelte der bisherigen Größe, um weitere Einträge aufzunehmen.

transient Node<K,V> table; //enthält alle Einträge.

In table, each index is a Node of either a LinkedList or a RedBlackTree.
Die Hierarchie der Einträge sieht wie folgt aus:

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

LinkedList Node:

statische Klasse Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //zur Verwaltung einer 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 , verwendet RedBlackTree nach einem bestimmten Schwellenwert, bekannt als TREEIFY_THRESHOLD (Standardwert 8), da es eine Worst-Case-Zeitkomplexität von O(log n) ergibt, im Vergleich zu LinkedList, das die Suche in O(n) ergibt.

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; // benötigt, um next beim Löschen zu entkoppeln
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

Arbeitsweise von HashMap-Funktionen

1. Es wird geprüft, ob key null ist oder nicht. Wenn key null ist, dann werden Nullschlüssel immer auf Hash 0 abgebildet, also Index 0 der Tabelle.
2. Wenn Schlüssel nicht null ist, dann ruft Methode hashCode() Methode auf dem Schlüsselobjekt (überschrieben durch den Benutzer in der jeweiligen Schlüsselklasse) und wendet zurückgegebenen hashValue auf seine eigene statische Hash-Funktion, um eine Bucket-Speicherort (Backing-Array), wo Schlüssel und Werte in Form einer verschachtelten Klasse namens Entry gespeichert sind.
Der Bucket-Speicherort ist ein Index der Entry nämlich Tabelle.

HINWEIS: Wir berechnen den Hashwert erneut mit hash(hashValue), da es gegen Hashfunktionen von schlechter Qualität schützt.

3. Der endgültige Hashwert wird verwendet, um den Bereich zu finden, in dem das Entry-Objekt gespeichert ist.
Die Komplexität von get() und put() ist O(1), vorausgesetzt, die Hash-Funktion verteilt die Elemente ordnungsgemäß auf die Buckets.

Anmerkung: Wie wir jetzt wissen, werden Eintragsobjekte im Falle einer Hash-Kollision als Knoten in einer verknüpften Liste gespeichert und die Methode equals() wird zum Vergleich der Schlüssel verwendet. Dieser Vergleich, um den richtigen Schlüssel in einer verknüpften Liste zu finden, ist eine lineare Operation, so dass im schlimmsten Fall die Komplexität O(n) wird.
Um dieses Problem zu lösen, verwenden Java 8 Hash-Elemente ab einem bestimmten Schwellenwert ausgeglichene Bäume anstelle von verknüpften Listen. Das bedeutet, dass HashMap mit der Speicherung von Eintragsobjekten in einer verknüpften Liste beginnt, aber nachdem die Anzahl der Elemente in einem Hash einen bestimmten Schwellenwert überschreitet, wird der Hash von einer verknüpften Liste zu einem ausgeglichenen Baum wechseln, was die Leistung im schlimmsten Fall von O(n) auf O(log n) verbessert.

Was ist, wenn zwei verschiedene Schlüssel den gleichen Hashcode haben?

4. Bei einem Index können wir mehrere Werte haben, da wir beim Hashing Kollisionen haben können. Um herauszufinden, welchen wir brauchen, nimmt HashMap die Hilfe von equals().

Lösung, equals() Methode kommt zur Rettung. Da es sich um einen Bucket handelt und wir zwei Objekte mit demselben Hashcode haben.

Nachdem der Index des Schlüssels abgerufen wurde, wird der erste Knoten in diesem Index abgerufen. Wenn dies der gewünschte Knoten ist, wird der Wert direkt von hier zurückgegeben.
Andernfalls wird die Instanz des Knotens ermittelt, um herauszufinden, ob die in diesem Index gespeicherten Daten im Format einer verknüpften Liste oder eines RedBlack-Baums vorliegen.

Wenn wir das herausgefunden haben, durchlaufen wir die verknüpfte Liste oder den Baum, indem wir die Schlüssel in jedem Eintrag mit keys.equals() vergleichen, bis es wahr ist. Dann wird das entsprechende Eintragsobjekt Value zurückgegeben.

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; //representiert das Array von Entry
Node<K,V> first, e;
int n; K k;

/* Überprüfen, ob die Tabelle Einträge hat .*/
/* Außerdem wird der Index auf der Grundlage des in den vorherigen Schritten berechneten Hashes gefunden, wobei der Eintrag entweder als Listen- oder Baumknoten gespeichert wird.*/

if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Abrufen des ersten Knotens in dem auf der Grundlage des Hashes erhaltenen Index.*/
if (first.hash == hash && /* immer den ersten Knoten prüfen*/
((k = first.key) == key|| (key != null && key.equals(k))))
return first;

/*Wenn der erste Knoten des Index nicht der gesuchte Wert ist, dann wird er durchlaufen.*/
if ((e = first.next) != null) {
if (erste Instanz von TreeNode)
/*Abholen von Red Black Tree, wenn der Knoten auf dem Index if von TreeNode beginnt.*/

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

/*Fetching from LinkedList if the starting node is of type Node and not of 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. Sie prüft, ob key null ist oder nicht.
Wenn key null ist, dann werden Null-Schlüssel immer auf Hash 0 abgebildet, also Index 0 der Tabelle.
2. Wenn key nicht null ist, ruft die Methode die Methode hashCode() auf dem key-Objekt auf (vom Benutzer in der jeweiligen Key-Klasse überschrieben) und wendet den zurückgegebenen hashValue auf seine eigene statische Hash-Funktion an, um eine Bucket-Position (Backing Array) zu finden, in der Schlüssel und Werte in Form einer verschachtelten Klasse namens Entry gespeichert werden sollen.Die Bucket-Position ist ein Index des Eintrags, d.h. der Tabelle.
3. Der endgültige Hash-Wert wird verwendet, um die Bucket-Position zu finden, an der das Eintragsobjekt gespeichert werden soll. Dann werden die Schlüssel in der gleichen Weise wie in get() beschrieben durchlaufen, um zu prüfen, ob der Schlüssel bereits existiert, wenn er existiert, wird der Wert durch den neuen Wert ersetzt.
Andernfalls wird die Größe der Liste überprüft,
Wenn sie den TREEIFY_THRESHOLD (Standardwert 8) überschreitet, werden die Knoten in RedBlackTree umstrukturiert und der neue Schlüssel mit dem Wert darin gespeichert.
Wenn der Schwellenwert nicht überschritten wird, wird der neue Eintrag mit dem entsprechenden Schlüssel-Wert erstellt und gespeichert.

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 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);
/*Um zu prüfen, ob der TREEIFY_THRESHOLD überschritten wurde oder nicht.*/

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

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

if (e != null) { /* vorhandene Zuordnung für Schlüssel*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}

++modCount;

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