SortedMap

SortedMap

Dalam pelajaran ini, kita akan mempelajari antarmuka SortedMap . Kami akan menjelajahi metode baru yang muncul di antarmuka ini, serta fitur dari satu implementasi SortedMap — TreeMap — dan perbedaan antar implementasi, serta kelebihannya dibandingkan dengan HashMap .

Mari kita lihat seperti apa hierarki peta itu. Berikan perhatian khusus pada antarmuka SortedMap dan implementasi TreeMap -nya — ini adalah fokus kami hari ini:

Antarmuka SortedMap memperluas antarmuka Peta . Dalam banyak hal, ini mirip dengan SortedSet (yang pada gilirannya memperluas Set ), karena keduanya menjelaskan fungsi serupa untuk menyimpan dan menggunakan nilai yang diurutkan.

SortedSet berfungsi dengan dan menyimpan<TValue>, tetapi SortedMap menyimpan<TKey, TValue>. Ini adalah peta yang menyimpan semua elemennya dalam urutan naik dari kuncinya.

Antarmuka SortedMap memperluas Map . Itu menambahkan metode berikut:

kelas TreeMap

Kelas TreeMap adalah implementasi dari antarmuka SortedMap . Artinya, TreeMap mengimplementasikan semua metode yang ditambahkan oleh SortedMap serta metode standar dari antarmuka Peta .

Anda dapat membuat objek TreeMap menggunakan konstruktor seperti ini:

• TreeMap() : membuat peta kosong yang diimplementasikan sebagai pohon;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : membuat pohon dan menambahkan semua elemen dari peta input;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : membuat pohon dan menambahkan semua elemen dari input peta terurut;

• TreeMap(Comparator<? super TKey> comparator) : membuat pohon kosong — pembanding akan digunakan untuk mengurutkan semua elemen setelah ditambahkan.

Di sini TKey adalah jenis kunci dalam pasangan yang disimpan, dan TValue adalah jenis nilai dalam pasangan yang disimpan dalam TreeMap .

Komparator cukup penting untuk SortedMap / TreeMap . Ini menetapkan aturan untuk menyortir — atau mengurutkan — peta kita. Jika kita tidak menyediakan pembanding, maka pengurutan alami kunci kita akan digunakan saat kita membuat SortedMap .

Menambahkan elemen ke TreeMap

Elemen ditambahkan ke peta sebagai pasangan menggunakan metode put() . Kunci diteruskan sebagai argumen pertama, dan nilainya diteruskan sebagai argumen kedua. Misalnya, kita ingin membuat daftar siswa dan nilainya.

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);

Hasil:

Saat kita menambahkan key-value pair, jika kunci sudah ada di koleksi, maka nilai lama diganti dengan nilai baru. Perilaku ini diilustrasikan dalam contoh kami dengan dua pasangan yang memiliki kunci yang sama — ("Oliver", 3) dan ("Oliver", 5) .

Mari kita lihat contoh dengan Comparator yang kita buat. Misalkan kita ingin menyimpan elemen yang diurutkan berdasarkan panjang string kunci. Jika panjang kunci sama, maka kami akan mengurutkan berdasarkan abjad (urutan alami string):

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);

Inilah urutan yang dihasilkan:

Perilaku ini membuat TreeMap seperti larik atau daftar terurut yang indeksnya berupa kata ( String ) alih-alih angka.

Metode SortedMap di kelas TreeMap

1. Jika Anda perlu mendapatkan kunci siswa pertama, Anda dapat menggunakan metode firstKey() :

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

   Hasil: Kunci pertama → Anthony

2. Jika Anda perlu mendapatkan kunci siswa terakhir, Anda dapat menggunakan metode lastKey() :

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

   Hasil: Kunci Terakhir → Jeff

3. Dapatkan semua objek yang muncul setelah objek dengan kunci " Sara ":

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

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

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

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

   Hasil: headMap: {Anthony=5}

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

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

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

Perbandingan HashMap dan SortedMap/TreeMap

Mari kita bicara tentang bagaimana elemen disusun dan disimpan:

• Karena HashMap tidak memberi kami jaminan apa pun tentang pesanan saat iterasi, pesanan dapat sepenuhnya berubah saat elemen baru ditambahkan.

• Di TreeMap , urutan didasarkan pada "urutan alami" dari kunci sesuai dengan metode compareTo() mereka (atau Pembanding yang kami sediakan). Juga, jangan lupa bahwa TreeMap mengimplementasikan antarmuka SortedMap , yang berisi metode yang bergantung pada urutan pengurutan ini.

Sekarang kita beralih ke pertimbangan kinerja dan kecepatan:

• HashMap adalah peta berdasarkan kunci hashing. Itu dapat memasukkan dan mendapatkan elemen dalamO(1), waktu konstan. Untuk mendukung ini, kunci harus mengimplementasikanhashCode()danequals().

• TreeMap adalah peta berbasis pohon. Operasi penyisipan dan pengambilannya membutuhkan waktu logaritmik, yaituO(log n), yang bergantung pada jumlah elemen di peta. Ini diperlukan agar elemen memiliki semacam mekanisme perbandingan yang disediakan oleh kunci kita atau Pembanding eksternal. Mekanisme ini menentukan urutan iterasi.

Dan faktor-faktor ini membantu kami memutuskan koleksi mana yang akan digunakan dan kapan.

Jika kita perlu menyimpan nilai dalam urutan tertentu, pilihannya sudah jelas — kita memerlukan SortedMap . Meskipun sedikit lebih lambat dari HashMap , ia melakukan tugas-tugas penting bagi kami.

Seperti disebutkan sebelumnya, SortedMap dapat memberi kita kunci pertama (atau terakhir), atau nilai, atau pasangan kunci-nilai di peta kita, terlepas dari kapan nilai itu ditambahkan. Implementasi HashMap tidak dapat melakukan ini .

Misalnya, pertimbangkan peta dengan kunci (nama siswa) dan nilai (nilai mereka). Katakanlah kita ingin bekerja dengan daftar dalam urutan 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 bahwa menggunakan HashMap membuat tugas lebih rumit, karena HashMap tidak menjamin urutan penyimpanan maupun urutan mendapatkan elemen dari peta.