streamalism.org

1. Bemutatkozás

Ebben a cikkben kettőt fogunk összehasonlítani Térkép megvalósítások: TreeMap és HashMap.

Mindkét megvalósítás a Java szerves részét képezi Gyűjtemények Keret és tárolja az adatokat kulcs érték párok.

2. Különbségek

2.1. Végrehajtás

Először a HashMap ami hashtable-alapú megvalósítás. Kiterjeszti a AbstractMap osztály és végrehajtja a Térkép felület. A HashMap elvén működik hash.

Ez Térkép a megvalósítás általában sávként működik hash asztal, de ha a vödrök túl nagyok lesznek, azok csomópontokká alakulnak TreeNodes, mindegyik hasonlóan van felépítve, mint a java.util.TreeMap.

További információt a HashMap's a cikk belső elemei erre összpontosítottak.

Másrészről, TreeMap kiterjed AbstractMap osztály és eszközei NavigableMap felület. A TreeMap térképelemeket tárol a Piros fekete fa, amely a Önkiegyensúlyozó Bináris keresési fa.

És további információkat talál a TreeMap's a cikk belső elemei itt erre összpontosítottak.

2.2. Rendelés

HashMap nem nyújt garanciát az elemek elrendezésére Térkép.

Azt jelenti, sorrendet nem vállalhatunk az ismétlés közben kulcsok és értékek a HashMap:

@Test public void whenInsertObjectsHashMap_thenRandomOrder () {Map hashmap = new HashMap (); hashmap.put (3, "TreeMap"); hashmap.put (2, "vs"); hashmap.put (1, "HashMap"); assertThat (hashmap.keySet (), tartalmazzaInAnyOrder (1, 2, 3)); }

Azonban az a TreeMap vannak természetes rendjük szerint válogatva.

Ha TreeMap az objektumok nem rendezhetők természetes sorrend szerint, akkor használhatjuk a Összehasonlító vagy Hasonló az elemek sorrendjének meghatározása az Térkép:

@Test public void whenInsertObjectsTreeMap_thenNaturalOrder () {Map treemap = new TreeMap (); treemap.put (3, "TreeMap"); treemap.put (2, "vs"); treemap.put (1, "HashMap"); assertThat (treemap.keySet (), tartalmazza (1, 2, 3)); }

2.3. Nulla Értékek

HashMap legfeljebb egy tárolást tesz lehetővé nullakulcs és sok nulla értékek.

Lássunk egy példát:

@Test public void whenInsertNullInHashMap_thenInsertsNull () {Map hashmap = new HashMap (); hashmap.put (null, null); assertNull (hashmap.get (null)); }

Azonban, TreeMap nem engedélyezi a nullakulcs de sokakat tartalmazhat nulla értékek.

A nulla kulcs nem engedélyezett, mert a összehasonlítani() vagy a összehasonlít () módszer dob a NullPointerException:

@Test (várható = NullPointerException.class) public void whenInsertNullInTreeMap_thenException () {Map treemap = new TreeMap (); treemap.put (null, "NullPointerException"); }

Ha a TreeMap egy felhasználó által definiált Összehasonlító, akkor ez az összehasonlítás végrehajtásától függ() módszer hogyan nulla értékeket kezelnek.

3. Teljesítményelemzés

A teljesítmény a legkritikusabb mutató, amely segít megérteni egy adat-struktúra alkalmasságát adott felhasználási eset esetén.

Ebben a szakaszban átfogó elemzést adunk a teljesítményről HashMap és TreeMap.

3.1. HashMap

HashMap, hashtable-alapú megvalósítás lévén, belsőleg egy tömb-alapú adatszerkezetet használ elemeinek a hash funkció.

HashMap biztosítja a várható állandó idejű teljesítményt O (1) a legtöbb művelethez, mint például add (), eltávolítás () és tartalmaz (). Ezért lényegesen gyorsabb, mint a TreeMap.

A hash-táblában az elem ésszerű feltételezés alapján történő keresésének átlagos ideje: O (1). De a program nem megfelelő végrehajtása hash funkció gyenge értékeloszláshoz vezethet a vödrökben, ami a következőket eredményezi:

• Memória rezsi - sok vödör marad kihasználatlanul
• Teljesítményromlás – minél nagyobb az ütközések száma, annál alacsonyabb a teljesítmény

Java 8 előtt Külön láncolás az egyetlen előnyös módszer az ütközések kezelésére. Általában összekapcsolt listák segítségével valósítják meg, azaz, ha ütközés van, vagy két különböző elemnek azonos hash értéke van, akkor mindkét elemet ugyanabban a csatolt listában tárolja.

Ezért elem keresése a HashMap, legrosszabb esetben eltarthatott volna egy elem keresése egy összekapcsolt listában azazTovább) idő.

A képbe kerülő JEP 180-val azonban finom változás történt az elemek elrendezésének módjában. HashMap.

A specifikáció szerint, ha a vödrök túl nagyok és elegendő csomópontot tartalmaznak, azok módokká alakulnak át TreeNodes, mindegyik hasonlóan van felépítve, mint a TreeMap.

Ezért nagy hash ütközések esetén a legrosszabb esetben a teljesítmény javulni fog Tovább) nak nek O (log n).

Az átalakítást végrehajtó kódot az alábbiakban szemléltetjük:

if (binCount> = TREEIFY_THRESHOLD - 1) {treeifyBin (tab, hash); }

A (z) értéke TREEIFY_THRESHOLD nyolc, amely gyakorlatilag egy fa csatolásának küszöbértékét jelöli, nem pedig egy csatolt listát.

Nyilvánvaló, hogy:

• A HashMap sokkal több memóriát igényel, mint amennyi az adatainak tárolásához szükséges
• A HashMap nem lehet több 70-75% -nál. Ha közel kerül, akkor átméretezik, és a bejegyzéseket újraszerkesztik
• Az újraterheléshez szükség van n műveletek, amelyek költségesek, ahol az állandó időbetétünk rendbe kerül Tovább)
• A hash algoritmus határozza meg az objektumok beszúrási sorrendjét a HashMap

Az előadás a HashMap a szokás beállításával hangolható kezdeti kapacitás és a terhelési tényező, idején HashMap maga a tárgyalkotás.

Azonban a HashMap ha:

• hozzávetőlegesen tudjuk, hány elemet kell fenntartani a gyűjteményünkben
• nem szeretnénk természetes sorrendben kinyerni az elemeket

A fenti körülmények között HashMap a legjobb választásunk, mert állandó időbeillesztést, keresést és törlést kínál.

3.2. TreeMap

A TreeMap adatait egy hierarchikus fában tárolja, azzal a képességgel, hogy az elemeket egy egyedi segítségével rendezze Összehasonlító.

Összefoglaló teljesítményéről:

• TreeMap előadását nyújtja O (log (n)) a legtöbb művelethez, mint például add (), eltávolítás () és tartalmaz ()
• A Treemap memóriát takaríthat meg (a HashMap) mert csak annyi memóriát használ fel, amely az elemei tárolásához szükséges, ellentétben a HashMap amely összefüggő memóriaterületet használ
• A fának meg kell őriznie egyensúlyát a tervezett teljesítmény megőrzése érdekében, ez jelentős erőfeszítéseket igényel, ezért bonyolítja a megvalósítást

El kellene mennünk a TreeMap bármikor:

• figyelembe kell venni a memória korlátait
• nem tudjuk, hány elemet kell tárolni a memóriában
• a tárgyakat természetes sorrendben szeretnénk kinyerni
• ha az elemeket következetesen hozzáadják és eltávolítják
• hajlandóak vagyunk elfogadni O (log n) keresési idő

4. Hasonlóságok

4.1. Egyedi elemek

Mindkét TreeMap és HashMap nem támogatja a duplikált kulcsokat. Ha hozzá van adva, felülírja az előző elemet (hiba vagy kivétel nélkül):

@Test public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique () {Map treeMap = new HashMap (); treeMap.put (1, "Baeldung"); treeMap.put (1, "Baeldung"); assertTrue (treeMap.size () == 1); Map treeMap2 = new TreeMap (); treeMap2.put (1, "Baeldung"); treeMap2.put (1, "Baeldung"); assertTrue (treeMap2.size () == 1); }

4.2. Egyidejű hozzáférés

Mindkét Térkép megvalósítások nem szinkronizált és egyedül kell kezelnünk az egyidejű hozzáférést.

Mindkettőt külsőleg kell szinkronizálni, amikor több szál egyidejűleg fér hozzá, és legalább az egyik szál módosítja őket.

Kifejezetten használnunk kell Collections.synchronizedMap (mapName) a megadott térkép szinkronizált nézetének megszerzéséhez.

4.3. Gyorsan elterülő iterátorok

A Iterátor dob egy ConcurrentModificationException ha a Térkép az iterátor létrehozása után bármilyen módon és bármikor módosul.

Ezenkívül használhatjuk az iterátor eltávolítási módszerét a Térkép iteráció közben.

Lássunk egy példát:

@Test public void whenModifyMapDuringIteration_thenThrowExecption () {Map hashmap = new HashMap (); hashmap.put (1, "One"); hashmap.put (2, "Kettő"); Futtatható futtatható = () -> hashmap .forEach ((kulcs, érték) -> hashmap.remove (1)); assertThrows (ConcurrentModificationException.class, végrehajtható); }

5. Melyik megvalósítást használja?

Általában mindkét megvalósításnak megvannak a maga előnyei és hátrányai, azonban arról szól, hogy megértsük az alapul szolgáló elvárásokat és követelményeket, amelyeknek vezérelniük kell az ezzel kapcsolatos választásunkat.

Összegezve:

• Használnunk kell a TreeMap ha rendezni akarjuk a bejegyzéseinket
• Használnunk kell a HashMap ha a teljesítményt előnyben részesítjük a memóriafogyasztással szemben
• Mivel a TreeMap jelentősebb helye van, akkor fontolóra vehetjük, ha olyan tárgyakhoz szeretnénk hozzáférni, amelyek természetes sorrendjük szerint viszonylag közel vannak egymáshoz
• HashMap hangolható a kezdeti Kapacitás és terhelési tényező, ami nem lehetséges a TreeMap
• Használhatjuk a LinkedHashMap ha meg akarjuk őrizni a beillesztési sorrendet, miközben a folyamatos időelérés előnyeit élvezzük

6. Következtetés

Ebben a cikkben megmutattuk a különbségeket és hasonlóságokat TreeMap és HashMap.

Mint mindig, a cikk kódpéldái is elérhetők a GitHubon.