Java HashMap under panseret

1. Oversikt

I denne artikkelen skal vi utforske den mest populære implementeringen av Kart grensesnitt fra Java Collections Framework mer detaljert, og plukket opp der introartikkelen vår slapp.

Før vi begynner med implementeringen, er det viktig å påpeke at den primære Liste og Sett samlingsgrensesnitt utvides Samling men Kart gjør ikke.

Enkelt sagt, den HashMap lagrer verdier etter nøkkel og gir APIer for å legge til, hente og manipulere lagrede data på forskjellige måter. Gjennomføringen er basert på prinsippene til en hashtable, som i utgangspunktet høres litt komplisert ut, men faktisk er veldig lett å forstå.

Nøkkelverdipar er lagret i såkalte bøtter som til sammen utgjør det som kalles en tabell, som faktisk er en intern matrise.

Når vi vet nøkkelen som et objekt lagres under eller skal lagres under, lagring og henting skjer i konstant tid, O (1) i et godt dimensjonert hash-kart.

For å forstå hvordan hash-kart fungerer under panseret, må man forstå lagrings- og hentemekanismen som brukes av HashMap. Vi vil fokusere mye på disse.

Endelig, HashMap relaterte spørsmål er ganske vanlige i intervjuer, så dette er en solid måte å enten forberede et intervju eller forberede seg på det.

2. Den sette() API

For å lagre en verdi i et hash-kart, kaller vi sette API som tar to parametere; en nøkkel og den tilsvarende verdien:

V put (K-tast, V-verdi);

Når en verdi legges til på kartet under en nøkkel, vises hashCode () API for nøkkelobjektet kalles for å hente det som kalles den første hashverdien.

For å se dette i aksjon, la oss lage et objekt som vil fungere som en nøkkel. Vi vil bare lage et enkelt attributt som skal brukes som hash-kode for å simulere den første fasen av hashing:

offentlig klasse MyKey {privat int id; @ Override public int hashCode () {System.out.println ("Calling hashCode ()"); retur id; } // konstruktør, settere og getters}

Vi kan nå bruke dette objektet til å kartlegge en verdi i hash-kartet:

@Test offentlig ugyldig nårHashCodeIsCalledOnPut_thenCorrect () {MyKey key = new MyKey (1); Kartkart = nytt HashMap (); map.put (nøkkel, "val"); }

Det skjer ikke mye i koden ovenfor, men vær oppmerksom på konsollutgangen. Faktisk hashCode metoden blir påkalt:

Ringer til hashCode ()

Neste, den hasj () API for hash-kart kalles internt for å beregne den endelige hash-verdien ved hjelp av den opprinnelige hash-verdien.

Denne endelige hashverdien koker til slutt ned til en indeks i den interne matrisen eller det vi kaller en bøtteplassering.

De hasj funksjon av HashMap ser slik ut:

statisk slutt int hash (Objektnøkkel) {int h; returnere (nøkkel == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); }

Det vi bør merke oss her er bare bruk av hash-koden fra nøkkelobjektet for å beregne en endelig hash-verdi.

Mens du er inne i sette funksjon, blir den endelige hashverdien brukt slik:

public V put (K key, V value) {return putVal (hash (key), key, value, false, true); }

Legg merke til at en intern putVal funksjonen blir kalt og gitt den endelige hashverdien som den første parameteren.

Man kan lure på hvorfor nøkkelen igjen brukes i denne funksjonen siden vi allerede har brukt den til å beregne hashverdien.

Årsaken er at hash-kart lagrer både nøkkel og verdi i bøtteplasseringen som en Kart. Inngang gjenstand.

Som diskutert tidligere, utvides alle rammegrensesnitt for Java-samlinger Samling grensesnitt men Kart gjør ikke. Sammenlign erklæringen om kartgrensesnitt vi så tidligere med den Sett grensesnitt:

offentlig grensesnitt Set utvider samlingen

Årsaken er at kart lagrer ikke akkurat enkeltelementer som andre samlinger, men heller en samling nøkkelverdipar.

Så de generiske metodene for Samling grensesnitt som legge til, toArray ikke gi mening når det gjelder Kart.

Konseptet vi har dekket i de siste tre avsnittene, gir et av mest populære spørsmål om Java Collections Framework. Så det er verdt å forstå.

En spesiell egenskap med hash-kartet er at den godtar null verdier og nulltaster:

@Test offentlig ugyldig givenNullKeyAndVal_whenAccepts_thenCorrect () {Map map = new HashMap (); map.put (null, null); }

Når det oppstår en nullnøkkel under en sette operasjonen tildeles den automatisk den endelige hashverdien på 0, noe som betyr at det blir det første elementet i den underliggende matrisen.

Dette betyr også at når nøkkelen er null, er det ingen hashingoperasjon, og derfor blir hashCode API for nøkkelen blir ikke påkalt, og til slutt unngås et unntak for nullpeker.

I løpet av en sette Når vi bruker en nøkkel som allerede ble brukt til å lagre en verdi, returnerer den den forrige verdien som er knyttet til nøkkelen:

@Test offentlig ugyldig gittExistingKey_whenPutReturnsPrevValue_thenCorrect () {Map map = new HashMap (); map.put ("nøkkel1", "val1"); Streng rtnVal = map.put ("key1", "val2"); assertEquals ("val1", rtnVal); }

ellers kommer den tilbake null:

@Test public void givenNewKey_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); Streng rtnVal = map.put ("key1", "val1"); assertNull (rtnVal); }

Når sette returnerer null, det kan også bety at den forrige verdien knyttet til nøkkelen er null, ikke nødvendigvis at det er en ny nøkkelverdikartlegging:

@Test offentlig ugyldighet givenNullVal_whenPutReturnsNull_thenCorrect () {Map map = new HashMap (); Streng rtnVal = map.put ("key1", null); assertNull (rtnVal); }

De inneholder nøkkel API kan brukes til å skille mellom slike scenarier som vi vil se i neste underavsnitt.

3. Den API

For å hente et objekt som allerede er lagret i hash-kartet, må vi vite nøkkelen det ble lagret under. Vi kaller API og send nøkkelobjektet til det:

@Test offentlig ugyldig når GetWorks_thenCorrect () {Map map = new HashMap (); map.put ("nøkkel", "val"); Streng val = map.get ("nøkkel"); assertEquals ("val", val); }

Internt brukes det samme hashing-prinsippet. HashCode () API til nøkkelobjektet kalles for å oppnå den opprinnelige hashverdien:

@Test offentlig ugyldig nårHashCodeIsCalledOnGet_thenCorrect () {MyKey key = new MyKey (1); Kartkart = nytt HashMap (); map.put (nøkkel, "val"); map.get (nøkkel); }

Denne gangen, den hashCode API av Nøkkelen min kalles to ganger; en gang for sette og en gang for :

Ringer til hashCode () Ringer til hashCode ()

Denne verdien vaskes deretter ved å ringe den interne hasj () API for å oppnå den endelige hashverdien.

Som vi så i forrige avsnitt, koker denne endelige hashverdien til slutt ned til en bøtteplassering eller en indeks for den interne matrisen.

Verdiobjektet som er lagret på dette stedet blir deretter hentet og returnert til anropsfunksjonen.

Når den returnerte verdien er null, kan det bety at nøkkelobjektet ikke er knyttet til noen verdi i hash-kartet:

@Test offentlig ugyldighet gittUnmappedKey_whenGetReturnsNull_thenCorrect () {Map map = new HashMap (); Streng rtnVal = map.get ("key1"); assertNull (rtnVal); }

Eller det kan ganske enkelt bety at nøkkelen eksplisitt ble kartlagt til en null forekomst:

@Test offentlig ugyldighet givenNullVal_whenRetrieves_thenCorrect () {Map map = new HashMap (); map.put ("nøkkel", null); Streng val = map.get ("nøkkel"); assertNull (val); }

For å skille mellom de to scenariene kan vi bruke inneholder nøkkel API, som vi sender nøkkelen til, og den returnerer sant hvis og bare hvis en kartlegging ble opprettet for den angitte nøkkelen i hash-kartet:

@Test offentlig ugyldig nårContainsDistinguishesNullValues_thenCorrect () {Map map = new HashMap (); Streng val1 = map.get ("nøkkel"); boolsk valPresent = map.containsKey ("nøkkel"); assertNull (val1); assertFalse (valPresent); map.put ("nøkkel", null); Streng val = map.get ("nøkkel"); valPresent = map.containsKey ("nøkkel"); assertNull (val); assertTrue (valPresent); }

For begge tilfeller i testen ovenfor er returverdien av API-anrop er null, men vi kan skille hvilken som er hvilken.

4. Samlingsvisning i HashMap

HashMap tilbyr tre visninger som gjør det mulig for oss å behandle nøklene og verdiene som en annen samling. Vi kan få et sett med alle tastene på kartet:

@Test offentlig ugyldig gittHashMap_whenRetrievesKeyset_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blogg"); Sett taster = map.keySet (); assertEquals (2, keys.size ()); assertTrue (keys.contains ("navn")); assertTrue (keys.contains ("type")); }

Settet er støttet av selve kartet. Så endringer i settet gjenspeiles i kartet:

@Test offentlig tomrom gittKeySet_whenChangeReflectsInMap_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blogg"); assertEquals (2, map.size ()); Sett taster = map.keySet (); keys.remove ("navn"); assertEquals (1, map.size ()); }

Vi kan også få en samlingsvisning av verdiene:

@Test offentlig ugyldighet gittHashMap_whenRetrievesValues_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blogg"); Samlingsverdier = map.values ​​(); assertEquals (2, values.size ()); assertTrue (values.contains ("baeldung")); assertTrue (values.contains ("blogg")); }

Akkurat som nøkkelsettet, hvilken som helst endringer som er gjort i denne samlingen vil gjenspeiles i det underliggende kartet.

Endelig kan vi få en angi visning av alle oppføringene på kartet:

@Test offentlig ugyldig givenHashMap_whenRetrievesEntries_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blogg"); Sett oppføringer = map.entrySet (); assertEquals (2, entries.size ()); for (Oppføring e: oppføringer)}

Husk at et hash-kart spesifikt inneholder ikke-ordnede elementer, derfor antar vi hvilken som helst rekkefølge når vi tester nøklene og verdiene til oppføringene i for hver Løkke.

Mange ganger vil du bruke samlingsvisningene i en løkke som i det siste eksemplet, og mer spesifikt ved hjelp av iteratorene deres.

Bare husk at iteratorer for alle ovennevnte synspunkter er mislykkes raskt.

Hvis det gjøres noen strukturendringer på kartet, etter at iteratoren er opprettet, vil et samtidig modifikasjons unntak bli kastet:

@Test (forventet = ConcurrentModificationException.class) offentlig ugyldig givenIterator_whenFailsFastOnModification_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blogg"); Sett taster = map.keySet (); Iterator it = keys.iterator (); map.remove ("type"); while (it.hasNext ()) {Strengnøkkel = it.next (); }}

Den eneste tillatt strukturendring er en fjerne operasjon utført gjennom selve iteratoren:

public void givenIterator_whenRemoveWorks_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blogg"); Sett nøkler = map.keySet (); Iterator it = keys.iterator (); mens (it.hasNext ()) {it.next (); it.remove (); } assertEquals (0, map.size ()); }

Den siste tingen å huske på disse samlingsvisningene er utførelsen av iterasjoner. Det er her et hash-kart fungerer ganske dårlig sammenlignet med dets motparter knyttet hash-kart og trekart.

Iterasjon over et hash-kart skjer i verste fall På) hvor n er summen av kapasiteten og antall oppføringer.

5. HashMap-ytelse

Ytelsen til et hash-kart påvirkes av to parametere: Startkapasitet og Lastfaktor. Kapasiteten er antall bøtter eller den underliggende matriselengden, og den opprinnelige kapasiteten er ganske enkelt kapasiteten under opprettelsen.

Lastfaktoren eller LF er kort sagt et mål på hvor full hash-kartet skal være etter å ha lagt til noen verdier før det endres.

Standard startkapasitet er 16 og standard belastningsfaktor er 0.75. Vi kan lage et hash-kart med egendefinerte verdier for startkapasitet og LF:

Kart hashMapWithCapacity = ny HashMap (32); Kart hashMapWithCapacityAndLF = ny HashMap (32, 0.5f);

Standardverdiene satt av Java-teamet er godt optimalisert for de fleste tilfeller. Men hvis du trenger å bruke dine egne verdier, noe som er veldig greit, må du forstå ytelsesimplikasjonene slik at du vet hva du gjør.

Når antall hash-kartoppføringer overstiger produktet av LF og kapasitet, da gjenvask forekommer dvs. en annen intern matrise opprettes med dobbelt så stor som den opprinnelige, og alle oppføringene flyttes til nye bøtteplasser i den nye matrisen.

EN lav startkapasitet reduserer plasskostnad, men øker hyppigheten av gjenvasking. Rehashing er åpenbart en veldig kostbar prosess. Så hvis du forventer mange oppføringer, bør du som regel sette en betydelig høy startkapasitet.

På baksiden, hvis du angir startkapasiteten for høy, betaler du kostnadene i iterasjonstid. Som vi så i forrige avsnitt.

en høy startkapasitet er bra for et stort antall oppføringer kombinert med liten eller ingen iterasjon.

EN lav startkapasitet er bra for få oppføringer med mye iterasjon.

6. Kollisjoner i HashMap

En kollisjon, eller mer spesifikt, en hash-kodekollisjon i en HashMap, er en situasjon der to eller flere nøkkelobjekter produserer den samme endelige hashverdien og pek derfor til samme bøtteplassering eller matriseindeks.

Dette scenariet kan oppstå fordi i henhold til er lik og hashCode kontrakt, to ulike objekter i Java kan ha samme hash-kode.

Det kan også skje på grunn av den endelige størrelsen på den underliggende matrisen, det vil si før du endrer størrelsen. Jo mindre denne matrisen er, desto større er sjansene for kollisjon.

Når det er sagt, er det verdt å nevne at Java implementerer en teknikk for oppløsning av hash-kode, som vi vil se ved hjelp av et eksempel.

Husk at det er hashverdien til nøkkelen som bestemmer bøtta objektet skal lagres i. Hvis hasjkodene til to tastene kolliderer, vil oppføringene deres fortsatt bli lagret i samme bøtte.

Som standard bruker implementeringen en koblet liste som implementering av bøtter.

Den opprinnelige konstante tiden O (1)sette og operasjoner vil skje i lineær tid På) i tilfelle en kollisjon. Etter at du har funnet bøtteplasseringen med den endelige hashverdien, vil hver av tastene på dette stedet bli sammenlignet med det oppgitte nøkkelobjektet ved hjelp av er lik API.

For å simulere denne oppløsningsteknikken, la oss endre vårt tidligere nøkkelobjekt litt:

offentlig klasse MyKey {privat strengnavn; privat int id; offentlig MyKey (int id, strengnavn) {this.id = id; this.name = navn; } // standard getters og settere @Override public int hashCode () {System.out.println ("Calling hashCode ()"); retur id; } // toString overstyring for pen logging @ Override offentlige boolske lik (Objekt obj) {System.out.println ("Ringer tilsvarer () for nøkkel:" + obj); // generert implementering}}

Legg merke til hvordan vi bare returnerer id attributt som hash-koden - og dermed tvinge en kollisjon til å oppstå.

Vær også oppmerksom på at vi har lagt til logguttalelser i vår er lik og hashCode implementeringer - slik at vi vet nøyaktig når logikken kalles.

La oss nå fortsette å lagre og hente noen gjenstander som kolliderer på et tidspunkt:

@Test offentlig ugyldig nårCallsEqualsOnCollision_thenCorrect () {HashMap map = new HashMap (); MyKey k1 = nye MyKey (1, "firstKey"); MyKey k2 = nye MyKey (2, "secondKey"); MyKey k3 = nye MyKey (2, "thirdKey"); System.out.println ("lagringsverdi for k1"); map.put (k1, "firstValue"); System.out.println ("lagringsverdi for k2"); map.put (k2, "secondValue"); System.out.println ("lagringsverdi for k3"); map.put (k3, "thirdValue"); System.out.println ("henter verdi for k1"); Streng v1 = map.get (k1); System.out.println ("henter verdi for k2"); Streng v2 = map.get (k2); System.out.println ("henter verdi for k3"); Streng v3 = map.get (k3); assertEquals ("firstValue", v1); assertEquals ("secondValue", v2); assertEquals ("thirdValue", v3); }

I testen ovenfor oppretter vi tre forskjellige nøkler - en har en unik id og de to andre har det samme id. Siden vi bruker id som den første hashverdien, det vil definitivt være en kollisjon både under lagring og henting av data med disse nøklene.

I tillegg til det, takket være kollisjonsoppløsningsteknikken vi så tidligere, forventer vi at hver av våre lagrede verdier blir hentet riktig, derav påstandene i de tre siste linjene.

Når vi kjører testen, skal den bestå, noe som indikerer at kollisjoner ble løst, og vi vil bruke loggføringen som er produsert for å bekrefte at kollisjonene faktisk har skjedd:

lagrer verdi for k1 Ringer hashCode () lagrer verdi for k2 Ringer hashCode () lagrer verdi for k3 Ringer hashCode () Ringer tilsvarer () for nøkkel: MyKey [navn = secondKey, id = 2] henter verdi for k1 Ringer hashCode () henting verdi for k2 Ringer hashCode () henter verdi for k3 Ringer hashCode () Ringer tilsvarer () for nøkkel: MyKey [navn = secondKey, id = 2]

Legg merke til at under lagringsoperasjoner, k1 og k2 ble vellykket tilordnet sine verdier ved hjelp av bare hash-koden.

Imidlertid lagring av k3 ikke var så enkelt, oppdaget systemet at bøtteplasseringen allerede inneholdt en kartlegging for k2. Derfor, er lik sammenligning ble brukt for å skille dem ut og en lenket liste ble opprettet for å inneholde begge kartlegginger.

Enhver annen påfølgende kartlegging hvis nøkkel hashes til samme bøtteplassering, følger samme rute og ender med å erstatte en av nodene i den koblede listen eller legges til lederen av listen hvis er lik sammenligning returnerer falsk for alle eksisterende noder.

Likeledes under henting, k3 og k2 var er lik-sammenlignet for å identifisere riktig nøkkel hvis verdi skal hentes.

Til slutt, fra Java 8, erstattes de lenkede listene dynamisk med balanserte binære søketrær i kollisjonsoppløsning etter at antall kollisjoner i en gitt bøtteplassering overstiger en viss terskel.

Denne endringen gir et ytelsesløft, siden lagring og henting skjer i tilfelle kollisjon O (log n).

Denne delen er veldig vanlig i tekniske intervjuer, spesielt etter de grunnleggende spørsmålene om lagring og henting.

7. Konklusjon

I denne artikkelen har vi utforsket HashMap implementering av Java Kart grensesnitt.

Den fullstendige kildekoden for alle eksemplene som brukes i denne artikkelen finner du i GitHub-prosjektet.