HashMap er en datastruktur, som gemmer data i (Key, Value) par, svarende til Dictionary i python, hvis du er til det!
For at forstå den interne funktion af Hashmap skal vi gøre os bekendt med følgende udtryk:
HASHING:
Hashing er processen med at omdanne en given nøgle til en anden værdi baseret på en formel ved hjælp af en funktion. En hash-funktion bruges til at generere den nye værdi i henhold til en matematisk algoritme. Resultatet af en hash-funktion er kendt som en hash-værdi eller blot som en hash. Den bruges til at indeksere og hente elementer og til
krypteringsalgoritmer.
En ægte hashfunktion skal følge denne regel –
“Hashfunktionen skal returnere den samme hashkode hver eneste gang, når funktionen anvendes på samme eller lige store objekter. Med andre ord skal to ens objekter konsekvent give den samme hashkode.”
Alle objekter i Java arver en standardimplementering af hashCode()-funktionen, der er defineret i Object-klassen.
KOLLISIONER :
Husk, at to nøgler kan generere den samme hash, som kan føre til den samme adresse. Dette fænomen er kendt som en kollision.
HashMap-funktioner
1. Public V get(Object key) : dvs. at hente en værdi fra kortet på grundlag af nøglen.
2. Public V put(K key, V value) : eller at indsætte et nøgle , værdipar i kortet.
Bemærkning: Det er generelt nødvendigt at overskrive hashCode() metoden, hver gang equals() metoden overskrives, for at opretholde den generelle kontrakt for hashCode() metoden, som siger, at ens objekter skal have ens hashkoder.
HashMap i JAVA
Måder at instantiere et HashMap i java:
1. Konstruerer et tomt HashMap med den angivne initial
kapacitet og belastningsfaktor.
public HashMap(int initialCapacity, float loadFactor)
2. Konstruerer et tomt HashMap med den angivne initial
kapacitet og standardbelastningsfaktoren (0,75).
public HashMap(int initialCapacity)
3. Konstruerer en tom HashMap med den angivne standardinitialkapacitet (16) og standardbelastningsfaktoren (0.75).
public HashMap()
Belastningsfaktor og startkapacitet.
En instans af HashMap har to parametre, der påvirker dens ydeevne:
1. Initial kapacitet
2. Belastningsfaktor.
Initial kapacitet :
Kapaciteten er antallet af spande i hashtabellen, og den initiale kapacitet er simpelthen kapaciteten på det tidspunkt, hvor hashtabellen oprettes.
Load Factor:
Lastfaktoren er et mål for, hvor fuld hashtabellen må blive, før dens kapacitet automatisk øges. Når antallet af poster i hashtabellen overstiger produktet af belastningsfaktoren og den aktuelle kapacitet, bliver hashtabellen rehashet (det vil sige, at interne datastrukturer genopbygges), så hashtabellen har ca. det dobbelte antal spande.
BEMÆRK:
Som hovedregel giver standardbelastningsfaktoren (.75) et godt kompromis mellem tids- og pladsomkostninger. Højere værdier mindsker pladsoverheadet, men øger opslagsomkostningerne (hvilket afspejles i de fleste operationer i HashMap-klassen, herunder get og put.
Det forventede antal poster i kortet og dets belastningsfaktor bør tages i betragtning, når dets oprindelige kapacitet fastsættes, så antallet af rehash-operationer minimeres. Hvis den oprindelige kapacitet er større end det maksimale antal poster divideret med belastningsfaktoren, vil der aldrig forekomme nogen rehash-operationer.
HashMap i Java 8
Et HashMap(fra java 8) gemmer data i flere enkeltvis forbundne lister af poster eller flere Red BlacK Trees eller en blanding af begge , afhængigt af tærsklen, også kaldet buckets eller bins.
Alle listerne/træerne er registreret i et array af Entry (Entry<K,V> table), og standardkapaciteten for dette indre array er 16.
Hver enkelt post eller et enkelt par af nøgle og en værdi i et HashMap kaldes som Entry<Key,Value>.
Entry
HashMaps bruger en indre klasse til at gemme data: Entry<K,V>.
Denne post er et simpelt nøgle-værdipar med to ekstra værdier, som er som følger:
1. En reference til en anden Entry, således at et HashMap kan gemme entries som enkeltkoblede lister eller som Tree med venstre og højre knudepunkter for at give bedre søgning.
2. En hash-værdi, der repræsenterer nøgleens hash-værdi. Denne hashværdi lagres for at undgå beregning af hashværdien, hver gang HashMap har brug for den.
Engang i java 8 kan være af 2 typer LinkedList Node eller RedBlack Tree Node.
*størrelse af denne som diskuteret ovenfor er enten defineret under instantiering eller standard 16. På baggrund af belastningsfaktoren øges den til det dobbelte af den tidligere størrelse for at kunne rumme yderligere poster.
transient Node<K,V> tabel; //indeholder alle posterne.
I tabellen er hvert indeks en node af enten en LinkedList eller et RedBlackTree.
Indgangshierarkiet ser således ud:
Map.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>
LinkedList Node:
statisk klasse Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //til vedligeholdelse af 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 , bruger RedBlackTree efter en vis tærskel kendt som TREEIFY_THRESHOLD(standardværdi 8), da det giver en worst case tidskompleksitet på O(log n), sammenlignet med LinkedList, der giver søgningen i O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // rød-sort træforbindelser
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // nødvendigt at fjerne linket til next ved sletning
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Arbejdsmåde for HashMap-funktioner
1. Den kontrollerer, om key er null eller ej . Bemærk, at der kun kan være én null-nøgle i HashMap.Hvis key er null , så mapper null-nøgler altid til hash 0, og dermed indeks 0 i tabellen.
2. Hvis key ikke er null, kalder metoden hashCode()-metoden på key-objektet (overstyret af brugeren i den respektive Key-klasse) og anvender den returnerede hashValue på sin egen statiske hashfunktion for at finde en spandplacering (backing array), hvor nøgler og værdier er gemt i form af en indlejret klasse kaldet Entry.
Spandplaceringen er et indeks i Entry, nemlig tabellen.
BEMÆRK: Vi beregner hashværdien igen ved hjælp af hash(hashValue), da det forsvarer mod hashfunktion af dårlig kvalitet.
3. Den endelige hashværdi bruges til at finde den bucket-placering, hvor Entry-objektet er gemt.
Kompleksiteten af get() og put() er O(1) , forudsat at hashfunktionen spreder elementerne korrekt blandt spandene.
Note: Som vi nu ved, er entry-objekter i tilfælde af hashkollision gemt som en node i en linked-list, og equals()-metoden bruges til at sammenligne nøgler. Denne sammenligning for at finde den korrekte nøgle med i en linked-list er en lineær operation, så i værste fald bliver kompleksiteten O(n).
For at løse dette problem anvender Java 8 hash-elementer afbalancerede træer i stedet for linked-lister efter en vis tærskelværdi. Hvilket betyder, at HashMap starter med at lagre Entry-objekter i linked list, men efter at antallet af elementer i en hash bliver større end en vis tærskel, vil hashen skifte fra at bruge en linked list til et balanceret træ, hvilket vil forbedre den værst tænkelige ydeevne fra O(n) til O(log n).
Hvad sker der, når to forskellige nøgler har den samme hashkode?
4. Ved et indeks kan vi have flere værdier, da vi kan have kollisioner i hashing. For at finde ud af, hvilken vi har brug for, tager HashMap hjælp af equals().
Løsningen er, at equals()-metoden kommer til undsætning. Da bucket er én, og vi har to objekter med samme hash-kode .
Så efter at have hentet indekset for nøglen hentes den første knude, der er til stede på dette indeks. Den første node sammenlignes derefter med nøglen ved hjælp af equals(), Hvis dette er den ønskede node, returnerer den værdien direkte herfra.
Else, finder den ud af instansen af noden, for at finde ud af, om de indeholdende data, der er gemt i dette indeks, er i formatet af linked list eller RedBlack tree.
Når vi finder ud af det, gennemgår vi LinkedList eller Tree , sammenligner nøgler i hver post ved hjælp af keys.equals(), indtil det returnerer sandt. Derefter returneres det tilsvarende postobjekt Værdi .
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; //repræsenterer Array of Entry
Node<K,V> first, e;
int n; K k;/* Kontrol af, om tabellen har poster .*/
/* Også finde indekset på grundlag af den beregnede hash i de foregående trin, hvor posten er gemt enten som liste- eller træknude */if ((tab = tabel) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Hente den første knude i det indeks, der er opnået på grundlag af hash.*/
if (first.hash == hash && /*Kontroller altid første node*/
((k = first.key) == key||| (key != null && key.equals(k))))
return first;/*Hvis første node i det pågældende indeks ikke er den værdi, vi søger, så går den til traversering.*/
if ((e = first.next) ! = = null) {
if (første instans af TreeNode)
/*Henter fra Red Black Tree hvis starter Node på indekset if af TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/*Henter fra LinkedList, hvis startknuden er af typen Node og ikke af typen Tree.*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
returner e;
}
while ((e = e.next) != null);
}}
returnerer null;
}
PUT:
1. Den kontrollerer, om key er null eller ej. Hvis key er null , så mapper null-nøgler altid til hash 0, og dermed indeks 0 i tabellen.
2. Hvis key ikke er null, kalder metoden hashCode()-metoden på key-objektet (overstyret af brugeren i den respektive Key-klasse) og anvender den returnerede hashValue på sin egen statiske hash-funktion for at finde en spandplacering (backing array), hvor nøgler og værdier skal gemmes i form af en indlejret klasse kaldet Entry.Spandplaceringen er et indeks for Entry, nemlig tabellen.
3. Den endelige hash-værdi anvendes til at finde den spandplacering, hvor Entry-objektet skal gemmes. Derefter gennemløbes nøglerne på samme måde som beskrevet i get() for at kontrollere, om nøglen allerede eksisterer, hvis den eksisterer, erstattes værdien med den nye værdi.
Else, listens størrelse kontrolleres,
Hvis den overstiger TREEIFY_THRESHOLD(standard 8), omstruktureres noderne til RedBlackTree, og den nye nøgle lagres med værdien i den.
Hvis tærsklen ikke overskrides, oprettes den nye Entry med den respektive nøgle-værdi, og lagres.
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 som i 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);
/*For at kontrollere, om TREEIFY_THRESHOLD er overskredet eller ej.*/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) { /* eksisterende mapping for key*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}++modCount;
if (++size > tærskel)
resize();
afterNodeInsertion(evict);
return null;}
Mere at læse
Nøgle uforanderlighed:
Hvorfor Strings og Integers er en god implementering af nøgler til HashMap? Mest fordi de er uforanderlige! Hvis du vælger at oprette din egen nøgleklasse og ikke gør den uforanderlig, kan du miste data inde i HashMap.
Rehashing:
Rehashing er processen med at genberegne hashkoden for allerede lagrede poster (nøgle-værdipar) for at flytte dem til en anden hashmap af større størrelse, når Load factor-tærsklen er nået.
Når antallet af elementer i kortet krydser grænsen for belastningsfaktoren, fordobles hashmap’s kapacitet på det tidspunkt, og hashkoden genberegnes for allerede lagrede elementer med henblik på en jævn fordeling af nøgle-værdipar på nye spande.
Hvorfor er det nødvendigt?
Når kapaciteten fordobles, hvad skal man så gøre med de nøgleværdipar, der allerede findes i spande?
Hvis vi beholder de eksisterende nøgleværdipar som de er, hjælper en fordobling af kapaciteten måske ikke, fordi O(1) kompleksitet kun opnås, hvis elementerne er jævnt fordelt over alle spande.
Så for hvert eksisterende nøgle-værdipar beregnes hashkoden igen med øget hashmap-kapacitet som parameter, hvilket resulterer i, at elementet enten placeres i samme spand eller i en anden spand.