Sorteret kort

Sorteret kort

I denne lektion vil vi studere SortedMap- grænsefladen. Vi vil udforske nye metoder, der vises i denne grænseflade, såvel som funktionerne i en implementering af SortedMap — TreeMap — og forskellene mellem implementeringer, såvel som deres fordele sammenlignet med HashMap .

Lad os se, hvordan hierarkiet af kort ser ud. Vær særlig opmærksom på SortedMap- grænsefladen og dens TreeMap- implementering - de er vores fokus i dag:

SortedMap - grænsefladen udvider kortgrænsefladen . På mange måder ligner det SortedSet (som igen udvider Set ), da de begge beskriver lignende funktionalitet til lagring og brug af sorterede værdier.

SortedSet fungerer med og gemmer<TValue>-objekter, men SortedMap gemmer<TKey, TValue>-par. Det er et kort, der gemmer alle dets elementer i stigende rækkefølge efter deres nøgler.

SortedMap - grænsefladen udvider Map . Det tilføjer følgende metoder:

TreeMap klasse

TreeMap - klassen er en implementering af SortedMap- grænsefladen. Det vil sige, at TreeMap implementerer alle metoderne tilføjet af SortedMap såvel som standardmetoderne fra kortgrænsefladen .

Du kan oprette et TreeMap- objekt ved hjælp af konstruktører som disse:

• TreeMap() : opretter et tomt kort implementeret som et træ;

• TreeMap(Map<? udvider TKey, ? udvider TValue> map) : opretter et træ og tilføjer alle elementer fra inputkortet;

• TreeMap(SortedMap<TKey, ? udvider TValue> smap) : opretter et træ og tilføjer alle elementer fra det inputsorterede kort;

• TreeMap(Comparator<? super TKey> komparator) : opretter et tomt træ — komparatoren vil blive brugt til at sortere alle elementer, efterhånden som de tilføjes efterfølgende.

Her er TKey typen af ​​nøglerne i de lagrede par, og TValue er typen af ​​værdierne i parrene, der er gemt i TreeMap .

Komparator er ret vigtig for SortedMap / TreeMap . Det fastlægger reglerne for sortering - eller bestilling - af vores kort. Hvis vi ikke leverer en komparator, vil den naturlige rækkefølge af vores nøgler blive brugt, når vi opretter et SortedMap .

Tilføjelse af elementer til et trækort

Elementer tilføjes til et kort som par ved hjælp af put() -metoden. Nøglen sendes som det første argument, og værdien videregives som det andet. Antag for eksempel, at vi vil oprette en liste over elever og deres karakterer.

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

Resultat:

Når vi tilføjer et nøgle-værdi-par, hvis nøglen allerede findes i samlingen, erstattes den gamle værdi med den nye værdi. Denne adfærd er illustreret i vores eksempel med to par, der har den samme nøgle — ("Oliver", 3) og ("Oliver", 5) .

Lad os se på et eksempel med en komparator , som vi laver. Antag, at vi ønsker at gemme elementerne sorteret efter længden af ​​nøglestrengen. Hvis længden af ​​tasterne er ens, vil vi sortere alfabetisk (den naturlige rækkefølge af strenge):

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

Her er den resulterende sekvens:

Denne adfærd gør et TreeMap som en sorteret matrix eller liste, hvis indekser er ord ( String ) i stedet for tal.

SortedMap-metoder i TreeMap-klassen

1. Hvis du har brug for at få nøglen til den første elev, kan du bruge firstKey() metoden:

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

   Resultat: Første nøgle → Anthony

2. Hvis du har brug for at få nøglen til den sidste elev, kan du bruge lastKey () metoden:

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

   Resultat: Sidste nøgle → Jeff

3. Hent alle objekter, der kommer efter objektet med nøglen " Sara ":

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

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

4. Hent alle objekter, der kommer før objektet med nøglen " Nick ":

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

   Resultat: headMap: {Anthony=5}

5. Hent alle objekter, der kommer efter objektet med nøglen " Oliver " og kom før objektet med nøglen " Sara ":

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

   Resultat: underkort: {Oliver=5, Roxy=5}

Sammenligning af HashMap og SortedMap/TreeMap

Lad os tale om, hvordan elementerne er bestilt og opbevaret:

• Da HashMap ikke giver os nogen garantier om ordre ved iteration, kan ordren ændre sig fuldstændigt, når nye elementer tilføjes.

• I TreeMap er rækkefølgen baseret på den "naturlige rækkefølge" af nøglerne i henhold til deres compareTo()- metode (eller en komparator , som vi leverer). Glem heller ikke, at TreeMap implementerer SortedMap- grænsefladen, som indeholder metoder, der afhænger af denne sorteringsrækkefølge.

Nu vender vi os til en overvejelse af ydeevne og hastighed:

• HashMap er et kort baseret på hashing-nøgler. Den kan indsætte og få elementer iO(1), konstant tid. For at understøtte dette skal nøglerne implementerehashCode()ogequals().

• TreeMap er et træbaseret kort. Dets indsættelses- og hente-operationer tager logaritmisk tid, dvs.O(log n), som afhænger af antallet af elementer i kortet. Dette er nødvendigt, for at elementerne har en form for sammenligningsmekanisme leveret af enten vores nøgle eller en ekstern komparator. Denne mekanisme bestemmer iterationsrækkefølgen.

Og disse faktorer hjælper os med at beslutte, hvilke samlinger vi skal bruge og hvornår.

Hvis vi skal gemme værdier i en bestemt rækkefølge, er valget oplagt - vi har brug for et SortedMap . Selvom det er lidt langsommere end HashMap , udfører det vigtige opgaver for os.

Som tidligere nævnt kan SortedMap give os den første (eller sidste) nøgle eller værdi eller nøgleværdi-par i vores kort, uanset hvornår denne værdi blev tilføjet. HashMap - implementeringen kan ikke gøre dette.

Overvej for eksempel et kort med nøgler (elevernes navne) og værdier (deres karakterer). Lad os sige, at vi vil arbejde med en liste i omvendt alfabetisk rækkefølge.

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

Eksemplet viser, at brug af et HashMap gør opgaven mere kompliceret, da HashMap hverken garanterer rækkefølgen af ​​lagring eller rækkefølgen for at hente elementer fra kortet.