Sortert kart

Sortert kart

I denne leksjonen skal vi studere SortedMap- grensesnittet. Vi vil utforske nye metoder som vises i dette grensesnittet, så vel som funksjonene til én implementering av SortedMap — TreeMap — og forskjellene mellom implementeringer, samt deres fordeler sammenlignet med HashMap .

La oss se hvordan karthierarkiet ser ut. Vær spesielt oppmerksom på SortedMap- grensesnittet og dets TreeMap- implementering - de er vårt fokus i dag:

SortedMap - grensesnittet utvider Map- grensesnittet. På mange måter ligner det på SortedSet (som igjen utvider Set ), siden de begge beskriver lignende funksjonalitet for lagring og bruk av sorterte verdier.

SortedSet fungerer med og lagrer<TValue>-objekter, men SortedMap lagrer<TKey, TValue>-par. Det er et kart som lagrer alle elementene i stigende rekkefølge etter nøklene.

SortedMap - grensesnittet utvider Map . Den legger til følgende metoder:

TreeMap-klassen

TreeMap - klassen er en implementering av SortedMap- grensesnittet. Det vil si at TreeMap implementerer alle metodene lagt til av SortedMap , så vel som standardene fra Map- grensesnittet.

Du kan lage et TreeMap- objekt ved å bruke konstruktører som disse:

• TreeMap() : lager et tomt kart implementert som et tre;

• TreeMap(Map<? utvider TKey, ? utvider TValue> map) : oppretter et tre og legger til alle elementene fra inndatakartet;

• TreeMap(SortedMap<TKey, ? utvider TValue> smap) : oppretter et tre og legger til alle elementer fra inndatasortert kart;

• TreeMap(Comparator<? super TKey> komparator) : oppretter et tomt tre — komparatoren vil bli brukt til å sortere alle elementer etter hvert som de blir lagt til.

Her er TKey typen av nøklene i de lagrede parene, og TValue er typen av verdiene i parene som er lagret i TreeMap .

Komparator er ganske viktig for SortedMap / TreeMap . Den fastsetter reglene for sortering - eller bestilling - kartet vårt. Hvis vi ikke tilbyr en komparator, vil den naturlige rekkefølgen av nøklene våre bli brukt når vi lager et SortedMap .

Legge til elementer i et trekart

Elementer legges til et kart som par ved å bruke put() -metoden. Nøkkelen sendes som det første argumentet, og verdien sendes som det andre. Anta for eksempel at vi ønsker å lage 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 legger til et nøkkelverdi-par, hvis nøkkelen allerede finnes i samlingen, erstattes den gamle verdien med den nye verdien. Denne oppførselen er illustrert i vårt eksempel med to par som har samme nøkkel — ("Oliver", 3) og ("Oliver", 5) .

La oss se på et eksempel med en komparator som vi lager. Anta at vi ønsker å lagre elementene sortert etter lengden på nøkkelstrengen. Hvis lengden på tastene er lik, vil vi sortere alfabetisk (den naturlige rekkefølgen av strenger):

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 sekvensen:

Denne oppførselen gjør et TreeMap som en sortert matrise eller liste hvis indekser er ord ( String ) i stedet for tall.

SortedMap-metoder i TreeMap-klassen

1. Hvis du trenger å få nøkkelen til den første studenten, kan du bruke firstKey() -metoden:

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

   Resultat: Første nøkkel → Anthony

2. Hvis du trenger å få nøkkelen til den siste studenten, kan du bruke lastKey () -metoden:

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

   Resultat: Siste nøkkel → Jeff

3. Få alle objekter som kommer etter objektet med nøkkelen " Sara ":

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

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

4. Få alle objekter som kommer foran objektet med nøkkelen " Nick ":

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

   Resultat: headMap: {Anthony=5}

5. Få alle objekter som kommer etter objektet med nøkkelen " Oliver " og kom foran objektet med nøkkelen " Sara ":

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

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

Sammenligning av HashMap og SortedMap/TreeMap

La oss snakke om hvordan elementene er bestilt og lagret:

• Siden HashMap ikke gir oss noen garantier om ordre ved iterasjon, kan rekkefølgen endres fullstendig når nye elementer legges til.

• I TreeMap er rekkefølgen basert på den "naturlige rekkefølgen" av nøklene i henhold til deres compareTo() -metode (eller en komparator som vi tilbyr). Ikke glem at TreeMap implementerer SortedMap- grensesnittet, som inneholder metoder som avhenger av denne sorteringsrekkefølgen.

Nå vender vi oss til en vurdering av ytelse og hastighet:

• HashMap er et kart basert på hashing-nøkler. Den kan sette inn og få elementer iO(1), konstant tid. For å støtte dette må nøklene implementerehashCode()ogequals().

• TreeMap er et trebasert kart. Innsettings- og henteoperasjonene tar logaritmisk tid, dvs.O(log n), som avhenger av antall elementer i kartet. Dette er nødvendig for at elementene skal ha en slags sammenligningsmekanisme levert av enten nøkkelen vår eller en ekstern komparator. Denne mekanismen bestemmer iterasjonsrekkefølgen.

Og disse faktorene hjelper oss med å bestemme hvilke samlinger vi skal bruke og når.

Hvis vi trenger å lagre verdier i en bestemt rekkefølge, er valget åpenbart - vi trenger et SortedMap . Selv om den er litt tregere enn HashMap , utfører den viktige oppgaver for oss.

Som nevnt tidligere kan SortedMap gi oss den første (eller siste) nøkkelen, eller verdien, eller nøkkelverdi-paret i kartet vårt, uavhengig av når denne verdien ble lagt til. HashMap - implementeringen kan ikke gjøre dette.

Tenk for eksempel på et kart med nøkler (elevenes navn) og verdier (karakterene deres). La oss si at vi ønsker å jobbe med en liste i omvendt alfabetisk rekkefø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 bruk av et HashMap gjør oppgaven mer komplisert, siden HashMap hverken garanterer rekkefølgen på lagring eller rekkefølgen for å hente elementer fra kartet.