Java-da TreeMap-ın xüsusiyyətləri

Bu məqaləni oxuyursunuzsa, çox güman ki, Xəritə interfeysi və onun istifadələri ilə tanışsınız. Yoxdursa, deməli bura gedirsən. Bu gün biz TreeMap-ın tətbiqi xüsusiyyətlərindən, daha dəqiq desək, onun HashMap- dan nə ilə fərqləndiyi və ondan düzgün istifadə edilməsi haqqında danışacağıq .

TreeMap, HashMap və LinkedHashMap-ın müqayisəsi

Xəritə interfeysinin ən çox istifadə edilən tətbiqi HashMap- dır . İstifadəsi asandır və məlumatlara sürətli çıxışa zəmanət verir, bu da onu əksər tapşırıqlar üçün ən yaxşı namizəd edir. Çoxu, amma hamısı deyil. Bəzən məlumatların üzərində hərəkət etmək imkanı ilə strukturlaşdırılmış formada saxlamaq lazımdır. Bu vəziyyətdə, Xəritə interfeysinin başqa bir tətbiqi xilasetmə üçün gəlir - TreeMap . TreeMap SortedMap- dan miras qalan NavigableMap interfeysini həyata keçirir və bu da öz növbəsində Xəritə interfeysindən miras qalır . NavigableMap və SortedMap interfeyslərini tətbiq etməklə TreeMap , HashMap-ın əldə etmədiyi əlavə funksionallıq əldə edir , lakin bu, performans baxımından baha başa gəlir. LinkedHashMap sinfi də var , bu da məlumatları müəyyən bir ardıcıllıqla - əlavə olunduğu qaydada saxlamağa imkan verir. Bu üç sinif arasındakı fərqləri başa düşməyinizə kömək etmək üçün bu cədvələ baxın: Gördüyünüz kimi, bu siniflərin çoxlu ortaq cəhətləri var, lakin bəzi fərqlər də var. Sinif ən çoxfunksiyalı olsa da , həmişə açar kimi TreeMapsaxlanıla bilməz . nullBundan əlavə, TreeMap elementlərinə giriş vaxtı ən uzun olacaq. Buna görə də, məlumatları çeşidlənmiş formada saxlamağa ehtiyac yoxdursa, HashMapvə ya istifadə etmək daha yaxşıdır LinkedHashMap.

Qırmızı qara ağac

Yəqin ki, qeyd etdiyiniz kimi, başlıq altında TreeMapqırmızı-qara ağac adlanan məlumat strukturundan istifadə edir. Məhz verilənlərin bu strukturda saxlanması verilənlərin saxlanma ardıcıllığını təmin edir. Bu ağac nədir? Gəlin bunu anlayaq! Təsəvvür edin ki, siz Number-String cütlərini saxlamalısınız. 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 nömrələri açar olacaq. Məlumatları ənənəvi siyahıda saxlayırsınızsa və 101 açarı olan elementi tapmaq lazımdırsa, onu tapmaq üçün bütün 13 elementi təkrarlamalı olacaqsınız. 13 element üçün bu kritik deyil, bir milyonla işləyərkən böyük çətinliklərlə üzləşəcəyik. Bu cür problemləri həll etmək üçün proqramçılar bir az daha mürəkkəb məlumat strukturlarından istifadə edirlər. Buna görə də qırmızı-qara ağacla tanış olun!

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

Tələb olunan elementin axtarışı ağacın kökündən başlayır, bizim vəziyyətimizdə 61-dir. Sonra, tələb olunan dəyərlə müqayisə aparılır. Dəyərimiz azdırsa, sola, çoxdursa, sağa gedirik. Bu, biz tələb olunan dəyəri tapana və ya dəyəri olan elementə null(ağac yarpağı) vurana qədər baş verir. Qırmızı və qara rənglər ağacın naviqasiyasını və balansını asanlaşdırmaq üçün istifadə olunur. Qırmızı-qara ağac qurarkən həmişə riayət edilməli olan qaydalar var:

• Kök qara rəngdə olmalıdır.
• Ağacın yarpaqları qara olmalıdır.
• Qırmızı node iki qara uşaq node olmalıdır.
• Qara node hər hansı uşaq qovşaqlarına malik ola bilər.
• Düyündən onun yarpaqlarına gedən yol eyni sayda qara qovşaqdan ibarət olmalıdır.
• Yarpaqların yerinə yeni düyünlər əlavə olunur.

3, 4 və 5-ci qaydalara birlikdə baxsanız, rəngləmə qovşaqlarının ağacda naviqasiyanı necə sürətləndirdiyini başa düşə bilərsiniz: qara qovşaqlardan keçən yol həmişə qırmızı olanlardan daha qısadır. Buna görə ağacın ümumi ölçüsü qara düyünlərin sayı ilə müəyyən edilir və bu ölçü "qara hündürlük" adlanır. Qırmızı-qara ağac müxtəlif proqramlaşdırma dillərində həyata keçirilir. İnternetdə Java üçün bir çox tətbiq var, buna görə də biz bu barədə uzun müddət dayanmayacağıq, lakin funksionallıqla tanış olmağa davam edəcəyik TreeMap.

SortedMap və NavigableMap interfeyslərindən əldə edilən üsullar

Necə ki HashMap, TreeMapo, interfeysi həyata keçirir Map, yəni TreeMapbütün üsullara malikdir HashMap. Bununla yanaşı, TreeMapo, interfeysləri həyata keçirir SortedMapvə NavigableMaponlardan əlavə funksionallıq əldə edir. — çeşidlənmiş məlumat dəstinə uyğun metodları SortedMapgenişləndirən və əlavə edən interfeys :Map

• firstKey(): xəritənin birinci elementinin açarını qaytarır;
• lastKey(): sonuncu elementin açarını qaytarır;
• headMap(K end): açarı ilə başlanğıcdan elementə qədər cari xəritənin bütün elementlərini ehtiva edən xəritəni qaytarır end;
• tailMap(K start): elementdən başlayaraq startsonuna qədər cari olanın bütün elementlərini ehtiva edən xəritəni qaytarır;
• subMap(K start, K end): elementdən başlayaraq startvə açarı olan elementlə bitən cari xəritənin bütün elementlərini ehtiva edən xəritəni qaytarır end.

NavigableMapSortedMap— xəritə elementləri arasında naviqasiya metodlarını genişləndirən və əlavə edən interfeys :

• firstEntry(): ilk açar-dəyər cütünü qaytarır;
• lastEntry(): son açar-dəyər cütünü qaytarır;
• pollFirstEntry(): ilk cütü qaytarır və çıxarır;
• pollLastEntry(): sonuncu cütü qaytarır və çıxarır;
• ceilingKey(K obj): obj açarından böyük və ya ona bərabər olan ən kiçik k düyməsini qaytarır. Əgər belə açar yoxdursa, null qaytarır;
• floorKey(K obj): obj açarından kiçik və ya ona bərabər olan ən böyük k düyməsini qaytarır. Əgər belə açar yoxdursa, null qaytarır;
• lowerKey(K obj): obj açarından kiçik olan ən böyük k düyməsini qaytarır. Əgər belə açar yoxdursa, null qaytarır;
• higherKey(K obj): obj açarından böyük olan ən kiçik k düyməsini qaytarır. Əgər belə açar yoxdursa, null qaytarır;
• ceilingEntry(K obj): tavanKey(K obj) metoduna bənzər, lakin açar-dəyər cütünü (və ya null) qaytarır;
• floorEntry(K obj): floorKey(K obj) metoduna bənzər, lakin açar-dəyər cütünü (və ya null) qaytarır;
• lowerEntry(K obj): lowKey(K obj) metoduna bənzər, lakin açar-dəyər cütünü (və ya null) qaytarır;
• higherEntry(K obj): highKey(K obj) metoduna bənzər, lakin açar-dəyər cütünü (və ya null) qaytarır;
• descendingKeySet(): əks ardıcıllıqla çeşidlənmiş bütün düymələri ehtiva edən NavigableSet-i qaytarır;
• descendingMap(): əks ardıcıllıqla çeşidlənmiş bütün cütləri ehtiva edən Naviqasiya Xəritəsini qaytarır;
• navigableKeySet(): saxlama qaydasında bütün açarları ehtiva edən NavigableSet obyektini qaytarır;
• headMap(K upperBound, boolean incl): əvvəldən yuxarı sərhəd elementinə qədər cütləri ehtiva edən xəritəni qaytarır. incl arqumenti yuxarı sərhəd elementinin qaytarılmış xəritəyə daxil edilib-edilmədiyini müəyyən edir;
• tailMap(K lowerBound, boolean incl): funksionallıq əvvəlki metoda bənzəyir, yalnız LowerBound-dan sona qədər olan cütlər qaytarılır;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Əvvəlki üsullarda olduğu kimi, LowIncl və highIncl arqumentləri yeni xəritəyə sərhəd elementlərinin daxil edilib-edilmədiyini göstərən LowIncl və highIncl arqumentləri olan LowBound-dan upperBound-a qədər cütlüklər qaytarılır.

Tətbiqin özündə TreeMap, tanış olduğumuz konstruktorlardan əlavə, müqayisənin nümunəsini qəbul edən daha biri əlavə olunur. Bu müqayisəçi elementlərin saxlanma qaydasına cavabdeh olacaq.

TreeMap istifadə nümunələri

Əlavə üsulların bu qədər çoxluğu lazımsız görünə bilər, lakin çox vaxt onlar əvvəlcə göründüyündən daha faydalı olurlar. Gəlin sizinlə bu nümunəyə baxaq. Təsəvvür edin ki, biz böyük bir şirkətin marketinq departamentində işləyirik və bizdə reklam göstərmək istədiyimiz insanların məlumat bazası var. Bunun iki nüansı var:

• hər bir insana olan təəssüratların sayını izləməliyik;
• Yetkinlik yaşına çatmayanlara reklamın göstərilməsi alqoritmi fərqlidir.

PersonGəlin bir şəxs haqqında əlimizdə olan bütün məlumatları saxlayacaq bir sinif yaradaq :

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

Sinifdə məntiqi həyata keçiririk 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){}
}

MainYaratdığımız sinifdə TreeMap, keykonkret şəxs haradadır və valuebu ay reklam təəssüratlarının sayıdır. Konstruktorda insanları yaşa görə çeşidləyən bir müqayisə aparırıq. Təsadüfi dəyərlərlə doldurun map. İndi mini məlumat mağazamızda ilk böyüklərə istinad etməliyik. Biz bunu Stream API istifadə edərək edirik. Bundan sonra biz iki müstəqil xəritə alırıq, onları reklamı göstərən üsullara keçirik. Bu problemi həll etməyin bir çox yolu var. Sinfin metodlar arsenalı TreeMaphər zövqə uyğun həllər icad etməyə imkan verir. Onların hamısını xatırlamaq lazım deyil, çünki siz həmişə inkişaf mühitindən sənədlərdən və ya göstərişlərdən istifadə edə bilərsiniz. Hamısı budur! Ümid edirəm ki, sinif indi TreeMapsizə aydındır və siz praktiki məsələlərin həllində onun dəqiq tətbiqini tapacaqsınız.