Sorterad karta

Sorterad karta

I den här lektionen kommer vi att studera SortedMap- gränssnittet. Vi kommer att utforska nya metoder som visas i det här gränssnittet, såväl som funktionerna i en implementering av SortedMap — TreeMap — och skillnaderna mellan implementeringar, såväl som deras fördelar jämfört med HashMap .

Låt oss se hur karthierarkin ser ut. Var särskilt uppmärksam på SortedMap- gränssnittet och dess TreeMap- implementering - de är vårt fokus idag:

SortedMap - gränssnittet utökar Map- gränssnittet. På många sätt liknar det SortedSet (som i sin tur utökar Set ), eftersom de båda beskriver liknande funktionalitet för att lagra och använda sorterade värden.

SortedSet fungerar med och lagrar<TValue>-objekt, men SortedMap lagrar<TKey, TValue>-par. Det är en karta som lagrar alla dess element i stigande ordning efter deras nycklar.

SortedMap - gränssnittet utökar Map . Den lägger till följande metoder:

TreeMap klass

Klassen TreeMap är en implementering av SortedMap- gränssnittet. Det vill säga, TreeMap implementerar alla metoder som lagts till av SortedMap såväl som standardmetoderna från kartgränssnittet .

Du kan skapa ett TreeMap- objekt med konstruktorer som dessa:

• TreeMap() : skapar en tom karta implementerad som ett träd;

• TreeMap(Map<? utökar TKey, ? utökar TValue> map) : skapar ett träd och lägger till alla element från inmatningskartan;

• TreeMap(SortedMap<TKey, ? utökar TValue> smap) : skapar ett träd och lägger till alla element från den inmatade sorterade kartan;

• TreeMap(Comparator<? super TKey> komparator) : skapar ett tomt träd — komparatorn kommer att användas för att sortera alla element allteftersom de läggs till.

Här är TKey typen av nycklar i de lagrade paren, och TValue är typen av värden i paren lagrade i TreeMap .

Comparator är ganska viktigt för SortedMap / TreeMap . Den fastställer reglerna för sortering – eller beställning av – vår karta. Om vi ​​inte tillhandahåller en komparator kommer den naturliga ordningen av våra nycklar att användas när vi skapar en SortedMap .

Lägga till element i en TreeMap

Element läggs till i en karta som par med put()- metoden. Nyckeln skickas som det första argumentet och värdet skickas som det andra. Anta till exempel att vi vill skapa en lista över elever och deras betyg.

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 lägger till ett nyckel-värdepar, om nyckeln redan finns i samlingen, ersätts det gamla värdet med det nya värdet. Detta beteende illustreras i vårt exempel med två par som har samma nyckel — ("Oliver", 3) och ("Oliver", 5) .

Låt oss titta på ett exempel med en komparator som vi skapar. Anta att vi vill lagra elementen sorterade efter nyckelsträngens längd. Om längden på tangenterna är lika, kommer vi att sortera alfabetiskt (den naturliga ordningen av strängar):

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

Här är den resulterande sekvensen:

Detta beteende gör en TreeMap som en sorterad array eller lista vars index är ord ( String ) istället för siffror.

SortedMap-metoder i klassen TreeMap

1. Om du behöver få nyckeln till den första studenten kan du använda metoden firstKey() :

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

   Resultat: Första tangenten → Anthony

2. Om du behöver få nyckeln till den sista studenten kan du använda metoden lastKey() :

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

   Resultat: Last Key → Jeff

3. Få alla objekt som kommer efter objektet med nyckeln " Sara ":

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

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

4. Få alla objekt som kommer före objektet med nyckeln " Nick ":

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

   Resultat: headMap: {Anthony=5}

5. Få alla objekt som kommer efter objektet med nyckeln " Oliver " och kom före objektet med nyckeln " Sara ":

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

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

Jämförelse av HashMap och SortedMap/TreeMap

Låt oss prata om hur elementen beställs och lagras:

• Eftersom HashMap inte ger oss några garantier om beställning vid iteration, kan beställningen ändras helt när nya element läggs till.

• I TreeMap är ordningen baserad på den "naturliga ordningen" av nycklarna enligt deras compareTo()- metod (eller en Comparator som vi tillhandahåller). Glöm inte heller att TreeMap implementerar SortedMap- gränssnittet, som innehåller metoder som är beroende av denna sorteringsordning.

Nu övergår vi till en övervägande av prestanda och hastighet:

• HashMap är en karta baserad på hash-nycklar. Den kan infoga och få element iO(1), konstant tid. För att stödja detta måste nycklarna implementerahashCode()ochequals().

• TreeMap är en trädbaserad karta. Dess infogning och hämtning tar logaritmisk tid, dvsO(log n), vilket beror på antalet element i kartan. Detta är nödvändigt så att elementen har någon form av jämförelsemekanism som tillhandahålls av antingen vår nyckel eller en extern komparator. Denna mekanism bestämmer iterationsordningen.

Och dessa faktorer hjälper oss att bestämma vilka samlingar vi ska använda och när.

Om vi ​​behöver lagra värden i en viss ordning är valet självklart — vi behöver en SortedMap . Även om det är lite långsammare än HashMap , utför det viktiga uppgifter för oss.

Som nämnts tidigare kan SortedMap ge oss den första (eller sista) nyckeln, eller värdet eller nyckel-värdeparet i vår karta, oavsett när det värdet lades till. HashMap - implementeringen kan inte göra detta.

Tänk till exempel på en karta med nycklar (elevernas namn) och värden (deras betyg). Låt oss säga att vi vill arbeta med en lista i omvänd alfabetisk ordning.

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

Exemplet visar att användningen av en HashMap gör uppgiften mer komplicerad, eftersom HashMap varken garanterar lagringsordningen eller ordningen för att hämta element från kartan.