Peta Tersusun

Peta Isih

Dalam pelajaran ini, kita akan mengkaji antara muka SortedMap . Kami akan meneroka kaedah baharu yang muncul dalam antara muka ini, serta ciri satu pelaksanaan SortedMap — TreeMap — dan perbezaan antara pelaksanaan, serta kelebihannya berbanding HashMap .

Mari lihat rupa hierarki peta. Beri perhatian khusus kepada antara muka SortedMap dan pelaksanaan TreeMapnya — ia adalah tumpuan kami hari ini:

Antara muka SortedMap memanjangkan antara muka Peta . Dalam banyak cara, ia serupa dengan SortedSet (yang seterusnya memanjangkan Set ), kerana kedua-duanya menerangkan fungsi yang serupa untuk menyimpan dan menggunakan nilai yang diisih.

SortedSet berfungsi dengan dan menyimpan<TValue>, tetapi SortedMap menyimpan<TKey, TValue>. Ia adalah peta yang menyimpan semua elemennya dalam tertib menaik bagi kuncinya.

Antara muka SortedMap memanjangkan Peta . Ia menambah kaedah berikut:

Kelas TreeMap

Kelas TreeMap ialah pelaksanaan antara muka SortedMap . Iaitu, TreeMap melaksanakan semua kaedah yang ditambahkan oleh SortedMap serta kaedah standard daripada antara muka Peta .

Anda boleh membuat objek TreeMap menggunakan pembina seperti ini:

• TreeMap() : mencipta peta kosong yang dilaksanakan sebagai pokok;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : mencipta pokok dan menambah semua elemen daripada peta input;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : mencipta pepohon dan menambah semua elemen daripada peta diisih input;

• TreeMap(Comparator<? super TKey> comparator) : mencipta pokok kosong — pembanding akan digunakan untuk mengisih semua elemen kerana ia kemudiannya ditambah.

Di sini TKey ialah jenis kekunci dalam pasangan yang disimpan, dan TValue ialah jenis nilai dalam pasangan yang disimpan dalam TreeMap .

Comparator cukup penting untuk SortedMap / TreeMap . Ia menetapkan peraturan untuk mengisih — atau memesan — peta kami. Jika kami tidak menyediakan pembanding, maka susunan semula jadi kunci kami akan digunakan apabila kami membuat SortedMap .

Menambah elemen pada TreeMap

Elemen ditambah pada peta sebagai pasangan menggunakan kaedah put() . Kunci diluluskan sebagai hujah pertama, dan nilai diluluskan sebagai yang kedua. Sebagai contoh, katakan kita ingin membuat senarai pelajar dan gred mereka.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Keputusan:

Apabila kita menambah pasangan nilai kunci, jika kunci sudah wujud dalam koleksi, maka nilai lama digantikan dengan nilai baharu. Tingkah laku ini digambarkan dalam contoh kami dengan dua pasangan yang mempunyai kunci yang sama — ("Oliver", 3) dan ("Oliver", 5) .

Mari kita lihat contoh dengan Comparator yang kami buat. Katakan kita ingin menyimpan elemen yang disusun mengikut panjang rentetan kunci. Jika panjang kekunci adalah sama, maka kami akan mengisih mengikut abjad (urutan semula jadi rentetan):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Berikut ialah urutan yang terhasil:

Tingkah laku ini menjadikan TreeMap seperti tatasusunan atau senarai yang diisih yang indeksnya ialah perkataan ( String ) dan bukannya nombor.

Kaedah SortedMap dalam kelas TreeMap

1. Jika anda perlu mendapatkan kunci pelajar pertama, anda boleh menggunakan kaedah firstKey() :

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Keputusan: Kunci pertama → Anthony

2. Jika anda perlu mendapatkan kunci pelajar terakhir, anda boleh menggunakan kaedah lastKey() :

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Keputusan: Kunci Terakhir → Jeff

3. Dapatkan semua objek yang datang selepas objek dengan kekunci " Sara ":

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Keputusan: tailMap: {Sara=5, Jeff=4}

4. Dapatkan semua objek yang datang sebelum objek dengan kekunci " Nick ":

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Keputusan: headMap: {Anthony=5}

5. Dapatkan semua objek yang datang selepas objek dengan kunci " Oliver " dan datang sebelum objek dengan kunci " Sara ":

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Keputusan: subPeta: {Oliver=5, Roxy=5}

Perbandingan HashMap dan SortedMap/TreeMap

Mari kita bincangkan tentang cara elemen disusun dan disimpan:

• Memandangkan HashMap tidak memberi kami sebarang jaminan tentang pesanan semasa berulang, pesanan itu mungkin berubah sepenuhnya apabila elemen baharu ditambahkan.

• Dalam TreeMap , pesanan adalah berdasarkan "pesanan semula jadi" kekunci mengikut kaedah compareTo() mereka (atau Comparator yang kami sediakan). Juga, jangan lupa bahawa TreeMap melaksanakan antara muka SortedMap , yang mengandungi kaedah yang bergantung pada susunan isihan ini.

Sekarang kita beralih kepada pertimbangan prestasi dan kelajuan:

• HashMap ialah peta berdasarkan kekunci pencincangan. Ia boleh memasukkan dan mendapatkan elemen dalamO(1), masa tetap. Untuk menyokong ini, kunci mesti melaksanakanhashCode()danequals().

• TreeMap ialah peta berasaskan pokok. Operasi memasukkan dan mengambilnya mengambil masa logaritma, iaituO(log n), yang bergantung pada bilangan elemen dalam peta. Ini adalah perlu supaya elemen mempunyai sejenis mekanisme perbandingan yang disediakan oleh sama ada kunci kami atau Pembanding luaran. Mekanisme ini menentukan susunan lelaran.

Dan faktor ini membantu kami memutuskan koleksi yang hendak digunakan dan bila.

Jika kita perlu menyimpan nilai dalam susunan tertentu, pilihannya adalah jelas — kita memerlukan SortedMap . Walaupun ia lebih perlahan daripada HashMap , ia melaksanakan tugas penting untuk kami.

Seperti yang dinyatakan sebelum ini, SortedMap boleh memberi kami kunci pertama (atau terakhir), atau nilai, atau pasangan nilai kunci dalam peta kami, tidak kira bila nilai itu ditambahkan. Pelaksanaan HashMap tidak boleh melakukan ini .

Sebagai contoh, pertimbangkan peta dengan kunci (nama pelajar) dan nilai (gred mereka). Katakan kita mahu bekerja dengan senarai dalam susunan abjad terbalik.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Contoh menunjukkan bahawa menggunakan HashMap menjadikan tugasan lebih rumit, kerana HashMap tidak menjamin susunan storan mahupun susunan mendapatkan elemen daripada peta.