SortedMap

SortedMap

Bu ma'ruzada SortedMap interfeysini o'rganamiz. Ushbu interfeysda mavjud bo'lgan yangi metodlarni ko'rib chiqamiz, shuningdek, SortedMap ning bir amalga oshirilishi — TreeMap va ularning farqlarini, shuningdek, HashMap bilan solishtirganda afzalliklarini tushunamiz.

Kartalar ierarxiyasi qanday tuzilganligini ko'rib chiqamiz. Bugun gapirayotgan SortedMap interfeysiga va uning amalga oshirilishi TreeMap ga alohida e'tibor bering:

SortedMap interfeysi — Map interfeysining kengaytmasi. U ko'p jihatdan SortedSet ga o'xshaydi (u o'z navbatida Set ni kengaytiradi), chunki ular ikkalasi ham tartiblangan qiymatlarni saqlash va ishlatish uchun o'xshash funksionallikni tasvirlaydi.

SortedSet <TValue> ni ishlatadi va saqlaydi, SortedMap SortedMap — juftliklar <TKey, TValue>. Bu karta, unda barcha elementlar klavishlarning o'sish tartibida tartiblangan.

SortedMap interfeysi Map ni kengaytiradi. Unda qo'shimcha quyidagi metodlar e'lon qilingan:

TreeMap Sinf

TreeMap sinfi SortedMap interfeysini amalga oshirilishi. Demak, TreeMap da SortedMap ning barcha qo'shimcha metodlari va Map interfeysidan kelgan standart metodlar amalga oshirilgan.

TreeMap turidagi obyektni quyidagicha yaratishingiz mumkin:

• TreeMap(): bo'sh kartani daraxt shaklida yaratadi;

• TreeMap(Map<? extends TKey,​? extends TValue> map): map kartasidan barcha elementlarni qo'shib daraxt yaratadi;

• TreeMap(SortedMap<TKey, ? extends TValue> smap): smap kartasidan barcha elementlarni qo'shib daraxt yaratadi;

• TreeMap(Comparator<? super TKey> comparator): qo'shiladigan barcha elementlar keyinchalik comparator tomonidan tartiblanadigan bo'sh daraxt yaratadi.

Kerakli joy TKey — juftlik elementlaridan klavishlarning turi, TValue — juftlik elementlaridagi qiymatlarni saqlaydigan TreeMap kartasidagi qiymatlar turi.

Comparator — bu SortedMap/TreeMap uchun juda muhim narsa. U bizga tartibni qanday qoidalar asosida tuzish kerakligini, ya'ni, kartamizda qanday tartibni yaratish kerakligini aytadi. Agar u SortedMap yaratilayotganda berilmagan bo'lsa, unda klavishimizning tabiiy tartibi ishlatiladi.

TreeMap ga elementlar qo'shish

Elementlar karta ichiga darhol juftliklar sifatida qo'shiladi: buning uchun put() metodi ishlatiladi. Birinchi argument sifatida klavish, ikkinchi argument sifatida qiymat yig'iladi. Masalan, talabalarning ro'yxati va ularning baholarini yaratmoqchimiz.

// Talabalar kartasi yaratamiz va baholarini qo'shamiz
SortedMap<String, Integer> map = new TreeMap <String,Integer>();

map.put("Anton", 5);
map.put("Sergey", 5);
map.put("Ruslan", 5);
map.put("Yuriy", 4);
map.put("Nikolay", 4);
map.put("Oleg", 3);
map.put("Oleg", 5);

System.out.println(map); // Kartani chop etamiz

Natija:

Agar element qo'shilayotganda shu klavish bilan ma'lumot allaqachon mavjud bo'lsa, eski qiymat yangi qiymat bilan almashtiriladi. Bu ikki juftlik elementlari — ("Oleg",3) va ("Oleg",5) namunasi orqali ko'rsatilgan.

Endi yaratilgan Comparator bilan misolni ko'rib chiqamiz. Faraz qilaylik, biz klavish-string uzunligiga qarab tartiblangan elementlarni saqlashimiz kerak. Agar klavishlarning uzunligi teng bo'lsa, keyinchalik alifbo tartibida (stringlar uchun tabiiy tartib) taqqoslash amalga oshiriladi:

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

// LengthComparator orqali tartiblangan kartani yaratamiz
SortedMap<String, Integer> lengthComaredMap = new TreeMap<String,Integer>(new LengthComparator());

lengthComaredMap.put("Yuriy",4);
lengthComaredMap.put("Oleg",5);
lengthComaredMap.put("Ruslan",4);
lengthComaredMap.put("Yan",4);

Ketma-ketlik quyidagicha bo'ladi:

Bunday xatti-harakat TreeMap ni indekslar sifatida so'zlar (String), sonlar emas, bo'lsa ajratilgan massiv yoki ro'yxatga o'xshaydi.

Metodlar SortedMap TreeMap sinfi misolida

1. Agar sizga birinchi talabani klavishini olish kerak bo'lsa, firstKey() metodidan foydalanishingiz mumkin:

   
   // Birinchi klavish
   String firstKey = map.firstKey();
   System.out.println("Birinchi klavish → " + firstKey);
   

   Natija: Birinchi klavish → Anton

2. Agar sizga oxirgi talabani klavishini olish kerak bo'lsa, lastKey() metodidan foydalanishingiz mumkin:

   
   // Oxirgi klavish
   String lastKey = map.lastKey();
   System.out.println("Oxirgi klavish → " + lastKey);
   

   Natija: Oxirgi klavish → Yuriy

3. “Sergey” klavishidan keyingi barcha obyektlarni olish:

   
   // Sergey klavishidan keyin boshlangandan keyin kartadagi elementlarni olish
   Map<String, Integer> tailMap = map.tailMap("Sergey");
   System.out.println("tailMap: " + tailMap);
   

   Natija: tailMap: {Sergey=5, Yuriy=4}

4. “Nikolay” klavishidan oldingi barcha obyektlarni olish:

   
   Map<String, Integer> headMap = map.headMap("Nikolay");
   System.out.println("headMap: " + headMap);
   

   Natija: headMap: {Anton=5}

5. “Oleg” klavishidan keyingi, lekin “Sergey” klavishidan oldingi barcha obyektlarni olish:

   
   // Oleg va Sergey klavishlari orasidagi kartadagi elementlarni olish
   Map<String, Integer> subMap = map.subMap("Oleg", "Sergey");
   System.out.println("subMap: " + subMap);
   

   Natija: subMap: {Oleg=5, Ruslan=5}

HashMap va SortedMap/TreeMap solishtirish

Keling, elementlarni saqlash tartibi va ketma-ketligi haqida gaplashamiz:

• HashMap bizga iteratsiyalar tartibi haqida hech qanday kafolat bermaydi, u yangi elementlar qo'shilishi bilan butunlay o'zgarishi mumkin.

• TreeMap da tartib klavishlarning "natural order" ga muvofiq bo'ladi va ular compareTo() metodi bo'yicha taqqoslanadi (yoki tashqaridan taqdim etilgan Comparator orqali). Shuningdek, unutmaslik kerakki, TreeMap SortedMap interfeysini amalga oshiradi, unda ushbu tartiblangan tartibga bog'liq metodlar mavjud.

Agar biz samaradorlik va tezlik haqida gapiradigan bo'lsak:

• HashMap — klavishlarni xeshlash asosida ishlaydigan karta. U kiritish va olish amallarini O(1) vaqtida qo'llab-quvvatlaydi. Buning uchun klavishlarda hashCode() va equals() metodlari mavjud bo'lishi kerak.

• TreeMap — daraxt asosida qilinadigan karta. Uning kiritish va olish amallari kartadagi elementlar soniga bog'liq logarifmik vaqt bilan amalga oshiriladi, bu O(log n) bo'ladi. Bu elementlarning qaysidir taqqoslash mexanizmi bo'lishi kerak, u bizning klavishimiz orqali yoki tashqi Comparator orqali taqdim etiladi. Bu iteratsiyalar tartibini belgilaydi.

Ushbu omillarga asoslanib, qachon va nima ishlatishimiz yaxshiroq ekanini aniqlaymiz.

Agar bizga qiymatlarni qaysidir tartibda saqlash kerak bo'lsa, tanlov aniq — bizga SortedMap kerak. Garchi u HashMap ga qaraganda biroz sekinroq ishlasa ham, u biz uchun muhim vazifalarni bajaradi.

Ilgari aytilganidek, SortedMap bilan biz birinchi (yoki oxirgi) klavishni, qiymatni yoki kartamizdagi klavish-qiymat juftligini olishingiz mumkin, bu qiymat qachon qo'shilganligidan qat'iy nazar. HashMap ning amalga oshirilishi bilan biz buni qila olmaymiz.

Buni talabalarning nomi klavishlari va baholari qiymatlari bo'lgan karta misolida ko'rib chiqamiz. Keling, ro'yxat bilan teskari alifbo tartibida ishlashni xohlaysiz deb tasavvur qilaylik.

1.

// Teskari tartibda SortedMap yaratamiz
SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anton", 5);
sorted.put("Sergey", 5);
sorted.put("Yuriy", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

// HashMap va manual ravishda tartiblash
HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anton", 5);
hash.put("Sergey", 5);
hash.put("Yuriy", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Yoki qo'lda tartiblash, elementlarni massiv yoki ro'yxatga saqlash (qo'shilish tartibini saqlash)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();

Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Misolda ko'rsatilgandek: HashMap ni ishlatishda vazifa ancha murakkab ko'rinadi, chunki HashMap bizga na saqlash tartibini, na karta elementlarini olish tartibini kafolatlaydi.