TreeMap di Jawa

Jika Anda membaca artikel ini, kemungkinan besar Anda sudah familiar dengan antarmuka Peta dan di mana dapat diterapkan dengan tepat. Jika tidak, maka datanglah ke sini . Hari ini kita akan berbicara tentang fitur implementasi Java TreeMap, dan lebih khusus lagi, perbedaannya dari HashMap dan cara menggunakannya dengan benar.

Membandingkan TreeMap, HashMap, dan LinkedHashMap

Implementasi antarmuka Peta yang paling banyak digunakan adalah HashMap. Mudah digunakan dan menjamin akses cepat ke data, sehingga merupakan kandidat terbaik untuk memecahkan sebagian besar masalah. Sebagian besar, tetapi tidak semua. Terkadang Anda perlu menyimpan data dengan cara yang terstruktur dan dapat menjelajahinya. Dalam hal ini, implementasi lain dari antarmuka Peta (TreeMap) datang untuk menyelamatkan. TreeMap mengimplementasikan antarmuka NavigableMap , yang mewarisi SortedMap , yang pada gilirannya mewarisi antarmuka Peta. Dengan menerapkan antarmuka NavigableMap dan SortedMap , TreeMap menerima fungsionalitas tambahan yang tidak tersedia di HashMap, tetapi membayar harga dalam hal kinerja. Ada juga LinkedHashMapclass , yang juga memungkinkan Anda untuk menyimpan data dalam urutan tertentu (urutan yang Anda tambahkan ke peta). Untuk memahami perbedaan antara ketiga kelas ini, lihat tabel ini: Seperti yang Anda lihat, kelas-kelas ini memiliki banyak kesamaan, tetapi ada juga beberapa perbedaan. Meskipun kelas TreeMap adalah yang paling serbaguna, kelas ini tidak selalu dapat menyimpan null sebagai kunci. Selain itu, mengakses elemen TreeMap membutuhkan waktu paling lama. Jadi, jika Anda tidak perlu menyimpan data dalam beberapa urutan, lebih baik menggunakan HashMap atau LinkedHashMap .

Pohon merah-hitam

Anda mungkin memperhatikan bahwa, di balik terpal, TreeMap menggunakan struktur data yang disebut pohon merah-hitam. Menyimpan data dalam struktur ini justru menyediakan pengurutan data. Jadi 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, dan 101 akan menjadi kunci. Jika Anda menyimpan data dalam daftar tradisional dan Anda perlu menemukan elemen dengan kunci 101, maka Anda harus melewati semua 13 elemen untuk menemukannya. Untuk 13 elemen, ini bukan masalah besar, tetapi saat bekerja dengan sejuta, kami akan mendapat masalah besar. Untuk mengatasi masalah ini, pemrogram menggunakan struktur data yang sedikit lebih kompleks. Di sinilah pohon merah-hitam memasuki panggung!Pencarian elemen dimulai dari akar pohon, yang dalam kasus kita adalah 61. Kemudian kita membandingkan nilai node dengan nilai yang kita cari. Jika nilai kita lebih kecil, maka kita pergi ke kiri; jika lebih besar, maka kita ke kanan. Proses ini berulang hingga kita menemukan nilai yang diinginkan atau menemukan elemen yang nilainya null (daun pohon). Warna merah dan hitam digunakan untuk menyederhanakan navigasi dan menyeimbangkan pohon. Ada aturan yang harus selalu diperhatikan saat membangun pohon merah-hitam:

• Akar harus hitam.
• Daun pohon harus berwarna hitam.
• Simpul merah harus memiliki dua simpul anak hitam.
• Node hitam dapat memiliki node anak dengan warna apa saja.
• Jalur dari simpul ke daunnya harus berisi jumlah simpul hitam yang sama.
• Node baru ditambahkan ke daun.

Jika Anda mempertimbangkan Aturan 3, 4, dan 5 secara bersamaan, Anda dapat memahami bagaimana warna simpul memungkinkan kita menavigasi pohon lebih cepat: jalur melalui simpul hitam selalu lebih pendek daripada jalur melalui simpul merah. Dengan demikian, ukuran total pohon ditentukan oleh jumlah simpul hitam, yang disebut "ketinggian hitam". Struktur data pohon merah-hitam diimplementasikan dalam berbagai bahasa pemrograman. Ada banyak implementasi Java di Internet, jadi kami tidak akan berlama-lama di sini. Sebagai gantinya, mari kita terus mengenal fungsionalitas TreeMap.

Metode yang berasal dari antarmuka SortedMap dan NavigableMap

Seperti HashMap, TreeMap mengimplementasikan antarmuka Peta, yang artinya TreeMap memiliki semua metode yang ada di HashMap. Tapi TreeMap juga mengimplementasikan antarmuka SortedMap dan NavigableMap , dan dengan demikian mendapatkan fungsionalitas tambahan darinya. SortedMap adalah antarmuka yang memperluas Peta dan menambahkan metode yang relevan dengan kumpulan data yang diurutkan:

• firstKey() : mengembalikan kunci elemen pertama di peta
• lastKey() : mengembalikan kunci elemen terakhir
• headMap(K end) : mengembalikan peta yang berisi semua elemen peta saat ini, dari awal hingga elemen dengan kunci akhir
• tailMap(K start) : mengembalikan peta yang berisi semua elemen peta saat ini, dari elemen awal hingga akhir
• subMap(K start, K ​​end) : mengembalikan peta yang berisi semua elemen peta saat ini, dari elemen awal hingga elemen dengan ujung kunci.

NavigableMap adalah antarmuka yang memperluas SortedMap dan menambahkan metode untuk menavigasi antar elemen peta:

• firstEntry() : mengembalikan pasangan kunci-nilai pertama
• lastEntry() : mengembalikan pasangan kunci-nilai terakhir
• pollFirstEntry() : mengembalikan dan menghapus pasangan pertama
• pollLastEntry() : mengembalikan dan menghapus pasangan terakhir
• ceilingKey(K obj) : mengembalikan kunci terkecil k yang lebih besar dari atau sama dengan kunci obj. Jika tidak ada kunci seperti itu, kembalikan nol
• floorKey(K obj) : mengembalikan kunci terbesar k yang kurang dari atau sama dengan kunci obj. Jika tidak ada kunci seperti itu, kembalikan nol
• lowerKey(K obj) : mengembalikan kunci terbesar k yang kurang dari kunci obj. Jika tidak ada kunci seperti itu, kembalikan nol
• higherKey(K obj) : mengembalikan kunci terkecil k yang lebih besar dari kunci obj. Jika tidak ada kunci seperti itu, kembalikan nol
• ceilingEntry(K obj) : mirip dengan metode ceilingKey(K obj), hanya mengembalikan key-value pair (atau null)
• floorEntry(K obj) : mirip dengan metode floorKey(K obj), hanya mengembalikan key-value pair (atau null)
• lowerEntry(K obj) : mirip dengan metode lowerKey(K obj), hanya mengembalikan key-value pair (atau null)
• higherEntry(K obj) : mirip dengan metode higherKey(K obj), hanya mengembalikan key-value pair (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 penyimpanannya
• headMap(K upperBound, boolean incl) : mengembalikan peta yang berisi pasangan dari awal hingga elemen upperBound. Parameter incl menunjukkan apakah akan menyertakan elemen upperBound di peta yang dikembalikan
• tailMap(K lowerBound, boolean incl) : fungsionalitas yang mirip dengan metode sebelumnya, hanya mengembalikan pasangan dari lowerBound hingga akhir
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : seperti metode sebelumnya, mengembalikan pasangan dari lowerBound ke upperBound; argumen lowIncl dan highIncl menunjukkan apakah akan menyertakan elemen batas dalam peta baru.

Selain konstruktor biasa, TreeMap memiliki konstruktor lain yang menerima turunan pembanding. Komparator ini bertanggung jawab atas urutan penyimpanan elemen.

Contoh Peta Pohon

Kelimpahan metode tambahan ini mungkin tampak tidak perlu, tetapi ternyata jauh lebih berguna daripada yang mungkin Anda sadari pada pandangan pertama. Mari kita jelajahi contoh berikut bersama-sama. Bayangkan kita bekerja di departemen pemasaran sebuah perusahaan besar, dan kita memiliki database orang-orang yang ingin kita tampilkan iklannya. Ada dua detail yang perlu diingat:

• Kami perlu melacak jumlah tayangan untuk setiap orang
• Algoritme untuk menampilkan iklan kepada anak di bawah umur berbeda.

Mari buat kelas Person , yang akan menyimpan semua informasi yang relevan tentang setiap orang:

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 Utama :

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("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 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 Utama, buat Peta Pohon, di mana setiap kunci mewakili orang tertentu, dan setiap nilai adalah jumlah tayangan iklan bulan ini. Kami memberikan konstruktor pembanding yang mengurutkan orang berdasarkan usia. Kami mengisi peta dengan nilai arbitrer. Sekarang kami ingin mendapatkan referensi ke orang dewasa pertama di gudang data kecil kami. Kami melakukan ini menggunakan Stream API. Kemudian kami mendapatkan dua peta terpisah, yang kami berikan ke metode yang menampilkan iklan. Ada banyak, banyak cara kami dapat menyelesaikan tugas ini. Gudang metode kelas TreeMap memungkinkan kita membuat solusi khusus untuk setiap kebutuhan. Anda tidak perlu mengingat semuanya, karena Anda selalu dapat menggunakan dokumentasi atau tips dari IDE Anda. Untuk memperkuat apa yang Anda pelajari, kami sarankan Anda menonton video pelajaran dari Kursus Java kami Itu saja untuk saat ini! Saya harap kelas TreeMap jelas bagi Anda sekarang, dan Anda akan menerapkannya dengan benar dalam menyelesaikan tugas pengkodean praktis.