Java-da TreeMap-yň aýratynlyklary

Bu makalany okaýan bolsaňyz, Karta interfeýsi we ulanylyşy bilen tanyş bolmagyňyz mümkin . Notok bolsa, şu ýere gidersiň. Bu gün “TreeMap” -yň durmuşa geçiriş aýratynlyklary, has takygy, “HashMap” -dan nähili tapawudy we ony nädip dogry ulanmalydygy barada gürleşeris .

TreeMap, HashMap we LinkedHashMap deňeşdirmek

Karta interfeýsiniň iň köp ulanylýan ýerine ýetirilişi HashMap . Ulanmak aňsat we maglumatlaryň çalt elýeterliligini kepillendirýär we ony köp meseleler üçin iň gowy kandidat edýär. Köp, ýöne hemmesi däl. Käwagt maglumatlaryň üstünden geçmek ukyby bilen gurluşly görnüşde saklamak zerur bolýar. Bu ýagdaýda Karta interfeýsiniň başga bir durmuşa geçirilmegi - TreeMap kömek edýär . TreeMap , SortedMap- dan miras galan NavigableMap interfeýsini amala aşyrýar , bu bolsa öz gezeginde Karta interfeýsinden miras alýar . “NavigableMap” we “SortedMap” interfeýslerini ýerine ýetirmek bilen , “TreeMap” “HashMap” -yň ýerine ýetirmeýän goşmaça funksiýasyna eýe bolýar , ýöne bu öndürijilik nukdaýnazaryndan bahadan çykýar. Şeýle hem, LinkedHashMap synpy bar , bu hem maglumatlary belli bir tertipde - goşulan tertipde saklamaga mümkinçilik berýär. Bu üç synpyň arasyndaky tapawutlara düşünmäge kömek etmek üçin şu tablisa serediň: Görşüňiz ýaly, bu synplaryň köp umumylygy bar, ýöne käbir tapawutlaram bar. Synp iň köp wezipeli bolsa-da , elmydama açar hökmünde TreeMapsaklanyp bilinmez . nullMundan başga-da, TreeMap elementlerine giriş wagty iň uzyn bolar. Şonuň üçin maglumatlary tertipli görnüşde saklamak zerurlygy ýok bolsa, ulanmak has gowudyr HashMapýa-da LinkedHashMap.

Gyzyl reňkli agaç

Üns beren bolsaňyz, kapotyň aşagynda TreeMapgyzyl-gara agaç diýilýän maglumat gurluşy ulanylýar. Maglumatlaryň bu tertipde saklanmagy, maglumatlaryň saklanyş tertibini üpjün edýär. Bu agaç näme? Geliň, düşüneliň! “Number-String” jübütlerini saklamalydygyny göz öňüne getiriň. 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 sanlar açar bolar. Maglumatlary adaty sanawda saklasaňyz we 101 açary bolan bir element tapmaly bolsaňyz, ony tapmak üçin 13 elementiň hemmesini gaýtalamaly bolarsyňyz. 13 element üçin bu möhüm däl, million bilen işlänimizde uly kynçylyklar ýüze çykar. Şeýle meseleleri çözmek üçin programmistler birneme çylşyrymly maglumat gurluşlaryny ulanýarlar. Şonuň üçin gyzyl-gara agaç bilen tanyş!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

Gerekli elementi gözlemek agajyň kökünden başlaýar, biziň ýagdaýymyzda 61 bolýar. Soňra zerur baha bilen deňeşdirilýär. Gymmatlygymyz az bolsa, çepe gidýäris, has köp bolsa sag tarapa gidýäris. Bu, zerur bahany tapýançak ýa-da gymmaty bolan bir elementi null(agajyň ýapragy) urýançak bolýar. Agajyň ýöremegini we deňagramlylygyny aňsatlaşdyrmak üçin gyzyl we gara reňkler ulanylýar. Gyzyl-gara agaç gurlanda hemişe berjaý edilmeli düzgünler bar:

• Kök gara reňkli bolmaly.
• Agajyň ýapraklary gara bolmaly.
• Gyzyl düwünde iki sany gara çaga düwünleri bolmaly.
• Gara düwünde islendik çaga düwünleri bolup biler.
• Düwünden ýapraklaryna barýan ýolda şol bir mukdarda gara düwün bolmaly.
• Leavesapraklaryň ýerine täze düwünler goşulýar.

3, 4 we 5 düzgünleri bilelikde gözden geçirseňiz, reňk düwünleriniň agaçdan nawigasiýany nädip çaltlaşdyrýandygyna düşünip bilersiňiz: gara düwünlerden geçýän ýol hemişe gyzyl reňklerden has gysga. Şonuň üçin agajyň umumy ululygy gara düwünleriň sany bilen kesgitlenýär we bu ululyga “gara beýiklik” diýilýär. Gyzyl-gara agaç dürli programmirleme dillerinde amala aşyrylýar. Java üçin internetde köp ýerine ýetiriş bar, şonuň üçin bu barada uzak wagtlap durup bilmeris, ýöne işleýşi bilen tanyşmagy dowam etdireris TreeMap.

SortedMap we NavigableMap interfeýslerinden alnan usullar

Halaýan ýaly HashMap, TreeMapinterfeýsi ýerine ýetirýär , bu onuň ähli usullarynyň bardygyny Mapaňladýar . Mundan başga-da, interfeýsleri amala aşyrýar we olardan goşmaça funksiýa alýar. - tertipleşdirilen maglumatlar toplumyna degişli usullary giňeldýän we goşýan interfeýs :TreeMapHashMapTreeMapSortedMapNavigableMapSortedMapMap

• firstKey(): kartanyň birinji elementiniň açaryny yzyna berýär;
• lastKey(): soňky elementiň açaryny yzyna berýär;
• headMap(K end): häzirki elementiň ähli elementlerini öz içine alýan kartany, başyndan elemente açar bilen gaýtaryp berýär end;
• tailMap(K start): häzirki elementiň ähli elementlerini öz içine alýan kartany, elementden başlap start, soňuna çenli gutarýar;
• subMap(K start, K end)start: elementden başlap, element bilen açar bilen gutarýan häzirki elementiň hemmesini öz içine alýan kartany görkezýär end.

NavigableMapSortedMap- karta elementleriniň arasynda nawigasiýa usullaryny giňeldýän we goşýan interfeýs :

• firstEntry(): ilkinji açar bahasy jübütini yzyna berýär;
• lastEntry(): iň soňky açar-baha jübütini yzyna berýär;
• pollFirstEntry(): gaýdyp gelýär we birinji jübüti aýyrýar;
• pollLastEntry(): gaýdyp gelýär we soňky jübüti aýyrýar;
• ceilingKey(K obj): Düwmeleriň garşysyndan uly ýa-da deň bolan iň kiçi k k gaýtarýar. Şeýle açar ýok bolsa, null gaýdyp gelýär;
• floorKey(K obj): Düwmeleriň garşysyndan az ýa-da deň bolan iň uly açary k görkezýär. Şeýle açar ýok bolsa, null gaýdyp gelýär;
• lowerKey(K obj): Düwmeleriň garşysyndan has kiçi k düwmesini görkezýär. Şeýle açar ýok bolsa, null gaýdyp gelýär;
• higherKey(K obj): Düwmeleriň garşysyndan uly bolan iň kiçi k k gaýtarýar. Şeýle açar ýok bolsa, null gaýdyp gelýär;
• ceilingEntry(K obj): potolokKey (K obj) usulyna meňzeýär, ýöne açar bahaly jübüti (ýa-da null) gaýtaryp berýär;
• floorEntry(K obj): polKey (K obj) usulyna meňzeýär, ýöne açar bahaly jübüti (ýa-da null) gaýtaryp berýär;
• lowerEntry(K obj): lowerKey (K obj) usulyna meňzeýär, ýöne açar bahaly jübüti (ýa-da null) gaýtaryp berýär;
• higherEntry(K obj): has ýokaryKey (K obj) usulyna meňzeýär, ýöne açar bahaly jübüti (ýa-da null) gaýtaryp berýär;
• descendingKeySet(): ters tertipde tertiplenen ähli düwmeleri öz içine alýan NavigableSet-i yzyna berýär;
• descendingMap(): ters tertipde tertiplenen ähli jübütleri öz içine alýan NavigableMap-y gaýtarýar;
• navigableKeySet(): saklamak tertibinde ähli düwmeleri öz içine alýan NavigableSet obýektini yzyna berýär;
• headMap(K upperBound, boolean incl): başyndan ýokarkyBound elementine jübütleri öz içine alýan kartany gaýtaryp berýär. Goşma argumenti, ýokarkyBound elementiniň yzyna gaýdyp gelen kartada goşulmalydygyny ýa-da ýokdugyny kesgitleýär;
• tailMap(K lowerBound, boolean incl): işleýşi öňki usula meňzeýär, diňe “LowBound” -dan ahyryna çenli jübütler yzyna gaýtarylýar;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Öňki usullarda bolşy ýaly, aşakyBound-dan upperBound-a çenli jübütler yzyna gaýtarylýar, täze kartada serhet elementlerini goşmalydygyny görkezýän lowIncl we highIncl argumentleri.

Durmuşa geçirişiň özünde TreeMap, tanyş konstruktorlarymyzdan başga-da, deňeşdirijiniň mysalyny kabul edýän ýene biri goşuldy. Bu deňeşdiriji elementleriň saklanyş tertibi üçin jogapkärçilik çeker.

TreeMap ulanmagyň mysallary

Şeýle goşmaça usullaryň köp bolmagy zerur däl ýaly bolup görünse-de, köplenç başda görünişinden has peýdaly bolup çykýar. Geliň, bu mysaly siziň bilen göreliň. Uly bir kompaniýanyň marketing bölüminde işleýändigimizi we mahabat görkezmek isleýän adamlarymyzyň maglumatlar bazasynyň bardygyny göz öňüne getiriň. Munuň iki nuansy bar:

• her adama täsirleriň sanyny yzarlamalydyrys;
• Kämillik ýaşyna ýetmediklere mahabat görkezmek algoritmi başga.

PersonBir adam hakda bize bar bolan ähli maglumatlary saklaýan synp döredeliň :

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;
   }
}

Logikany synpda durmuşa geçirýäris Main:

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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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){}
}

MainDöredýän synpymyzda TreeMap, keybelli bir adam nirede we valuebu aýda mahabat täsirleriniň sany. Konstruktorda adamlary ýaşy boýunça tertipleşdirjek deňeşdirijiden geçýäris. Tötänleýin bahalar bilen dolduryň map. Indi kiçi maglumat dükanymyzdaky ilkinji ululara salgylanma almaly. Muny Stream API ulanyp edýäris. Ondan soň mahabaty görkezýän usullara geçýän iki sany garaşsyz karta alarys. Bu meseläni çözmegiň köp, köp usuly bar. Synpyň arsenaly, TreeMapher tagamyna laýyk çözgütleri oýlap tapmaga mümkinçilik berýär. Olaryň hemmesini ýatda saklamak hökman däl, sebäbi resminamalary ýa-da ösüş gurşawyndaky görkezmeleri elmydama ulanyp bilersiňiz. Bu hemmesi! Synp indi TreeMapsize düşnükli we amaly meseleleri çözmekde takyk amaly taparsyňyz diýip umyt edýärin.