TreeMap di Jawa

Jika anda membaca artikel ini, kemungkinan besar anda sudah biasa dengan antara muka Peta dan tempat yang sesuai digunakan. Jika tidak, datanglah ke sini . Hari ini kita akan bercakap tentang ciri-ciri pelaksanaan Java TreeMap, dan lebih khusus lagi, bagaimana ia berbeza daripada HashMap dan cara menggunakannya dengan betul.

Membandingkan TreeMap, HashMap dan LinkedHashMap

Pelaksanaan antara muka Peta yang paling banyak digunakan ialah HashMap. Ia mudah digunakan dan menjamin akses cepat kepada data, jadi ia adalah calon terbaik untuk menyelesaikan kebanyakan masalah. Kebanyakan, tetapi tidak semua. Kadangkala anda perlu menyimpan data dalam cara berstruktur dan boleh menavigasi melaluinya. Dalam kes ini, satu lagi pelaksanaan antara muka Peta (TreeMap) datang untuk menyelamatkan. TreeMap melaksanakan antara muka NavigableMap , yang mewarisi SortedMap , yang seterusnya mewarisi antara muka Peta. Dengan melaksanakan antara muka NavigableMap dan SortedMap , TreeMap menerima fungsi tambahan yang tidak tersedia dalam HashMap, tetapi ia membayar harga dari segi prestasi. Terdapat juga LinkedHashMapclass , yang juga membolehkan anda menyimpan data dalam susunan tertentu (urutan yang anda tambahkan pada peta). Untuk memahami perbezaan antara tiga kelas ini, lihat jadual ini: Seperti yang anda lihat, kelas ini mempunyai banyak persamaan, tetapi terdapat juga beberapa perbezaan. Walaupun kelas TreeMap adalah yang paling serba boleh, ia tidak boleh sentiasa menyimpan null sebagai kunci. Selain itu, mengakses elemen TreeMap mengambil masa yang paling lama. Jadi, jika anda tidak perlu menyimpan data dalam beberapa susunan yang disusun, lebih baik menggunakan HashMap atau LinkedHashMap .

Pokok merah-hitam

Anda mungkin perasan bahawa, di bawah tudung, TreeMap menggunakan struktur data yang dipanggil pokok merah-hitam. Menyimpan data dalam struktur ini adalah tepat yang menyediakan pesanan data. Jadi apakah jenis pokok ini? Mari kita fikirkan! Bayangkan anda perlu menyimpan pasangan Number-String. Nombor 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, dan 101 akan menjadi kunci. Jika anda menyimpan data dalam senarai tradisional dan anda perlu mencari elemen dengan kunci 101, maka anda perlu melangkah ke semua 13 elemen untuk mencarinya. Untuk 13 elemen, ini bukan masalah besar, tetapi apabila bekerja dengan sejuta, kita akan menghadapi masalah besar. Untuk menyelesaikan masalah ini, pengaturcara menggunakan struktur data yang sedikit lebih kompleks. Di sinilah pokok merah-hitam memasuki pentas!Carian untuk elemen bermula pada akar pokok, yang dalam kes kami ialah 61. Kemudian kami membandingkan nilai nod dengan nilai yang kami cari. Jika nilai kita kurang, maka kita pergi ke kiri; jika ia lebih besar, maka kita pergi ke kanan. Proses ini berulang sehingga kita menemui nilai yang diingini atau menemui elemen yang nilainya adalah null (daun pokok). Warna merah dan hitam digunakan untuk memudahkan navigasi dan mengimbangi pokok. Terdapat peraturan yang mesti sentiasa dipatuhi apabila membina pokok merah-hitam:

• Akar mesti hitam.
• Daun pokok mestilah berwarna hitam.
• Nod merah mesti mempunyai dua nod anak hitam.
• Nod hitam boleh mempunyai nod anak dalam sebarang warna.
• Laluan dari nod ke daunnya mesti mengandungi bilangan nod hitam yang sama.
• Nod baharu ditambahkan pada daun.

Jika anda mempertimbangkan Peraturan 3, 4 dan 5 bersama-sama, anda boleh memahami cara warna nod membolehkan kami menavigasi pepohon dengan lebih cepat: laluan melalui nod hitam sentiasa lebih pendek daripada satu melalui nod merah. Sehubungan itu, jumlah saiz pokok ditentukan oleh bilangan nod hitam, yang dipanggil "ketinggian hitam". Struktur data pokok merah-hitam dilaksanakan dalam pelbagai bahasa pengaturcaraan. Terdapat banyak pelaksanaan Java di Internet, jadi kami tidak akan berlama-lama di sini. Sebaliknya, mari teruskan mengenali fungsi TreeMap.

Kaedah yang datang daripada antara muka SortedMap dan NavigableMap

Seperti HashMap, TreeMap melaksanakan antara muka Peta, yang bermaksud TreeMap mempunyai semua kaedah yang wujud dalam HashMap. Tetapi TreeMap juga melaksanakan antara muka SortedMap dan NavigableMap , dan dengan itu memperoleh fungsi tambahan daripadanya. SortedMap ialah antara muka yang memanjangkan Peta dan menambahkan kaedah yang berkaitan dengan set data yang diisih:

• firstKey() : mengembalikan kunci elemen pertama dalam peta
• lastKey() : mengembalikan kunci elemen terakhir
• headMap(K end) : mengembalikan peta yang mengandungi semua elemen peta semasa, dari awal hingga elemen dengan hujung kunci
• tailMap(K start) : mengembalikan peta yang mengandungi semua elemen peta semasa, dari elemen mula hingga akhir
• subMap(K start, K ​​end) : mengembalikan peta yang mengandungi semua elemen peta semasa, dari elemen mula hingga elemen dengan hujung kunci.

NavigableMap ialah antara muka yang memanjangkan SortedMap dan menambahkan kaedah untuk menavigasi antara elemen peta:

• firstEntry() : mengembalikan pasangan nilai kunci pertama
• lastEntry() : mengembalikan pasangan nilai kunci terakhir
• pollFirstEntry() : mengembalikan dan memadamkan pasangan pertama
• pollLastEntry() : mengembalikan dan memadam pasangan terakhir
• ceilingKey(K obj) : mengembalikan kunci terkecil k yang lebih besar daripada atau sama dengan kunci obj. Jika tiada kunci sedemikian, mengembalikan null
• floorKey(K obj) : mengembalikan kunci terbesar k yang kurang daripada atau sama dengan kunci obj. Jika tiada kunci sedemikian, mengembalikan null
• lowerKey(K obj) : mengembalikan kunci terbesar k yang kurang daripada kunci obj. Jika tiada kunci sedemikian, mengembalikan null
• higherKey(K obj) : mengembalikan kunci terkecil k yang lebih besar daripada obj kunci. Jika tiada kunci sedemikian, mengembalikan null
• ceilingEntry(K obj) : serupa dengan kaedah ceilingKey(K obj), hanya mengembalikan pasangan nilai kunci (atau null)
• floorEntry(K obj) : serupa dengan kaedah floorKey(K obj), hanya mengembalikan pasangan nilai kunci (atau null)
• lowerEntry(K obj) : serupa dengan kaedah lowerKey(K obj), hanya mengembalikan pasangan nilai kunci (atau null)
• higherEntry(K obj) : serupa dengan kaedah higherKey(K obj), hanya mengembalikan pasangan nilai kunci (atau null)
• descendingKeySet() : mengembalikan NavigableSet yang mengandungi semua kunci yang diisih dalam susunan terbalik
• descendingMap() : mengembalikan NavigableMap yang mengandungi semua pasangan yang diisih dalam susunan terbalik
• navigableKeySet() : mengembalikan objek NavigableSet yang mengandungi semua kunci dalam susunan ia disimpan
• headMap(K upperBound, boolean incl) : mengembalikan peta yang mengandungi pasangan dari awal hingga elemen upperBound. Parameter incl menunjukkan sama ada untuk memasukkan elemen upperBound dalam peta yang dikembalikan
• tailMap(K lowerBound, boolean incl) : fungsi yang serupa dengan kaedah sebelumnya, hanya mengembalikan pasangan dari lowerBound hingga akhir
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : seperti kaedah sebelumnya, mengembalikan pasangan dari lowerBound ke upperBound; hujah lowIncl dan highIncl menunjukkan sama ada untuk memasukkan unsur sempadan dalam peta baharu.

Sebagai tambahan kepada pembina biasa, TreeMap mempunyai pembina lain yang menerima contoh pembanding. Pembanding ini bertanggungjawab untuk susunan elemen disimpan.

Contoh TreeMap

Banyak kaedah tambahan ini mungkin kelihatan tidak perlu, tetapi ia ternyata lebih berguna daripada yang anda mungkin sedari pada pandangan pertama. Mari kita terokai contoh berikut bersama-sama. Bayangkan kami bekerja di bahagian pemasaran sebuah syarikat besar, dan kami mempunyai pangkalan data orang yang ingin kami paparkan iklan. Terdapat dua butiran yang perlu diingat:

• Kita perlu menjejaki bilangan tera untuk setiap orang
• Algoritma untuk memaparkan iklan kepada kanak-kanak bawah umur adalah berbeza.

Mari buat kelas Orang , yang akan menyimpan semua maklumat yang berkaitan 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 melaksanakan logik dalam 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) {}
}

Dalam kelas Utama, buat TreeMap, di mana setiap kunci mewakili orang tertentu dan setiap nilai ialah bilangan tera iklan bulan ini. Kami memberikan pembina sebagai pembanding yang menyusun orang mengikut umur. Kami mengisi peta dengan nilai sewenang-wenangnya. Sekarang kami ingin mendapatkan rujukan kepada orang dewasa pertama dalam repositori data kecil kami. Kami melakukan ini menggunakan API Strim. Kemudian kami mendapat dua peta berasingan, yang kami hantar kepada kaedah yang memaparkan iklan. Terdapat banyak cara yang boleh kami lakukan untuk menyelesaikan tugasan ini. Senjata kaedah kelas TreeMap membolehkan kami mencipta penyelesaian tersuai untuk setiap keperluan. Anda tidak perlu mengingati kesemuanya, kerana anda sentiasa boleh menggunakan dokumentasi atau petua daripada IDE anda. Untuk mengukuhkan apa yang anda pelajari, kami cadangkan anda menonton pelajaran video daripada Kursus Java kami Itu sahaja buat masa ini! Saya berharap kelas TreeMap jelas kepada anda sekarang, dan anda akan menggunakannya dengan betul dalam menyelesaikan tugas pengekodan praktikal.