SortedMap

SortedMap

Ing wulangan iki, kita bakal sinau antarmuka SortedMap . Kita bakal njelajah cara anyar sing katon ing antarmuka iki, uga fitur saka siji implementasine saka SortedMap — TreeMap — lan beda antarane implementasine, uga kaluwihan dibandhingake HashMap .

Ayo ndeleng kaya apa hierarki peta. Pay manungsa waé khusus kanggo antarmuka SortedMap lan implementasine TreeMap - iku fokus kita saiki:

Antarmuka SortedMap ngluwihi antarmuka Peta . Akeh cara, padha karo SortedSet (sing uga ngluwihi Set ), amarga loro-lorone nggambarake fungsi sing padha kanggo nyimpen lan nggunakake nilai sing diurutake.

SortedSet bisa digunakake lan nyimpen<TValue>obyek, nanging SortedMap nyimpen<TKey, TValue>. Iku peta sing nyimpen kabeh unsur ing urutan munggah tombol.

Antarmuka SortedMap ngluwihi Peta . Iku nambah cara ing ngisor iki:

Kelas TreeMap

Kelas TreeMap minangka implementasi antarmuka SortedMap . Yaiku, TreeMap ngetrapake kabeh metode sing ditambahake dening SortedMap uga sing standar saka antarmuka Peta .

Sampeyan bisa nggawe obyek TreeMap nggunakake konstruktor kaya iki:

• TreeMap() : nggawe peta kosong sing diimplementasikake minangka wit;

• TreeMap(Map<? ngluwihi TKey, ? ngluwihi TValue> map) : nggawe wit lan nambah kabeh unsur saka peta input;

• TreeMap(SortedMap<TKey, ? ngluwihi TValue> smap) : nggawe wit lan nambah kabeh unsur saka peta diurutake input;

• TreeMap(Comparator<? super TKey> comparator) : nggawe wit kosong — comparator bakal digunakake kanggo ngurutake kabeh unsur nalika lagi ditambahake.

Ing kene TKey minangka jinis tombol ing pasangan sing disimpen, lan TValue minangka jinis nilai ing pasangan sing disimpen ing TreeMap .

Comparator cukup penting kanggo SortedMap / TreeMap . Iku netepake aturan kanggo ngurutake - utawa pesenan - peta kita. Yen kita ora nyedhiyakake komparator, mula urutan alami kunci kita bakal digunakake nalika nggawe SortedMap .

Nambahake unsur menyang TreeMap

Unsur ditambahake menyang peta minangka pasangan nggunakake metode put () . Tombol kasebut dilewati minangka argumen pisanan, lan nilai kasebut dilewati minangka nomer loro. Contone, umpamane kita pengin nggawe dhaptar siswa lan bijine.

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

asil:

Nalika kita nambah pasangan kunci-nilai, yen kunci wis ana ing koleksi, banjur nilai lawas diganti karo nilai anyar. Prilaku iki digambarake ing conto kita karo rong pasangan sing duwe kunci sing padha - ("Oliver", 3) lan ("Oliver", 5) .

Ayo goleki conto karo Comparator sing digawe. Upaminipun kita pengin nyimpen unsur diurutake dening dawa senar tombol. Yen dawa tombol padha, banjur kita bakal ngurutake abjad (urutan alami saka strings):

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

Punika urutan asil:

Prilaku iki ndadekake TreeMap kaya array utawa dhaptar sing diurutake sing indeks minangka tembung ( String ) tinimbang angka.

Metode SortedMap ing kelas TreeMap

1. Yen sampeyan kudu njaluk kunci siswa pisanan, sampeyan bisa nggunakake metode firstKey() :

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

   Asil: Tombol pisanan → Anthony

2. Yen sampeyan butuh kunci siswa pungkasan, sampeyan bisa nggunakake metode lastKey () :

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

   Asil: Kunci Terakhir → Jeff

3. Entuk kabeh obyek sing ana ing mburi obyek kanthi tombol " Sara ":

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

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

4. Entuk kabeh obyek sing ana sadurunge obyek kanthi tombol " Nick ":

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

   Hasil: headMap: {Anthony=5}

5. Entuk kabeh obyek sing ana ing mburi obyek kanthi tombol " Oliver " lan teka sadurunge obyek kanthi tombol " Sara ":

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

   Asil: subMap: {Oliver=5, Roxy=5}

Perbandingan HashMap lan SortedMap/TreeMap

Ayo pirembagan babagan carane unsur-unsur kasebut diurut lan disimpen:

• Amarga HashMap ora menehi jaminan babagan pesenan nalika diulang, pesenan bisa diganti kanthi lengkap nalika unsur anyar ditambahake.

• Ing TreeMap , urutan kasebut adhedhasar "urutan alami" tombol miturut metode compareTo () (utawa Comparator sing diwenehake). Uga, aja lali yen TreeMap ngleksanakake antarmuka SortedMap , sing ngemot metode sing gumantung saka urutan urutan iki.

Saiki kita nimbang kinerja lan kacepetan:

• HashMap minangka peta adhedhasar tombol hashing. Bisa nglebokake lan entuk unsur ingO(1), wektu konstan. Kanggo ndhukung iki, tombol kudu ngleksanakakehashCode ()lanpadha ().

• TreeMap minangka peta adhedhasar wit. Operasi insert lan njupuk njupuk wektu logaritmik, yaikuO(log n), sing gumantung saka jumlah unsur ing peta. Iki perlu supaya unsur duwe sawetara jinis mekanisme perbandingan sing diwenehake dening kunci kita utawa komparator eksternal. Mekanisme iki nemtokake urutan pengulangan.

Lan faktor kasebut mbantu kita mutusake koleksi sing arep digunakake lan kapan.

Yen kita kudu nyimpen nilai ing urutan tartamtu, pilihan iku ketok - kita kudu SortedMap . Sanajan rada alon tinimbang HashMap , nanging nindakake tugas penting kanggo kita.

Kaya sing wis kasebut sadurunge, SortedMap bisa menehi kunci pisanan (utawa pungkasan), utawa nilai, utawa pasangan kunci-nilai ing peta kita, ora preduli kapan nilai kasebut ditambahake. Implementasi HashMap ora bisa nindakake iki .

Contone, nimbang peta kanthi kunci (jeneng siswa) lan nilai (bijine). Contone, kita pengin nggarap dhaptar kanthi urutan alfabetis.

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

Conto nuduhake yen nggunakake HashMap nggawe tugas luwih rumit, amarga HashMap ora njamin urutan panyimpenan utawa urutan njupuk unsur saka peta.