TreeMap Java nyelven

Ha ezt a cikket olvassa, valószínűleg ismeri a térképes felületet, és azt, hogy hol lehet megfelelően alkalmazni. Ha nem, akkor gyere ide . Ma a Java TreeMap megvalósításának jellemzőiről fogunk beszélni, pontosabban arról, hogy miben különbözik a HashMaptől, és hogyan kell helyesen használni.

A TreeMap, a HashMap és a LinkedHashMap összehasonlítása

A Map felület leggyakrabban használt megvalósítása a HashMap. Könnyen használható és gyors adathozzáférést garantál, így a legtöbb probléma megoldására a legjobb jelölt. A legtöbb, de nem az összes. Néha strukturáltan kell tárolnia az adatokat, és képesnek kell lennie a navigációra. Ebben az esetben a Map interfész egy másik implementációja (TreeMap) segít. A TreeMap a NavigableMap felületet valósítja meg, amely örökli a SortedMap -et , amely viszont örökli a Térkép felületet. A NavigableMap és SortedMap interfészek megvalósításával a TreeMap olyan további funkciókat kap, amelyek a HashMapben nem érhetők el, de a teljesítmény tekintetében árat fizet. Ott van a LinkedHashMap isosztály , amely lehetővé teszi az adatok meghatározott sorrendben történő tárolását is (a térképhez való felvétel sorrendjében). A három osztály közötti különbségek megértéséhez nézze meg ezt a táblázatot: Mint látható, ezekben az osztályokban sok a közös, de van néhány különbség is. Bár a TreeMap osztály a legsokoldalúbb, nem mindig tárolhatja a nullát kulcsként. Ezenkívül a TreeMap elemeinek elérése a leghosszabb ideig tart. Tehát, ha nem kell az adatokat valamilyen rendezett sorrendben tárolnia, akkor jobb a HashMap vagy a LinkedHashMap használata .

Vörös-fekete fa

Valószínűleg észrevette, hogy a burkolat alatt a TreeMap egy vörös-fekete fának nevezett adatstruktúrát használ. Pontosan az adatok tárolása ebben a struktúrában biztosítja az adatok rendezését. Szóval milyen fa ez? Találjuk ki! Képzelje el, hogy szám-karakterlánc párokat kell tárolnia. A 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 és 101 számok kulcsok lesznek. Ha hagyományos listában tárolja az adatokat, és meg kell találnia az elemet a 101-es kulccsal, akkor mind a 13 elemen keresztül kell lépnie a megtaláláshoz. 13 elemnél ez nem nagy baj, de ha millióval dolgozunk, akkor nagy problémáink lesznek. E problémák megoldására a programozók valamivel bonyolultabb adatstruktúrákat használnak. Itt lép színpadra a piros-fekete fa!Egy elem keresése a fa gyökerénél kezdődik, ami esetünkben 61. Ezután összehasonlítjuk a csomópontértékeket a keresett értékkel. Ha kisebb az értékünk, akkor balra megyünk; ha nagyobb, akkor jobbra megyünk. Ez a folyamat addig ismétlődik, amíg meg nem találjuk a kívánt értéket, vagy találkozunk egy elemmel, amelynek értéke null (a fa levele). A piros és fekete színek a fán való navigálás és egyensúlyozás egyszerűsítésére szolgálnak. Vannak szabályok, amelyeket mindig be kell tartani egy piros-fekete fa építésekor:

• A gyökérnek feketének kell lennie.
• A fa leveleinek feketének kell lenniük.
• Egy piros csomópontnak két fekete gyermekcsomóponttal kell rendelkeznie.
• Egy fekete csomópontnak bármilyen színű gyermekcsomópontja lehet.
• A csomóponttól a leveleihez vezető útvonalnak ugyanannyi fekete csomópontot kell tartalmaznia.
• Új csomópontok kerülnek a levelekhez.

Ha a 3., 4. és 5. szabályt együtt vesszük figyelembe, megértheti, hogy a csomópontok színe miként tesz lehetővé a fán való gyorsabb navigálást: a fekete csomópontokon át vezető út mindig rövidebb, mint a piros csomópontokon keresztül. Ennek megfelelően a fa teljes méretét a fekete csomópontok száma határozza meg, amelyet "fekete magasságnak" neveznek. A piros-fekete fa adatszerkezetet különféle programozási nyelveken valósítják meg. Nagyon sok Java implementáció található az interneten, ezért itt nem késlekedünk. Ehelyett folytassuk a TreeMap funkcióinak megismerését.

A SortedMap és a NavigableMap felületekről származó módszerek

A HashMaphez hasonlóan a TreeMap is megvalósítja a Map felületet, ami azt jelenti, hogy a TreeMap rendelkezik a HashMapben létező összes metódussal. De a TreeMap a SortedMap és a NavigableMap felületeket is megvalósítja , és így további funkcionalitást nyer belőlük. A SortedMap egy olyan felület, amely kiterjeszti a térképet , és hozzáadja a rendezett adatkészlethez releváns metódusokat:

• firstKey() : a térkép első elemének kulcsát adja vissza
• lastKey() : az utolsó elem kulcsát adja vissza
• headMap(K end) : olyan térképet ad vissza, amely az aktuális térkép összes elemét tartalmazza, az elejétől a kulcsvégű elemig
• tailMap(K start) : olyan térképet ad vissza, amely az aktuális térkép összes elemét tartalmazza, a kezdőelemtől a végéig
• subMap(K start, K ​​end) : olyan térképet ad vissza, amely az aktuális térkép összes elemét tartalmazza, a kezdőelemtől a kulcsvégű elemig.

A NavigableMap egy olyan felület, amely kiterjeszti a SortedMap alkalmazást, és módszereket ad hozzá a térkép elemei közötti navigációhoz:

• firstEntry() : az első kulcs-érték párt adja vissza
• lastEntry() : az utolsó kulcs-érték párt adja vissza
• pollFirstEntry() : visszaadja és törli az első párt
• pollLastEntry() : visszaadja és törli az utolsó párt
• maximumKey(K obj) : a legkisebb k kulcsot adja vissza, amely nagyobb vagy egyenlő, mint az obj kulcs. Ha nincs ilyen kulcs, nullát ad vissza
• floorKey(K obj) : a legnagyobb k kulcsot adja vissza, amely kisebb vagy egyenlő, mint az obj kulcs. Ha nincs ilyen kulcs, nullát ad vissza
• alsóKey(K obj) : a legnagyobb k kulcsot adja vissza, amely kisebb, mint az obj kulcs. Ha nincs ilyen kulcs, nullát ad vissza
• highKey(K obj) : a legkisebb k kulcsot adja vissza, amely nagyobb, mint az obj kulcs. Ha nincs ilyen kulcs, nullát ad vissza
• maximumEntry(K obj) : a maximumKey(K obj) metódushoz hasonlóan csak kulcs-érték párt ad vissza (vagy nullát)
• floorEntry(K obj) : a floorKey(K obj) metódushoz hasonlóan csak kulcs-érték párt ad vissza (vagy nullát)
• lowEntry(K obj) : hasonlóan a lowKey(K obj) metódushoz, csak kulcs-érték párt ad vissza (vagy nullát)
• highEntry(K obj) : a HighKey(K obj) metódushoz hasonlóan csak kulcs-érték párt ad vissza (vagy nullát)
• descendingKeySet() : egy NavigableSet-et ad vissza, amely az összes kulcsot fordított sorrendben tartalmazza
• descendingMap() : egy NavigableMap-et ad vissza, amely az összes párt fordított sorrendben tartalmazza
• navigableKeySet() : egy NavigableSet objektumot ad vissza, amely tartalmazza az összes kulcsot a tárolási sorrendben
• headMap(K felső határ, logikai incl) : olyan térképet ad vissza, amely párokat tartalmaz az elejétől a felső határig. Az incl paraméter jelzi, hogy szerepeljen-e a felső határ elem a visszaadott térképben
• tailMap(K alsó határ, logikai incl) : az előző módszerhez hasonló funkcionalitás, csak párokat ad vissza az alsó határtól a végéig
• subMap(K alsóBound, logikai alacsonyIncl, K felső határ, logikai highIncl) : az előző módszerekhez hasonlóan párokat ad vissza alsó határtól felső határig; az lowIncl és a highIncl argumentumok jelzik, hogy bele kell-e venni a határelemeket az új térképbe.

A szokásos konstruktorokon kívül a TreeMap rendelkezik egy másik konstruktorral is, amely elfogad egy összehasonlító példányt. Ez az összehasonlító felelős az elemek tárolási sorrendjéért.

Példák a TreeMap-re

Ez a rengeteg extra módszer feleslegesnek tűnik, de sokkal hasznosabbnak bizonyulnak, mint első pillantásra gondolnád. Vizsgáljuk meg együtt a következő példát. Képzelje el, hogy egy nagy cég marketing osztályán dolgozunk, és van egy adatbázisunk azokról az emberekről, akiknek hirdetéseket szeretnénk megjeleníteni. Két részletet kell szem előtt tartani:

• Nyomon kell tartanunk az egyes személyekre vonatkozó megjelenítések számát
• A kiskorúaknak szóló hirdetések megjelenítésének algoritmusa eltérő.

Hozzunk létre egy Személy osztályt, amely minden személyről minden lényeges információt tárol:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

A logikát a fő osztályban valósítjuk meg :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

A Fő osztályban hozzon létre egy TreeMap-et, amelyben minden kulcs egy adott személyt jelöl, és minden érték a hirdetésmegjelenítések száma ebben a hónapban. Átadunk a kivitelezőnek egy komparátort, amely életkor szerint osztályozza az embereket. A térképet tetszőleges értékekkel töltjük fel. Most szeretnénk hivatkozást kapni az első felnőttre a kis adattárunkban. Ezt a Stream API segítségével tesszük. Ezután két különálló térképet kapunk, amelyeket átadunk a hirdetéseket megjelenítő metódusoknak. Sok-sokféleképpen teljesíthettük volna ezt a feladatot. A TreeMap osztály módszerarzenálja lehetővé teszi, hogy minden igényre egyedi megoldásokat készítsünk. Nem kell mindegyikre emlékeznie, mert mindig használhatja az IDE dokumentációját vagy tippjeit. A tanultak megerősítése érdekében javasoljuk, hogy nézzen meg egy videóleckét a Java-tanfolyamról Ez minden most! Remélem, most már világos számodra a TreeMap osztály, és megfelelően alkalmazod a gyakorlati kódolási feladatok megoldásában.