streamalism.org

1. Prehľad

V tomto článku sa budeme zaoberať internou implementáciou LinkedHashMap trieda. LinkedHashMap je spoločná implementácia Mapa rozhranie.

Táto konkrétna implementácia je podtriedou HashMap a preto zdieľa základné stavebné prvky HashMap implementácia. Vo výsledku sa preto dôrazne odporúča oprášiť to skôr, ako budete pokračovať v tomto článku.

2. LinkedHashMap vs HashMap

The LinkedHashMap trieda je veľmi podobná HashMap vo väčšine aspektov. Prepojená hašovacia mapa je však založená na hašovacej tabuľke aj na prepojenom zozname, aby sa zlepšila funkčnosť hashovacej mapy.

Udržuje zoznam dvojnásobne prepojený, ktorý beží cez všetky jeho položky, okrem základného poľa predvolenej veľkosti 16.

Aby sa zachovalo poradie prvkov, prepojená hashmapa upravuje Mapa. ​​Vstup trieda HashMap pridaním ukazovateľov k nasledujúcemu a predchádzajúcemu záznamu:

statická trieda Entry extends HashMap.Node {Entry before, after; Entry (int hash, K key, V value, Node next) {super (hash, key, value, next); }}

Všimnite si, že Vstup trieda jednoducho pridá dva ukazovatele; predtým a po ktoré mu umožňujú pripojiť sa k prepojenému zoznamu. Okrem toho používa Vstup trieda implementácie HashMap.

Na záver nezabudnite, že tento prepojený zoznam definuje poradie iterácie, ktoré je predvolene poradie vkladania prvkov (poradie vloženia).

3. Objednávka vloženia LinkedHashMap

Pozrime sa na prepojenú inštanciu hašovacej mapy, ktorá zoradí jej položky podľa toho, ako sú vložené do mapy. Tiež zaručuje, že toto poradie bude zachované počas celého životného cyklu mapy:

@Test public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect () {LinkedHashMap mapa = nový LinkedHashMap (); map.put (1, null); map.put (2, null); map.put (3, null); map.put (4, null); map.put (5, null); Nastaviť klávesy = map.keySet (); Celé číslo [] arr = keys.toArray (nové celé číslo [0]); for (int i = 0; i <arr.length; i ++) {assertEquals (new Integer (i + 1), arr [i]); }}

Tu jednoducho robíme primárny, nezvratný test poradia záznamov na prepojenej hašovacej mape.

Môžeme zaručiť, že tento test vždy prejde, pretože objednávka vloženia bude vždy zachovaná. Nemôžeme poskytnúť rovnakú záruku pre HashMap.

Tento atribút môže byť veľkou výhodou v rozhraní API, ktoré prijíma ľubovoľné mapy, vytvára kópie na manipuláciu a vracia ich do volacieho kódu. Ak klient potrebuje, aby sa vrátená mapa objednala rovnakým spôsobom pred volaním rozhrania API, potom je k dispozícii prepojená hashmapa.

Ak je kľúč znova vložený do mapy, poradie vloženia to neovplyvní.

4. Objednávka prístupu LinkedHashMap

LinkedHashMap poskytuje špeciálny konštruktor, ktorý nám umožňuje určiť medzi vlastným koeficientom zaťaženia (LF) a počiatočnou kapacitou, iný objednávací mechanizmus / stratégia s názvom access-order:

Mapa LinkedHashMap = nová LinkedHashMap (16, .75f, true);

Prvým parametrom je počiatočná kapacita, za ktorou nasleduje faktor zaťaženia a posledným parametrom je režim objednávania. Takže okolo pravda, zapli sme objednávku prístupu, zatiaľ čo predvolená bola objednávka vloženia.

Tento mechanizmus zaisťuje, že poradie iterácie prvkov je poradie, v akom boli prvky naposledy prístupné, od najmenej nedávno sprístupnených po naposledy sprístupnené.

Takže zostavenie medzipamäte LRU (Least Nedávno použité) je s týmto typom mapy celkom jednoduché a praktické. Úspešný dať alebo dostať výsledkom operácie je prístup k záznamu:

@Test public void 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); Nastaviť klávesy = 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 ()); }

Všimnite si ako poradie prvkov v sade kľúčov sa transformuje, keď vykonávame operácie prístupu na mape.

Jednoducho povedané, akákoľvek operácia prístupu na mape má za následok poradie tak, aby sa prvok, ku ktorému sa pristupovalo, zobrazil ako posledný, ak by sa mala okamžite vykonať iterácia.

Po vyššie uvedených príkladoch by malo byť zrejmé, že a putAll operácia vygeneruje jeden vstupný prístup pre každé z mapovaní v zadanej mape.

Iterácia po zobrazení mapy prirodzene neovplyvňuje poradie iterácie podkladovej mapy; poradie ovplyvnia iba operácie explicitného prístupu na mape.

LinkedHashMap poskytuje tiež mechanizmus na udržiavanie stáleho počtu priradení a na neustále vypúšťanie najstarších záznamov v prípade, že je potrebné pridať nový.

The removeEldestEntry Môže byť prepísaná metóda na vynútenie tejto politiky automatického odstraňovania zastaraných mapovaní.

Aby sme to videli v praxi, vytvorme si našu vlastnú triedu prepojených hašovacích máp, ktorej jediným účelom je vynútiť odstránenie zastaraných mapovaní rozšírením LinkedHashMap:

verejná trieda MyLinkedHashMap rozširuje LinkedHashMap {private static final int MAX_ENTRIES = 5; public MyLinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder) {super (initialCapacity, loadFactor, accessOrder); } @Override chránený boolean removeEldestEntry (Map.Entry eldest) {návratová veľkosť ()> MAX_ENTRIES; }}

Naše vyššie uvedené prepísanie umožní rast mapy na maximálnu veľkosť 5 záznamov. Keď veľkosť presiahne túto veľkosť, každý nový záznam sa vloží za cenu straty najstaršieho záznamu na mape, t. J. Záznamu, ktorého čas posledného prístupu predchádza všetkým ostatným záznamom:

@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); Nastaviť klávesy = 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 ()); }

Všimnite si, ako najstaršie záznamy na začiatku sady kľúčov neustále klesajú, keď pridávame nové na mapu.

5. Úvahy o výkonnosti

Rovnako ako HashMap, LinkedHashMap vykonáva zákl Mapa operácie pridania, odstránenia a obsahuje v konštantnom čase, pokiaľ je hash funkcia dobre dimenzovaná. Prijíma tiež nulový kľúč aj nulové hodnoty.

Avšak toto výkon v konštantnom čase LinkedHashMap je pravdepodobne o niečo horšie ako konštantný čas HashMap kvôli zvýšenej réžii pri udržiavaní dvojnásobne prepojeného zoznamu.

Iterácia nad zobrazeniami zbierky LinkedHashMap tiež trvá lineárny čas O (n) podobné tomu z HashMap. Na opačnej strane,LinkedHashMapLineárny časový výkon počas iterácie je lepší ako HashMapLineárny čas.

Je to preto, lebo LinkedHashMap, n v O (n) je iba počet záznamov na mape bez ohľadu na kapacitu. Keďže pre HashMap, n je kapacita a zhrnutá veľkosť, O (veľkosť + kapacita).

Faktor zaťaženia a počiatočná kapacita sú definované presne ako pre HashMap. Všimnite si však, že pokuta za výber nadmerne vysokej hodnoty počiatočnej kapacity je menej prísna pre LinkedHashMap ako pre HashMap, pretože iteračné časy pre túto triedu nie sú kapacitne ovplyvnené.

6. Súbežnosť

Rovnako ako HashMap, LinkedHashMap implementácia nie je synchronizovaná. Takže ak sa k nemu chystáte pristupovať z viacerých vlákien a je pravdepodobné, že aspoň jedno z týchto vlákien to štrukturálne zmení, musí byť externe synchronizované.

Najlepšie je to urobiť pri tvorbe:

Mapa m = Collections.synchronizedMap (new LinkedHashMap ());

Rozdiel s HashMap spočíva v tom, čo znamená štrukturálnu úpravu. V prístupovo usporiadaných prepojených hašovacích mapách iba volanie na dostať Výsledkom API je štrukturálna modifikácia. Popri tom sú operácie ako dať a odstrániť.

7. Záver

V tomto článku sme preskúmali Javu LinkedHashMap triedy ako jedna z najdôležitejších implementácií Mapa užívateľské rozhranie. Preskúmali sme tiež jeho interné fungovanie z hľadiska rozdielu od HashMap čo je jeho nadtrieda.

Dúfajme, že po prečítaní tohto príspevku budete môcť prijímať informovanejšie a efektívnejšie rozhodnutia o tom, ktorú implementáciu mapy vo vašom prípade použitia použijete.

Celý zdrojový kód všetkých príkladov použitých v tomto článku nájdete v projekte GitHub.