Fitur TreeMap di Java

Jika Anda membaca artikel ini, kemungkinan besar Anda sudah familiar dengan antarmuka Peta dan kegunaannya. Jika tidak, maka ini dia. Hari ini kita akan berbicara tentang fitur implementasi TreeMap, dan lebih khusus lagi, perbedaannya dengan HashMap dan cara menggunakannya dengan benar.

Perbandingan TreeMap, HashMap dan LinkedHashMap

Implementasi antarmuka Map yang paling umum digunakan adalah HashMap . Mudah digunakan dan menjamin akses cepat ke data, menjadikannya kandidat terbaik untuk sebagian besar tugas. Sebagian besar, tapi tidak semua. Terkadang perlu untuk menyimpan data dalam bentuk terstruktur dengan kemampuan untuk menavigasinya. Dalam hal ini, implementasi lain dari antarmuka Peta akan membantu - TreeMap . TreeMap mengimplementasikan antarmuka NavigableMap , yang mewarisi dari SortedMap , yang pada gilirannya mewarisi dari antarmuka Peta . Dengan mengimplementasikan antarmuka NavigableMap dan SortedMap , TreeMap memperoleh fungsionalitas tambahan yang tidak dimiliki HashMap , tetapi hal ini harus dibayar mahal dalam hal kinerja. Ada juga kelas LinkedHashMap , yang juga memungkinkan Anda menyimpan data dalam urutan tertentu - sesuai urutan penambahannya. Untuk membantu Anda memahami perbedaan ketiga kelas ini, lihat tabel ini: Seperti yang Anda lihat, kelas-kelas ini memiliki banyak kesamaan, namun ada juga beberapa perbedaan. Meskipun kelas TreeMapadalah yang paling multifungsi, namun tidak selalu dapat disimpan nullsebagai kunci. Selain itu, waktu akses ke elemen TreeMap akan menjadi yang paling lama. Oleh karena itu, jika tidak perlu menyimpan data dalam bentuk yang diurutkan, lebih baik menggunakan HashMapatau LinkedHashMap.

Pohon ebony merah

Seperti yang mungkin Anda perhatikan, TreeMapia menggunakan struktur data yang disebut pohon merah-hitam. Penyimpanan data dalam struktur inilah yang memastikan urutan penyimpanan data. Pohon apa ini? Mari kita cari tahu! Bayangkan Anda perlu menyimpan pasangan Number-String. Angka 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 akan menjadi kuncinya. Jika Anda menyimpan data dalam daftar tradisional dan perlu menemukan elemen dengan kunci 101, Anda perlu mengulangi ke-13 elemen untuk menemukannya. Untuk 13 elemen ini tidak penting, ketika bekerja dengan satu juta kita akan mendapat masalah besar. Untuk memecahkan masalah tersebut, pemrogram menggunakan struktur data yang sedikit lebih kompleks. Oleh karena itu, temuilah pohon merah-hitam!

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

Pencarian elemen yang diperlukan dimulai dari akar pohon, dalam kasus kami adalah 61. Selanjutnya dilakukan perbandingan dengan nilai yang diperlukan. Kalau nilainya lebih kecil kita ke kiri, kalau lebih kita ke kanan. Hal ini terjadi sampai kita menemukan nilai yang diperlukan atau menemukan elemen dengan nilai null(daun pohon). Warna merah dan hitam digunakan untuk membuat pohon lebih mudah dinavigasi dan diseimbangkan. Ada aturan yang harus selalu dipatuhi saat membangun pohon merah-hitam:

• Akarnya harus berwarna hitam.
• Daun pohonnya harus berwarna hitam.
• Node merah harus memiliki dua node anak berwarna hitam.
• Node hitam dapat memiliki node turunan apa pun.
• Jalur dari sebuah node ke daunnya harus berisi jumlah node hitam yang sama.
• Node baru ditambahkan sebagai pengganti daun.

Jika Anda melihat aturan 3, 4, dan 5 secara bersamaan, Anda dapat memahami bagaimana pewarnaan node mempercepat navigasi melalui pohon: jalur melalui node hitam selalu lebih pendek daripada melalui node merah. Oleh karena itu, ukuran total pohon ditentukan oleh jumlah simpul hitam, dan ukuran ini disebut “tinggi hitam”. Pohon merah-hitam diimplementasikan dalam berbagai bahasa pemrograman. Ada banyak implementasi Java di Internet, jadi kami tidak akan membahasnya terlalu lama, tetapi akan terus mengenal fungsinya TreeMap.

Metode yang berasal dari antarmuka SortedMap dan NavigableMap

Seperti HashMap, TreeMapia mengimplementasikan antarmuka Map, yang berarti ia TreeMapmemiliki semua metode yang ada HashMap. Namun selain itu, TreeMapia mengimplementasikan antarmuka SortedMapdan NavigableMap, memperoleh fungsionalitas tambahan darinya. SortedMap— antarmuka yang memperluas Mapdan menambahkan metode yang relevan dengan kumpulan data yang diurutkan:

• firstKey(): mengembalikan kunci elemen pertama peta;
• lastKey(): mengembalikan kunci elemen terakhir;
• headMap(K end): mengembalikan peta yang berisi semua elemen yang ada saat ini, dari awal hingga elemen dengan kunci end;
• tailMap(K start): mengembalikan peta yang berisi semua elemen saat ini, dimulai dengan elemen startdan diakhiri dengan akhir;
• subMap(K start, K end): mengembalikan peta yang berisi semua elemen yang ada saat ini, dimulai dengan elemen startdan diakhiri dengan elemen dengan key end.

NavigableMap— antarmuka yang memperluas SortedMapdan menambahkan metode untuk bernavigasi antar elemen peta:

• firstEntry(): mengembalikan pasangan nilai kunci pertama;
• lastEntry(): mengembalikan pasangan nilai kunci terakhir;
• pollFirstEntry(): mengembalikan dan menghapus pasangan pertama;
• pollLastEntry(): mengembalikan dan menghapus pasangan terakhir;
• ceilingKey(K obj): Mengembalikan kunci terkecil k yang lebih besar atau sama dengan objek kunci. Jika tidak ada kunci seperti itu, kembalikan null;
• floorKey(K obj): Mengembalikan k kunci terbesar yang kurang dari atau sama dengan objek kunci. Jika tidak ada kunci seperti itu, kembalikan null;
• lowerKey(K obj): Mengembalikan k kunci terbesar yang lebih kecil dari objek kunci. Jika tidak ada kunci seperti itu, kembalikan null;
• higherKey(K obj): Mengembalikan kunci terkecil k yang lebih besar dari kunci obj. Jika tidak ada kunci seperti itu, kembalikan null;
• ceilingEntry(K obj): mirip dengan metode langit-langitKey(K obj), tetapi mengembalikan pasangan nilai kunci (atau null);
• floorEntry(K obj): mirip dengan metode floorKey(K obj), tetapi mengembalikan pasangan nilai kunci (atau null);
• lowerEntry(K obj): mirip dengan metode lowerKey(K obj), tetapi mengembalikan pasangan nilai kunci (atau null);
• higherEntry(K obj): mirip dengan metode highKey(K obj), tetapi mengembalikan pasangan nilai kunci (atau null);
• descendingKeySet(): mengembalikan NavigableSet yang berisi semua kunci yang diurutkan dalam urutan terbalik;
• descendingMap(): mengembalikan NavigableMap yang berisi semua pasangan yang diurutkan dalam urutan terbalik;
• navigableKeySet(): mengembalikan objek NavigableSet yang berisi semua kunci dalam urutan penyimpanan;
• headMap(K upperBound, boolean incl): mengembalikan peta yang berisi pasangan dari awal hingga elemen batas atas. Argumen incl menentukan apakah elemen upperBound harus disertakan dalam peta yang dikembalikan;
• tailMap(K lowerBound, boolean incl): fungsinya mirip dengan metode sebelumnya, hanya pasangan dari LowerBound hingga akhir yang dikembalikan;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Seperti pada metode sebelumnya, pasangan dari lowerBound ke upperBound dikembalikan, argumen lowIncl dan highIncl menunjukkan apakah akan menyertakan elemen batas di peta baru.

Dalam implementasinya sendiri TreeMap, selain konstruktor yang kita kenal, satu lagi ditambahkan, yang menerima instance dari komparator. Komparator ini akan bertanggung jawab atas urutan penyimpanan elemen.

Contoh penggunaan TreeMap

Banyaknya metode tambahan mungkin tampak tidak diperlukan, tetapi sering kali metode tersebut ternyata jauh lebih berguna daripada yang terlihat pada awalnya. Mari kita lihat contoh ini bersama Anda. Bayangkan kita bekerja di departemen pemasaran sebuah perusahaan besar, dan kita memiliki database orang-orang yang ingin kita tampilkan iklannya. Ada dua perbedaan dalam hal ini:

• kita perlu melacak jumlah tayangan setiap orang;
• Algoritme untuk menampilkan iklan kepada anak di bawah umur berbeda-beda.

Mari kita buat kelas Personyang akan menyimpan semua informasi yang tersedia bagi kita tentang seseorang:

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

Kami menerapkan logika di kelas 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){}
}

Di kelas Mainyang kami buat TreeMap, di mana keyorang tertentu, dan valuejumlah tayangan iklan bulan ini. Di konstruktor kami melewati komparator yang akan mengurutkan orang berdasarkan usia. Isi dengan mapnilai acak. Sekarang kita perlu mendapatkan referensi ke orang dewasa pertama di penyimpanan data mini kita. Kami melakukan ini menggunakan Stream API. Setelah ini, kami mendapatkan dua peta independen, yang kami teruskan ke metode menampilkan iklan. Ada banyak sekali cara untuk mengatasi masalah ini. Kumpulan metode kelas ini TreeMapmemungkinkan Anda menemukan solusi yang sesuai dengan setiap selera. Tidak perlu mengingat semuanya, karena Anda selalu dapat menggunakan dokumentasi atau petunjuk dari lingkungan pengembangan. Itu saja! Saya harap kelas ini sekarang TreeMapjelas bagi Anda, dan Anda akan menemukan penerapan yang tepat dalam memecahkan masalah praktis.