HashMap är en datastruktur som lagrar data i (nyckel, värde)-par, som liknar Dictionary i python om du gillar det!
För att förstå hur Hashmap fungerar internt måste vi bekanta oss med följande termer:
HASHING:
Hashing är processen att omvandla en given nyckel till ett annat värde baserat på en formel med hjälp av en funktion. En hashfunktion används för att generera det nya värdet enligt en matematisk algoritm. Resultatet av en hashfunktion är känt som ett hashvärde eller helt enkelt en hash. Den används för att indexera och hämta objekt och för
krypteringsalgoritmer.
En sann hashfunktion måste följa den här regeln –
”Hashfunktionen ska returnera samma hashkod varje gång när funktionen tillämpas på samma eller likvärdiga objekt. Med andra ord måste två likvärdiga objekt konsekvent ge samma hashkod.”
Alla objekt i Java ärver en standardimplementation av hashCode()-funktionen som definieras i klassen Object.
KOLLISIONER :
Håller i minnet att två nycklar kan generera samma hash som kan leda till samma adress. Detta fenomen kallas kollision.
HashMap-funktioner
1. Public V get(Object key) : dvs. för att hämta ett värde från kartan utifrån nyckeln.
2. Public V put(K key, V value) : eller för att infoga ett nyckel , värdepar i kartan.
Anmärkning: Det är i allmänhet nödvändigt att åsidosätta hashCode()-metoden närhelst equals()-metoden åsidosätts, så att det allmänna kontraktet för hashCode()-metoden bibehålls, enligt vilket lika objekt måste ha lika hashkoder.
HashMap i JAVA
Metoder för att instantiera en HashMap i java:
1. Konstruerar en tom HashMap med den angivna initiala
kapaciteten och belastningsfaktorn.
public HashMap(int initialCapacity, float loadFactor)
2. Konstruerar en tom HashMap med den angivna initiala
kapaciteten och standardbelastningsfaktorn (0,75).
public HashMap(int initialCapacity)
3. Konstruerar en tom HashMap med standardiserad initial kapacitet (16) och standardbelastningsfaktor (0.75).
public HashMap()
Lastfaktor och initial kapacitet.
En instans av HashMap har två parametrar som påverkar dess prestanda:
1. Initial kapacitet
2. Belastningsfaktor.
Initial kapacitet:
Kapaciteten är antalet hinkar i hashtabellen, och den initiala kapaciteten är helt enkelt kapaciteten vid den tidpunkt då hashtabellen skapas.
Lastfaktor:
Lastfaktorn är ett mått på hur full hashtabellen tillåts bli innan dess kapacitet ökas automatiskt. När antalet poster i hashtabellen överskrider produkten av belastningsfaktorn och den aktuella kapaciteten, omhashas hashtabellen (det vill säga interna datastrukturer byggs om) så att hashtabellen har ungefär dubbelt så många hinkar.
OBS:
Som allmän regel ger standardbelastningsfaktorn (.75) en bra avvägning mellan tids- och utrymmeskostnader. Högre värden minskar utrymmeskostnaden men ökar uppslagningskostnaden (vilket återspeglas i de flesta av operationerna i HashMap-klassen, inklusive get och put.
Det förväntade antalet poster i mappen och dess belastningsfaktor bör beaktas när man fastställer dess initiala kapacitet, så att antalet rehash-operationer minimeras. Om den initiala kapaciteten är större än det maximala antalet poster dividerat med belastningsfaktorn kommer inga rehash-operationer någonsin att inträffa.
HashMap i Java 8
En HashMap(från java 8) lagrar data i flera singelt länkade listor med poster eller flera Red BlacK Trees eller en blandning av båda , beroende på tröskelvärdet, även kallade hinkar eller bins.
Alla listor/träd registreras i en array av Entry (Entry<K,V> table) och standardkapaciteten för denna inre array är 16.
Varje enskild post eller ett enskilt par av nyckel och ett värde i en HashMap kallas Entry<Key,Value>.
Entry
HashMaps använder en inre klass för att lagra data: Entry<K, V>.
Den här posten är ett enkelt nyckel-värdepar med två extra värden som är följande:
1. En referens till en annan Entry så att en HashMap kan lagra poster som enkelt länkade listor, eller som träd med vänster och höger noder för att ge bättre sökning.
2. Ett hashvärde som representerar hashvärdet för nyckeln. Detta hashvärde lagras för att undvika beräkning av hashvärdet varje gång HashMap behöver det.
Entrén i java 8 kan vara av 2 typer LinkedList Node eller RedBlack Tree Node.
*storlek av denna som diskuterats ovan är antingen definierad under instantiering eller standard 16. På grundval av belastningsfaktorn ökar den till dubbla den tidigare storleken för att rymma ytterligare poster.
transient Node<K,V> table; //innehåller alla poster.
I table är varje index en nod i antingen en LinkedList eller ett RedBlackTree.
Hierarkin för poster ser ut så här:
Map.Entry<K,V> → implementerar → Node<K,V> → extends → TreeNode<K,V>
LinkedList Node:
statisk klass Node<K,V> implementerar Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //för att upprätthålla en 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, i java 8 , använder RedBlackTree efter ett visst tröskelvärde som kallas TREEIFY_THRESHOLD(standardvärde 8), eftersom det ger en tidskomplexitet i värsta fall på O(log n), jämfört med LinkedList som ger sökning på O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // röd-svarta trädlänkar
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // behövs för att avlänka nästa vid radering
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
HashMap-funktionernas funktionssätt
1. Den kontrollerar om key är null eller inte . Observera att det bara kan finnas en null-nyckel i HashMap.Om key är null , så mappas null-nycklar alltid till hash 0, alltså index 0 i tabellen.
2. Om nyckeln inte är noll kallar metoden hashCode() på nyckelobjektet (överstyrs av användaren i respektive nyckelklass) och tillämpar den returnerade hashValue på sin egen statiska hashfunktion för att hitta en plats för en hink (backing array) där nycklar och värden lagras i form av en inbäddad klass som kallas Entry.
Hinkens plats är ett index för Entry, nämligen tabellen.
OBS: Vi beräknar hashvärdet igen med hash(hashValue) eftersom det skyddar mot hashfunktion av dålig kvalitet.
3. Slutligt hashvärde används för att hitta den hinkplats där Entry-objektet lagras.
Komplexiteten hos get() och put() är O(1) , förutsatt att hashfunktionen sprider elementen korrekt mellan hinkarna.
Anmärkning: Vi vet nu att vid hashkollisioner lagras entry-objekten som en nod i en länkad lista och metoden equals() används för att jämföra nycklar. Denna jämförelse för att hitta rätt nyckel i en länkad lista är en linjär operation så i värsta fall blir komplexiteten O(n).
För att lösa detta problem använder Java 8 hashelement balanserade träd i stället för länkade listor efter att ett visst tröskelvärde har uppnåtts. Vilket innebär att HashMap börjar med att lagra Entry-objekt i länkade listor, men efter att antalet objekt i en hash blir större än ett visst tröskelvärde ändras hashen från att använda en länkad lista till ett balanserat träd, vilket förbättrar prestandan i värsta fall från O(n) till O(log n).
Hur blir det om två olika nycklar har samma hashkod?
4. Vid ett index kan vi ha flera värden eftersom vi kan ha kollisioner vid hashing. För att ta reda på vilket vi behöver tar HashMap hjälp av equals().
Lösning: metoden equals() kommer till undsättning. Eftersom bucket är en och vi har två objekt med samma hashkod .
Så efter att ha hämtat indexet för nyckeln hämtar den den första noden som finns på det indexet. Den första noden jämförs sedan med nyckeln med hjälp av equals(), Om detta är den önskade noden, returnerar den värdet direkt härifrån.
Else, den tar reda på instansen av noden, för att ta reda på om den innehållande data som lagras i detta index är i formatet länkad lista eller RedBlack tree.
När vi har räknat ut det, går vi över den länkade listan eller trädet, och jämför nycklar i varje post med hjälp av keys.equals() tills det returnerar sant. Då returneras motsvarande postobjekt 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; //presenterar Array of Entry
Node<K,V> first, e;
int n; K k;/* Kontrollerar om tabellen har poster .*/
/* Dessutom hittas indexet på grundval av den beräknade hashen i tidigare steg, där posten lagras antingen som en lista eller en trädnod.*/if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Hämtning av den första noden i indexet som erhållits på grundval av hashen.*/
if (first.hash == hash && /* Kontrollera alltid den första noden*/
((k = first.key) == key|| (key != null && key.equals(k))))
returnera first;/*Om den första noden i det indexet inte är det värde som vi söker, så går det till traversering.*/
if ((e = first.next) != null) {
if (första instansen av TreeNode)
/*Hämtning från Red Black Tree om startnoden på indexet if för TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
while ((e = e.next) != null);
}}
returnerar null;
}
PUT:
1. Den kontrollerar om nyckeln är noll eller ej. Om nyckeln är noll, mappas nollnycklar alltid till hash 0, alltså index 0 i tabellen.
2. Om nyckeln inte är noll anropar metoden hashCode()-metoden på nyckelobjektet (överstyrs av användaren i respektive nyckelklass) och tillämpar den återgivna hashValue på sin egen statiska hash-funktion för att hitta en plats för en hink (backing array) där nycklar och värden ska lagras i form av en inbäddad klass som kallas Entry.Hinkplatsen är ett index för Entry, nämligen tabellen.
3. Det slutliga hashvärdet används för att hitta den hinkplats där Entry-objektet ska lagras. Därefter genomkorsas nycklarna på samma sätt som beskrivs i get(), för att kontrollera om nyckeln redan existerar, om den existerar ersätts värdet med det nya värdet.
Else, listans storlek kontrolleras,
Om den överskrider TREEIFY_THRESHOLD(standard 8) omstruktureras noderna till RedBlackTree och den nya nyckeln lagras med värdet i den.
Om tröskelvärdet inte överskrids skapas den nya Entry med respektive nyckel-värde och lagras.
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);
/*För att kontrollera om TREEIFY_THRESHOLD överskrids eller inte.*/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) { /* befintlig mappning för nyckel*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;}
Mer att läsa
Nyckel oföränderlighet:
Varför strängar och heltal är en bra implementering av nycklar för HashMap? Mest för att de är oföränderliga! Om du väljer att skapa en egen nyckelklass och inte gör den oföränderlig kan du förlora data i HashMap.
Rehashing:
Rehashing är en process där hashkoden för redan lagrade poster (nyckel-värdepar) beräknas på nytt för att flytta dem till en annan större hashmap när tröskelvärdet för belastningsfaktorn har uppnåtts.
När antalet poster i kartan överskrider gränsen för belastningsfaktorn fördubblar hashmap sin kapacitet och hashkoden beräknas på nytt för redan lagrade element för en jämn fördelning av nyckel-värdepar över nya hinkar.
Varför behövs det?
När kapaciteten har fördubblats, vad gör man då med de nyckelvärdespar som redan finns i hinkarna?
Om vi behåller de befintliga nyckelvärdesparen som de är, hjälper det kanske inte att fördubbla kapaciteten, eftersom O(1)-komplexitet endast uppnås om elementen fördelas jämnt över alla hinkar.
För varje befintligt nyckel-värdepar beräknas hashkoden på nytt med den ökade hashmapkapaciteten som parameter, vilket resulterar i att objektet antingen placeras i samma hink eller i en annan hink.