streamalism.org

1. Áttekintés

Ebben a cikkben megvizsgáljuk a LinkedHashMap osztály. LinkedHashMap közös megvalósítása Térkép felület.

Ez a konkrét megvalósítás a HashMap és ezért osztozik a HashMap végrehajtás. Ennek eredményeként erősen ajánlott ezt a cikket folytatni.

2. LinkedHashMap vs. HashMap

A LinkedHashMap osztály nagyon hasonlít a HashMap a legtöbb szempontból. A csatolt hash-térkép azonban mind a hash-táblán, mind a linkelt listán alapul, hogy javítsa a hash map funkcionalitását.

Kétszer összekapcsolt listát tart fenn, amely az alapértelmezett 16 méretű tömb mellett az összes bejegyzését végigfuttatja.

Az elemek sorrendjének fenntartása érdekében a csatolt hashmap módosítja az Térkép. Belépés Osztálya HashMap mutatók hozzáadásával a következő és az előző bejegyzésekhez:

static class Entry kiterjeszti a HashMap.Node {Entry before, after; Bejegyzés (int hash, K kulcs, V érték, csomópont következő) {super (hash, kulcs, érték, következő); }}

Figyeljük meg, hogy a Belépés osztály egyszerűen hozzáad két mutatót; előtt és utána amelyek lehetővé teszik, hogy bekapcsolódjon a linkelt listába. Ettől eltekintve a Belépés osztályú megvalósítása a HashMap.

Végül ne feledje, hogy ez a összekapcsolt lista meghatározza az iteráció sorrendjét, amely alapértelmezés szerint az elemek beszúrási sorrendje (beszúrási sorrend).

3. Beszúrási sorrend LinkedHashMap

Vessen egy pillantást egy összekapcsolt hash térképpéldányra, amely a bejegyzéseket a térképbe illesztésük szerint rendezi. Ez garantálja azt is, hogy ez a sorrend megmarad a térkép teljes életciklusa alatt:

@Test public void 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); Set keys = map.keySet (); Egész szám [] arr = keys.toArray (új egész szám [0]); for (int i = 0; i <arr.length; i ++) {assertEquals (új egész szám (i + 1), arr [i]); }}

Itt egyszerűen egy kezdetleges, nem meggyőző tesztet hajtunk végre a linkelt hash térkép bejegyzéseinek sorrendjében.

Garantálhatjuk, hogy ez a teszt mindig sikeres lesz, mivel a beszúrási sorrend mindig fennmarad. Nem tehetünk ugyanezt a garanciát egy HashMap-ra.

Ez az attribútum nagy előnyt jelenthet egy olyan API-ban, amely bármilyen térképet kap, másolatot készít a manipulálásra és visszaadja a hívó kódnak. Ha az ügyfélnek szüksége van a visszaküldött térkép megrendelésére ugyanúgy, mielőtt meghívja az API-t, akkor egy összekapcsolt hashmap a helyes út.

A behelyezési sorrendet ez nem érinti, ha egy kulcsot újra beillesztenek a térképbe.

4. Hozzáférés-Rendelés LinkedHashMap

LinkedHashMap egy speciális konstruktort biztosít, amely lehetővé teszi számunkra, hogy az egyedi terhelési tényező (LF) és a kezdeti kapacitás között meghatározzuk, egy másik rendelési mechanizmus / stratégia, az úgynevezett hozzáférés-rend:

LinkedHashMap map = új LinkedHashMap (16, .75f, true);

Az első paraméter a kezdeti kapacitás, majd a terhelési tényező és a utolsó param a rendelési mód. Tehát, átadással igaz, bekapcsoltuk a hozzáférési sorrendet, míg az alapértelmezett a beillesztési sorrend volt.

Ez a mechanizmus biztosítja, hogy az elemek iterációs sorrendje legyen az a sorrend, amelyben az elemeket utoljára, a legkevésbé a legutóbb elérte.

Ezért a legkevésbé használt (LRU) gyorsítótár létrehozása meglehetősen egyszerű és praktikus egy ilyen térképpel. Egy sikeres tedd vagy kap művelet hozzáférést eredményez a bejegyzéshez:

@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); Set keys = map.keySet (); assertEquals ("[1, 2, 3, 4, 5]", kulcsok.String ()); map.get (4); assertEquals ("[1, 2, 3, 5, 4]", kulcsok.String ()); map.get (1); assertEquals ("[2, 3, 5, 4, 1]", kulcsok.String ()); map.get (3); assertEquals ("[2, 5, 4, 1, 3]", kulcsok.String ()); }

Figyelje meg, hogyan a kulcskészlet elemeinek sorrendje átalakul, amikor a térképen hozzáférési műveleteket hajtunk végre.

Egyszerűen fogalmazva: a térkép bármely hozzáférési művelete olyan sorrendet eredményez, hogy az az elem, amelyhez hozzáfértek, utoljára jelenik meg, ha egy iterációt azonnal végrehajtanak.

A fenti példák után nyilvánvalónak kell lennie, hogy a putAll művelet egy belépési hozzáférést generál a megadott térkép minden hozzárendeléséhez.

Természetesen az iteráció a térkép nézetében nem befolyásolja a háttértér iterációs sorrendjét; csak a térképen történő kifejezett hozzáférési műveletek befolyásolják a sorrendet.

LinkedHashMap mechanizmust is biztosít rögzített számú leképezés fenntartásához, és a legrégebbi bejegyzések folyamatos elhagyásához, ha újat kell hozzáadni.

A removeEldestEntry metódus felülbírálható ennek a házirendnek az érvényesítéséhez az elavult leképezések automatikus eltávolításához.

Hogy ezt a gyakorlatban lássuk, hozzunk létre saját összekapcsolt hash map osztályt, amelynek egyetlen célja az elavult leképezések eltávolításának kikényszerítése azáltal, hogy kiterjesztjük LinkedHashMap:

public class MyLinkedHashMap kiterjeszti a LinkedHashMap {private static final int MAX_ENTRIES = 5; public MyLinkedHashMap (int kezdetiCapacity, float loadFactor, boolean accessOrder) {super (initialCapacity, loadFactor, accessOrder); } @Orride védett logikai érték eltávolításaEldestEntry (Map.Entry eldest) {return size ()> MAX_ENTRIES; }}

A fenti felülírás lehetővé teszi, hogy a térkép legfeljebb 5 bejegyzésre nőjön. Ha a méret meghaladja ezt, minden új bejegyzést be kell illeszteni a térkép legidősebb bejegyzésének elvesztése árán, vagyis az a bejegyzés, amelynek utolsó hozzáférési ideje megelőzi az összes többi bejegyzést:

@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); Set keys = map.keySet (); assertEquals ("[1, 2, 3, 4, 5]", kulcsok.String ()); map.put (6, null); assertEquals ("[2, 3, 4, 5, 6]", billentyűk.String ()); map.put (7, null); assertEquals ("[3, 4, 5, 6, 7]", billentyűk.String ()); map.put (8, null); assertEquals ("[4, 5, 6, 7, 8]", kulcsok.String ()); }

Figyelje meg, hogy a kulcskészlet elején lévő legrégebbi bejegyzések folyamatosan csökkennek, amikor újakat adunk a térképhez.

5. Teljesítmény szempontok

Mint HashMap, LinkedHashMap elvégzi az alap Térkép az összeadás, az eltávolítás és az állandó időben történő műveletek, mindaddig, amíg a hash függvény jól méretezett. Ezenkívül elfogad egy null kulcsot és null értékeket is.

Ez azonban állandó idejű teljesítménye LinkedHashMap valószínűleg kissé rosszabb, mint a konstans ideje HashMap a kétszeresen összekapcsolt lista fenntartásának többletköltségei miatt.

Ismétlés a LinkedHashMap lineáris időt is igénybe vesz Tovább) hasonló a HashMap. Másik oldalán,LinkedHashMapA lineáris időteljesítmény az iteráció során jobb, mint HashMapLineáris ideje.

Ez azért van, mert LinkedHashMap, n ban ben Tovább) csak a bejegyzések száma a térképen, a kapacitástól függetlenül. Mivel HashMap, n a kapacitás és a méret összegezve, O (méret + kapacitás).

A terhelési tényezőt és a kezdeti kapacitást pontosan úgy definiálják, mint a HashMap. Ne feledje azonban a kezdeti kapacitás túlzottan magas értékének megválasztása esetén a büntetés kevésbé szigorú LinkedHashMap mint a HashMap, mivel ennek az osztálynak az iterációs idejét a kapacitás nem befolyásolja.

6. Egyidejűség

Mint HashMap, LinkedHashMap a megvalósítás nincs szinkronizálva. Tehát, ha több szálból kívánja elérni, és ezek közül legalább az egyik valószínűleg strukturálisan megváltoztatja, akkor azt külsőleg szinkronizálni kell.

A legjobb, ha ezt a létrehozáskor teszed:

Map m = Collections.synchronizedMap (új LinkedHashMap ());

A különbség a HashMap abban rejlik, ami strukturális módosítást von maga után. A hozzáférés sorrendjében összekapcsolt hash térképeken pusztán a kap Az API strukturális módosítást eredményez. Mellette vannak olyan műveletek, mint tedd és eltávolítani.

7. Következtetés

Ebben a cikkben feltártuk a Java-t LinkedHashMap osztály az egyik legfontosabb megvalósítása Térkép felület a használat szempontjából. Felfedeztük a belső működését is a különbség szempontjából HashMap ami a szuperosztálya.

Remélhetőleg, miután elolvasta ezt a bejegyzést, megalapozottabb és hatékonyabb döntéseket hozhat arról, hogy melyik Map-megvalósítást alkalmazza az Ön esetére.

A cikkben használt összes példa teljes forráskódja megtalálható a GitHub projektben.