streamalism.org

1. Oversikt

I denne artikkelen vil vi se hvordan du bruker HashMap i Java, og vi vil se på hvordan det fungerer internt.

En klasse veldig lik HashMap er Hashtable. Se et par av våre andre artikler for å lære mer om java.util.Hashtable klassen selv og forskjellene mellom HashMap og Hashtable.

2. Grunnleggende bruk

La oss først se på hva det betyr det HashMap er et kart. Et kart er en nøkkelverdikartlegging, noe som betyr at hver nøkkel blir kartlagt til nøyaktig en verdi, og at vi kan bruke nøkkelen til å hente den tilsvarende verdien fra et kart.

Man kan spørre hvorfor ikke bare legge verdien til en liste. Hvorfor trenger vi en HashMap? Den enkle grunnen er ytelse. Hvis vi vil finne et bestemt element i en liste, er tidskompleksiteten På) og hvis listen er sortert, blir den det O (log n) ved hjelp av for eksempel et binært søk.

Fordelen med en HashMap er at tidskompleksiteten for å sette inn og hente en verdi er O (1) gjennomsnittlig. Vi ser på hvordan det kan oppnås senere. La oss først se på hvordan du bruker HashMap.

2.1. Oppsett

La oss lage en enkel klasse som vi bruker gjennom hele artikkelen:

offentlig klasse Produkt {privat strengnavn; privat strengbeskrivelse; private liste koder; // standard getters / setters / constructors public Product addTagsOfOtherProdcut (Product product) {this.tags.addAll (product.getTags ()); returner dette; }}

2.2. Sette

Vi kan nå lage en HashMap med nøkkelen av typen String og elementer av typen Produkt:

Kartlegg produkterByName = ny HashMap (); 

Og legg til produkter i vår HashMap:

Produkt eBike = nytt produkt ("E-Bike", "En sykkel med batteri"); Produkt roadBike = nytt produkt ("landeveissykkel", "en sykkel for konkurranse"); productsByName.put (eBike.getName (), eBike); productsByName.put (roadBike.getName (), roadBike); 

2.3. Få

Vi kan hente en verdi fra kartet ved hjelp av nøkkelen:

Produkt nextPurchase = productsByName.get ("E-Bike"); assertEquals ("En sykkel med batteri", nextPurchase.getDescription ());

Hvis vi prøver å finne en verdi for en nøkkel som ikke finnes på kartet, får vi en null verdi:

Produkt nextPurchase = productsByName.get ("Car"); assertNull (nesteKjøp);

Og hvis vi setter inn en andre verdi med samme nøkkel, får vi bare den siste satte inn verdien for den nøkkelen:

Produkt newEBike = nytt produkt ("E-Bike", "En sykkel med bedre batteri"); productsByName.put (newEBike.getName (), newEBike); assertEquals ("En sykkel med bedre batteri", productsByName.get ("E-Bike"). getDescription ());

2.4. Null som nøkkelen

HashMap tillater oss også å ha null som en nøkkel:

Produkt defaultProduct = nytt produkt ("Sjokolade", "I det minste kjøp sjokolade"); productsByName.put (null, defaultProduct); Produkt nextPurchase = productsByName.get (null); assertEquals ("I det minste kjøpe sjokolade", nextPurchase.getDescription ());

2.5. Verdier med samme nøkkel

Videre kan vi sette inn det samme objektet to ganger med en annen nøkkel:

productsByName.put (defaultProduct.getName (), defaultProduct); assertSame (productsByName.get (null), productsByName.get ("Chocolate"));

2.6. Fjern en verdi

Vi kan fjerne en nøkkelverdikartlegging fra HashMap:

productsByName.remove ("E-Bike"); assertNull (productsByName.get ("E-Bike"));

2.7. Sjekk om det finnes en nøkkel eller verdi i kartet

For å sjekke om en nøkkel er til stede på kartet, kan vi bruke inneholderKey () metode:

productsByName.containsKey ("E-Bike");

Eller for å sjekke om det er en verdi på kartet, kan vi bruke inneholder verdi () metode:

productsByName.containsValue (eBike);

Begge metodeanropene kommer tilbake ekte i vårt eksempel. Selv om de ser veldig like ut, er det en viktig forskjell i ytelse mellom disse to metodeanropene. Kompleksiteten for å sjekke om en nøkkel eksisterer er O (1), mens kompleksiteten å sjekke for et element er På), da det er nødvendig å løpe over alle elementene på kartet.

2.8. Iterere over en HashMap

Det er tre grunnleggende måter å gjenta over alle nøkkelverdipar i a HashMap.

Vi kan gjenta over settet med alle nøkler:

for (String key: productsByName.keySet ()) {Product product = productsByName.get (key); }

Eller vi kan gjenta over settet med alle oppføringer:

for (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); Strengnøkkel = entry.getKey (); // gjør noe med nøkkelen og verdien}

Til slutt kan vi gjenta alle verdier:

Liste produkter = ny ArrayList (productsByName.values ​​());

3. Nøkkelen

Vi kan bruke hvilken som helst klasse som nøkkelen i vår HashMap. For at kartet skal fungere skikkelig, må vi imidlertid gi en implementering for er lik() og hashCode ().La oss si at vi vil ha et kart med produktet som nøkkel og prisen som verdi:

HashMap priceByProduct = ny HashMap (); priceByProduct.put (eBike, 900);

La oss implementere er lik() og hashCode () metoder:

@ Override offentlig boolsk er lik (Objekt o) {hvis (dette == o) {returner sant; } hvis (o == null || getClass ()! = o.getClass ()) {return false; } Produktprodukt = (Produkt) o; returner Objects.equals (navn, produkt.navn) && Objects.equals (beskrivelse, produkt.beskrivelse); } @Override public int hashCode () {return Objects.hash (navn, beskrivelse); }

Noter det hashCode () og er lik() må kun overstyres for klasser som vi vil bruke som kartnøkler, ikke for klasser som bare brukes som verdier i et kart. Vi får se hvorfor dette er nødvendig i avsnitt 5 i denne artikkelen.

4. Ytterligere metoder fra Java 8

Java 8 la til flere funksjonelle metoder HashMap. I denne delen vil vi se på noen av disse metodene.

For hver metode ser vi på to eksempler. Det første eksemplet viser hvordan du bruker den nye metoden, og det andre eksemplet viser hvordan du oppnår det samme i tidligere versjoner av Java.

Siden disse metodene er ganske greie, vil vi ikke se på mer detaljerte eksempler.

4.1. for hver()

De for hver metoden er den funksjonelle måten å gjenta over alle elementene i kartet:

productsByName.forEach ((nøkkel, produkt) -> {System.out.println ("Nøkkel:" + nøkkel + "Produkt:" + produkt.getDescription ()); // gjør noe med nøkkel og verdi}); 

Før Java 8:

for (Map.Entry entry: productsByName.entrySet ()) {Product product = entry.getValue (); Strengnøkkel = entry.getKey (); // gjør noe med nøkkelen og verdien}

Vår artikkel Guide til Java 8 for hver dekker for hver løkke mer detaljert.

4.2. getOrDefault ()

Bruker getOrDefault () metode, kan vi få en verdi fra kartet eller returnere et standardelement i tilfelle det ikke er noen kartlegging for den gitte nøkkelen:

Produkt sjokolade = nytt produkt ("sjokolade", "noe søtt"); Produkt defaultProduct = productsByName.getOrDefault ("hestevogn", sjokolade); Produktsykkel = productsByName.getOrDefault ("E-Bike", sjokolade);

Før Java 8:

Produkt bike2 = productsByName.containsKey ("E-Bike")? productsByName.get ("E-Bike"): sjokolade; Produkt defaultProduct2 = productsByName.containsKey ("hestevogn")? productsByName.get ("hestevogn"): sjokolade; 

4.3. putIfAbsent ()

Med denne metoden kan vi legge til en ny kartlegging, men bare hvis det ennå ikke er en kartlegging for den gitte nøkkelen:

productsByName.putIfAbsent ("E-Bike", sjokolade); 

Før Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.put ("E-Bike", sjokolade); }

Artikkelen vår Sammenslåing av to kart med Java 8 ser nærmere på denne metoden.

4.4. slå sammen()

Og med slå sammen(), vi kan endre verdien for en gitt nøkkel hvis en kartlegging eksisterer, eller legge til en ny verdi ellers:

Produkt eBike2 = nytt produkt ("E-Bike", "En sykkel med batteri"); eBike2.getTags (). add ("sport"); productsByName.merge ("E-Bike", eBike2, Produkt :: addTagsOfOtherProdcut);

Før Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } annet {productsByName.put ("E-Bike", eBike2); } 

4.5. beregne ()

Med beregne () metode, kan vi beregne verdien for en gitt nøkkel:

productsByName.compute ("E-Bike", (k, v) -> {if (v! = null) {return v.addTagsOfOtherProdcut (eBike2);} else {return eBike2;}});

Før Java 8:

if (productsByName.containsKey ("E-Bike")) {productsByName.get ("E-Bike"). addTagsOfOtherProdcut (eBike2); } annet {productsByName.put ("E-Bike", eBike2); } 

Det er verdt å merke seg at metoder slå sammen() og beregne () er ganske like. De beregne () metode godtar to argumenter: nøkkel og en BiFunction for kartleggingen. Og slå sammen() godtar tre parametere: nøkkel, a standardverdi for å legge til på kartet hvis nøkkelen ikke finnes ennå, og a BiFunction for kartleggingen.

5. HashMap Internals

I denne delen vil vi se på hvordan HashMap fungerer internt og hva er fordelene med å bruke HashMap i stedet for en enkel liste, for eksempel.

Som vi har sett, kan vi hente et element fra a HashMap ved nøkkelen. En tilnærming ville være å bruke en liste, gjenta over alle elementene og komme tilbake når vi finner et element som nøkkelen samsvarer med. Både tid og romkompleksitet av denne tilnærmingen ville være På).

Med HashMap, kan vi oppnå en gjennomsnittlig tidskompleksitet på O (1) for sette og få operasjoner og romkompleksitet av På). La oss se hvordan det fungerer.

5.1. Hash-koden og lik

I stedet for å gjentatte over alle elementene, HashMap prøver å beregne posisjonen til en verdi basert på nøkkelen.

Den naive tilnærmingen ville være å ha en liste som kan inneholde så mange elementer som det er mulige nøkler. La oss si et eksempel, at nøkkelen er en liten bokstav. Da er det tilstrekkelig å ha en liste over størrelse 26, og hvis vi vil ha tilgang til elementet med nøkkelen ‘c’, vil vi vite at det er den i posisjon 3, og vi kan hente den direkte.

Denne tilnærmingen vil imidlertid ikke være veldig effektiv hvis vi har et mye større tastatur. La oss for eksempel si at nøkkelen vår var et helt tall. I dette tilfellet vil størrelsen på listen måtte være 2.147.483.647. I de fleste tilfeller vil vi også ha langt færre elementer, så en stor del av det tildelte minnet vil forbli ubrukt.

HashMap lagrer elementer i såkalte bøtter og antall bøtter kalles kapasitet.

Når vi setter en verdi i kartet, er nøkkelen hashCode () metoden brukes til å bestemme skuffen som verdien skal lagres i.

For å hente verdien, HashMap beregner skuffen på samme måte - ved hjelp av hashCode (). Deretter går det gjennom gjenstandene som finnes i den bøtta, og bruk nøklene er lik() metode for å finne nøyaktig samsvar.

5.2. Keys 'uforanderlighet

I de fleste tilfeller bør vi bruke uforanderlige nøkler. Eller i det minste må vi være klar over konsekvensene av å bruke foranderlige nøkler.

La oss se hva som skjer når nøkkelen vår endres etter at vi brukte den til å lagre en verdi på et kart.

For dette eksemplet oppretter vi MutableKey:

offentlig klasse MutableKey {privat strengnavn; // standardkonstruktør, getter og setter @Override offentlige boolske lik (Object o) {if (this == o) {return true; } hvis (o == null || getClass ()! = o.getClass ()) {return false; } MutableKey that = (MutableKey) o; returner Objects.equals (navn, det.navnet); } @ Override public int hashCode () {return Objects.hash (name); }}

Og her går testen:

MutableKey key = new MutableKey ("initial"); Kartelementer = nytt HashMap (); items.put (nøkkel, "suksess"); key.setName ("endret"); assertNull (items.get (key));

Som vi kan se, er vi ikke lenger i stand til å få den tilsvarende verdien når nøkkelen er endret, i stedet for, null blir returnert. Dette er fordi HashMap søker i feil bøtte.

Ovennevnte testtilfelle kan være overraskende hvis vi ikke har en god forståelse av hvordan HashMap jobber internt.

5.3. Kollisjoner

For at dette skal fungere riktig, må like taster ha samme hash, men forskjellige nøkler kan ha samme hash. Hvis to forskjellige nøkler har samme hasj, lagres de to verdiene som tilhører dem i samme bøtte. Inne i en bøtte lagres verdiene i en liste og hentes ved å løkke over alle elementene. Kostnaden for dette er På).

Fra og med Java 8 (se JEP 180), endres datastrukturen der verdiene i en bøtte er lagret fra en liste til et balansert tre hvis en bøtte inneholder 8 eller flere verdier, og den blir endret tilbake til en liste hvis, ved noen poeng er det bare 6 verdier igjen i bøtta. Dette forbedrer ytelsen å være O (log n).

5.4. Kapasitet og lastfaktor

For å unngå å ha mange skuffer med flere verdier, blir kapasiteten doblet hvis 75% (lastfaktoren) av skuffene blir tomme. Standardverdien for lastfaktoren er 75%, og standard startkapasitet er 16. Begge kan stilles inn i konstruktøren.

5.5. Sammendrag av sette og få Operasjoner

La oss oppsummere hvordan sette og få drift fungerer.

Når vi legger til et element på kartet,HashMap beregner bøtta. Hvis skuffen allerede inneholder en verdi, legges verdien til i listen (eller treet) som tilhører skuffen. Hvis lastfaktoren blir større enn kartets maksimale lastfaktor, dobles kapasiteten.

Når vi ønsker å få en verdi fra kartet,HashMap beregner skuffen og får verdien med samme nøkkel fra listen (eller treet).

6. Konklusjon

I denne artikkelen så vi hvordan du bruker en HashMap og hvordan det fungerer internt. Sammen med ArrayList, HashMap er en av de mest brukte datastrukturene i Java, så det er veldig nyttig å ha god kunnskap om hvordan du bruker den og hvordan den fungerer under panseret. Vår artikkel The Java HashMap Under the Hood dekker det indre av HashMap i mer detalj.

Som vanlig er den komplette kildekoden tilgjengelig på Github.