En guide til Java HashMap
1. Oversigt
I denne artikel vil vi se, hvordan du bruger HashMap i Java, og vi vil se på, hvordan det fungerer internt.
En klasse, der ligner meget HashMap er Hashtable. Se et par af vores andre artikler for at lære mere om java.util.Hashtable klassen selv og forskellene mellem HashMap og Hashtable.
2. Grundlæggende anvendelse
Lad os først se på, hvad det betyder det HashMap er et kort. Et kort er en nøgleværdikortlægning, hvilket betyder, at hver nøgle kortlægges til nøjagtigt en værdi, og at vi kan bruge nøglen til at hente den tilsvarende værdi fra et kort.
Man kan spørge, hvorfor ikke blot tilføje værdien til en liste. Hvorfor har vi brug for en HashMap? Den enkle årsag er ydeevne. Hvis vi vil finde et bestemt element på en liste, er tidskompleksiteten På) og hvis listen er sorteret, vil den være O (log n) ved hjælp af for eksempel en binær søgning.
Fordelen ved en HashMap er, at tidskompleksiteten for at indsætte og hente en værdi er O (1) gennemsnitlig. Vi ser på, hvordan det kan opnås senere. Lad os først se på, hvordan du bruger HashMap.
2.1. Opsætning
Lad os oprette en simpel klasse, som vi bruger i hele artiklen:
offentlig klasse Produkt {privat strengnavn; privat streng beskrivelse; private List tags; // standard getters / setters / constructors public Product addTagsOfOtherProdcut (Product product) {this.tags.addAll (product.getTags ()); returner dette; }}2.2. Sætte
Vi kan nu oprette en HashMap med nøglen af typen Snor og elementer af typen Produkt:
Kortlæg produkterByName = nyt HashMap (); Og tilføj produkter til vores HashMap:
Produkt eBike = nyt produkt ("E-Bike", "En cykel med batteri"); Produkt roadBike = nyt produkt ("Racercykel", "En cykel til konkurrence"); productsByName.put (eBike.getName (), eBike); productsByName.put (roadBike.getName (), roadBike); 2.3. Få
Vi kan hente en værdi fra kortet ved hjælp af dens nøgle:
Produkt nextPurchase = productsByName.get ("E-Bike"); assertEquals ("En cykel med et batteri", nextPurchase.getDescription ());Hvis vi forsøger at finde en værdi til en nøgle, der ikke findes på kortet, får vi en nul værdi:
Produkt nextPurchase = productsByName.get ("bil"); assertNull (nextPurchase);Og hvis vi indsætter en anden værdi med den samme nøgle, får vi kun den sidst indsatte værdi for den nøgle:
Produkt newEBike = nyt produkt ("E-Bike", "En cykel med bedre batteri"); productsByName.put (newEBike.getName (), newEBike); assertEquals ("En cykel med et bedre batteri", productsByName.get ("E-Bike"). getDescription ());2.4. Null som nøglen
HashMap tillader os også at have nul som en nøgle:
Produkt defaultProduct = nyt produkt ("Chokolade", "I det mindste køb chokolade"); productsByName.put (null, defaultProduct); Produkt nextPurchase = productsByName.get (null); assertEquals ("I det mindste købe chokolade", nextPurchase.getDescription ());2.5. Værdier med samme nøgle
Desuden kan vi indsætte det samme objekt to gange med en anden nøgle:
productsByName.put (defaultProduct.getName (), defaultProduct); assertSame (productsByName.get (null), productsByName.get ("Chokolade"));2.6. Fjern en værdi
Vi kan fjerne en nøgleværdikortlægning fra HashMap:
productsByName.remove ("E-Bike"); assertNull (productsByName.get ("E-Bike"));2.7. Kontroller, om der findes en nøgle eller værdi på kortet
For at kontrollere, om en nøgle er til stede på kortet, kan vi bruge indeholderKey () metode:
productsByName.containsKey ("E-Bike");Eller for at kontrollere, om der er en værdi på kortet, kan vi bruge indeholder værdi () metode:
productsByName.containsValue (eBike);Begge metodeopkald vender tilbage rigtigt i vores eksempel. Selvom de ser meget ens ud, er der en vigtig forskel i ydeevne mellem disse to metodeopkald. Kompleksiteten til at kontrollere, om der findes en nøgle, er O (1), mens kompleksiteten til at kontrollere et element er På), da det er nødvendigt at sløjfe over alle elementerne på kortet.
2.8. Itererer over en HashMap
Der er tre grundlæggende måder at gentage over alle nøgleværdipar i a HashMap.
Vi kan gentage sæt af alle taster:
for (String key: productsByName.keySet ()) {Product product = productsByName.get (key); }Eller vi kan gentage sæt af alle poster:
for (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); Strengnøgle = entry.getKey (); // gør noget med nøglen og værdien}Endelig kan vi gentage alle værdier:
Vis produkter = ny ArrayList (productsByName.values ());3. Nøglen
Vi kan bruge enhver klasse som nøglen i vores HashMap. For at kortet skal fungere korrekt, er vi dog nødt til at give en implementering til lige med() og hashCode ().Lad os sige, at vi vil have et kort med produktet som nøgle og prisen som værdi:
HashMap priceByProduct = ny HashMap (); priceByProduct.put (eBike, 900);Lad os implementere lige med() og hashCode () metoder:
@ Override offentlige boolske er lig med (Objekt o) {hvis (dette == o) {returner sandt; } hvis (o == null || getClass ()! = o.getClass ()) {returner false; } Produktprodukt = (Produkt) o; returnere Objects.equals (navn, produkt.navn) && Objects.equals (beskrivelse, produkt.beskrivelse); } @ Override public int hashCode () {return Objects.hash (navn, beskrivelse); }Noter det hashCode () og lige med() behøver kun at blive tilsidesat for klasser, som vi vil bruge som kortnøgler, ikke for klasser, der kun bruges som værdier på et kort. Vi får se, hvorfor dette er nødvendigt i afsnit 5 i denne artikel.
4. Yderligere metoder fra Java 8
Java 8 tilføjede flere metoder til funktionel stil til HashMap. I dette afsnit vil vi se på nogle af disse metoder.
For hver metode ser vi på to eksempler. Det første eksempel viser, hvordan man bruger den nye metode, og det andet eksempel viser, hvordan man opnår det samme i tidligere versioner af Java.
Da disse metoder er ret ligetil, ser vi ikke på mere detaljerede eksempler.
4.1. for hver()
Det for hver metode er den funktionelle måde at gentage alle elementer på kortet:
productsByName.forEach ((nøgle, produkt) -> {System.out.println ("Nøgle:" + nøgle + "Produkt:" + product.getDescription ()); // gør noget med nøglen og værdien}); Før Java 8:
for (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); Strengnøgle = entry.getKey (); // gør noget med nøglen og værdien}Vores artikel Guide til Java 8 for hver dækker for hver loop mere detaljeret.
4.2. getOrDefault ()
Bruger getOrDefault () metode, kan vi få en værdi fra kortet eller returnere et standardelement, hvis der ikke er nogen kortlægning for den givne nøgle:
Produktchokolade = nyt produkt ("chokolade", "noget sødt"); Produkt defaultProduct = productsByName.getOrDefault ("hestevogn", chokolade); Produktcykel = productsByName.getOrDefault ("E-cykel", chokolade);Før Java 8:
Produkt cykel2 = productsByName.containsKey ("E-cykel")? productsByName.get ("E-Bike"): chokolade; Produkt defaultProduct2 = productsByName.containsKey ("hestevogn")? productsByName.get ("hestevogn"): chokolade; 4.3. putIfAbsent ()
Med denne metode kan vi tilføje en ny kortlægning, men kun hvis der endnu ikke er en kortlægning for den givne nøgle:
productsByName.putIfAbsent ("E-Bike", chokolade); Før Java 8:
if (productsByName.containsKey ("E-Bike")) {productsByName.put ("E-Bike", chokolade); }Vores artikel Fletning af to kort med Java 8 ser nærmere på denne metode.
4.4. fusionere()
Og med fusionere(), Vi kan ændre værdien for en given nøgle, hvis der findes en kortlægning, eller tilføje en ny værdi ellers:
Produkt eBike2 = nyt produkt ("E-Bike", "En cykel med batteri"); eBike2.getTags (). tilføj ("sport"); productsByName.merge ("E-Bike", eBike2, Produkt :: addTagsOfOtherProdcut);Før Java 8:
if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } andet {productsByName.put ("E-Bike", eBike2); } 4.5. beregne ()
Med beregne () metode, kan vi beregne værdien for en given nøgle:
productsByName.compute ("E-Bike", (k, v) -> {if (v! = null) {return v.addTagsOfOtherProdcut (eBike2);} ellers {return eBike2;}});Før Java 8:
if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } andet {productsByName.put ("E-Bike", eBike2); } Det er værd at bemærke, at metoder fusionere() og beregne () er meget ens. Det beregne () metode accepterer to argumenter: nøgle og en BiFunction til omlægningen. Og fusionere() accepterer tre parametre: nøgle, a standard værdi for at føje til kortet, hvis nøglen ikke findes endnu, og a BiFunction til omlægningen.
5. HashMap Internals
I dette afsnit vil vi se på, hvordan HashMap fungerer internt, og hvad er fordelene ved at bruge HashMap i stedet for en simpel liste, for eksempel.
Som vi har set, kan vi hente et element fra en HashMap ved dens nøgle. En tilgang ville være at bruge en liste, gentage alle elementer og vende tilbage, når vi finder et element, som nøglen matcher med. Både tid og rumkompleksitet af denne tilgang ville være På).
Med HashMap, kan vi opnå en gennemsnitlig tidskompleksitet på O (1) til sætte og få operationer og rumkompleksitet af På). Lad os se, hvordan det fungerer.
5.1. Hash-koden og lige
I stedet for at gentage alle dets elementer, HashMap forsøger at beregne placeringen af en værdi baseret på dens nøgle.
Den naive tilgang ville være at have en liste, der kan indeholde så mange elementer, som der er nøgler mulige. Lad os som et eksempel sige, at vores nøgle er små bogstaver. Så er det tilstrækkeligt at have en liste over størrelse 26, og hvis vi vil have adgang til elementet med nøglen 'c', ville vi vide, at det er den i position 3, og vi kan hente det direkte.
Denne tilgang ville dog ikke være særlig effektiv, hvis vi har et meget større nøgleområde. Lad os for eksempel sige, at vores nøgle var et heltal. I dette tilfælde skal størrelsen på listen være 2.147.483.647. I de fleste tilfælde ville vi også have langt færre elementer, så en stor del af den tildelte hukommelse forbliver ubrugt.
HashMap gemmer elementer i såkaldte spande, og antallet af spande kaldes kapacitet.
Når vi lægger en værdi på kortet, er nøglerne hashCode () metoden bruges til at bestemme den skovl, hvor værdien skal gemmes.
For at hente værdien, HashMap beregner skovlen på samme måde - ved hjælp af hashCode (). Derefter gentager det sig gennem objekterne, der findes i den spand, og brug nøgler lige med() metode til at finde det nøjagtige match.
5.2. Tasternes uforanderlighed
I de fleste tilfælde skal vi bruge uforanderlige nøgler. Eller i det mindste skal vi være opmærksomme på konsekvenserne af at bruge ændrede nøgler.
Lad os se, hvad der sker, når vores nøgle ændres, efter at vi har brugt den til at gemme en værdi på et kort.
I dette eksempel opretter vi MutableKey:
offentlig klasse MutableKey {privat strengnavn; // standardkonstruktør, getter og setter @Override offentlige boolske lig (Objekt o) {hvis (dette == o) {returner sand; } hvis (o == null || getClass ()! = o.getClass ()) {returner false; } MutableKey that = (MutableKey) o; returnere Objects.equals (navn, det.navn); } @ Override public int hashCode () {return Objects.hash (name); }}Og her går testen:
MutableKey-nøgle = ny MutableKey ("initial"); Kortelementer = nyt HashMap (); items.put (nøgle, "succes"); key.setName ("ændret"); assertNull (items.get (key));Som vi kan se, er vi ikke længere i stand til at få den tilsvarende værdi, når nøglen er ændret, i stedet for nul returneres. Dette er fordi HashMap søger i den forkerte spand.
Ovenstående testsag kan være overraskende, hvis vi ikke har en god forståelse af hvordan HashMap arbejder internt.
5.3. Kollisioner
For at dette kan fungere korrekt, skal lige nøgler have samme hash, men forskellige nøgler kan have samme hash. Hvis to forskellige taster har samme hash, gemmes de to værdier, der hører til dem, i den samme skovl. Inde i en spand gemmes værdier på en liste og hentes ved at løkke over alle elementer. Omkostningerne ved dette er På).
Fra Java 8 (se JEP 180) ændres datastrukturen, hvori værdierne i en spand er gemt, fra en liste til et afbalanceret træ, hvis en spand indeholder 8 eller flere værdier, og den ændres tilbage til en liste, hvis nogle punkter er der kun 6 værdier tilbage i skovlen. Dette forbedrer den ydelse, der skal være O (log n).
5.4. Kapacitet og belastningsfaktor
For at undgå at have mange skovle med flere værdier fordobles kapaciteten, hvis 75% (belastningsfaktoren) af skovlene bliver tomme. Standardværdien for belastningsfaktoren er 75%, og den oprindelige startkapacitet er 16. Begge kan indstilles i konstruktøren.
5.5. Resumé af sætte og få Operationer
Lad os sammenfatte, hvordan sætte og få operationer fungerer.
Når vi tilføjer et element til kortet,HashMap beregner spanden. Hvis skovlen allerede indeholder en værdi, føjes værdien til listen (eller træet), der hører til skovlen. Hvis belastningsfaktoren bliver større end kortets maksimale belastningsfaktor, fordobles kapaciteten.
Når vi ønsker at få en værdi fra kortet,HashMap beregner skovlen og får værdien med den samme nøgle fra listen (eller træet).
6. Konklusion
I denne artikel så vi, hvordan man bruger en HashMap og hvordan det fungerer internt. Sammen med ArrayList, HashMap er en af de hyppigst anvendte datastrukturer i Java, så det er meget praktisk at have god viden om, hvordan man bruger det, og hvordan det fungerer under emhætten. Vores artikel Java HashMap under hætte dækker det indre af HashMap mere detaljeret.
Som sædvanlig er den komplette kildekode tilgængelig på Github.
