Rendezett térkép

Rendezett térkép

Ebben a leckében a SortedMap felületet tanulmányozzuk . Megvizsgáljuk az ezen a felületen megjelenő új metódusokat, valamint a SortedMap egyik implementációjának – a TreeMap – jellemzőit és az implementációk közötti különbségeket, valamint előnyeit a HashMaphez képest .

Nézzük meg, hogyan néz ki a térképek hierarchiája. Fordítson különös figyelmet a SortedMap felületre és annak TreeMap megvalósítására – ezekre összpontosítunk ma:

A SortedMap felület kiterjeszti a térképes felületet. Sok tekintetben hasonlít a SortedSet- hez (ami viszont kiterjeszti a Set -et ), mivel mindkettő hasonló funkciókat ír le a rendezett értékek tárolására és használatára.

A SortedSet működik és tároljaa <TValue>objektumokat, de a SortedMap tároljaa <TKey, TValue>párokat. Ez egy térkép, amely minden elemét a kulcsok növekvő sorrendjében tárolja.

A SortedMap felület kiterjeszti a Térképet . A következő módszerekkel egészíti ki:

TreeMap osztály

A TreeMap osztály a SortedMap felület megvalósítása . Vagyis a TreeMap megvalósítja a SortedMap által hozzáadott összes metódust , valamint a szabványosokat a Map felületről.

Létrehozhat egy TreeMap objektumot a következő konstruktorokkal:

• TreeMap() : egy faként megvalósított üres térképet hoz létre;

• TreeMap(Térkép<? kiterjeszti a TKey-t, ? kiterjeszti a TVérték> térképet) : létrehoz egy fát és hozzáadja az összes elemet a bemeneti térképről;

• TreeMap(SortedMap<TKKey, ? kiterjeszti TVérték> smap) : létrehoz egy fát és hozzáadja az összes elemet a bemeneti rendezett térképből;

• TreeMap(Összehasonlító<? szuper TKey> összehasonlító) : üres fát hoz létre – az összehasonlító az összes elemet a későbbi hozzáadáskor rendezi.

Itt a TKey a tárolt párokban lévő kulcsok típusa, a TValue pedig a TreeMap- ben tárolt párok értékeinek típusa .

Az összehasonlító nagyon fontos a SortedMap / TreeMap számára . Megállapítja a térképünk válogatásának – vagy megrendelésének – szabályait. Ha nem adunk meg összehasonlítót, akkor a kulcsaink természetes sorrendje kerül felhasználásra a SortedMap létrehozásakor.

Elemek hozzáadása a TreeMaphez

Az elemek a put() metódussal párokként kerülnek a térképhez . A kulcsot első argumentumként, az értéket pedig másodikként adjuk át. Tegyük fel például, hogy szeretnénk létrehozni egy listát a tanulókról és az osztályzataikról.

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

Eredmény:

Amikor hozzáadunk egy kulcs-érték párt, ha a kulcs már létezik a gyűjteményben, akkor a régi érték helyére az új érték lép. Példánkban ezt a viselkedést szemléltetjük két olyan párral, amelyeknek ugyanaz a kulcsa: ("Oliver", 3) és ("Oliver", 5) .

Nézzünk egy példát az általunk létrehozott Comparatorral . Tegyük fel, hogy az elemeket a kulcskarakterlánc hossza szerint rendezve szeretnénk tárolni. Ha a billentyűk hossza egyenlő, akkor ábécé szerint rendezzük (a karakterláncok természetes sorrendje):

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

Íme az eredményül kapott sorrend:

Ez a viselkedés a TreeMap-et rendezett tömbbé vagy listává teszi, amelynek indexei szavak ( String ) nem számok.

SortedMap metódusok a TreeMap osztályban

1. Ha meg kell szereznie az első tanuló kulcsát, használhatja a firstKey() metódust:

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

   Eredmény: Első kulcs → Anthony

2. Ha meg kell szereznie az utolsó tanuló kulcsát, használhatja a lastKey() metódust:

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

   Eredmény: Utolsó kulcs → Jeff

3. Szerezze be az összes objektumot, amely az objektum után következik a " Sara " kulccsal :

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

   Eredmény: tailMap: {Sara=5, Jeff=4}

4. Az összes objektum lekérése, amely a " Nick " kulccsal rendelkező objektum elé kerül :

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

   Eredmény: fejtérkép: {Anthony=5}

5. Szerezze be az összes objektumot, amely az " Oliver " kulcsú objektum után , és a " Sara " kulcsú objektum elé kerül :

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

   Eredmény: altérkép: {Oliver=5, Roxy=5}

A HashMap és a SortedMap/TreeMap összehasonlítása

Beszéljünk az elemek rendezéséről és tárolásáról:

• Mivel a HashMap nem ad garanciát a sorrendre az iteráció során, a sorrend teljesen megváltozhat új elemek hozzáadásakor.

• A TreeMap alkalmazásban a sorrend a kulcsok "természetes sorrendjén" alapul, a ComparTo() metódusuk (vagy az általunk biztosított összehasonlító ) szerint. Ne felejtsük el, hogy a TreeMap a SortedMap felületet valósítja meg, amely ettől a rendezési sorrendtől függő metódusokat tartalmaz.

Most rátérünk a teljesítményre és a sebességre:

• A HashMap egy kivonatoló kulcsokon alapuló térkép. O(1), állandó idejűelemeket tud beilleszteni és beszerezniEnnek támogatásához a kulcsoknak végre kell hajtaniuka hashCode()ésaz equals() kódot.

• A TreeMap egy fa alapú térkép. Beszúrási és lekérési műveletei logaritmikus időt vesznek igénybe, azazO(log n), ami a térkép elemeinek számától függ. Erre azért van szükség, hogy az elemeknek legyen valamiféle összehasonlítási mechanizmusa, amelyet akár a kulcsunk, akár egy külső összehasonlító biztosítja. Ez a mechanizmus határozza meg az iterációs sorrendet.

És ezek a tényezők segítenek eldönteni, hogy mely gyűjteményeket használjuk és mikor.

Ha bizonyos sorrendben kell tárolnunk az értékeket, akkor a választás nyilvánvaló – szükségünk van egy SortedMap-re . Bár egy kicsit lassabb, mint a HashMap , fontos feladatokat lát el számunkra.

Amint azt korábban említettük, a SortedMap megadhatja nekünk az első (vagy utolsó) kulcsot, értéket vagy kulcs-érték párt a térképünkön, függetlenül attól, hogy az értéket mikor adtuk hozzá. A HashMap implementáció erre nem képes.

Vegyünk például egy térképet kulcsokkal (a tanulók neveivel) és értékeivel (érdemjegyeik). Tegyük fel, hogy egy listával szeretnénk dolgozni fordított ábécé sorrendben.

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

A példa azt mutatja, hogy a HashMap használata bonyolultabbá teszi a feladatot, mivel a HashMap nem garantálja sem a tárolási sorrendet, sem az elemek lekérésének sorrendjét a térképről.