Java тіліндегі TreeMap мүмкіндіктері

Егер сіз осы мақаланы оқып жатсаңыз, сіз Карта интерфейсімен және оның қолданылуымен таныс болуыңыз мүмкін . Олай болмаса, міне. Бүгін біз TreeMap-ті іске асыру мүмкіндіктері туралы, дәлірек айтқанда, оның HashMap- тен айырмашылығы және оны қалай дұрыс пайдалану керектігі туралы сөйлесетін боламыз.

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

Карта интерфейсінің ең жиі қолданылатын іске асуы - HashMap . Оны пайдалану оңай және деректерге жылдам қол жеткізуге кепілдік береді, бұл оны көптеген тапсырмалар үшін ең жақсы үміткер етеді. Көпшілігі, бірақ бәрі емес. Кейде деректерді оны шарлау мүмкіндігімен құрылымдық пішінде сақтау қажет. Бұл жағдайда Карта интерфейсінің басқа іске асуы құтқаруға келеді - TreeMap . TreeMap NavigableMap интерфейсін жүзеге асырады , ол SortedMap- тен мұрагер , ол өз кезегінде Map интерфейсінен мұрагер болады . NavigableMap және SortedMap интерфейстерін енгізу арқылы TreeMap HashMap қолданbyteын қосымша функционалдылыққа ие болады , бірақ бұл өнімділік тұрғысынан бағаға ие болады. Сондай-ақ, LinkedHashMap класы бар , ол деректерді белгілі бір ретпен - олар қосылған ретпен сақтауға мүмкіндік береді. Осы үш сыныптың арасындағы айырмашылықтарды түсінуге көмектесу үшін мына кестені қараңыз: Көріп отырғаныңыздай, бұл сыныптардың ортақ жақтары көп, бірақ аздаған айырмашылықтары да бар. Класс TreeMapең көп функциялы болғанымен, оны әрқашан nullкілт ретінде сақтау мүмкін емес. Сонымен қатар, TreeMap элементтеріне қол жеткізу уақыты ең ұзақ болады. HashMapСондықтан, егер деректерді сұрыпталған түрде сақтау қажет болмаса, немесе пайдаланған дұрыс LinkedHashMap.

Қызыл қара ағаш

Сіз байқағаныңыздай, капюшонның астында TreeMapол қызыл-қара ағаш деп аталатын деректер құрылымын пайдаланады. Дәл осы құрылымдағы мәліметтерді сақтау деректердің сақталу ретін қамтамасыз етеді. Бұл қандай ағаш? Оны анықтап алайық! Сандар-жол жұптарын сақтау керек деп елестетіңіз. 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, TreeMapол интерфейсті жүзеге асырады Map, яғни оның TreeMapбарлық әдістері бар HashMap. Сонымен қатар, TreeMapол интерфейстерді жүзеге асырады SortedMapжәне NavigableMapолардан қосымша функционалдылықты алады. — сұрыпталған деректер жиынына қатысты әдістерді SortedMapкеңейтетін және қосатын интерфейс :Map

• 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 пернесінен үлкен немесе оған тең ең кіші k пернесін қайтарады. Егер мұндай кілт жоқ болса, нөлді қайтарады;
• floorKey(K obj): obj пернесінен кіші немесе оған тең ең үлкен k пернесін қайтарады. Егер мұндай кілт жоқ болса, нөлді қайтарады;
• lowerKey(K obj): obj кілтінен кіші ең үлкен k пернесін қайтарады. Егер мұндай кілт жоқ болса, нөлді қайтарады;
• higherKey(K obj): obj кілтінен үлкен ең кіші k пернесін қайтарады. Егер мұндай кілт жоқ болса, нөлді қайтарады;
• 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 нысанын қайтарады;
• headMap(K upperBound, boolean incl): басынан жоғарғы шегіне дейінгі жұптарды қамтитын картаны қайтарады. incl аргументі upperBound элементінің қайтарылған картаға қосылуы қажеттігін көрсетеді;
• tailMap(K lowerBound, boolean incl): функционалдылық алдыңғы әдіске ұқсас, тек lowBound-тан соңына дейін жұптар қайтарылады;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Алдыңғы әдістердегідей, lowIncl және highIncl аргументтері жаңа картаға шекара элементтерін қосу-қосу-қосу жоқтығын көрсететін lowIncl және highIncl аргументтерінен lowBound-тен upperBound-қа дейінгі жұптар қайтарылады.

Іске асырудың өзінде TreeMapбізге таныс конструкторлардан басқа компаратордың данасын қабылдайтын тағы біреуі қосылады. Бұл компаратор элементтердің сақталу ретіне жауапты болады.

TreeMap қолдану мысалдары

Қосымша әдістердің мұндай көптігі қажетсіз болып көрінуі мүмкін, бірақ көбінесе олар бастапқыда көрінгеннен әлдеқайда пайдалы болып шығады. Осы мысалды сіздермен бірге қарастырайық. Елестетіп көріңізші, біз үлкен компанияның маркетинг бөлімінде жұмыс істейміз және бізде жарнама көрсеткіміз келетін адамдар туралы мәліметтер базасы бар. Бұған екі нюанс бар:

• біз әр адамға алған әсерлердің санын қадағалап отыруымыз керек;
• Кәмелетке толмағандарға жарнаманы көрсету алгоритмі басқаша.

PersonАдам туралы бізге қол жетімді барлық ақпаратты сақтайтын класс құрайық :

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қай жерде және осы айдағы жарнамалық әсерлердің саны. Конструкторда біз адамдарды жасына қарай сұрыптайтын компараторды береміз. Кездейсоқ мәндермен толтырыңыз . Енді біз шағын деректер қоймасындағы бірінші ересек адамға анықтама алуымыз керек. Біз мұны Stream API арқылы жасаймыз. Осыдан кейін біз екі тәуелсіз карта аламыз, оны біз жарнаманы көрсететін әдістерге береміз. Бұл мәселені шешудің көптеген жолдары бар. Сыныптың әдістер арсеналы кез келген талғамға сай шешімдерді ойлап табуға мүмкіндік береді. Олардың барлығын есте сақтаудың қажеті жоқ, өйткені сіз әрқашан әзірлеу ортасындағы құжаттаманы немесе кеңестерді пайдалана аласыз. Бар болғаны! Класс енді сізге түсінікті болды және практикалық есептерді шешуде оның нақты қолданылуын табасыз деп үміттенемін. keyvaluemapTreeMapTreeMap