En guide til LinkedHashMap i Java

1. Oversigt

I denne artikel skal vi undersøge den interne implementering af LinkedHashMap klasse. LinkedHashMap er en fælles implementering af Kort interface.

Denne særlige implementering er en underklasse af HashMap og deler derfor kernens byggesten i HashMap implementering. Som et resultat anbefales det stærkt at gøre noget ved det, før du fortsætter med denne artikel.

2. LinkedHashMap vs. HashMap

Det LinkedHashMap klasse er meget lig HashMap i de fleste aspekter. Det linkede hashkort er dog baseret på både hash-tabel og linket liste for at forbedre funktionaliteten af ​​hash-kort.

Den opretholder en dobbeltkoblet liste, der kører gennem alle dens poster ud over et underliggende array med standardstørrelse 16.

For at opretholde rækkefølgen af ​​elementer ændrer den sammenkædede hashmap den Kort. Indgang klasse af HashMap ved at tilføje markører til næste og forrige poster:

statisk klasse Indgang udvider HashMap.Node {Indgang før, efter; Indtastning (int-hash, K-nøgle, V-værdi, Node næste) {super (hash, nøgle, værdi, næste); }}

Bemærk, at Indgang klasse tilføjer blot to pointer; Før og efter som gør det muligt at tilslutte sig den linkede liste. Bortset fra det bruger den Indgang klasseimplementering af en HashMap.

Endelig skal du huske, at denne sammenkædede liste definerer rækkefølgen af ​​iteration, som som standard er rækkefølgen for indsættelse af elementer (insertion-order).

3. Indsætningsordre LinkedHashMap

Lad os se på en sammenkædet hash-kortforekomst, der bestiller dens poster i henhold til, hvordan de indsættes på kortet. Det garanterer også, at denne ordre opretholdes gennem kortets livscyklus:

@Test offentlig ugyldighed givenLinkedHashMap_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); Indstil taster = map.keySet (); Heltal [] arr = keys.toArray (nyt heltal [0]); for (int i = 0; i <arr.length; i ++) {assertEquals (nyt heltal (i + 1), arr [i]); }}

Her laver vi simpelthen en rudimentær, ikke-afgørende test på rækkefølgen af ​​poster i det sammenkædede hash-kort.

Vi kan garantere, at denne test altid vil bestå, da indsætningsordren altid opretholdes. Vi kan ikke stille den samme garanti for et HashMap.

Denne attribut kan være af stor fordel i en API, der modtager ethvert kort, laver en kopi til manipulation og returnerer den til opkaldskoden. Hvis klienten har brug for, at det returnerede kort bestilles på samme måde, inden han ringer til API'en, er et linket hashmap den rigtige vej.

Indføringsrækkefølgen påvirkes ikke, hvis en nøgle indsættes igen på kortet.

4. Adgangsordre LinkedHashMap

LinkedHashMap giver en speciel konstruktør, der gør det muligt for os at specificere blandt brugerdefineret belastningsfaktor (LF) og startkapacitet, en anden ordningsmekanisme / strategi kaldet adgangsordre:

LinkedHashMap-kort = nyt LinkedHashMap (16, .75f, sandt);

Den første parameter er startkapaciteten efterfulgt af belastningsfaktoren og sidste param er bestillingstilstand. Så ved at passere ind rigtigt, vi aktiverede adgangsordre, mens standard var indsættelsesordre.

Denne mekanisme sikrer, at rækkefølgen af ​​iteration af elementer er den rækkefølge, i hvilken elementerne sidst blev tilgået, fra mindst for nylig adgang til senest åbnet.

Og det er ret nemt og praktisk at opbygge en mindst-brugt (LRU) cache med denne form for kort. En vellykket sætte eller operation resulterer i en adgang til posten:

@Test offentlig ugyldighed givenLinkedHashMap_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); Indstil taster = 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 ()); }

Læg mærke til hvordan rækkefølgen af ​​elementer i nøglesættet transformeres, når vi udfører adgangsoperationer på kortet.

Kort sagt, enhver adgangsfunktion på kortet resulterer i en rækkefølge, således at det element, der blev åbnet, vises sidst, hvis en iteration skulle udføres med det samme.

Efter ovenstående eksempler skal det være indlysende, at en sæt alt operation genererer en adgangsadgang for hver af kortlægningerne på det angivne kort.

Naturligvis påvirker iteration over en visning af kortet ikke rækkefølgen af ​​iteration af backing-kortet; kun eksplicit adgangsoperationer på kortet påvirker ordren.

LinkedHashMap giver også en mekanisme til opretholdelse af et fast antal kortlægninger og til fortsat at aflevere de ældste poster, hvis en ny skal tilføjes.

Det removeEldestEntry Metoden kan tilsidesættes for at håndhæve denne politik til automatisk fjernelse af uaktuelle kortlægninger.

For at se dette i praksis, lad os oprette vores egen tilknyttede hash-kortklasse med det ene formål at håndhæve fjernelsen af ​​uaktuelle kortlægninger ved at udvide LinkedHashMap:

offentlig klasse MyLinkedHashMap udvider LinkedHashMap {privat statisk endelig int MAX_ENTRIES = 5; offentlig MyLinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder) {super (initialCapacity, loadFactor, accessOrder); } @ Override beskyttet boolesk removeEldestEntry (Map.Entry ældste) {returstørrelse ()> MAX_ENTRIES; }}

Vores tilsidesættelse ovenfor tillader, at kortet vokser til en maksimal størrelse på 5 poster. Når størrelsen overstiger dette, indsættes hver nye post på bekostning af at miste den ældste post på kortet, dvs. den post, hvis sidste adgangstid går forud for alle andre poster:

@Test offentlig ugyldighed 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); Indstil taster = 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 ()); }

Bemærk, hvordan ældste poster i starten af ​​nøglesættet fortsætter med at falde, når vi tilføjer nye til kortet.

5. Ydelsesovervejelser

Ligesom HashMap, LinkedHashMap udfører det grundlæggende Kort operationer for at tilføje, fjerne og indeholder i konstant tid, så længe hash-funktionen er godt dimensioneret. Det accepterer også en nul-nøgle såvel som nulværdier.

Men dette konstant udførelse af LinkedHashMap er sandsynligvis lidt værre end konstant-tiden for HashMap på grund af den ekstra omkostning ved opretholdelse af en dobbeltkoblet liste.

Iteration over indsamlingsudsigter over LinkedHashMap tager også lineær tid På) svarende til den af HashMap. På bagsiden,LinkedHashMap'S lineære tidsydelse under iteration er bedre end HashMap'S lineære tid.

Dette er fordi, for LinkedHashMap, n i På) er kun antallet af poster på kortet uanset kapacitet. Der henviser til, for HashMap, n er kapacitet og størrelsen opsummeret, O (størrelse + kapacitet).

Belastningsfaktor og startkapacitet defineres nøjagtigt som for HashMap. Bemærk dog, at straffen for at vælge en alt for høj værdi til startkapacitet er mindre alvorlig for LinkedHashMap end for HashMap, da iterationstider for denne klasse ikke påvirkes af kapacitet.

6. Samtidighed

Ligesom HashMap, LinkedHashMap implementeringen er ikke synkroniseret. Så hvis du vil få adgang til det fra flere tråde, og mindst en af ​​disse tråde sandsynligvis vil ændre det strukturelt, så skal det synkroniseres eksternt.

Det er bedst at gøre dette ved oprettelsen:

Kort m = Collections.synchronizedMap (nyt LinkedHashMap ());

Forskellen med HashMap ligger i, hvad der indebærer en strukturændring. I adgangsbestilt sammenkædede hash-kort, blot ved at kalde API resulterer i en strukturændring. Ved siden af ​​dette er operationer som sætte og fjerne.

7. Konklusion

I denne artikel har vi udforsket Java LinkedHashMap klasse som en af ​​de førende implementeringer af Kort interface med hensyn til brug. Vi har også undersøgt dets interne funktion med hensyn til forskellen fra HashMap hvilket er dens superklasse.

Forhåbentlig kan du efter at have læst dette indlæg træffe mere informerede og effektive beslutninger om, hvilken kortimplementering du skal bruge i din brugssag.

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


$config[zx-auto] not found$config[zx-overlay] not found