Gesorteerde kaart

Gesorteerde kaart

In deze les bestuderen we de SortedMap- interface. We zullen nieuwe methoden onderzoeken die in deze interface verschijnen, evenals de kenmerken van één implementatie van SortedMap - TreeMap - en de verschillen tussen implementaties, evenals hun voordelen in vergelijking met HashMap .

Laten we eens kijken hoe de hiërarchie van kaarten eruit ziet. Besteed speciale aandacht aan de SortedMap- interface en de TreeMap- implementatie ervan - ze zijn vandaag onze focus:

De SortedMap- interface breidt de kaartinterface uit . In veel opzichten is het vergelijkbaar met SortedSet (dat op zijn beurt Set uitbreidt ), omdat ze allebei vergelijkbare functionaliteit beschrijven voor het opslaan en gebruiken van gesorteerde waarden.

SortedSet werkt met en slaat<TValue>objecten op, maar SortedMap slaat<TKey, TValue>paren op. Het is een kaart die alle elementen opslaat in oplopende volgorde van hun sleutels.

De SortedMap- interface breidt Map uit . Het voegt de volgende methoden toe:

TreeMap-klasse

De TreeMap- klasse is een implementatie van de SortedMap- interface. Dat wil zeggen, TreeMap implementeert alle methoden die door SortedMap zijn toegevoegd , evenals de standaardmethoden van de kaartinterface .

U kunt een TreeMap- object maken met behulp van constructors zoals deze:

• TreeMap() : maakt een lege kaart die is geïmplementeerd als een boom;

• TreeMap(Map<? breidt TKey uit, ?breidt TValue> map uit) : maakt een boom en voegt alle elementen van de invoerkaart toe;

• TreeMap(SortedMap<TKey, ?extens TValue> smap) : maakt een boom en voegt alle elementen toe van de ingevoerde gesorteerde kaart;

• TreeMap(Comparator<?super TKey> comparator) : maakt een lege boom — de comparator wordt gebruikt om alle elementen te sorteren wanneer ze vervolgens worden toegevoegd.

Hier is TKey het type van de sleutels in de opgeslagen paren, en TValue is het type van de waarden in de paren die zijn opgeslagen in de TreeMap .

Comparator is behoorlijk belangrijk voor SortedMap / TreeMap . Het stelt de regels vast voor het sorteren - of ordenen - van onze kaart. Als we geen comparator bieden, wordt de natuurlijke volgorde van onze sleutels gebruikt wanneer we een SortedMap maken .

Elementen toevoegen aan een TreeMap

Elementen worden als paren aan een kaart toegevoegd met behulp van de methode put() . De sleutel wordt doorgegeven als het eerste argument en de waarde wordt doorgegeven als het tweede. Stel dat we een lijst met studenten en hun cijfers willen maken.

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

Resultaat:

Als we een sleutel-waardepaar toevoegen en de sleutel al in de verzameling bestaat, wordt de oude waarde vervangen door de nieuwe waarde. Dit gedrag wordt in ons voorbeeld geïllustreerd met twee paren die dezelfde sleutel hebben — ("Oliver", 3) en ("Oliver", 5) .

Laten we eens kijken naar een voorbeeld met een comparator die we maken. Stel dat we de elementen willen opslaan gesorteerd op de lengte van de sleutelreeks. Als de lengte van de sleutels gelijk is, sorteren we alfabetisch (de natuurlijke volgorde van 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);

Dit is de resulterende reeks:

Dit gedrag zorgt ervoor dat een TreeMap lijkt op een gesorteerde array of lijst waarvan de indexen woorden ( String ) zijn in plaats van getallen.

SortedMap-methoden in de TreeMap-klasse

1. Als je de sleutel van de eerste student nodig hebt, kun je de methode firstKey() gebruiken:

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

   Resultaat: Eerste sleutel → Anthony

2. Als je de sleutel van de laatste leerling nodig hebt, kun je de methode lastKey() gebruiken :

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

   Resultaat: Laatste sleutel → Jeff

3. Krijg alle objecten die na het object komen met de sleutel " Sara ":

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

   Resultaat: staartMap: {Sara=5, Jeff=4}

4. Pak alle objecten die voor het object komen met de sleutel " Nick ":

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

   Resultaat: headMap: {Anthony=5}

5. Pak alle objecten die na het object komen met de sleutel " Olivier " en vóór het object komen met de sleutel " Sara ":

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

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

Vergelijking van HashMap en SortedMap/TreeMap

Laten we het hebben over hoe de elementen zijn geordend en opgeslagen:

• Aangezien HashMap ons geen garanties geeft over de volgorde bij iteratie, kan de volgorde volledig veranderen wanneer nieuwe elementen worden toegevoegd.

• In TreeMap is de volgorde gebaseerd op de "natuurlijke volgorde" van de sleutels volgens hun CompareTo() -methode (of een Comparator die wij leveren). Vergeet ook niet dat TreeMap de SortedMap- interface implementeert , die methoden bevat die afhankelijk zijn van deze sorteervolgorde.

Nu kijken we naar een overweging van prestaties en snelheid:

• HashMap is een kaart op basis van hash-sleutels. Het kan elementen invoegen en ophalen inO(1), constante tijd. Om dit te ondersteunen, moeten de sleutelshashCode()enequals().

• TreeMap is een op bomen gebaseerde kaart. De invoeg- en ophaalbewerkingen nemen logaritmische tijd in beslag, dwzO(log n), die afhangt van het aantal elementen in de kaart. Dit is nodig zodat de elementen een soort vergelijkingsmechanisme hebben dat wordt geleverd door onze sleutel of een externe vergelijker. Dit mechanisme bepaalt de iteratievolgorde.

En deze factoren helpen ons beslissen welke collecties we gebruiken en wanneer.

Als we waarden in een bepaalde volgorde moeten opslaan, ligt de keuze voor de hand: we hebben een SortedMap nodig . Hoewel het iets langzamer is dan HashMap , voert het belangrijke taken voor ons uit.

Zoals eerder vermeld, kan SortedMap ons de eerste (of laatste) sleutel, of waarde, of sleutel-waardepaar in onze kaart geven, ongeacht wanneer die waarde is toegevoegd. De HashMap- implementatie kan dit niet.

Neem bijvoorbeeld een kaart met sleutels (namen van leerlingen) en waarden (hun cijfers). Laten we zeggen dat we willen werken met een lijst in omgekeerde alfabetische volgorde.

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

Het voorbeeld laat zien dat het gebruik van een HashMap de taak ingewikkelder maakt, aangezien HashMap noch de volgorde van opslag, noch de volgorde van het verkrijgen van elementen uit de kaart garandeert.