HashMap et collections en Java

Une Map stocke une association entre chaque clé et une valeur. Dans une Map de stocks, un nom de produit est la clé et sa quantité est la valeur. Deux produits peuvent avoir la même quantité, mais une clé de produit ne peut pas correspondre à deux entrées distinctes.

Créer la Map

import java.util.HashMap;

HashMap<String, Integer> stock = new HashMap<>();

Le premier type, String, décrit les clés. Le second, Integer, décrit les valeurs. Le diamant <> à droite permet à Java de déduire ces types. Les arguments de type doivent être des types référence : utilise Integer, Double, Character ou Boolean au lieu de int, double, char ou boolean. Java effectue l’autoboxing d’un simple int lorsqu’il le stocke comme Integer, et l’unboxing d’un Integer lorsqu’un int est nécessaire.

Suivre chaque modification

stock.put("apple", 12);
stock.put("pear", 7);
Integer previous = stock.put("apple", 15);

Le premier appel crée apple=12 ; le deuxième ajoute pear=7. Le troisième trouve la clé "apple" existante et remplace sa valeur. La Map contient maintenant deux entrées et previous contient 12. Un appel à put pour une clé sans association précédente renvoie null.

stock.get("apple") renvoie maintenant 15. stock.remove("pear") renvoie 7 et supprime cette entrée. Une nouvelle suppression de "pear" renvoie null. size() compte les entrées, isEmpty() vérifie s’il n’y en a aucune et clear() les supprime toutes.

Traiter une clé absente

stock.get("kiwi") renvoie null et stock.containsKey("kiwi") renvoie false. Cette instruction se compile mais échoue à l’exécution :

int quantity = stock.get("kiwi");

Java essaie d’effectuer l’unboxing de null en int, ce qui provoque une NullPointerException. Pour une Map de quantités non nulles, utilise une valeur par défaut :

int quantity = stock.getOrDefault("kiwi", 0);

Cela donne 0 sans ajouter "kiwi" à la Map. Tu peux aussi vérifier avec containsKey avant la lecture. containsValue(15) vérifie si une entrée possède cette valeur ; la méthode peut parcourir toutes les valeurs, ce qui diffère de la recherche d’une clé connue.

Une HashMap autorise aussi une clé null et des valeurs null. Si une clé est explicitement associée à null, getOrDefault renvoie ce null stocké, et non la valeur par défaut. containsKey distingue ce cas d’une clé absente. Les Map de quantités sont plus simples lorsque chaque quantité stockée est une valeur numérique plutôt que null.

Faire correspondre correctement les clés et les valeurs

Les clés de type String sont sensibles à la casse : "apple", "Apple" et "apple " sont différentes. Applique le même nettoyage avant le stockage et la recherche, par exemple avec name.trim().toLowerCase(). Nettoyer uniquement une clé de recherche ne peut pas corriger des clés stockées de façon incohérente.

Compare le contenu des valeurs enveloppées avec equals. Si deux entrées contiennent chacune 1000, leurs références Integer peuvent être différentes : == peut donc être faux même si leurs contenus numériques correspondent. Après avoir vérifié que les deux valeurs sont non nulles, a.equals(b) compare leurs contenus.

Une Map peut répondre à une recherche ponctuelle ou fournir toutes ses données à une boucle. Choisis la vue qui donne les éléments nécessaires à la boucle. Les vues sont liées à la Map : les modifications effectuées par leur intermédiaire peuvent donc aussi modifier la Map.

Choisir les clés, les valeurs ou les entrées

Utilise keySet() pour parcourir les clés. Une recherche dans cette boucle permet de retrouver chaque valeur :

for (String name : phoneBook.keySet()) {
    System.out.println(name + ": " + phoneBook.get(name));
}

Utilise values() lorsque les clés n’ont pas d’importance. Pour les quantités en stock apple 15, pear 7 et fig 3 :

int total = 0;
for (int quantity : stock.values()) {
    total += quantity;
}

La somme devient 25. Les valeurs répétées contribuent chacune séparément : une vue des valeurs n’est pas un ensemble.

Une entrée réunit une clé et sa valeur. Importe java.util.Map et utilise Map.Entry<K, V> avec getKey() et getValue(). Cela évite une seconde recherche :

String best = null;
int bestScore = Integer.MIN_VALUE;
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    if (best == null || entry.getValue() > bestScore) {
        best = entry.getKey();
        bestScore = entry.getValue();
    }
}

Pour Ana 82, Ben 91 et Cai 77, le résultat est Ben avec 91. Le test best == null traite aussi le cas où le premier score est égal au plus petit int possible. Si la Map est vide, best reste à null.

Choisir explicitement l’ordre

Une HashMap ne garantit aucun ordre de parcours. Tu ne peux pas supposer qu’il s’agit de l’ordre d’insertion, de l’ordre trié ou de l’ordre affiché aujourd’hui. Une LinkedHashMap conserve l’ordre d’insertion ; une TreeMap parcourt les clés triées. Si deux scores sont égaux, la boucle précédente conserve le premier rencontré. Avec une HashMap, l’un ou l’autre des noms à égalité peut gagner. Ajoute une règle explicite de départage lorsque le résultat doit être prévisible.

Supprimer des entrées avec l’itérateur

Appeler stock.remove(key) dans une boucle for-each sur stock.keySet() modifie les clés que parcourt la boucle. Cela peut provoquer une ConcurrentModificationException. La détection n’est pas garantie : une exécution sans exception ne rend pas ce schéma valide.

Utilise la méthode de suppression propre à l’itérateur :

Iterator<Map.Entry<String, Integer>> it =
    stock.entrySet().iterator();
while (it.hasNext()) {
    if (it.next().getValue() == 0) {
        it.remove();
    }
}

Importe java.util.Iterator. Pour apple 15, pear 0, fig 0 et kiwi 4, ce code supprime pear et fig. Une autre approche sûre consiste à noter les clés dans une liste, à terminer la boucle, puis à supprimer ces clés.

Remplacer une valeur existante n’ajoute ni ne supprime de clé. Pendant un parcours des entrées, entry.setValue(entry.getValue() * 2) peut doubler les quantités sans erreur. N’ajoute pas de nouvelles clés par l’intermédiaire de la Map pendant cette boucle.

Distinguer une vue d’une copie

stock.keySet().remove("apple") supprime l’entrée correspondante de la Map. Une liste distincte créée avec new ArrayList<>(stock.keySet()) est une copie des clés présentes à cet instant. Trier cette liste ne réordonne pas la Map, et supprimer un nom de la liste ne supprime pas son association.

Un identifiant de produit stocké sous forme de String possède déjà des règles d’égalité adaptées. Pour une clé issue de ta propre classe, tu dois décider si deux objets distincts ayant les mêmes données représentent la même clé.

Les codes de hachage ciblent la recherche ; l’égalité la confirme

Une HashMap utilise hashCode() pour aider à localiser une clé et equals() pour vérifier une correspondance. Des clés égales doivent avoir des codes de hachage égaux. Des clés différentes peuvent partager un code de hachage ; l’égalité permet tout de même de les distinguer. Les classes de valeurs standard comme String et Integer respectent déjà ce contrat.

Sans redéfinition, une classe hérite de Object une égalité fondée sur l’identité. Deux points créés séparément, de coordonnées 2 et 3, sont des clés différentes même si leurs champs correspondent :

labels.put(new Point(2, 3), "door");
String label = labels.get(new Point(2, 3));

Avec l’égalité par identité, label vaut null. La recherche a créé un second objet, différent de celui utilisé pour l’insertion.

Redéfinir les deux méthodes ensemble

Ici, les coordonnées d’un point définissent son contenu :

import java.util.Objects;

final class Point {
    private final int x;
    private final int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (!(other instanceof Point)) {
            return false;
        }
        Point point = (Point) other;
        return x == point.x && y == point.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

La vérification d’identité traite rapidement le cas du même objet. La vérification du type rejette null et les objets d’un autre type. La dernière comparaison vérifie les deux coordonnées. Objects.hash(x, y) construit le code de hachage à partir de ces mêmes champs. Avec cette classe, la recherche précédente renvoie "door".

Redéfinir uniquement equals laisse en place la méthode de hachage héritée, qui ne garantit pas des codes de hachage égaux pour des objets distincts dont les champs sont égaux. Une Map peut alors ne pas trouver une clé égale. Un code de hachage constant préserverait la correction du résultat, mais ralentirait la recherche. Générer les deux redéfinitions dans un éditeur aide à éviter d’utiliser des champs différents.

Utiliser la signature exacte de la méthode

public boolean equals(Point other) surcharge la méthode ; elle ne remplace pas equals(Object). La recherche dans une Map utilise equals(Object) : la nouvelle surcharge ne lui donne donc pas une égalité de contenu. L’annotation @Override transforme une signature incorrecte en erreur de compilation, au lieu de laisser un bogue de recherche caché.

Garder stables les éléments qui déterminent l’identité de la clé

Ne modifie pas les champs qui déterminent l’égalité ou le code de hachage d’une clé tant qu’elle est stockée. Si un point stocké passe de (2, 3) à (5, 3), la Map peut ne plus le retrouver sous l’une ou l’autre valeur, même si size() reste inchangée. Supprime-le avant de le modifier, puis réinsère-le. Déclarer les champs de la clé final, comme ci-dessus, empêche cette erreur.

Ces règles déterminent aussi l’appartenance à une HashSet. Une ArrayList utilise equals pour les recherches de contenu comme contains ; elle n’a pas besoin de codes de hachage pour cette recherche.

Un tableau des effectifs possède une clé pour chaque élément distinct et un nombre indiquant ses occurrences. La première occurrence initialise un effectif ; chaque occurrence suivante met à jour cette même entrée.

Construire un effectif élément par élément

HashMap<String, Integer> counts = new HashMap<>();
for (String word : text.split(" ")) {
    int oldCount = counts.getOrDefault(word, 0);
    counts.put(word, oldCount + 1);
}

Pour le texte « the cat saw the dog and the cat ran », le premier "the" est absent : son ancien effectif est donc de 0 et son nouvel effectif de 1. Ses deux apparitions suivantes font passer cette entrée à 2 puis à 3. "cat" termine à 2 ; "saw", "dog", "and" et "ran" terminent chacun à 1.

Il y a 6 mots distincts, donc counts.size() vaut 6. La somme des valeurs est de 9, le nombre d’occurrences de mots. Ces nombres mesurent des choses différentes : la taille de la Map n’est pas la longueur de la séquence d’origine.

La mise à jour peut s’écrire sur une ligne :

counts.put(word, counts.getOrDefault(word, 0) + 1);

Une forme équivalente plus longue vérifie avec containsKey, incrémente un effectif existant et stocke 1 pour une nouvelle clé. Dans ce schéma, tous les effectifs stockés sont non nuls.

Préserver le résultat précédent

Appeler counts.put(word, 1) pour chaque mot remplace à chaque fois l’effectif par 1. Cela enregistre l’existence d’un mot, mais perd son effectif. Appeler counts.get(word) + 1 sans traiter la première occurrence essaie d’effectuer l’unboxing de null et échoue. La valeur par défaut intervient à l’étape de lecture ; l’effectif augmenté doit ensuite être stocké.

Décider ce qui constitue un même élément

L’égalité des chaînes est exacte. "The" et "the" sont des clés différentes, tout comme "cat" et "cat,". Si la tâche les considère comme un même mot, nettoie chaque jeton avant de le compter. Mets le texte en minuscules et supprime la ponctuation que le programme traite comme séparateur. Utilise une règle cohérente pour que les résultats ne dépendent pas de la graphie rencontrée en premier.

La clé peut aussi être un caractère. Avec HashMap<Character, Integer>, une boucle sur "banana".toCharArray() produit a=3, n=2 et b=1 avec le même schéma de lecture, d’augmentation et de stockage.

Accumuler des montants plutôt que des occurrences

Pour les sommes par catégorie, ajoute le montant actuel au lieu de 1 :

HashMap<String, Double> totals = new HashMap<>();
double oldTotal = totals.getOrDefault(category, 0.0);
totals.put(category, oldTotal + amount);

Alimentation 12,50, transport 3,20 et alimentation 7,25 donnent alimentation 19,75 et transport 3,20. La valeur par défaut est 0.0, ce qui correspond au type de valeur Double. La Map conserve une entrée par catégorie, quel que soit le nombre de montants additionnés.

Lire le tableau terminé

Parcours les entrées pour trouver le plus grand effectif ou la plus grande somme, en mémorisant la meilleure clé et sa valeur. Précise une règle de départage si nécessaire. Pour un compte rendu alphabétique, new TreeMap<>(counts) copie les associations en triant les clés. Les effectifs restent inchangés ; trier les clés ne trie pas les catégories selon leurs sommes.

La valeur d’une Map peut être une collection. Lorsque plusieurs étudiants suivent un même cours, le cours est une clé et la liste associée contient tous ses étudiants. La règle d’unicité des clés de la Map s’applique toujours : la liste est l’unique valeur associée à ce cours.

Créer un groupe avant d’y ajouter un élément

HashMap<Character, ArrayList<String>> groups = new HashMap<>();
for (String fruit : fruits) {
    char letter = fruit.charAt(0);
    if (!groups.containsKey(letter)) {
        groups.put(letter, new ArrayList<>());
    }
    groups.get(letter).add(fruit);
}

Pour « apple », « banana », « avocado », « cherry » et « blueberry », le premier fruit crée la liste pour a et y ajoute « apple ». « Banana » crée la liste pour b. « Avocado » trouve la liste a existante et s’y ajoute. Le résultat est a → [apple, avocado], b → [banana, blueberry] et c → [cherry]. Chaque liste conserve son propre ordre d’insertion, même si la HashMap n’ordonne pas ses clés.

La vérification peut être raccourcie :

groups.putIfAbsent(letter, new ArrayList<>());
groups.get(letter).add(fruit);

putIfAbsent conserve une liste existante non nulle. Le get suivant renvoie cette liste, prête pour l’ajout.

Conserver la liste déjà construite

Un groups.put(letter, new ArrayList<>()) inconditionnel dans la boucle remplace l’ancienne liste à chaque occurrence. Seul le dernier fruit de chaque lettre subsiste après le add suivant. L’erreur inverse consiste à sauter entièrement la création : groups.get(letter).add(fruit) lève une NullPointerException pour une nouvelle clé car aucune liste n’existe encore.

Comprendre la référence

get renvoie la référence à la liste stockée. Lui ajouter un élément modifie cette même liste : il n’est donc pas nécessaire de la réinsérer. Cela explique aussi un bogue lié au partage :

ArrayList<String> shared = new ArrayList<>();
courses.put("Art", shared);
courses.put("Music", shared);
courses.get("Art").add("Jin");

Les deux clés mènent maintenant à [Jin]. Les deux clés n’ont pas créé deux listes. Crée une nouvelle liste pour chaque nouveau groupe lorsque les groupes doivent être indépendants.

Choisir des listes ou des ensembles dans les groupes

Une liste conserve les ajouts répétés. Un ensemble empêche les doublons dans ce groupe. Une HashMap<String, HashSet<String>> peut donc réunir les étudiants distincts inscrits à chaque cours sans compter deux fois le même étudiant dans un cours. La règle de l’ensemble s’applique à l’intérieur de chaque valeur ; la Map externe conserve une entrée par cours.

Pour lire un groupe qui peut être absent, vérifie avec containsKey ou utilise groups.getOrDefault(letter, new ArrayList<>()). Une clé absente donne alors une liste vide pour cet appel. La liste par défaut n’est pas automatiquement insérée ; lui ajouter un élément ne crée pas de groupe stocké.

Supprimer le dernier élément d’un groupe laisse la clé associée à une collection vide. Si le programme ne doit plus énumérer les groupes vides, vérifie avec isEmpty() et supprime aussi cette clé. Compte les groupes avec la taille de la Map externe et les éléments avec les tailles des collections internes.

Un index associe une clé d’identification à un objet. Une bibliothèque peut trouver un livre par son ISBN sans parcourir tous les livres d’une liste. Une table de correspondance utilise la même structure pour associer un code à une valeur simple, comme le prix d’un produit.

Choisir une clé d’identification

Une HashMap<String, Book> peut associer un ISBN à son livre. Chaque recherche ne nécessite que la clé. Le nom d’une personne est souvent une mauvaise clé unique : stocker une autre personne appelée « Sam Lee » sous cette même chaîne remplace la personne précédente. Utilise un identifiant unique ou une Map de regroupement si un nom doit mener à plusieurs personnes.

Conserve un index dans la classe responsable des données :

class Library {
    private HashMap<String, Book> byIsbn;

    Library() {
        byIsbn = new HashMap<>();
    }

    void addBook(Book book) {
        byIsbn.put(book.getIsbn(), book);
    }

    Book findByIsbn(String isbn) {
        return byIsbn.get(isbn);
    }
}

Ici, Book fournit une méthode getIsbn(). Les appelants utilisent addBook et findByIsbn ; ils n’ont pas besoin de connaître l’implémentation de la Map stockée. Le champ privé donne aussi à la classe un endroit unique où faire respecter ses règles d’ajout et de remplacement des livres.

Vérifier un résultat absent

Si findByIsbn renvoie null, aucun livre n’a été trouvé. Teste le résultat avant d’appeler une méthode sur celui-ci :

Book found = library.findByIsbn("978-0-00-000000-2");
if (found != null) {
    found.setOnLoan(true);
}

Appeler setOnLoan directement sur un résultat absent lèverait une NullPointerException. Une méthode comme hasBook(isbn) permet aussi aux appelants de vérifier la présence d’une clé.

Suivre les objets partagés entre les index

Une Map stocke une référence à un objet, pas une nouvelle copie de cet objet. Si le même livre figure dans une liste de tous les livres, une Map par ISBN et un regroupement par auteur, setOnLoan(true) modifie l’unique livre auquel les trois structures font référence. Cela évite que trois objets livre distincts divergent.

Les structures de collection elles-mêmes doivent tout de même être mises à jour. Supprimer un livre de la Map par ISBN ne supprime pas sa référence de la liste d’un auteur. Si une bibliothèque conserve les deux index, ses méthodes d’ajout et de suppression doivent mettre à jour les deux. Centraliser ces modifications dans des méthodes comme addBook et removeBook aide à garder des recherches cohérentes.

Utiliser une table dans un calcul

Supposons qu’une table de prix indique café 2,50, thé 2,00 et muffin 3,25. Pour deux cafés et un muffin :

double cost = 2 * prices.get("coffee") + prices.get("muffin");

Le sous-total des cafés est de 5,00 ; ajouter 3,25 donne 8,25. Les clés identifient les produits et les valeurs fournissent les montants. Un produit absent exige une décision explicite avant le calcul : une valeur par défaut de zéro le traiterait comme gratuit sans le signaler. La même technique de recherche peut donc nécessiter une règle différente de celle d’un tableau des effectifs pour les clés absentes.

Un ensemble contient chaque valeur au plus une fois. Il convient aux questions comme « Cette valeur est-elle déjà apparue ? » ou « Combien de valeurs différentes sont présentes ? ». Une HashSet permet de vérifier rapidement l’appartenance en moyenne, sans garantir d’ordre d’affichage.

Ajouter et vérifier des valeurs

import java.util.HashSet;

HashSet<String> visited = new HashSet<>();
boolean first = visited.add("Oslo");
boolean second = visited.add("Lima");
boolean third = visited.add("Oslo");
visited.add("Pune");

Les trois booléens stockés sont true, true et false. Le second « Oslo » correspond à un élément existant et n’est donc pas ajouté. La taille de l’ensemble est de 3. L’ajout d’un doublon ne remplace pas une case numérotée, car un ensemble n’a pas d’indice.

visited.contains("Lima") renvoie true. visited.remove("Lima") le supprime et renvoie true ; répéter cette suppression renvoie false. Utilise une boucle for-each pour parcourir les valeurs. Il n’existe pas de get(0) pour obtenir la première valeur d’une HashSet.

Supprimer les doublons d’une liste

ArrayList<Integer> values = new ArrayList<>();
values.add(3);
values.add(1);
values.add(3);
values.add(2);
values.add(1);
HashSet<Integer> distinct = new HashSet<>(values);

L’ensemble contient trois valeurs : {1, 2, 3}. Son ordre de parcours réel n’est pas spécifié. La liste source contient toujours cinq éléments car le constructeur crée une collection distincte.

Utilise new LinkedHashSet<>(values) pour conserver l’ordre des premières occurrences, ce qui donne 3, 1, 2. Utilise new TreeSet<>(values) pour obtenir les valeurs triées, 1, 2, 3. Les ensembles sont écrits ici entre accolades pour souligner l’appartenance ; la méthode toString() standard des ensembles en Java utilise des crochets.

Détecter la première répétition

Le résultat de add peut effectuer ensemble le test d’appartenance et l’insertion :

HashSet<Integer> seen = new HashSet<>();
for (int number : numbers) {
    if (!seen.add(number)) {
        System.out.println(number);
        break;
    }
}

Pour [4, 7, 2, 7, 4], la boucle affiche 7. C’est la première valeur rencontrée une seconde fois, même si 4 est apparu plus tôt dans la séquence. Avant que 7 se répète, l’ensemble contient 4, 7 et 2. L’échec de l’insertion déclenche l’arrêt.

Savoir ce qu’un ensemble ne peut pas indiquer

Vérifier avec contains avant chaque add est inutile car add traite déjà les doublons. Une liste accompagnée d’une vérification avec contains peut aussi conserver des valeurs distinctes, mais chaque recherche dans la liste peut parcourir tous les éléments stockés. Une HashSet exprime directement la règle.

L’égalité compte pour tes propres objets. Une HashSet<Point> a besoin d’une méthode equals fondée sur le contenu et d’un hashCode cohérent pour réunir des points créés séparément avec les mêmes coordonnées. Sans ces redéfinitions, des instances distinctes restent des éléments distincts.

Enfin, size() mesure les valeurs distinctes, pas les occurrences. Les neuf mots de « the cat saw the dog and the cat ran » produisent six mots distincts. Un ensemble ne permet plus de savoir que « the » est apparu trois fois ; utilise une Map d’effectifs lorsque ces effectifs comptent.

Les ensembles peuvent décrire des groupes et comparer leur appartenance. Si deux listes de participants à des événements contiennent plusieurs fois la même personne, un ensemble réduit d’abord chaque liste aux personnes présentes. Les opérations ensemblistes répondent ensuite aux questions portant sur l’un ou l’autre événement, les deux ou un seul.

Combiner deux groupes

Soit lundi {Ana, Ben, Cai, Dee} et mardi {Ben, Dee, Eva}.

Ces opérations sont l’union, l’intersection et la différence. Elles modifient l’ensemble receveur et renvoient un booléen indiquant s’il a changé. Elles ne renvoient pas un nouvel ensemble de résultats.

Préserver l’original

Fais une copie avant de modifier l’appartenance si tu as encore besoin de lundi :

HashSet<String> both = new HashSet<>(monday);
both.retainAll(tuesday);

both commence avec les quatre noms du lundi. retainAll supprime Ana et Cai car elles ne figurent pas dans mardi. Lundi lui-même reste inchangé. Pour trouver les personnes présentes uniquement le mardi, commence par une copie de mardi et supprime les noms du lundi : tu obtiens {Eva}. La différence a un sens ; l’inverser change la question.

Vérifier les sous-ensembles et l’égalité

monday.containsAll(group) vérifie si toutes les valeurs de group sont présentes dans lundi. Pour {Ben, Dee}, la méthode renvoie true : ce groupe est un sous-ensemble de lundi. Elle n’exige pas que lundi contienne uniquement ces deux personnes.

Deux ensembles sont égaux lorsque leurs éléments correspondent, quels que soient leur ordre d’insertion ou leur implémentation. Une HashSet contenant « x » et « y » est égale à une TreeSet contenant « y » et « x ». L’appartenance détermine l’égalité des ensembles : l’ordre seul ne peut donc pas les rendre différents.

Choisir un ordre de parcours

Les trois évitent les doublons. Utilise LinkedHashSet lorsque la première apparition de chaque nom compte. Utilise TreeSet lorsque chaque parcours doit déjà être trié. Pour les chaînes, le tri naturel suit les codes de caractères : les formes minuscules et majuscules ne se comportent pas comme dans un alphabet unique insensible à la casse.

Une TreeSet créée avec son constructeur par défaut nécessite des éléments possédant une comparaison naturelle, comme des chaînes, des nombres ou des objets qui implémentent Comparable. Dans cet ensemble, un résultat de comparaison égal à zéro indique un doublon. Une classe qui ne fournit aucune comparaison naturelle provoque une ClassCastException lors de l’insertion. Fournir un comparateur explicite est une autre façon de définir l’ordre d’une collection arborescente ; les exemples avec les réglages par défaut utilisent l’ordre naturel.

Une interface décrit les opérations fournies par une classe qui l’implémente. Elle permet au type d’une variable d’indiquer ce dont le code a besoin tout en laissant le choix du stockage à une classe concrète. List, Set et Map sont des interfaces liées aux collections dans java.util.

Lire les deux côtés d’une déclaration

List<String> names = new ArrayList<>();
Set<String> tags = new HashSet<>();
Map<String, Integer> counts = new HashMap<>();

Le côté gauche déclare le type de la variable. Le côté droit crée un objet d’une classe qui implémente ce type. Importe les deux types, par exemple java.util.List et java.util.ArrayList. Tu ne peux pas écrire new List<>() ou new Map<>() : une interface n’est pas un objet concret à construire.

Le code qui utilise counts peut appeler put, get et entrySet car Map les déclare. Si des clés classées par ordre alphabétique deviennent utiles, remplace la construction par new TreeMap<>(). Les appels existants se compilent toujours. Leur ordre peut changer car les implémentations peuvent garantir des ordres différents ; l’interface ne rend pas tous leurs comportements identiques.

Accepter la capacité nécessaire à une méthode

Une méthode qui ne fait que compter les mots longs peut accepter une Collection :

static int countLong(Collection<String> words, int min) {
    int count = 0;
    for (String word : words) {
        if (word.length() >= min) {
            count++;
        }
    }
    return count;
}

Pour [« a », « tree », « house »] et un minimum de 4, elle renvoie 2. La même méthode peut recevoir une ArrayList, une LinkedList, une HashSet ou List.of(...) car elle ne fait que lire les éléments. Un ensemble peut avoir déjà supprimé des doublons et fournir ainsi des données d’entrée différentes de celles d’une liste.

Utiliser un paramètre de type interface évite d’imposer une classe de stockage particulière lorsque la méthode n’en a pas besoin. Si les positions sont nécessaires, accepte List. Si la recherche par clé est nécessaire, accepte Map.

Connaître les limites du type déclaré

List<String> names = new ArrayList<>();
names.ensureCapacity(100);  // does not compile

L’objet est une ArrayList, mais List ne déclare pas ensureCapacity. Le compilateur vérifie le type déclaré de la variable. Utilise un type de classe concrète lorsque son opération particulière est réellement nécessaire ; ne modifie pas les paramètres de liste ordinaires simplement pour les faire correspondre à la classe d’un appelant.

Situer Map par rapport à Collection

List et Set étendent Collection, qui décrit un groupe d’éléments. Cette interface déclare des méthodes comme add, remove, contains, size, isEmpty, addAll et clear. La prise en charge d’une modification dépend de la collection effective.

Map n’étend pas Collection. Elle stocke des associations et fournit des vues qui sont des collections : keySet() est un Set, values() est une Collection et entrySet() est un Set d’entrées. Transmets counts.values() à une méthode qui attend une collection de valeurs, pas counts elle-même.

Une classe peut implémenter plusieurs interfaces. LinkedList implémente à la fois List et Deque, une interface de file à double extrémité. Ta propre classe indique les interfaces qu’elle s’engage à implémenter après implements, comme dans class Member implements Comparable<Member>.

Choisis une interface selon les règles dont tes données ont besoin. Des contenus d’apparence similaire ne rendent pas une liste, un ensemble et une Map interchangeables : chacun donne un sens différent aux positions, aux répétitions et à l’égalité.

Comparer les garanties

ArrayList et LinkedList implémentent List. HashSet, LinkedHashSet et TreeSet implémentent Set. HashMap, LinkedHashMap et TreeMap implémentent Map. Les versions fondées sur le hachage ne garantissent aucun ordre de parcours ; les versions chaînées conservent l’ordre d’insertion ; les versions arborescentes maintiennent les éléments ou les clés triés. Réinsérer une clé existante dans une LinkedHashMap ordinaire qui suit l’ordre d’insertion conserve sa place.

Examiner la suppression dans une liste d’entiers

Une List<Integer> possède deux surcharges pertinentes :

List<Integer> numbers = new ArrayList<>(List.of(1, 5, 7));
numbers.remove(1);

L’argument 1 est un int, donc Java supprime l’élément d’indice 1 : la valeur 5. Le résultat est [1, 7]. En repartant de [1, 5, 7], numbers.remove(Integer.valueOf(1)) sélectionne la suppression par valeur et laisse [5, 7]. L’objet enveloppe désigne clairement la surcharge voulue.

Comparer les contenus avec la bonne règle

Deux listes sont égales lorsque les mêmes éléments apparaissent dans le même ordre. Une ArrayList [1, 2] est égale à une LinkedList [1, 2], mais pas à une liste [2, 1]. Deux ensembles comparent l’appartenance, sans tenir compte de l’ordre. Deux Map comparent les associations : l’ordre d’insertion ne modifie donc pas leur égalité. Leurs classes concrètes peuvent différer alors que leurs contenus sont égaux selon la règle de l’interface.

Reconnaître les collections non modifiables

List<String> labels = List.of("a", "b");
Set<Integer> levels = Set.of(1, 2, 3);
Map<String, Double> prices = Map.of("tea", 2.0, "coffee", 2.5);

Ces fabriques renvoient des collections non modifiables. Toute tentative d’ajouter, de supprimer, de remplacer ou de trier leur contenu lève UnsupportedOperationException. Map.of accepte jusqu’à dix paires clé–valeur.

Les trois rejettent les éléments, clés ou valeurs null en levant NullPointerException. Set.of rejette les éléments en double et Map.of rejette les clés en double en levant IllegalArgumentException. List.of autorise les doublons car une liste peut répéter un élément. L’ordre de parcours des ensembles et des Map issus de ces fabriques n’est pas spécifié.

Copier lorsqu’une modification est nécessaire

new ArrayList<>(labels) crée une liste modifiable contenant les mêmes éléments. new HashSet<>(someList) et new HashMap<>(someMap) créent de même des structures de collection distinctes.

Ces copies sont superficielles : elles contiennent les mêmes références aux éléments. Supprimer un élément d’une copie laisse la structure d’origine intacte, mais modifier un objet mutable par l’une ou l’autre collection modifie l’objet partagé. Une collection non modifiable empêche les modifications de sa structure ; elle ne fige pas tous les objets qu’elle contient.

Une liste conserve un ordre, mais celui-ci peut simplement refléter l’arrivée des valeurs. Le tri réorganise la liste selon une règle de comparaison. Java fournit déjà un ordre naturel pour les nombres et les chaînes.

Trier une liste modifiable en place

List<Double> values = new ArrayList<>(List.of(3.5, -1.0, 2.25));
Collections.sort(values);

Importe java.util.Collections. La même liste contient maintenant [-1,0 ; 2,25 ; 3,5]. Le tri renvoie void, donc values = Collections.sort(values) ne se compile pas. values.sort(null) trie aussi dans l’ordre naturel. Pour un tableau, utilise Arrays.sort(array) ; un tableau contenant 5, 2 et 8 devient 2, 5, 8.

Prévoir l’ordre des chaînes caractère par caractère

La comparaison de chaînes examine le premier caractère qui diffère. Si une chaîne est le début d’une autre, la plus courte vient en premier. Ainsi, « apple » précède « apples ».

La liste [« pear », « Banana », « apple », « 10 », « 9 »] devient après tri [« 10 », « 9 », « Banana », « apple », « pear »]. Pour ces caractères, les chiffres précèdent les lettres majuscules, qui précèdent les minuscules. « 10 » précède « 9 » car '1' précède '9' ; l’ordre des chaînes n’interprète pas les chaînes de chiffres comme des nombres entiers. Stocke les données numériques sous forme de nombres lorsqu’un ordre numérique est nécessaire.

Utiliser des ordres différents prêts à l’emploi

names.sort(String.CASE_INSENSITIVE_ORDER);
values.sort(Collections.reverseOrder());

Le premier appel classe [« pear », « Banana », « apple »] dans l’ordre [« apple », « Banana », « pear »] sans modifier la casse stockée. Le second utilise l’ordre naturel décroissant. Les nombres 4, 9 et 1 deviennent 9, 4 et 1. Ces arguments sont des comparateurs, des objets qui fournissent un autre ordre.

Collections.reverse(list) inverse simplement la séquence actuelle. La méthode produit un ordre décroissant si cette séquence était déjà triée par ordre croissant ; elle ne trie pas à elle seule une liste quelconque.

Conserver la stabilité en cas d’égalité

Le tri des listes est stable : les éléments considérés comme égaux lors de la comparaison conservent leur ordre relatif précédent. Si une comparaison fondée uniquement sur le score met deux personnes à égalité, leur ordre antérieur dans la liste reste inchangé. La stabilité préserve cet ordre d’entrée ; elle n’invente pas de critère de départage alphabétique.

Reconnaître les échecs et les méthodes pratiques

Une liste issue de List.of(...) ne peut pas être triée en place. Copie-la d’abord dans une ArrayList. Pour une classe qui n’implémente pas Comparable, Collections.sort(list) échoue à la vérification des types lors de la compilation. Appeler list.sort(null) sur de tels objets échoue à l’exécution avec une ClassCastException lorsqu’une comparaison est nécessaire.

Collections.max(collection) et Collections.min(collection) trouvent le plus grand et le plus petit élément dans l’ordre naturel sans réorganiser la collection. Elles lèvent une NoSuchElementException pour une collection vide.

Pour obtenir les clés triées d’une Map, copie map.keySet() dans une ArrayList et trie la copie, ou utilise une TreeMap. Trier une copie de la liste des clés laisse inchangé l’ordre de parcours propre à la Map.

Java ne peut pas deviner si un membre doit être classé selon son nom, sa taille ou un autre champ. Implémente Comparable pour donner à la classe un ordre naturel. Le code de tri peut alors demander à chaque objet de se comparer à un autre objet de cette classe.

Écrire la méthode de comparaison

class Member implements Comparable<Member> {
    private String name;
    private int height;

    Member(String name, int height) {
        this.name = name;
        this.height = height;
    }

    @Override
    public int compareTo(Member other) {
        return Integer.compare(this.height, other.height);
    }
}

La taille est mesurée en centimètres. Comparable<Member> précise que l’autre objet est un Member ; aucun transtypage n’est nécessaire. public int compareTo(Member other) est la méthode requise. L’interface standard Comparable se trouve dans java.lang : aucune importation n’est donc nécessaire pour l’utiliser.

Pour a.compareTo(b), un résultat négatif place a avant b, zéro les place au même rang dans la comparaison et un résultat positif place a après b. Seul le signe compte : -35 est un résultat négatif aussi valide que -1.

Suivre l’ordre

Avec la comparaison des tailles, Ana 172, Ben 165 et Cai 180 sont triés en Ben 165, Ana 172 et Cai 180. Pour placer les membres les plus grands en premier, inverse les arguments :

return Integer.compare(other.height, this.height);

Modifie la règle délibérément. Inverser les arguments inverse le sens de l’ordre pour ce champ ; cela ne change pas la signification de la taille ni les données d’un membre.

Comparer des valeurs numériques entières sans erreur

La soustraction semble pratique, mais elle peut renvoyer le mauvais signe lorsqu’un int dépasse sa capacité. Pour -2 000 000 000 et 2 000 000 000, soustraire le second du premier produit par dépassement 294 967 296, un résultat positif. Integer.compare renvoie correctement un résultat négatif.

Pour les champs décimaux, utilise Double.compare(this.price, other.price). Transtyper une différence en int fait perdre de l’information : (int) (1.8 - 1.5) vaut 0, donc des prix différents deviennent égaux dans la comparaison. Une méthode de comparaison préserve l’ordre sans tronquer la différence.

Comparer du texte et réutiliser la règle

Pour ordonner par nom, renvoie this.name.compareTo(other.name). Cette méthode suit l’ordre des caractères des chaînes. compareToIgnoreCase fournit une comparaison textuelle insensible à la casse lorsque c’est la règle souhaitée pour le champ.

Une fois qu’une classe définit un ordre naturel, des opérations comme Collections.sort, Collections.max et les comparaisons par défaut de TreeSet ou de TreeMap peuvent l’utiliser. Une classe peut aussi implémenter d’autres interfaces, séparées par des virgules après implements.

La classe possède un seul ordre naturel : un compareTo différent n’est pas choisi pour chaque liste. Utilise des objets comparateurs distincts lorsqu’un contexte exige un ordre par nom et un autre un ordre par taille. Une comparaison fondée uniquement sur la taille met aussi à égalité toutes les tailles égales ; décider si cette égalité est acceptable devient particulièrement important dans les ensembles triés.

Une comparaison principale laisse souvent des égalités. Deux films peuvent avoir la même année ou deux joueurs le même score. Un critère de départage ne fait intervenir le champ suivant que lorsque les champs précédents sont égaux dans la comparaison.

Comparer les champs par ordre de priorité

@Override
public int compareTo(Film other) {
    int byYear = Integer.compare(this.year, other.year);
    if (byYear != 0) {
        return byYear;
    }
    return this.title.compareTo(other.title);
}

L’année est le critère principal. Le titre ne compte que si les années sont égales. Up (2009), Avatar (2009) et Alien (1979) sont triés en Alien (1979), Avatar (2009), Up (2009). Comparer d’abord les titres leur donnerait la priorité sur l’année et répondrait à une autre tâche de tri.

Le sens de l’ordre peut différer selon le champ. Pour les points du plus élevé au plus faible et les noms de A à Z, commence par Integer.compare(other.points, this.points). Si le résultat est zéro, renvoie this.name.compareTo(other.name). Inverser toute la liste finale inverserait aussi les noms parmi les scores à égalité.

Comprendre la règle des doublons d’un ensemble trié

Une TreeSet<Member> utilisée avec ses réglages par défaut emploie la comparaison naturelle à la fois pour ordonner les éléments et pour déterminer si un élément est déjà présent. Si Member.compareTo n’utilise que la taille, la comparaison d’Ana 172 et de Dee 172 donne zéro. Ajouter Ana renvoie true ; ajouter Dee renvoie false. Ana reste l’élément stocké, même si equals considère les deux membres comme différents.

Une liste peut conserver les deux objets à égalité ; un ensemble arborescent leur donne un seul rang dans la comparaison. Ajoute le critère de départage nécessaire s’ils doivent être distincts dans l’ensemble.

Rendre la comparaison cohérente avec l’égalité

Un ordre est cohérent avec equals lorsque la comparaison renvoie zéro si et seulement si equals renvoie true. Pour une classe dont l’égalité utilise la taille et le nom, comparer la taille puis le nom peut respecter cette règle. Si l’égalité repose sur une autre identité, comme un identifiant de membre, ajouter uniquement le nom comme critère de départage ne garantit pas cette cohérence.

La comparaison doit aussi se comporter comme un ordre valide. Si a précède b, la comparaison inverse doit placer b après a. Si a précède b et b précède c, a doit précéder c. Utiliser des méthodes qui comparent les champs dans leur intégralité selon un ordre de priorité fixe aide à respecter ces règles. Une méthode incohérente peut produire un ordre incorrect ou provoquer une IllegalArgumentException lors du tri.

Garder aussi les clés d’une Map triées

Une TreeMap trie les clés, pas les valeurs. Pour les effectifs des mots de « the cat saw the dog and the cat ran », la première clé est « and » et la dernière est « the ». firstKey() et lastKey() fournissent ces clés extrêmes. Déclare une TreeMap ou une interface de Map triée appropriée pour appeler des méthodes qu’une simple Map ne déclare pas.

La comparaison des clés définit aussi les clés correspondantes. Une seconde clé dont la comparaison donne zéro met à jour l’association existante, même si equals distingue les objets. Les collections arborescentes utilisées avec leurs réglages par défaut exigent des éléments ou des clés naturellement comparables ; insérer un objet sans comparaison adaptée lève ClassCastException. Un comparateur fourni explicitement peut définir un autre ordre.

Le coût d’une opération décrit comment le travail qu’elle demande augmente avec le nombre d’éléments stockés. Il aide à repérer un code rapide pour un petit exemple, mais lent lorsque la collection devient grande.

Comparer la croissance, pas les secondes

Un temps constant, O(1), reste approximativement indépendant de la taille de la collection. Un temps linéaire, O(n), peut augmenter proportionnellement au nombre d’éléments. Un temps logarithmique, O(log n), augmente lentement lorsque la taille grandit. Ces termes décrivent la croissance, pas les temps d’exécution exacts sur un ordinateur particulier.

Une recherche dans une ArrayList peut vérifier chaque élément ; les modifications près du début décalent les éléments suivants. Une LinkedList doit parcourir la liste jusqu’à une position : des accès répétés par indice peuvent donc être coûteux. ArrayList est un choix par défaut utile pour les opérations ordinaires sur les listes.

Repérer les parcours répétés

Supposons qu’un programme vérifie 10 000 noms dans une liste contenant 100 000 noms. Appeler list.contains(name) pour chaque nom peut nécessiter jusqu’à 1 000 000 000 vérifications d’égalité. Un appel de méthode qui semble rapide reste une recherche complète lorsqu’il est utilisé ainsi.

Construis une fois un ensemble pour les tests d’appartenance :

Set<String> allowed = new HashSet<>(allowedNames);
int matches = 0;
for (String name : incomingNames) {
    if (allowed.contains(name)) {
        matches++;
    }
}

La construction de l’ensemble de 100 000 éléments demande du travail, puis viennent 10 000 tests d’appartenance en temps constant en moyenne. En comptant les deux étapes, le travail total augmente approximativement avec la somme des tailles des deux entrées, plutôt qu’avec leur produit. Reconstruire l’ensemble dans la boucle répéterait le travail de mise en place et supprimerait cet avantage.

Bien comprendre les garanties en moyenne

Les opérations fondées sur le hachage reposent sur des clés dont les codes de hachage répartissent bien les valeurs. Renvoyer un seul code de hachage constant pour chaque objet peut toujours respecter la règle d’égalité, mais ralentit la recherche. Ce n’est pas une solution gratuite pour éviter d’écrire une méthode de hachage utile.

Les collections arborescentes maintiennent un ordre trié avec des opérations de base en temps logarithmique. Doubler le nombre d’éléments n’ajoute qu’une petite quantité de travail de recherche. Pour 100 000 éléments, le logarithme en base deux est d’environ 16,6 ; cela indique l’ordre de grandeur de la recherche, sans garantir exactement 17 comparaisons pour chaque recherche dans un arbre Java.

Tenir compte de toute la tâche

Construire un ensemble supplémentaire coûte du temps et de la mémoire. Pour quelques éléments ou une seule recherche, la liste d’origine peut suffire. Pour des tests d’appartenance répétés, un ensemble réutilisable supprime souvent le coût principal. Pars du comportement nécessaire, puis examine les opérations répétées le plus souvent.

La bonne collection conserve les informations nécessaires au programme et facilite l’expression de ses principales questions. Définis les règles des données avant de choisir le nom d’une classe familière.

Déterminer ce qui identifie un élément

Un double[12] peut contenir les précipitations en millimètres lorsque le mois de chaque case est connu. Une Map dont les seules clés sont les positions 0, 1, 2 et ainsi de suite ajoute une couche qu’une liste ou un tableau fournit déjà.

Choisir l’ordre nécessaire

Pour les Map et les ensembles, utilise HashMap ou HashSet si aucun ordre n’est nécessaire, LinkedHashMap ou LinkedHashSet pour l’ordre d’insertion, et TreeMap ou TreeSet pour des clés ou éléments triés. Pour une liste polyvalente, commence par ArrayList.

Les effectifs de mots affichés par ordre alphabétique conviennent à une TreeMap<String, Integer>. Une LinkedHashSet<String> convient à une liste de mots-clés distincts dans l’ordre de leur première apparition. Les morceaux répétés nécessitent une liste, même s’ils sont aussi stockés ailleurs dans un ensemble : supprimer les répétitions changerait la liste de lecture.

Combiner les collections lorsque les données ont plusieurs niveaux

Les étudiants par cours peuvent être représentés par une Map<String, List<String>> ; chaque valeur est une liste ordonnée d’inscriptions. Les mots-clés par article peuvent être représentés par une Map<String, Set<String>> ; chaque article reçoit des mots-clés distincts. Un classement peut être une List<Player> triée selon la comparaison naturelle des joueurs.

Les choix externe et interne répondent à des questions différentes. Si les cours doivent être énumérés par ordre alphabétique et les étudiants conservés dans l’ordre d’inscription, utilise une TreeMap à l’extérieur et une liste à l’intérieur. Trier les clés ne trie pas les listes. Si les inscriptions en double doivent être ignorées, utilise plutôt un ensemble pour les groupes internes.

Garder ensemble les données liées

Deux listes parallèles, l’une pour les noms et l’autre pour les numéros de téléphone, reposent sur la correspondance des positions. Supprimer un nom sans son numéro rompt toutes les associations suivantes. Si les noms identifient les personnes de façon unique, une Map peut conserver l’association. Si les noms se répètent ou si plusieurs champs concernent une personne, conserve des objets représentant les personnes dans une liste ou indexe-les par un identifiant unique.

Rechercher sans cesse dans une liste selon un champ est un autre signe qu’il faut envisager un index fondé sur une Map. Conserve aussi la liste si l’ordre d’affichage et les entrées répétées comptent, mais maintiens les deux structures ensemble lors des ajouts ou des suppressions de données.

Vérifier les règles des éléments et le type déclaré

Utilise une déclaration avec un type interface comme Map<String, Double> prices = new HashMap<>(); pour que les appelants s’appuient sur les opérations de Map dont ils ont besoin. Les collections fondées sur le hachage nécessitent une égalité adaptée et des codes de hachage cohérents pour les clés ou éléments personnalisés. Les collections arborescentes utilisées avec leurs réglages par défaut nécessitent une comparaison naturelle qui distingue exactement les valeurs que la collection doit conserver. Ces règles permettent à la collection choisie de représenter les données voulues.