streamalism.org

1. Áttekintés

Ebben a cikkben meg fogjuk vizsgálni TreeMap végrehajtása Térkép felület a Java Gyűjtemények keretrendszeréből (JCF).

TreeMap olyan térképi megvalósítás, amely a bejegyzéseket a kulcsainak természetes sorrendje szerint rendezi, vagy még jobb, ha összehasonlítót használ, ha a felhasználó az építkezés idején biztosítja.

Korábban már kitértünk rá HashMap és LinkedHashMap megvalósításokat, és rájövünk, hogy elég sok információ van arról, hogy ezek az osztályok hogyan működnek.

Az említett cikkeket erősen ajánlott elolvasni, mielőtt folytatnánk ezt.

2. Alapértelmezett rendezés TreeMap

Alapértelmezés szerint, TreeMap az összes bejegyzést a természetes sorrendjük szerint rendezi. Egy egész szám esetében ez növekvő sorrendet, a karakterláncok esetében pedig ábécé sorrendet jelentene.

Nézzük meg a teszt természetes sorrendjét:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect () {TreeMap map = new 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 ()); }

Vegye figyelembe, hogy az egész kulcsokat nem rendezett módon helyeztük el, de a kulcskészlet lekérésekor megerősítjük, hogy valóban növekvő sorrendben vannak. Ez az egész számok természetes rendezése.

Hasonlóképpen, amikor húrokat használunk, azok rendezésük a természetes sorrendben történik, azaz ábécé szerint:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2 () {TreeMap map = new 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 ()); }

TreeMapa hash térképpel és a linkelt hash térképpel ellentétben sehol sem alkalmazza a hash elvét, mivel nem használ egy tömböt a bejegyzéseinek tárolására.

3. Egyéni rendezés TreeMap

Ha nem vagyunk elégedettek a természetes sorrenddel TreeMap, definiálhatjuk a saját szabályunkat is a rendezéshez összehasonlító eszközzel egy fatérkép elkészítése során.

Az alábbi példában azt akarjuk, hogy az egész számkulcsokat csökkenő sorrendben rendezzük:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect () {TreeMap map = new 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 ()); }

A hash-térkép nem garantálja a tárolt kulcsok sorrendjét, és kifejezetten nem garantálja, hogy ez a sorrend az idő múlásával változatlan marad, de egy fa-térkép garantálja, hogy a kulcsok mindig a megadott sorrend szerint lesznek rendezve.

4. Fontossága TreeMap Válogató

Ezt már tudjuk TreeMap összes bejegyzését rendezett sorrendben tárolja. A fatérképek ezen attribútuma miatt olyan lekérdezéseket hajthatunk végre; keresse meg a „legnagyobb”, keresse meg a „legkisebb”, keresse meg az összes kulcsot, amely egy bizonyos értéknél kisebb vagy nagyobb, stb.

Az alábbi kód ezeknek az eseteknek csak kis hányadát fedi le:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect () {TreeMap map = new TreeMap (); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); Egész szám legnagyobbKey = map.lastKey (); Egész szám legalacsonyabb kulcs = map.firstKey (); Set keysLessThan3 = map.headMap (3) .keySet (); Set keysGreaterThanEqTo3 = map.tailMap (3) .keySet (); assertEquals (új egész szám (5), legmagasabb kulcs); assertEquals (új egész szám (1), legalacsonyabb kulcs); assertEquals ("[1, 2]", keysLessThan3.toString ()); assertEquals ("[3, 4, 5]", keysGreaterThanEqTo3.toString ()); }

5. A belső megvalósítása TreeMap

TreeMap megvalósítja NavigableMap interfész és belső munkáját a vörös-fekete fák elveire alapozza:

a TreeMap nyilvános osztály kiterjeszti az AbstractMap megvalósítja a NavigableMap, Cloneable, java.io.Serializable

A vörös-fekete fák elve meghaladja a cikk kereteit, azonban kulcsfontosságú dolgokra kell emlékezni, hogy megértsük, hogyan illeszkednek TreeMap.

Először is, a vörös-fekete fa egy adatszerkezet, amely csomópontokból áll; kép egy fordított mangófa, amelynek gyökere az égen és az ágak lefelé nőnek. A gyökér tartalmazza a fához hozzáadott első elemet.

A szabály az, hogy a gyökérből kiindulva bármelyik csomópont bal ágának bármelyik eleme mindig kisebb, mint maga a csomópont. A jobboldaliak mindig nagyobbak. Hogy mi határozza meg a nagyobbat vagy kevesebbet, azt az elemek természetes rendezése vagy a definiált összehasonlító határozza meg az építkezéskor, amint azt korábban láttuk.

Ez a szabály garantálja, hogy a treemap bejegyzései mindig rendezett és kiszámítható sorrendben lesznek.

Másodszor, a vörös-fekete fa egy önkiegyensúlyozó bináris kereső fa. Ez az attribútum és a fentiek garantálják, hogy az alapvető műveletek, például a keresés, beolvasás, eltávolítás és eltávolítás logaritmikus időt vegyenek igénybe O (log n).

Az önkiegyensúlyozottság kulcsfontosságú itt. Miközben folyamatosan szúrunk be és törlünk bejegyzéseket, ábrázoljuk a fát, amely az egyik szélén hosszabb, a másikon rövidebb.

Ez azt jelentené, hogy egy művelet rövidebb időt vesz igénybe a rövidebb ágon, és hosszabb időt vesz igénybe a gyökértől legtávolabbi ágon, amire nem akarunk sort keríteni.

Ezért a vörös-fekete fák tervezésénél erről gondoskodnak. Minden behelyezés és törlés esetén a fa bármely szélén a maximális magassága megmarad O (log n) vagyis a fa folyamatosan kiegyensúlyozza önmagát.

A hash térképhez és a linkelt hash térképhez hasonlóan a fák térképe sincs szinkronizálva, ezért a többszálas környezetben történő használatának szabályai hasonlóak a másik két térképes megvalósításhoz.

6. A megfelelő térkép kiválasztása

Miután megnézte HashMap és LinkedHashMap megvalósítások korábban és most TreeMap, fontos egy rövid összehasonlítás a három között, hogy eligazítsuk, melyik hova illik.

Hash térkép jó általános célú térkép-megvalósításként, amely gyors tárolási és visszakeresési műveleteket biztosít. A bejegyzések kaotikus és rendezetlen elrendezése miatt azonban elmarad.

Ez azt eredményezi, hogy rosszul teljesít olyan forgatókönyvekben, ahol sok az iteráció, mivel az alapul szolgáló tömb teljes kapacitása nemcsak a bejegyzések számát befolyásolja a bejárást.

Összekapcsolt hash térkép rendelkezik a hash térképek jó tulajdonságokkal és sorrendet ad a bejegyzésekhez. Jobban teljesít, ahol sok az iteráció, mert csak a bejegyzések számát vesszük figyelembe kapacitástól függetlenül.

Fa térkép a megrendelést a következő szintre emeli a kulcsok rendezésének teljes ellenőrzésével. A másik oldalon rosszabb általános teljesítményt nyújt, mint a másik két alternatíva.

Mondhatnánk a a összekapcsolt hash térkép csökkenti a káoszt a hash térkép sorrendjében anélkül, hogy a fa térkép teljesítmény büntetését kivonnák.

7. Következtetés

Ebben a cikkben feltártuk a Java-t TreeMap osztály és annak belső megvalósítása. Mivel ez az utolsó a közös Map interfész-implementációk sorozatában, folytattuk azt is, hogy röviden megvitassuk, hogy hol illik a legjobban a másik kettőhöz képest.

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