Javaдагы TreeMap өзгөчөлүктөрү

Эгер сиз бул макаланы окуп жатсаңыз, Карта интерфейси жана анын колдонулушу менен таанышсыз . Эгерде жок болсо, анда сен бар. Бүгүн биз TreeMapтин ишке ашыруу өзгөчөлүктөрү, тагыраагы, анын HashMapтан кандай айырмасы жана аны кантип туура колдонуу керектиги жөнүндө сүйлөшөбүз.

TreeMap, HashMap жана LinkedHashMap салыштыруу

Карта интерфейсинин эң көп колдонулган ишке ашырылышы - HashMap . Аны колдонуу оңой жана берorштерге тез жетүүгө кепилдик берип, аны көпчүлүк тапшырмалар үчүн эң мыкты талапкер кылат. Көпчүлүгү, бирок баары эмес. Кээде ал аркылуу өтүү мүмкүнчүлүгү менен структураланган түрдө маалыматтарды сактоо зарыл. Бул учурда, Карта интерфейсинин дагы бир ишке ашырылышы жардамга келет - TreeMap . TreeMap NavigableMap интерфейсин ишке ашырат , ал SortedMapдан мураска алат , ал өз кезегинде Карта интерфейсинен мурастайт . NavigableMap жана SortedMap интерфейстерин ишке ашыруу менен TreeMap HashMap албаган кошумча функцияларга ээ болот , бирок бул аткаруу жагынан баада болот. Ошондой эле LinkedHashMap классы бар , ал ошондой эле белгилүү бир тартипте маалыматтарды сактоого мүмкүндүк берет - алар кошулган тартипте. Бул үч класстын ортосундагы айырмачылыктарды түшүнүүгө жардам берүү үчүн , бул tableга карап: Көрүнүп тургандай, бул класстардын жалпылыгы көп, бирок бир аз айырмачылыктар да бар. Класс TreeMapэң көп функциялуу болгону менен, аны ар дайым nullачкыч катары сактоого болбойт. Мындан тышкары, TreeMap элементтерине кирүү убактысы эң узун болот. HashMapОшондуктан, маалыматтарды сорттолгон формада сактоонун кереги жок болсо, же колдонгон жакшы LinkedHashMap.

Кызыл кара жыгач

Сиз байкагандай, капоттун астында TreeMapал кызыл-кара дарак деп аталган маалымат структурасын колдонот. Дал ушул структурадагы маалыматтардын сакталышы маалыматтардын сакталуу тартибин камсыз кылат. Бул эмне деген дарак? Келгиле, аны аныктайлы! Сиз Number-String жуптарын сактоо керек деп элестетиңиз. 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 сандары ачкыч болот. Эгер сиз маалыматтарды салттуу тизмеде сактасаңыз жана 101 ачкычы бар элементти табышыңыз керек болсо, аны табуу үчүн бардык 13 элементти кайталашыңыз керек болот. 13 элемент үчүн бул өтө маанилүү эмес, миллион менен иштөөдө биз чоң кыйынчылыктарга дуушар болобуз. Мындай көйгөйлөрдү чечүү үчүн программисттер бир аз татаалыраак маалымат структураларын колдонушат. Ошондуктан, кызыл-кара даракты тосуп!

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

Керектүү элементти издөө дарактын тамырынан башталат, биздин учурда ал 61. Андан кийин керектүү маани менен салыштыруу жүргүзүлөт. Бааыбыз аз болсо солго, көп болсо оңго кетебиз. Бул биз керектүү маанини тапмайынча же мааниси бар элементке null(дарактын жалбырагы) тиймейинче болот. Кызыл жана кара түстөр дарактын багытын жана тең салмактуулугун жеңилдетүү үчүн колдонулат. Кызыл-кара даракты курууда дайыма карманууга тийиш болгон эрежелер бар:

• тамыры кара түстө болушу керек.
• Дарактын жалбырактары кара болушу керек.
• Кызыл түйүндө эки кара бала түйүн болушу керек.
• Кара түйүндө ар кандай бала түйүндөр болушу мүмкүн.
• Түйүндөн жалбырактарга чейинки жол бирдей сандагы кара түйүндөрдү камтышы керек.
• Жалбырактардын ордуна жаңы түйүндөр кошулат.

Эгерде сиз 3, 4 жана 5-эрежелерди чогуу карасаңыз, боёк түйүндөрүнүн дарак аркылуу навигацияны кантип тездеткенин түшүнө аласыз: кара түйүндөр аркылуу өткөн жол кызылга караганда дайыма кыскараак. Ошондуктан, дарактын жалпы өлчөмү кара түйүндөрдүн саны менен аныкталат жана бул өлчөмү "кара бийиктик" деп аталат. Кызыл-кара дарак ар кандай программалоо тилдеринде ишке ашырылат. Интернетте Java үчүн көптөгөн ишке ашыруулар бар, ошондуктан биз бул жөнүндө көпкө токтолбойбуз, бирок функция менен таанышууну улантабыз TreeMap.

SortedMap жана NavigableMap интерфейстеринен алынган методдор

Ал интерфейсти ишке ашырат HashMap, бул анын бардык ыкмалары бар экенин билдирет . Бирок андан тышкары, ал интерфейстерди ишке ашырат жана алардан кошумча функцияларды алат. — сорттолгон маалымат топтомуна тиешелүү ыкмаларды кеңейтүүчү жана кошо турган интерфейс :TreeMapMapTreeMapHashMapTreeMapSortedMapNavigableMapSortedMapMap

• firstKey(): картанын биринчи элементинин ачкычын кайтарат;
• lastKey(): акыркы элементтин ачкычын кайтарат;
• headMap(K end): ачкыч менен башынан элементке чейин учурдагы бардык элементтерди камтыган картаны кайтарат end;
• tailMap(K start): элементтен баштап start, аягы менен аяктаган учурдагы бардык элементтерди камтыган картаны кайтарат;
• subMap(K start, K end): элементтен баштап startжана ачкыч менен аяктаган элементтин бардык элементтерин камтыган картаны кайтарат end.

NavigableMapSortedMap— карта элементтеринин ортосунда навигация ыкмаларын кеңейтүүчү жана кошо турган интерфейс :

• firstEntry(): биринчи ачкыч-маани жупту кайтарат;
• lastEntry(): акыркы ачкыч-маани жуптарын кайтарат;
• pollFirstEntry(): биринчи жупту кайтарат жана жок кылат;
• pollLastEntry(): акыркы жупту кайтарат жана жок кылат;
• ceilingKey(K obj): obj ачкычынан чоң же барабар болгон эң кичине к баскычын кайтарат. Эгерде андай ачкыч жок болсо, нөлдү кайтарат;
• floorKey(K obj): негизги objден кичине же барабар болгон эң чоң к ачкычын кайтарат. Эгерде андай ачкыч жок болсо, нөлдү кайтарат;
• lowerKey(K obj): Негизги objден кичине болгон эң чоң ачкычты кайтарат. Эгерде андай ачкыч жок болсо, нөлдү кайтарат;
• higherKey(K obj): Негизги objден чоңураак болгон эң кичине к баскычын кайтарат. Эгерде андай ачкыч жок болсо, нөлдү кайтарат;
• ceilingEntry(K obj): ceilingKey(K obj) ыкмасына окшош, бирок ачкыч-маани жуптарын (же нөлдү) кайтарат;
• floorEntry(K obj): floorKey(K obj) ыкмасына окшош, бирок ачкыч-маани жуптарын (же нөл) кайтарат;
• lowerEntry(K obj): lowKey(K obj) ыкмасына окшош, бирок ачкыч-маани жуптарын (же нөл) кайтарат;
• higherEntry(K obj): highKey(K obj) ыкмасына окшош, бирок ачкыч-маани жуптарын (же нөл) кайтарат;
• descendingKeySet(): тескери тартипте иреттелген бардык баскычтарды камтыган NavigableSetти кайтарат;
• descendingMap(): тескери тартипте иреттелген бардык жуптарды камтыган NavigableMapты кайтарат;
• navigableKeySet(): сактоо тартибинде бардык ачкычтарды камтыган NavigableSet an objectин кайтарат;
• headMap(K upperBound, boolean incl): башынан жогорку чекке чейин жуптарды камтыган картаны кайтарат. incl аргументи upperBound элементи кайтарылган картага киргизorши керекпи же жокпу аныктайт;
• tailMap(K lowerBound, boolean incl): функционалдуулугу мурунку ыкмага окшош, төмөнкү чектен аягына чейин жуптар гана кайтарылат;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Мурунку ыкмалардагыдай, lowIncl жана highIncl аргументтери жаңы картага чек ара элементтерин кошуу керекпи же жокпу көрсөтүүчү, lowIncl жана highIncl аргументтери кайтарылып берилет.

Ишке ашыруунун өзүндө TreeMap, биз тааныш конструкторлордон тышкары, салыштыруучунун мисалын кабыл алган дагы бири кошулат. Бул компаратор элементтердин сакталуу тартиби үчүн жооптуу болот.

TreeMap колдонуу мисалдары

Кошумча ыкмалардын мындай көптүгү кереги жоктой сезorши мүмкүн, бирок көбүнчө алар башында көрүнгөндөн алда канча пайдалуу болуп чыгат. Келгиле, бул мисалды силер менен карап көрөлү. Элестеткиле, биз чоң компаниянын маркетинг бөлүмүндө иштейбиз жана бизде жарнама көрсөтүүнү каалаган адамдардын маалымат базасы бар. Бул үчүн эки нюанс бар:

• биз ар бир адамга болгон таасирлердин санын көзөмөлдөшүбүз керек;
• Жашы жете электерге жарнама көрсөтүүнүн алгоритми башкача.

PersonКелгиле, бир адам жөнүндө бизге жеткorктүү болгон бардык маалыматты сактай турган класс түзөлү :

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

Биз класста логиканы ишке ашырабыз 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){}
}

Класста Mainбиз түзөбүз TreeMap, keyбелгилүү бир адам кайда жана valueбул айда жарнамалык таасирлердин саны. Конструктордо биз адамдарды жашы боюнча сорттоочу компаратордон өтөбүз. mapКокус баалуулуктар менен толтуруңуз . Эми мини маалыматтар дүкөнүбүздө биринчи чоң кишиге шилтеме алышыбыз керек. Биз муну Stream API аркылуу жасайбыз. Андан кийин биз эки көз карандысыз картаны алабыз, аларды биз жарнаманы көрсөтүүчү ыкмаларга өткөрүп беребиз. Бул көйгөйдү чечүүнүн көптөгөн жолдору бар. Класстын методдор арсеналы TreeMapар кандай табитке ылайыктуу чечимдерди ойлоп табууга мүмкүндүк берет. Алардын баарын эстеп отуруунун кажети жок, анткени сиз ар дайым иштеп чыгуу чөйрөсүндөгү documentтерди же ишараттарды колдоно аласыз. Баары болду! Класс азыр TreeMapсизге түшүнүктүү жана практикалык маселелерди чечүүдө анын так колдонулушун таба аласыз деп ишенем.