Carte triée

Carte triée

Dans cette leçon, nous étudierons l' interface SortedMap . Nous explorerons les nouvelles méthodes qui apparaissent dans cette interface, ainsi que les fonctionnalités d'une implémentation de SortedMap — TreeMap — et les différences entre les implémentations, ainsi que leurs avantages par rapport à HashMap .

Voyons à quoi ressemble la hiérarchie des cartes. Portez une attention particulière à l' interface SortedMap et à son implémentation TreeMap - elles sont notre priorité aujourd'hui :

L' interface SortedMap étend l' interface Map . À bien des égards, il est similaire à SortedSet (qui à son tour étend Set ), car ils décrivent tous deux des fonctionnalités similaires pour stocker et utiliser des valeurs triées.

SortedSet fonctionne avec et stocke<TValue>, mais SortedMap stocke<TKey, TValue>. C'est une carte qui stocke tous ses éléments dans l'ordre croissant de leurs clés.

L' interface SortedMap étend Map . Il ajoute les méthodes suivantes :

Classe TreeMap

La classe TreeMap est une implémentation de l' interface SortedMap . C'est-à-dire que TreeMap implémente toutes les méthodes ajoutées par SortedMap ainsi que celles standard de l' interface Map .

Vous pouvez créer un objet TreeMap en utilisant des constructeurs comme ceux-ci :

• TreeMap() : crée une carte vide implémentée sous forme d'arbre ;

• TreeMap(Map<? extend TKey, ? extend TValue> map) : crée un arbre et ajoute tous les éléments de la carte d'entrée ;

• TreeMap(SortedMap<TKey, ? étend TValue> smap) : crée un arbre et ajoute tous les éléments de la carte triée en entrée ;

• TreeMap(Comparator<? super TKey> comparator) : crée un arbre vide — le comparateur sera utilisé pour trier tous les éléments au fur et à mesure qu'ils seront ajoutés par la suite.

Ici, TKey est le type des clés dans les paires stockées et TValue est le type des valeurs dans les paires stockées dans le TreeMap .

Le comparateur est assez important pour SortedMap / TreeMap . Il établit les règles de tri — ou d'ordre — de notre carte. Si nous ne fournissons pas de comparateur, l'ordre naturel de nos clés sera utilisé lors de la création d'un SortedMap .

Ajouter des éléments à un TreeMap

Les éléments sont ajoutés à une carte par paires à l'aide de la méthode put() . La clé est passée en premier argument et la valeur est passée en second. Par exemple, supposons que nous voulions créer une liste d'étudiants et leurs notes.

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

Résultat:

Lorsque nous ajoutons une paire clé-valeur, si la clé existe déjà dans la collection, l'ancienne valeur est remplacée par la nouvelle valeur. Ce comportement est illustré dans notre exemple avec deux paires qui ont la même clé — ("Oliver", 3) et ("Oliver", 5) .

Regardons un exemple avec un comparateur que nous créons. Supposons que nous voulions stocker les éléments triés par la longueur de la chaîne de clé. Si la longueur des clés est égale, alors nous trierons par ordre alphabétique (l'ordre naturel des chaînes) :

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

Voici la séquence résultante :

Ce comportement fait d'un TreeMap un tableau ou une liste triée dont les indices sont des mots ( String ) au lieu de nombres.

Méthodes SortedMap dans la classe TreeMap

1. Si vous avez besoin d'obtenir la clé du premier étudiant, vous pouvez utiliser la méthode firstKey() :

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

   Résultat : Première clé → Anthony

2. Si vous avez besoin d'obtenir la clé du dernier étudiant, vous pouvez utiliser la méthode lastKey() :

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

   Résultat : Dernière clé → Jeff

3. Récupère tous les objets qui viennent après l'objet avec la clé " Sara " :

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

   Résultat : tailMap : {Sara=5, Jeff=4}

4. Récupère tous les objets qui précèdent l'objet avec la clé " Nick " :

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

   Résultat : headMap : {Anthony=5}

5. Récupère tous les objets qui viennent après l'objet avec la clé « Oliver » et qui viennent avant l'objet avec la clé « Sara » :

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

   Résultat : sous-carte : {Oliver=5, Roxy=5}

Comparaison de HashMap et SortedMap/TreeMap

Parlons de la façon dont les éléments sont ordonnés et stockés :

• Étant donné que HashMap ne nous donne aucune garantie sur l'ordre lors de l'itération, l'ordre peut complètement changer lorsque de nouveaux éléments sont ajoutés.

• Dans TreeMap , l'ordre est basé sur "l'ordre naturel" des clés selon leur méthode compareTo() (ou un Comparator que nous fournissons). N'oubliez pas non plus que TreeMap implémente l' interface SortedMap , qui contient des méthodes qui dépendent de cet ordre de tri.

Passons maintenant à une considération de performances et de vitesse:

• HashMap est une carte basée sur des clés de hachage. Il peut insérer et récupérer des éléments enO(1), temps constant. Pour cela, les clés doivent implémenterhashCode()etequals().

• TreeMap est une carte arborescente. Ses opérations d'insertion et de récupération prennent un temps logarithmique, c'est-à-direO(log n), qui dépend du nombre d'éléments dans la carte. Cela est nécessaire pour que les éléments aient une sorte de mécanisme de comparaison fourni soit par notre clé, soit par un comparateur externe. Ce mécanisme détermine l'ordre des itérations.

Et ces facteurs nous aident à décider quelles collections utiliser et quand.

Si nous devons stocker des valeurs dans un certain ordre, le choix est évident — nous avons besoin d'un SortedMap . Bien qu'il soit un peu plus lent que HashMap , il effectue des tâches importantes pour nous.

Comme mentionné précédemment, SortedMap peut nous donner la première (ou la dernière) clé, ou valeur, ou paire clé-valeur de notre carte, quel que soit le moment où cette valeur a été ajoutée. L' implémentation HashMap ne peut pas faire cela.

Par exemple, considérez une carte avec des clés (noms des élèves) et des valeurs (leurs notes). Disons que nous voulons travailler avec une liste dans l'ordre alphabétique inverse.

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

L'exemple montre que l'utilisation d'un HashMap rend la tâche plus compliquée, puisque HashMap ne garantit ni l'ordre de stockage ni l'ordre d'obtention des éléments de la carte.