streamalism.org

1. Oversigt

I denne artikel vil vi undersøge den mest populære implementering af Kort grænseflade fra Java Collections Framework mere detaljeret og fortsætter, hvor vores intro-artikel slap.

Før vi kommer i gang med implementeringen, er det vigtigt at påpege, at den primære Liste og Sæt indsamlingsgrænseflader udvides Kollektion men Kort gør ikke.

Kort sagt, den HashMap gemmer værdier efter nøgle og leverer API'er til at tilføje, hente og manipulere lagrede data på forskellige måder. Implementeringen er baseret på principperne for en hashtable, der lyder lidt kompliceret i starten, men faktisk er meget let at forstå.

Nøgleværdipar lagres i såkaldte skovle, der tilsammen udgør det, der kaldes en tabel, som faktisk er et internt array.

Når vi kender nøglen, hvorunder et objekt er gemt eller skal lagres, lagring og hentning sker i konstant tid, O (1) i et veldimensioneret hash-kort.

For at forstå, hvordan hash-kort fungerer under emhætten, skal man forstå den lagrings- og hentemekanisme, der anvendes af HashMap. Vi fokuserer meget på disse.

Langt om længe, HashMap relaterede spørgsmål er ret almindelige i interviews, så dette er en solid måde at enten forberede et interview på eller forberede sig på det.

2. Den sætte() API

For at gemme en værdi på et hash-kort kalder vi sætte API, der tager to parametre; en nøgle og den tilsvarende værdi:

V put (K-tast, V-værdi);

Når en værdi tilføjes til kortet under en nøgle, vises hashCode () API for nøgleobjektet kaldes for at hente det, der kaldes den oprindelige hash-værdi.

For at se dette i aktion, lad os oprette et objekt, der fungerer som en nøgle. Vi opretter kun en enkelt attribut, der skal bruges som en hash-kode til at simulere den første fase af hashing:

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

Vi kan nu bruge dette objekt til at kortlægge en værdi på hash-kortet:

@Test offentlig ugyldig nårHashCodeIsCalledOnPut_thenCorrect () {MyKey-nøgle = ny MyKey (1); Kortkort = nyt HashMap (); map.put (nøgle, "val"); }

Der sker ikke meget i ovenstående kode, men vær opmærksom på konsoludgangen. Faktisk hashCode metode påberåbes:

Opkald til hashCode ()

Dernæst hash () API for hash-kortet kaldes internt for at beregne den endelige hash-værdi ved hjælp af den oprindelige hash-værdi.

Denne sidste hash-værdi koger i sidste ende ned til et indeks i det interne array eller hvad vi kalder en bucket-placering.

Det hash funktion af HashMap ser sådan ud:

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

Hvad vi skal bemærke her, er kun brugen af ​​hash-koden fra nøgleobjektet til at beregne en endelig hash-værdi.

Mens du er inde i sætte funktion, bruges den endelige hash-værdi således:

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

Bemærk, at en intern putVal funktion kaldes og får den endelige hash-værdi som den første parameter.

Man kan undre sig over, hvorfor nøglen igen bruges i denne funktion, da vi allerede har brugt den til at beregne hashværdien.

Årsagen er, at hash-kort gemmer både nøgle og værdi i skovlplaceringen som en Kort. Indgang objekt.

Som tidligere omtalt udvides alle Java-samlingsrammer til interface Kollektion interface men Kort gør ikke. Sammenlign erklæringen om kortgrænseflade, vi så tidligere, med den Sæt grænseflade:

public interface Set udvider samling

Årsagen er, at kort gemmer ikke ligefrem enkeltelementer ligesom andre samlinger, men snarere en samling nøgleværdipar.

Så de generiske metoder til Kollektion interface såsom tilføje, toArray giver ikke mening, når det kommer til Kort.

Det koncept, vi har dækket i de sidste tre afsnit, skaber et af mest populære spørgsmål om Java Collections Framework-interview. Så det er værd at forstå.

En særlig attribut med hash-kortet er, at den accepterer nul værdier og nul-nøgler:

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

Når der opstår en nul-nøgle under en sætte operation tildeles den automatisk en endelig hash-værdi på 0, hvilket betyder, at det bliver det første element i den underliggende matrix.

Dette betyder også, at når nøglen er nul, er der ingen hashing-handling, og derfor er hashCode API for nøglen påberåbes ikke, og i sidste ende undgås en nul pointer-undtagelse.

Under en sætte operation, når vi bruger en nøgle, der allerede blev brugt tidligere til at gemme en værdi, returnerer den den tidligere værdi, der er knyttet til nøglen:

@Test offentlig ugyldighed givetExistingKey_whenPutReturnsPrevValue_thenCorrect () {Map map = new HashMap (); map.put ("key1", "val1"); Streng rtnVal = map.put ("key1", "val2"); assertEquals ("val1", rtnVal); }

ellers vender det tilbage nul:

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

Hvornår sætte returnerer null, det kan også betyde, at den tidligere værdi tilknyttet nøglen er null, ikke nødvendigvis at det er en ny nøgleværdikortlægning:

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

Det indeholderKey API kan bruges til at skelne mellem sådanne scenarier, som vi vil se i næste afsnit.

3. Den få API

For at hente et objekt, der allerede er gemt på hash-kortet, skal vi kende nøglen, hvorunder det blev gemt. Vi kalder få API og videregive nøgleobjektet til det:

@Test offentlig ugyldig nårGetWorks_thenCorrect () {Map map = new HashMap (); map.put ("nøgle", "val"); String val = map.get ("nøgle"); assertEquals ("val", val); }

Internt anvendes det samme hashing-princip. HashCode () API for nøgleobjektet kaldes for at opnå den oprindelige hash-værdi:

@Test offentlig ugyldig nårHashCodeIsCalledOnGet_thenCorrect () {MyKey-nøgle = ny MyKey (1); Kortkort = nyt HashMap (); map.put (nøgle, "val"); map.get (nøgle); }

Denne gang, den hashCode API af MyKey kaldes to gange; en gang for sætte og en gang for få:

Opkald til hashCode () Opkald til hashCode ()

Denne værdi genvaskes derefter ved at kalde den interne hash () API for at opnå den endelige hash-værdi.

Som vi så i det foregående afsnit, koger denne endelige hash-værdi i sidste ende ned til en bucket-placering eller et indeks for det interne array.

Værdiobjektet, der er gemt på det sted, hentes derefter og returneres til opkaldsfunktionen.

Når den returnerede værdi er nul, kan det betyde, at nøgleobjektet ikke er knyttet til nogen værdi i hash-kortet:

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

Eller det kan simpelthen betyde, at nøglen eksplicit blev kortlagt til en null-forekomst:

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

For at skelne mellem de to scenarier kan vi bruge indeholderKey API, som vi sender nøglen til, og den returnerer sandt, hvis og kun hvis der blev oprettet en kortlægning for den angivne nøgle i hash-kortet:

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

I begge tilfælde i ovenstående test er returværdien af få API-opkald er nul, men vi kan skelne, hvilken der er hvilken.

4. Samlingsudsigter i HashMap

HashMap tilbyder tre visninger, der gør det muligt for os at behandle dens nøgler og værdier som en anden samling. Vi kan få et sæt af alle tasterne på kortet:

@Test offentlig ugyldighed givenHashMap_whenRetrievesKeyset_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blog"); Indstil taster = map.keySet (); assertEquals (2, keys.size ()); assertTrue (keys.contains ("navn")); assertTrue (keys.contains ("type")); }

Sættet bakkes op af selve kortet. Så enhver ændring foretaget i sættet afspejles på kortet:

@Test offentlig ugyldighed givenKeySet_whenChangeReflectsInMap_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blog"); assertEquals (2, map.size ()); Indstil taster = map.keySet (); keys.remove ("navn"); assertEquals (1, map.size ()); }

Vi kan også få en samlingsvisning af værdierne:

@Test offentlig ugyldighed givenHashMap_whenRetrievesValues_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blog"); Samlingsværdier = map.values ​​(); assertEquals (2, values.size ()); assertTrue (values.contains ("baeldung")); assertTrue (values.contains ("blog")); }

Ligesom nøglesættet ændringer foretaget i denne samling vil blive afspejlet i det underliggende kort.

Endelig kan vi få en indstil visning af alle poster på kortet:

@Test offentlig ugyldighed givenHashMap_whenRetrievesEntries_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blog"); Sæt poster = map.entrySet (); assertEquals (2, entries.size ()); for (Indtastning e: poster)}

Husk, at et hash-kort specifikt indeholder ikke-ordnede elementer, derfor antager vi enhver rækkefølge, når vi tester nøglerne og værdierne for poster i for hver løkke.

Mange gange bruger du samlingsvisningerne i en løkke som i det sidste eksempel og mere specifikt ved hjælp af deres iteratorer.

Bare husk at iteratorer for alle ovenstående synspunkter er mislykkes hurtigt.

Hvis der foretages strukturændringer på kortet, efter at iteratoren er oprettet, kastes en samtidig ændringsundtagelse:

@Test (forventet = ConcurrentModificationException.class) offentlig ugyldighed givenIterator_whenFailsFastOnModification_thenCorrect () {Map map = new HashMap (); map.put ("navn", "baeldung"); map.put ("type", "blog"); Indstil taster = map.keySet (); Iterator it = keys.iterator (); map.remove ("type"); while (it.hasNext ()) {String key = it.next (); }}

Den eneste tilladt strukturændring er en fjerne operation udført gennem selve iteratoren:

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

Den sidste ting at huske på disse samlinger er udførelsen af ​​iterationer. Det er her, et hash-kort fungerer ret dårligt sammenlignet med dets modpartslinkede hash-kort og trækort.

Iteration over et hash-kort sker i værste fald På) hvor n er summen af ​​dens kapacitet og antallet af poster.

5. HashMap-ydeevne

Udførelsen af ​​et hash-kort påvirkes af to parametre: Indledende kapacitet og Belastningsfaktor. Kapaciteten er antallet af skovle eller den underliggende matrixlængde, og den oprindelige kapacitet er simpelthen kapaciteten under oprettelsen.

Belastningsfaktoren eller LF er kort sagt et mål for, hvor fuldt hash-kortet skal være efter tilføjelse af nogle værdier, før det ændres.

Standard startkapacitet er 16 og standardbelastningsfaktor er 0.75. Vi kan oprette et hash-kort med brugerdefinerede værdier til startkapacitet og LF:

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

Standardværdierne, der er indstillet af Java-teamet, er godt optimeret i de fleste tilfælde. Men hvis du har brug for dine egne værdier, hvilket er meget okay, skal du forstå ydeevneimplikationerne, så du ved, hvad du laver.

Når antallet af hash-kortindgange overstiger produktet af LF og kapacitet, så genvaskning forekommer dvs. en anden intern matrix oprettes med dobbelt så stor som den oprindelige, og alle poster flyttes til nye placeringer i den nye matrix.

EN lav startkapacitet reducerer pladsomkostningerne, men øger hyppigheden af ​​genopvaskning. Genopvaskning er naturligvis en meget dyr proces. Så som regel, hvis du forventer mange poster, skal du indstille en betydeligt høj startkapacitet.

På bagsiden, hvis du indstiller startkapaciteten for højt, betaler du omkostningerne i iterationstid. Som vi så i det foregående afsnit.

Så en høj startkapacitet er god for et stort antal poster kombineret med ringe eller ingen iteration.

EN lav startkapacitet er god for få poster med meget iteration.

6. Kollisioner i HashMap

En kollision, eller mere specifikt, en hash-kodekollision i en HashMap, er en situation, hvor to eller flere nøgleobjekter producerer den samme endelige hash-værdi og peg derfor på den samme skovplacering eller arrayindeks.

Dette scenario kan forekomme, fordi i henhold til lige med og hashCode kontrakt, to ulige objekter i Java kan have den samme hash-kode.

Det kan også ske på grund af den begrænsede størrelse af det underliggende array, det vil sige før størrelsesændring. Jo mindre denne matrix er, desto større er chancerne for kollision.

Når det er sagt, er det værd at nævne, at Java implementerer en hash-kode kollision opløsningsteknik, som vi vil se ved hjælp af et eksempel.

Husk, at det er hash-værdien for nøglen, der bestemmer den spand, objektet skal gemmes i. Hvis hash-koder for to nøgler kolliderer, lagres deres poster stadig i den samme spand.

Og som standard bruger implementeringen en linket liste som implementering af bucket.

Den oprindeligt konstante tid O (1)sætte og få operationer vil ske i lineær tid På) i tilfælde af en kollision. Dette skyldes, at efter at have fundet skovlplaceringen med den endelige hash-værdi, vil hver af nøglerne på dette sted blive sammenlignet med det medfølgende nøgleobjekt ved hjælp af lige med API.

For at simulere denne kollisionsopløsningsteknik, lad os ændre vores tidligere nøgleobjekt lidt:

offentlig klasse MyKey {privat strengnavn; privat int id; offentlig MyKey (int id, streng navn) {this.id = id; dette.navn = navn; } // standard getters og settere @Override public int hashCode () {System.out.println ("Calling hashCode ()"); retur-id; } // toString tilsidesættelse for smuk logning @ Override offentlige boolske lig (Objekt obj) {System.out.println ("Opkald er lig med () for nøgle:" + obj); // genereret implementering}}

Læg mærke til, hvordan vi simpelthen returnerer id attribut som hash-kode - og dermed tvinge en kollision til at forekomme.

Bemærk også, at vi har tilføjet logopgørelser i vores lige med og hashCode implementeringer - så vi ved nøjagtigt, hvornår logikken kaldes.

Lad os nu fortsætte med at gemme og hente nogle genstande, der kolliderer på et eller andet tidspunkt:

@Test offentligt ugyldigt nårCallsEqualsOnCollision_thenCorrect () {HashMap-kort = nyt HashMap (); MyKey k1 = ny MyKey (1, "firstKey"); MyKey k2 = ny MyKey (2, "secondKey"); MyKey k3 = ny MyKey (2, "thirdKey"); System.out.println ("lagringsværdi for k1"); map.put (k1, "firstValue"); System.out.println ("lagringsværdi for k2"); map.put (k2, "secondValue"); System.out.println ("lagringsværdi for k3"); map.put (k3, "thirdValue"); System.out.println ("henter værdi for k1"); Streng v1 = map.get (k1); System.out.println ("henter værdi for k2"); Streng v2 = map.get (k2); System.out.println ("henter værdi for k3"); Streng v3 = map.get (k3); assertEquals ("firstValue", v1); assertEquals ("secondValue", v2); assertEquals ("thirdValue", v3); }

I ovenstående test opretter vi tre forskellige nøgler - den ene har en unik id og de to andre har det samme id. Da vi bruger id som den oprindelige hashværdi, der vil helt sikkert være en kollision under både lagring og hentning af data med disse nøgler.

Derudover forventer vi, takket være den kollisionsopløsningsmetode, vi så tidligere, at hver af vores lagrede værdier blev hentet korrekt, dermed påstandene i de sidste tre linjer.

Når vi kører testen, skal den bestå, hvilket indikerer, at kollisioner er løst, og vi bruger den producerede logning til at bekræfte, at kollisionerne faktisk opstod:

lagring af værdi for k1 Opkald til hashCode () lagring af værdi for k2 Opkald til hashCode () lagring af værdi for k3 Opkald til hashCode () Opkald er lig med () for nøgle: MyKey [name = secondKey, id = 2] hentning af værdi til k1 Opkald til hashCode () hentning værdi for k2 Opkald til hashCode () hentningsværdi til k3 Opkald til hashCode () Opkald er lig med () for nøgle: MyKey [navn = secondKey, id = 2]

Bemærk, at under opbevaringsoperationer, k1 og k2 blev kortlagt til deres værdier ved kun at bruge hash-koden.

Dog opbevaring af k3 ikke var så simpelt, opdagede systemet, at dets skovplacering allerede indeholdt en kortlægning til k2. Derfor, lige med sammenligning blev brugt til at skelne mellem dem og en linket liste blev oprettet til at indeholde begge kortlægninger.

Enhver anden efterfølgende kortlægning, hvis nøgle hashes til den samme skovplacering, følger den samme rute og ender med at erstatte en af ​​knudepunkterne i den linkede liste eller føjes til lederen af ​​listen, hvis lige med sammenligning returnerer falsk for alle eksisterende noder.

Ligeledes under hentning, k3 og k2 var lige med-sammenlignet for at identificere den korrekte nøgle, hvis værdi skal hentes.

På en sidste note, fra Java 8, erstattes de sammenkædede lister dynamisk med afbalancerede binære søgetræer i kollisionsopløsning, efter at antallet af kollisioner i en given skovplacering overstiger en bestemt tærskel.

Denne ændring giver et ydeevne boost, da lagring og hentning sker i tilfælde af kollision O (log n).

Dette afsnit er meget almindelig i tekniske interviews, især efter de grundlæggende spørgsmål om opbevaring og hentning.

7. Konklusion

I denne artikel har vi udforsket HashMap implementering af Java Kort interface.

Den fulde kildekode til alle eksemplerne i denne artikel kan findes i GitHub-projektet.