Ciri-ciri TreeMap dalam Java

Jika anda membaca artikel ini, kemungkinan besar anda sudah biasa dengan antara muka Peta dan kegunaannya. Jika tidak, maka di sini anda pergi. Hari ini kita akan bercakap tentang ciri pelaksanaan TreeMap, dan lebih khusus lagi, bagaimana ia berbeza daripada HashMap dan cara menggunakannya dengan betul.

Perbandingan TreeMap, HashMap dan LinkedHashMap

Pelaksanaan antara muka Peta yang paling biasa digunakan ialah HashMap . Ia mudah digunakan dan menjamin akses pantas kepada data, menjadikannya calon terbaik untuk kebanyakan tugas. Kebanyakan, tetapi tidak semua. Kadangkala adalah perlu untuk menyimpan data dalam bentuk berstruktur dengan keupayaan untuk menavigasi melaluinya. Dalam kes ini, satu lagi pelaksanaan antara muka Peta datang untuk menyelamatkan - TreeMap . TreeMap melaksanakan antara muka NavigableMap , yang mewarisi daripada SortedMap , yang seterusnya mewarisi daripada antara muka Peta . Dengan melaksanakan antara muka NavigableMap dan SortedMap , TreeMap memperoleh kefungsian tambahan yang HashMap tidak , tetapi ini memerlukan kos dalam prestasi. Terdapat juga kelas LinkedHashMap , yang juga membolehkan anda menyimpan data dalam susunan tertentu - mengikut susunan data itu ditambahkan. Untuk membantu anda 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 TreeMapadalah yang paling pelbagai fungsi, ia tidak boleh sentiasa disimpan nullsebagai kunci. Di samping itu, masa akses kepada elemen TreeMap akan menjadi yang paling lama. Oleh itu, jika anda tidak perlu menyimpan data dalam bentuk yang disusun, lebih baik menggunakan HashMapatau LinkedHashMap.

Pokok kayu hitam merah

Seperti yang mungkin anda perhatikan, di bawah tudung TreeMapia menggunakan struktur data yang dipanggil pokok merah-hitam. Ia adalah penyimpanan data dalam struktur ini yang memastikan susunan data disimpan. Apakah 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, 101 akan menjadi kunci. Jika anda menyimpan data dalam senarai tradisional dan perlu mencari elemen dengan kunci 101, anda perlu mengulangi kesemua 13 elemen untuk mencarinya. Untuk 13 elemen ini tidak kritikal; apabila bekerja dengan sejuta kita akan menghadapi masalah besar. Untuk menyelesaikan masalah tersebut, pengaturcara menggunakan struktur data yang lebih kompleks sedikit. Oleh itu, bertemu pokok merah-hitam!

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

Pencarian untuk elemen yang diperlukan bermula dari akar pokok, dalam kes kami adalah 61. Seterusnya, perbandingan dibuat dengan nilai yang diperlukan. Jika nilai kita kurang, kita ke kiri, jika lebih, kita ke kanan. Ini berlaku sehingga kita menemui nilai yang diperlukan atau memukul elemen dengan nilai null(daun pokok). Warna merah dan hitam digunakan untuk menjadikan pokok lebih mudah dinavigasi dan mengimbangi. Terdapat peraturan yang mesti sentiasa diikuti semasa membina pokok merah-hitam:

• Akar hendaklah berwarna hitam.
• Daun pokok itu hendaklah berwarna hitam.
• Nod merah mesti mempunyai dua nod anak hitam.
• Nod hitam boleh mempunyai sebarang nod anak.
• Laluan dari nod ke daunnya mesti mengandungi bilangan nod hitam yang sama.
• Nod baru ditambah sebagai ganti daun.

Jika anda melihat peraturan 3, 4 dan 5 bersama-sama, anda boleh memahami cara pewarnaan nod mempercepatkan navigasi melalui pepohon: laluan melalui nod hitam sentiasa lebih pendek daripada melalui nod merah. Oleh itu, jumlah saiz pokok ditentukan oleh bilangan nod hitam, dan saiz ini dipanggil "ketinggian hitam". Pokok merah-hitam dilaksanakan dalam bahasa pengaturcaraan yang berbeza. Terdapat banyak pelaksanaan untuk Java di Internet, jadi kami tidak akan memikirkannya lama, tetapi akan terus membiasakan diri dengan fungsi tersebut TreeMap.

Kaedah yang diperoleh daripada antara muka SortedMap dan NavigableMap

Seperti HashMap, TreeMapia melaksanakan antara muka Map, yang bermaksud bahawa ia TreeMapmempunyai semua kaedah yang HashMap. Tetapi sebagai tambahan, TreeMapia melaksanakan antara muka SortedMapdan NavigableMap, mendapatkan fungsi tambahan daripada mereka. SortedMap— antara muka yang memanjangkan Mapdan menambah kaedah yang berkaitan dengan set data yang diisih:

• firstKey(): mengembalikan kunci elemen pertama peta;
• lastKey(): mengembalikan kunci elemen terakhir;
• headMap(K end): mengembalikan peta yang mengandungi semua elemen semasa, dari awal hingga elemen dengan kunci end;
• tailMap(K start): mengembalikan peta yang mengandungi semua elemen semasa, bermula dengan elemen startdan berakhir dengan penghujung;
• subMap(K start, K end): mengembalikan peta yang mengandungi semua elemen semasa, bermula dengan elemen startdan berakhir dengan elemen dengan kunci end.

NavigableMap— antara muka yang memanjangkan SortedMapdan menambah kaedah untuk menavigasi antara elemen peta:

• firstEntry(): mengembalikan pasangan nilai kunci pertama;
• lastEntry(): mengembalikan pasangan nilai kunci terakhir;
• pollFirstEntry(): mengembalikan dan mengeluarkan pasangan pertama;
• pollLastEntry(): mengembalikan dan mengeluarkan pasangan terakhir;
• ceilingKey(K obj): Mengembalikan kunci terkecil k yang lebih besar daripada atau sama dengan obj kunci. Jika tiada kunci sedemikian, mengembalikan null;
• floorKey(K obj): Mengembalikan kunci terbesar k yang kurang daripada atau sama dengan obj kunci. Jika tiada kunci sedemikian, mengembalikan null;
• lowerKey(K obj): Mengembalikan kunci terbesar k yang lebih kecil daripada obj kunci. 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), tetapi mengembalikan pasangan nilai kunci (atau null);
• floorEntry(K obj): serupa dengan kaedah floorKey(K obj), tetapi mengembalikan pasangan nilai kunci (atau null);
• lowerEntry(K obj): serupa dengan kaedah lowerKey(K obj), tetapi mengembalikan pasangan nilai kunci (atau null);
• higherEntry(K obj): serupa dengan kaedah higherKey(K obj), tetapi 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 storan;
• headMap(K upperBound, boolean incl): mengembalikan peta yang mengandungi pasangan dari awal hingga elemen upperBound. Argumen incl menentukan sama ada elemen upperBound harus disertakan dalam peta yang dikembalikan;
• tailMap(K lowerBound, boolean incl): kefungsian adalah serupa dengan kaedah sebelumnya, hanya pasangan dari lowerBound hingga akhir dikembalikan;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Seperti dalam kaedah sebelumnya, pasangan dari lowerBound ke upperBound dikembalikan, argumen lowIncl dan highIncl menentukan sama ada untuk memasukkan elemen sempadan dalam peta baharu.

Dalam pelaksanaan itu sendiri TreeMap, sebagai tambahan kepada pembina yang kita kenali, satu lagi ditambah, yang menerima contoh pembanding. Pembanding ini akan bertanggungjawab untuk susunan unsur-unsur disimpan.

Contoh penggunaan TreeMap

Banyak kaedah tambahan seperti itu mungkin kelihatan tidak perlu, tetapi selalunya mereka ternyata lebih berguna daripada yang kelihatan pada mulanya. Mari lihat contoh ini bersama anda. Bayangkan bahawa kami bekerja di bahagian pemasaran sebuah syarikat besar, dan kami mempunyai pangkalan data orang yang kami ingin tunjukkan pengiklanan. Terdapat dua nuansa untuk ini:

• kita perlu menjejaki bilangan tera kepada setiap orang;
• Algoritma untuk memaparkan pengiklanan kepada kanak-kanak bawah umur adalah berbeza.

Mari buat kelas Personyang akan menyimpan semua maklumat yang tersedia kepada 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 melaksanakan logik dalam 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){}
}

Dalam kelas Mainyang kami buat TreeMap, di manakah keyorang tertentu, dan valueialah bilangan tera iklan bulan ini. Dalam pembina kita lulus pembanding yang akan menyusun orang mengikut umur. Isikan dengan mapnilai rawak. Kini kami perlu mendapatkan rujukan kepada orang dewasa pertama dalam stor data mini kami. Kami melakukan ini menggunakan API Strim. Selepas ini, kami mendapat dua peta bebas, yang kami berikan kepada kaedah yang memaparkan pengiklanan. Terdapat banyak cara untuk menyelesaikan masalah ini. Kumpulan kaedah kelas TreeMapmembolehkan anda mencipta penyelesaian untuk memenuhi setiap citarasa. Ia tidak perlu mengingati semuanya, kerana anda sentiasa boleh menggunakan dokumentasi atau petunjuk dari persekitaran pembangunan. Itu sahaja! Saya harap kelas itu kini TreeMapjelas kepada anda, dan anda akan mendapati aplikasi yang tepat untuknya dalam menyelesaikan masalah praktikal.