Java-da TreeMap-ning xususiyatlari

Agar siz ushbu maqolani o'qiyotgan bo'lsangiz, ehtimol siz Xarita interfeysi va undan foydalanish bilan tanishsiz . Agar yo'q bo'lsa, unda siz borasiz. Bugun biz TreeMap-ning amalga oshirish xususiyatlari, aniqrog'i, uning HashMap- dan farqi va undan qanday to'g'ri foydalanish haqida gaplashamiz.

TreeMap, HashMap va LinkedHashMap-ni taqqoslash

Xarita interfeysining eng ko'p qo'llaniladigan ilovasi HashMap hisoblanadi . Foydalanish oson va ma'lumotlarga tezkor kirishni kafolatlaydi, bu esa uni ko'pgina vazifalar uchun eng yaxshi nomzodga aylantiradi. Ko'pchilik, lekin hammasi emas. Ba'zan ma'lumotlarni ular bo'ylab harakatlanish imkoniyati bilan tuzilgan shaklda saqlash kerak bo'ladi. Bunday holda, Xarita interfeysining yana bir ilovasi qutqarish uchun keladi - TreeMap . TreeMap NavigableMap interfeysini amalga oshiradi , u SortedMap'dan meros bo'lib , o'z navbatida Map interfeysidan meros bo'lib qoladi . NavigableMap va SortedMap interfeyslarini qo'llash orqali TreeMap HashMap ega bo'lmagan qo'shimcha funksiyalarga ega bo'ladi , ammo bu ishlash jihatidan qimmatga tushadi. Bundan tashqari, LinkedHashMap sinfi mavjud bo'lib , u ham ma'lumotlarni ma'lum bir tartibda saqlashga imkon beradi - ular qo'shilgan tartibda. Ushbu uchta sinf o'rtasidagi farqni tushunishga yordam berish uchun ushbu jadvalga qarang: Ko'rib turganingizdek, bu sinflarning umumiy jihatlari juda ko'p, ammo bir nechta farqlar ham mavjud. Sinf TreeMapeng ko'p funktsiyali bo'lsa-da, uni har doim ham nullkalit sifatida saqlash mumkin emas. Bundan tashqari, TreeMap elementlariga kirish vaqti eng uzun bo'ladi. HashMapShuning uchun, agar ma'lumotlarni tartiblangan shaklda saqlash kerak bo'lmasa, yoki dan foydalanish yaxshidir LinkedHashMap.

Qizil qora daraxt

Siz sezganingizdek, kaput ostida TreeMapu qizil-qora daraxt deb ataladigan ma'lumotlar strukturasidan foydalanadi. Aynan ma'lumotlarning saqlanish tartibini ta'minlaydigan ushbu tuzilmadagi ma'lumotlarning saqlanishi. Bu nima daraxt? Keling, buni aniqlaylik! Tasavvur qiling-a, siz Number-String juftlarini saqlashingiz kerak. 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 raqamlari kalit bo'ladi. Agar siz ma'lumotlarni an'anaviy ro'yxatda saqlasangiz va 101 kalitli elementni topishingiz kerak bo'lsa, uni topish uchun barcha 13 elementni takrorlashingiz kerak bo'ladi. 13 element uchun bu muhim emas, million bilan ishlashda biz katta muammolarga duch kelamiz. Bunday muammolarni hal qilish uchun dasturchilar biroz murakkabroq ma'lumotlar tuzilmalaridan foydalanadilar. Shuning uchun, qizil-qora daraxt bilan tanishing!

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

Kerakli elementni qidirish daraxtning ildizidan boshlanadi, bizning holatlarimizda u 61. Keyinchalik, kerakli qiymat bilan taqqoslash amalga oshiriladi. Qadrimiz kam bo'lsa, chapga, ko'p bo'lsa, o'ngga boramiz. Bu biz kerakli qiymatni topmagunimizcha yoki qiymatga ega elementni null(daraxtning bargi) urmagunimizcha sodir bo'ladi. Qizil va qora ranglar daraxtning harakatlanishi va muvozanatini osonlashtirish uchun ishlatiladi. Qizil-qora daraxtni qurishda har doim rioya qilish kerak bo'lgan qoidalar mavjud:

• Ildiz qora rangga bo'yalgan bo'lishi kerak.
• Daraxtning barglari qora bo'lishi kerak.
• Qizil tugunda ikkita qora tugun bo'lishi kerak.
• Qora tugunda har qanday bola tugunlari bo'lishi mumkin.
• Tugundan uning barglarigacha bo'lgan yo'lda bir xil miqdordagi qora tugunlar bo'lishi kerak.
• Barglar o'rniga yangi tugunlar qo'shiladi.

Agar siz 3, 4 va 5-qoidalarni birgalikda ko'rib chiqsangiz, rang berish tugunlari daraxt bo'ylab navigatsiyani qanday tezlashtirishini tushunishingiz mumkin: qora tugunlardan o'tadigan yo'l har doim qizildan ko'ra qisqaroq. Shuning uchun daraxtning umumiy hajmi qora tugunlar soni bilan belgilanadi va bu o'lcham "qora balandlik" deb ataladi. Qizil-qora daraxt turli dasturlash tillarida amalga oshiriladi. Internetda Java uchun juda ko'p ilovalar mavjud, shuning uchun biz bu haqda uzoq vaqt to'xtalmaymiz, lekin funksionallik bilan tanishishni davom ettiramiz TreeMap.

SortedMap va NavigableMap interfeyslaridan olingan usullar

Kabi HashMap, TreeMapinterfeysni amalga oshiradi Map, ya'ni u TreeMapbarcha usullarga ega HashMap. Bundan tashqari, TreeMapu interfeyslarni amalga oshiradi SortedMapva NavigableMapulardan qo'shimcha funktsiyalarni oladi. — saralangan ma'lumotlar to'plamiga tegishli usullarni SortedMapkengaytiruvchi va qo'shadigan interfeys :Map

• firstKey(): xaritaning birinchi elementining kalitini qaytaradi;
• lastKey(): oxirgi elementning kalitini qaytaradi;
• headMap(K end): kalit bilan boshidan elementgacha joriyning barcha elementlarini o'z ichiga olgan xaritani qaytaradi end;
• tailMap(K start)start: elementdan boshlab va oxirigacha bo'lgan joriyning barcha elementlarini o'z ichiga olgan xaritani qaytaradi ;
• subMap(K start, K end)start: elementdan boshlab va tugmasi bo'lgan element bilan tugaydigan joriyning barcha elementlarini o'z ichiga olgan xaritani qaytaradi end.

NavigableMapSortedMap— xarita elementlari o‘rtasida harakatlanish usullarini kengaytiruvchi va qo‘shuvchi interfeys :

• firstEntry(): birinchi kalit-qiymat juftligini qaytaradi;
• lastEntry(): oxirgi kalit-qiymat juftligini qaytaradi;
• pollFirstEntry(): birinchi juftlikni qaytaradi va olib tashlaydi;
• pollLastEntry(): oxirgi juftlikni qaytaradi va olib tashlaydi;
• ceilingKey(K obj): obj kalitidan katta yoki unga teng bo'lgan eng kichik k kalitni qaytaradi. Agar bunday kalit bo'lmasa, nullni qaytaradi;
• floorKey(K obj): obj kalitidan kichik yoki teng bo'lgan eng katta k kalitni qaytaradi. Agar bunday kalit bo'lmasa, nullni qaytaradi;
• lowerKey(K obj): obj kalitidan kichikroq bo'lgan eng katta k kalitni qaytaradi. Agar bunday kalit bo'lmasa, nullni qaytaradi;
• higherKey(K obj): obj kalitidan katta bo'lgan eng kichik k kalitni qaytaradi. Agar bunday kalit bo'lmasa, nullni qaytaradi;
• ceilingEntry(K obj): ceilingKey(K obj) usuliga o'xshash, lekin kalit-qiymat juftligini (yoki null) qaytaradi;
• floorEntry(K obj): floorKey(K obj) usuliga o'xshash, lekin kalit-qiymat juftligini (yoki null) qaytaradi;
• lowerEntry(K obj): lowKey(K obj) usuliga o'xshash, lekin kalit-qiymat juftligini (yoki null) qaytaradi;
• higherEntry(K obj): highKey(K obj) usuliga o'xshash, lekin kalit-qiymat juftligini (yoki null) qaytaradi;
• descendingKeySet(): teskari tartibda tartiblangan barcha kalitlarni o'z ichiga olgan NavigablSetni qaytaradi;
• descendingMap(): teskari tartibda tartiblangan barcha juftlarni o'z ichiga olgan NavigableMapni qaytaradi;
• navigableKeySet(): saqlash tartibidagi barcha kalitlarni o'z ichiga olgan NavigableSet ob'ektini qaytaradi;
• headMap(K upperBound, boolean incl): boshidan yuqori chegara elementigacha bo'lgan juftlarni o'z ichiga olgan xaritani qaytaradi. incl argumenti upperBound elementi qaytarilgan xaritaga kiritilishi kerakligini belgilaydi;
• tailMap(K lowerBound, boolean incl): funksionallik avvalgi usulga o'xshaydi, faqat lowBound dan oxirigacha bo'lgan juftliklar qaytariladi;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Oldingi usullarda bo'lgani kabi, lowIncl va highIncl argumentlari yangi xaritaga chegara elementlarini kiritish yoki qo'shmaslik kerakligini ko'rsatadigan lowIncl va highIncl argumentlari qaytariladi.

Amalga oshirishning o'zida TreeMap, bizga tanish bo'lgan konstruktorlardan tashqari, taqqoslashning namunasini qabul qiladigan yana bittasi qo'shiladi. Ushbu taqqoslash moslamasi elementlarni saqlash tartibi uchun javobgar bo'ladi.

TreeMap-dan foydalanishga misollar

Qo'shimcha usullarning bunday ko'pligi keraksiz bo'lib tuyulishi mumkin, lekin ko'pincha ular dastlab tuyulganidan ko'ra foydaliroq bo'lib chiqadi. Keling, siz bilan ushbu misolni ko'rib chiqaylik. Tasavvur qiling, biz yirik kompaniyaning marketing bo'limida ishlaymiz va bizda reklama ko'rsatmoqchi bo'lgan odamlarning ma'lumotlar bazasi mavjud. Buning ikkita nuance bor:

• har bir odamga taassurotlar sonini kuzatib borishimiz kerak;
• Voyaga etmaganlarga reklama ko'rsatish algoritmi boshqacha.

PersonKeling , shaxs haqidagi barcha ma'lumotlarni saqlaydigan sinf yarataylik :

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

Biz sinfda mantiqni amalga oshiramiz 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){}
}

MainBiz yaratgan sinfda TreeMap, keyma'lum bir shaxs qayerda va valuebu oydagi reklama taassurotlari soni. Konstruktorda biz odamlarni yoshi bo'yicha saralaydigan komparatordan o'tamiz. mapTasodifiy qiymatlar bilan to'ldiring . Endi biz mini ma'lumotlar do'konimizdagi birinchi kattalar haqida ma'lumot olishimiz kerak. Biz buni Stream API yordamida qilamiz. Shundan so'ng, biz ikkita mustaqil xaritani olamiz, biz ularni reklama ko'rsatish usullariga o'tamiz. Ushbu muammoni hal qilishning ko'plab usullari mavjud. Sinfning usullar arsenali TreeMaphar qanday didga mos yechimlarni ixtiro qilish imkonini beradi. Ularning barchasini eslab qolish shart emas, chunki siz har doim ishlab chiqish muhitidagi hujjatlar yoki maslahatlardan foydalanishingiz mumkin. Ana xolos! Umid qilamanki, sinf endi TreeMapsiz uchun tushunarli va siz amaliy muammolarni hal qilishda uning aniq qo'llanilishini topasiz.