Хусусиятҳои TreeMap дар Java

Агар шумо ин мақоларо хонда истода бошед, эҳтимол шумо бо интерфейси Map ва истифодаи он шинос ҳастед. Агар не, пас шумо меравед. Имрӯз мо дар бораи хусусиятҳои татбиқи TreeMap сӯҳбат хоҳем кард ва аниқтараш, он чӣ гуна аз HashMap фарқ мекунад ва чӣ тавр дуруст истифода бурдани он.

Муқоисаи TreeMap, HashMap ва LinkedHashMap

Амалисозии маъмултарини интерфейси Map HashMap мебошад . Истифодаи он осон аст ва дастрасии зуд ба маълумотро кафолат медиҳад, ки онро беҳтарин номзад барои аксари вазифаҳо месозад. Аксарият, аммо на ҳама. Баъзан зарур аст, ки маълумотро дар шакли сохторӣ бо қобorяти паймоиш тавассути он нигоҳ доред. Дар ин ҳолат, татбиқи дигари интерфейси Харита ба наҷот меояд - TreeMap . TreeMap интерфейси NavigableMap - ро амалӣ мекунад , ки аз SortedMap мерос мегирад ва дар навбати худ аз интерфейси Map мерос мегирад . Бо татбиқи интерфейсҳои NavigableMap ва SortedMap , TreeMap функсияҳои иловагиро ба даст меорад, ки HashMap надорад , аммо ин аз ҷиҳати иҷроиш нарх дорад. Инчунин синфи LinkedHashMap мавҷуд аст , ки он инчунин ба шумо имкон медиҳад, ки маълумотро бо тартиби муайян нигоҳ доред - бо тартиби иловашуда. Барои фаҳмидани фарқияти байни ин се синф ба ин ҷадвал нигаред: Тавре ки шумо мебинед, ин синфҳо бисёр чизҳои умумӣ доранд, аммо фарқиятҳо низ мавҷуданд. Гарчанде ки синф аз ҳама бисёрфунксионалӣ аст, онро ҳамеша ҳамчун калид 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он 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.

NavigableMap— интерфейсе, ки SortedMapусулҳои паймоиш байни унсурҳои харитаро васеъ ва илова мекунад:

• firstEntry(): ҷуфти якуми калид-арзишро бар мегардонад;
• lastEntry(): ҷуфти охирини калид-арзишро бар мегардонад;
• pollFirstEntry(): ҷуфти аввалро бармегардонад ва хориҷ мекунад;
• pollLastEntry(): ҷуфти охиринро бармегардонад ва хориҷ мекунад;
• ceilingKey(K obj): Калиди хурдтарин k, ки аз калиди obj бузургтар ё баробар аст, бармегардонад. Агар чунин калид мавҷуд набошад, нулро бармегардонад;
• floorKey(K obj): Калиди калонтарини k, ки аз калиди obj камтар ё баробар аст, бармегардонад. Агар чунин калид мавҷуд набошад, нулро бармегардонад;
• lowerKey(K obj): Калиди калонтарини k, ки аз калиди obj хурдтар аст, бармегардонад. Агар чунин калид мавҷуд набошад, нулро бармегардонад;
• higherKey(K obj): Калиди хурдтарин k, ки аз калиди obj бузургтар аст, бармегардонад. Агар чунин калид мавҷуд набошад, нулро бармегардонад;
• ceilingEntry(K obj): монанд ба усули ceilingKey(K obj), аммо ҷуфти калид-арзишро (ё нул) бармегардонад;
• floorEntry(K obj): ба усули floorKey(K obj) монанд, аммо ҷуфти калид-арзишро бармегардонад (ё нул);
• lowerEntry(K obj): монанд ба усули belowKey(K obj), аммо ҷуфти калид-арзишро (ё нул) бармегардонад;
• higherEntry(K obj): монанд ба усули highKey(K obj), аммо ҷуфти калид-арзишро (ё нул) бармегардонад;
• descendingKeySet(): NavigableSet-ро бар мегардонад, ки дорои ҳамаи калидҳои бо тартиби баръакс мураттаб шудаанд;
• descendingMap(): харитаи Navigable-ро бар мегардонад, ки дорои ҳамаи ҷуфтҳои бо тартиби баръакс ҷудо карда шудааст;
• navigableKeySet(): an objectи NavigableSet-ро бар мегардонад, ки дорои ҳама калидҳо дар тартиби нигоҳдорӣ мебошад;
• headMap(K upperBound, boolean incl): харитаеро бар мегардонад, ки дорои ҷуфтҳо аз аввал то унсури болоӣ. Аргументи incl муайян мекунад, ки оё унсури болоӣ бояд ба харитаи баргардонидашуда дохил карда шавад;
• tailMap(K lowerBound, boolean incl): функсия ба усули қаблӣ монанд аст, танҳо ҷуфтҳо аз lowBound то ба охир баргардонида мешаванд;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Мисли усулҳои қаблӣ, ҷуфтҳо аз lowBound то upperBound баргардонида мешаванд, аргументҳои lowIncl ва highIncl нишон медиҳанд, ки оё унсурҳои сарҳадӣ ба харитаи нав дохил карда мешаванд.

Дар худи амалисозӣ 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, дар куҷо keyшахси мушаххас аст ва valueшумораи таассуроти таблиғотии ин моҳ аст. Дар конструктор мо муқоисакунандаеро мегузарем, ки одамонро аз рӯи синну сол ҷудо мекунад. Бо mapарзишҳои тасодуфӣ пур кунед. Ҳоло ба мо лозим аст, ки дар мағозаи маълумотии хурди худ ба аввалин калонсолон маълумот гирем. Мо инро бо истифода аз Stream API иҷро мекунем. Пас аз ин, мо ду харитаи мустақил мегирем, ки мо ба усулҳое мегузарем, ки таблиғро нишон медиҳанд. Роҳҳои зиёде мавҷуданд, ки ин мушкилотро метавон ҳал кард. Арсенали усулҳои синф TreeMapба шумо имкон медиҳад, ки ҳалли мувофиқи ҳар завқро ихтироъ кунед. Ҳамаи онҳоро ба ёд овардан шарт нест, зеро шумо ҳамеша метавонед ҳуҷҷатҳо ё маслиҳатҳоро аз муҳити таҳия истифода баред. Ҳамааш ҳамин! Ман умедворам, ки синф ҳоло TreeMapбарои шумо фаҳмо аст ва шумо дар ҳалли масъалаҳои амалӣ татбиқи дақиқи онро хоҳед ёфт.