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.
![Ciri-ciri TreeMap - 2]()
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 .
![Ciri-ciri TreeMap - 3]()
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:
Itu sahaja buat masa ini! Saya berharap kelas TreeMap jelas kepada anda sekarang, dan anda akan menggunakannya dengan betul dalam menyelesaikan tugas pengekodan praktikal.
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:
| HashMap | LinkedHashMap | Peta Pokok | |
|---|---|---|---|
| Susunan data | rawak. Tiada jaminan bahawa pesanan akan dikekalkan dari semasa ke semasa. | Dalam susunan data ditambah | Dalam tertib menaik atau berdasarkan pembanding yang ditentukan |
| Kerumitan masa | O(1) | O(1) | O(log(n)) |
| Antara muka yang dilaksanakan | Peta | Peta | NavigableMap SortedMap Map |
| Struktur data | baldi | baldi | Pokok merah-hitam |
| Sokongan untuk kunci null? | ya | ya | Ya, jika anda menggunakan pembanding, itu membenarkan null |
| Thread selamat? | Tidak | Tidak | Tidak |
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.
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.
- 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.
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.
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;
}
}
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) {}
}
GO TO FULL VERSION