streamalism.org

1. Prehľad

V tomto článku sa chystáme preskúmať TreeMap implementácia Mapa rozhranie z Java Collections Framework (JCF).

TreeMap je implementácia mapy, ktorá udržuje svoje záznamy zoradené podľa prirodzeného usporiadania svojich kľúčov alebo ešte lepšie pomocou komparátora, ak ho užívateľ poskytne v čase stavby.

Predtým sme pokryli HashMap a LinkedHashMap implementácie a uvedomíme si, že existuje dosť informácií o tom, ako tieto triedy fungujú, podobné.

Spomínané články sa dôrazne odporúčajú prečítať skôr, ako začnete s týmto.

2. Predvolené triedenie v TreeMap

Predvolene, TreeMap triedi všetky svoje záznamy podľa ich prirodzeného usporiadania. Pre celé číslo by to znamenalo vzostupné poradie a pre reťazce v abecednom poradí.

Pozrime sa na prirodzené usporiadanie v teste:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect () {mapa TreeMap = nová TreeMap (); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); assertEquals ("[1, 2, 3, 4, 5]", map.keySet (). toString ()); }

Všimnite si, že sme celočíselné kľúče umiestnili neusporiadane, ale pri načítaní sady kľúčov potvrdzujeme, že sú skutočne udržiavané vo vzostupnom poradí. Toto je prirodzené usporiadanie celých čísel.

Rovnako, keď použijeme reťazce, budú zoradené v prirodzenom poradí, tj. Podľa abecedy:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2 () {mapa TreeMap = nová TreeMap (); map.put ("c", "val"); map.put ("b", "val"); map.put ("a", "val"); map.put ("e", "val"); map.put ("d", "val"); assertEquals ("[a, b, c, d, e]", map.keySet (). toString ()); }

TreeMap, na rozdiel od hašovacej mapy a prepojenej hashovej mapy, nikde nepoužíva hashovací princíp, pretože na ukladanie svojich záznamov nepoužíva pole.

3. Vlastné triedenie v TreeMap

Ak nie sme spokojní s prirodzeným usporiadaním TreeMap, môžeme tiež definovať svoje vlastné pravidlo pre objednávanie pomocou komparátora pri stavbe stromovej mapy.

V nasledujúcom príklade chceme, aby sa celočíselné kľúče zoradili zostupne:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect () {mapa TreeMap = nová mapa TreeMap (Comparator.reverseOrder ()); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); assertEquals ("[5, 4, 3, 2, 1]", map.keySet (). toString ()); }

Hašovacia mapa nezaručuje poradie uložených kľúčov a konkrétne nezaručuje, že táto objednávka zostane časom rovnaká, stromová mapa však zaručuje, že kľúče budú vždy zoradené podľa zadaného poradia.

4. Dôležitosť TreeMap Triedenie

Teraz to už vieme TreeMap ukladá všetky svoje záznamy v zoradenom poradí. Kvôli tomuto atribútu stromových máp môžeme vykonávať dotazy ako; nájsť „najväčší“, nájsť „najmenší“, nájsť všetky kľúče menšie alebo väčšie ako určitá hodnota atď.

Kód uvedený nižšie pokrýva iba malé percento z týchto prípadov:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect () {mapa TreeMap = nová TreeMap (); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); Celé číslo najvyššieKey = map.lastKey (); Celé číslo nejnižšíKey = map.firstKey (); Nastaviť keysLessThan3 = map.headMap (3) .keySet (); Nastaviť keysGreaterThanEqTo3 = map.tailMap (3) .keySet (); assertEquals (nové celé číslo (5), nejvyššíKey); assertEquals (nové celé číslo (1), najmenší kľúč); assertEquals ("[1, 2]", keysLessThan3.toString ()); assertEquals ("[3, 4, 5]", keysGreaterThanEqTo3.toString ()); }

5. Interná implementácia TreeMap

TreeMap náradie NavigableMap rozhranie a zakladá svoju internú prácu na princípoch červeno-čiernych stromov:

verejná trieda TreeMap rozširuje AbstractMap implementuje NavigableMap, Cloneable, java.io.Serializable

Princíp červeno-čiernych stromov presahuje rámec tohto článku, je však potrebné pamätať na kľúčové veci, aby sme pochopili, ako zapadajú do TreeMap.

Po prvé, červeno-čierny strom je dátová štruktúra, ktorá sa skladá z uzlov; fotografia obrátený strom manga s koreňmi na oblohe a konármi rastúcimi smerom nadol. Koreň bude obsahovať prvý prvok pridaný do stromu.

Platí pravidlo, že počnúc koreňom je akýkoľvek prvok v ľavej vetve ľubovoľného uzla vždy menší ako prvok v samotnom uzle. Tie napravo sú vždy väčšie. Čo definuje väčšie alebo menšie ako určuje prirodzené usporiadanie prvkov alebo definovaný komparátor pri konštrukcii, ako sme videli už skôr.

Toto pravidlo zaručuje, že záznamy mapy budú vždy zoradené a predvídateľné.

Po druhé, červeno-čierny strom je samovyvažujúci sa binárny vyhľadávací strom. Tento atribút a vyššie uvedené zaručuje, že základné operácie ako hľadanie, získanie, vloženie a odstránenie zaberajú logaritmický čas O (log n).

Kľúčom je tu samovyvažovanie. Keď neustále vkladáme a odstraňujeme položky, predstavte si, ako strom rastie dlhšie na jednej hrane alebo kratšie na druhej.

To by znamenalo, že operácia by trvala kratšie na kratšej vetve a dlhšiu dobu na vetve, ktorá je najďalej od koreňa, čo by sme nechceli, aby sa stalo.

Preto je o to postarané v dizajne červeno-čiernych stromov. Pri každom vložení a odstránení sa zachová maximálna výška stromu na ktorejkoľvek hrane O (log n) tj. strom sa priebežne bilancuje.

Rovnako ako hash mapa a prepojená hash mapa, stromová mapa nie je synchronizovaná, a preto sú pravidlá jej používania v prostredí s viacerými vláknami podobné pravidlám v ostatných dvoch implementáciách máp.

6. Výber správnej mapy

Po pohľade na HashMap a LinkedHashMap implementácie predtým a teraz TreeMap, je dôležité urobiť krátke porovnanie medzi týmito tromi, aby sme sa dozvedeli, ktorá z nich sa kam hodí.

Hašovacia mapa je dobrá ako univerzálna implementácia máp, ktorá poskytuje rýchle operácie ukladania a načítania. Nedosahuje však chaotické a neusporiadané usporiadanie záznamov.

To spôsobí, že bude mať slabý výkon v scenároch, kde je veľa iterácií, pretože celá kapacita základného poľa ovplyvňuje iný prechod, ako len počet vstupov.

Prepojená hash mapa má dobré vlastnosti hash máp a dodáva záznamom poriadok. Podáva lepšie výsledky tam, kde je veľa iterácií, pretože sa zohľadňuje iba počet záznamov bez ohľadu na kapacitu.

Mapa stromu posúva objednávanie na ďalšiu úroveň tým, že poskytuje úplnú kontrolu nad tým, ako by sa mali kľúče triediť. Na druhej strane ponúka horší všeobecný výkon ako ostatné dve alternatívy.

Mohli by sme povedať a prepojená hashova mapa redukuje chaos v usporiadaní hashovacej mapy bez toho, aby mu hrozil výkonnostný limit stromovej mapy.

7. Záver

V tomto článku sme preskúmali Javu TreeMap triedy a jej interná implementácia. Pretože je to posledná v rade bežných implementácií rozhrania Map, pokračovali sme aj v krátkej diskusii o tom, kde to vo vzťahu k ostatným dvom vyhovuje najlepšie.

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