streamalism.org

1. Oversikt

I denne artikkelen skal vi utforske den interne implementeringen av LinkedHashMap klasse. LinkedHashMap er en vanlig implementering av Kart grensesnitt.

Denne spesielle implementeringen er en underklasse av HashMap og deler derfor kjernebyggesteinene i HashMap gjennomføring. Som et resultat anbefales det på det sterkeste å pusse opp det før du fortsetter med denne artikkelen.

2. LinkedHashMap vs. HashMap

De LinkedHashMap klasse er veldig lik HashMap i de fleste aspekter. Det tilknyttede hash-kartet er imidlertid basert på både hash-tabell og koblet liste for å forbedre funksjonaliteten til hash-kartet.

Den opprettholder en dobbeltkoblet liste som går gjennom alle oppføringene i tillegg til et underliggende utvalg av standardstørrelse 16.

For å opprettholde rekkefølgen på elementene endrer den tilknyttede hashmap den Kart. Inngang klasse av HashMap ved å legge til pekere til neste og forrige oppføring:

statisk klasse Oppføring utvider HashMap.Node {Oppføring før, etter; Oppføring (int-hash, K-tast, V-verdi, Node neste) {super (hash, nøkkel, verdi, neste); }}

Legg merke til at Inngang klasse legger bare til to pekere; før og etter som gjør det mulig å koble seg til den koblede listen. Bortsett fra det bruker den Inngang klasseimplementering av en HashMap.

Til slutt, husk at denne koblede listen definerer rekkefølgen på iterasjon, som som standard er rekkefølgen for innsetting av elementer (innsettingsrekkefølge).

3. Innsettingsordre LinkedHashMap

La oss se på en koblet hash-kartforekomst som bestiller oppføringene i henhold til hvordan de settes inn i kartet. Det garanterer også at denne ordren vil opprettholdes gjennom hele livssyklusen til kartet:

@Test offentlig ugyldighet gittLinkedHashMap_whenGetsOrderedKeyset_thenCorrect () {LinkedHashMap map = new LinkedHashMap (); map.put (1, null); map.put (2, null); map.put (3, null); map.put (4, null); map.put (5, null); Sett nøkler = map.keySet (); Heltall [] arr = keys.toArray (nytt Heltall [0]); for (int i = 0; i <arr.length; i ++) {assertEquals (new Integer (i + 1), arr [i]); }}

Her lager vi ganske enkelt en rudimentær, ikke-avgjørende test på rekkefølgen av oppføringer i det tilknyttede hash-kartet.

Vi kan garantere at denne testen alltid vil bestå da innsettingsrekkefølgen alltid vil opprettholdes. Vi kan ikke gi den samme garantien for et HashMap.

Denne egenskapen kan være av stor fordel i et API som mottar et hvilket som helst kart, lager en kopi for å manipulere og returnerer den til ringekoden. Hvis klienten trenger at det returnerte kartet skal bestilles på samme måte før han ringer API, er en koblet hashmap veien å gå.

Innføringsrekkefølgen påvirkes ikke hvis en nøkkel settes inn på nytt på kartet.

4. Tilgangsordre LinkedHashMap

LinkedHashMap gir en spesiell konstruktør som gjør det mulig for oss å spesifisere, blant tilpasset lastfaktor (LF) og startkapasitet, en annen ordningsmekanisme / strategi som kalles tilgangsordre:

LinkedHashMap-kart = nytt LinkedHashMap (16, .75f, sant);

Den første parameteren er startkapasiteten, etterfulgt av lastfaktoren og siste param er bestillingsmodus. Så ved å passere inn ekte, vi slo på tilgangsordre, mens standard var innsettingsordre.

Denne mekanismen sørger for at rekkefølgen på iterasjon av elementer er den rekkefølgen elementene sist ble åpnet, fra minst nylig tilgjengelige til nylig tilgjengelige.

Og det er ganske enkelt og praktisk å bygge en LRU-hurtigbuffer (LRU) med denne typen kart. En vellykket sette eller få operasjonen resulterer i en tilgang for oppføringen:

@Test offentlig ugyldighet gittLinkedHashMap_whenAccessOrderWorks_thenCorrect () {LinkedHashMap map = new LinkedHashMap (16, .75f, true); map.put (1, null); map.put (2, null); map.put (3, null); map.put (4, null); map.put (5, null); Sett nøkler = map.keySet (); assertEquals ("[1, 2, 3, 4, 5]", keys.toString ()); map.get (4); assertEquals ("[1, 2, 3, 5, 4]", keys.toString ()); map.get (1); assertEquals ("[2, 3, 5, 4, 1]", keys.toString ()); map.get (3); assertEquals ("[2, 5, 4, 1, 3]", keys.toString ()); }

Legg merke til hvordan rekkefølgen av elementene i nøkkelsettet transformeres når vi utfører tilgangsoperasjoner på kartet.

Enkelt sagt, enhver tilgangsoperasjon på kartet resulterer i en rekkefølge slik at elementet som ble åpnet, ville vises sist hvis en iterasjon skulle utføres med en gang.

Etter eksemplene ovenfor bør det være åpenbart at a putt alle operasjonen genererer en oppføringstilgang for hver av tilordningene i det angitte kartet.

Naturligvis påvirker iterasjon over en visning av kartet ikke rekkefølgen av iterasjon av backing-kartet; bare eksplisitte tilgangsoperasjoner på kartet vil påvirke bestillingen.

LinkedHashMap gir også en mekanisme for å opprettholde et fast antall kartlegginger og å fortsette å slippe av de eldste oppføringene i tilfelle en ny må legges til.

De removeEldestEntry metoden kan overstyres for å håndheve denne policyen for automatisk fjerning av foreldede kartlegginger.

For å se dette i praksis, la oss lage vår egen tilknyttede hash-kartklasse, med det ene formål å håndheve fjerning av foreldede kartlegginger ved å utvide LinkedHashMap:

offentlig klasse MyLinkedHashMap utvider LinkedHashMap {privat statisk slutt int MAX_ENTRIES = 5; offentlig MyLinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder) {super (initialCapacity, loadFactor, accessOrder); } @ Override-beskyttet boolsk removeEldestEntry (Map.Entry eldst) {returstørrelse ()> MAX_ENTRIES; }}

Overstyringen vår over vil tillate at kartet vokser til en maksimumsstørrelse på 5 oppføringer. Når størrelsen overstiger det, vil hver nye oppføring bli satt inn på bekostning av å miste den eldste oppføringen på kartet, dvs. oppføringen hvis siste tilgangstid går foran alle de andre oppføringene:

@Test public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect () {LinkedHashMap map = new MyLinkedHashMap (16, .75f, true); map.put (1, null); map.put (2, null); map.put (3, null); map.put (4, null); map.put (5, null); Sett nøkler = map.keySet (); assertEquals ("[1, 2, 3, 4, 5]", keys.toString ()); map.put (6, null); assertEquals ("[2, 3, 4, 5, 6]", keys.toString ()); map.put (7, null); assertEquals ("[3, 4, 5, 6, 7]", keys.toString ()); map.put (8, null); assertEquals ("[4, 5, 6, 7, 8]", keys.toString ()); }

Legg merke til hvordan eldste oppføringer i begynnelsen av nøkkelsettet fortsetter å falle når vi legger til nye på kartet.

5. Ytelseshensyn

Akkurat som HashMap, LinkedHashMap utfører det grunnleggende Kart operasjoner for å legge til, fjerne og inneholder i konstant tid, så lenge hash-funksjonen er godt dimensjonert. Den aksepterer også en nullnøkkel samt nullverdier.

Imidlertid dette konstant ytelse av LinkedHashMap er sannsynligvis litt verre enn konstant-tiden til HashMap på grunn av ekstra omkostninger for å opprettholde en dobbeltkoblet liste.

Iterasjon over samling visninger av LinkedHashMap tar også lineær tid På) ligner på HashMap. På den andre siden,LinkedHashMap’S lineære ytelse under iterasjon er bedre enn HashMap’S lineær tid.

Dette er fordi, for LinkedHashMap, n i På) er bare antall oppføringer på kartet uavhengig av kapasitet. Mens, for HashMap, n er kapasitet og størrelsen oppsummert, O (størrelse + kapasitet).

Lastfaktor og startkapasitet er definert nøyaktig som for HashMap. Vær imidlertid oppmerksom på at straffen for å velge en for høy verdi for startkapasiteten er mindre alvorlig for LinkedHashMap enn for HashMap, ettersom iterasjonstidene for denne klassen ikke påvirkes av kapasiteten.

6. Samtidighet

Akkurat som HashMap, LinkedHashMap implementering er ikke synkronisert. Så hvis du skal få tilgang til den fra flere tråder og minst en av disse trådene sannsynligvis vil endre den strukturelt, så må den være eksternt synkronisert.

Det er best å gjøre dette ved opprettelsen:

Kart m = Collections.synchronizedMap (ny LinkedHashMap ());

Forskjellen med HashMap ligger i det som innebærer en strukturendring. I tilgangsbestilte koblede hash-kart, bare ringe få API resulterer i en strukturendring. Ved siden av dette er operasjoner som sette og fjerne.

7. Konklusjon

I denne artikkelen har vi utforsket Java LinkedHashMap klasse som en av de fremste implementeringene av Kart grensesnitt når det gjelder bruk. Vi har også utforsket dets interne funksjoner når det gjelder forskjellen fra HashMap som er superklassen.

Forhåpentligvis, etter å ha lest dette innlegget, kan du ta mer informerte og effektive beslutninger om hvilken kartimplementering du skal bruke i din brukstilfelle.

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