Chapitre 1 · 5 h
Bibliothèques et collections
Chaînes de caractères, tableaux d'objets, List, ArrayList et Map, parcours et tri d'objets, généricité en première approche, entrées/sorties fichier.
Neuf chapitres ont appris à écrire une classe. Un programme réel en fait vivre des milliers d'instances ensemble : une bibliothèque contient des livres, un lecteur détient des emprunts, un catalogue associe un ISBN à un ouvrage.
Le tableau d'Algorithmique 1 ne suffit plus. Sa taille est fixée à la création, il n'offre aucune opération — ni insertion, ni suppression, ni recherche — et il ne sait rien associer. Ce chapitre donne les outils de la bibliothèque standard qui remplacent tout cela, et l'on retrouvera derrière chacun une structure d'Algorithmique 2.
Les chaînes, et un piège de complexité
String est la classe la plus employée de Java, et elle a une propriété qui explique tout son
comportement : elle est immuable. Une chaîne ne se modifie jamais ; toute opération en
fabrique une nouvelle.
String s = "bonjour";s.toUpperCase(); /* ne change PAS s */s = s.toUpperCase(); /* il faut réaffecter */L'immuabilité a des vertus — une chaîne peut être partagée sans risque, mise en cache, employée comme clé — et un coût, qui se paie dans une boucle :
String resultat = "";for (String mot : mots) { resultat = resultat + mot; /* QUADRATIQUE */}Chaque concaténation recopie tout ce qui précède dans une nouvelle chaîne. Sur mots, on
recopie caractères : c'est le du chapitre 4 d'Algorithmique 2. La
solution est StringBuilder, qui accumule dans un tampon extensible et ne construit la chaîne
qu'à la fin — le tableau dynamique du chapitre 8 du cours de programmation, exactement.
Rappel du chapitre 6, qui coûte cher chaque année : on compare deux chaînes avec equals,
jamais avec ==.
Les trois familles
La bibliothèque standard s'organise autour de trois interfaces, et le choix entre elles est une décision de modélisation.
| Interface | Contrat | Doublons | Ordre |
|---|---|---|---|
List | séquence indexée | oui | celui d'insertion |
Set | ensemble | non | selon l'implémentation |
Map | association clé → valeur | clés uniques | selon l'implémentation |
Le point de méthode le plus important du chapitre tient en une ligne :
List<Livre> catalogue = new ArrayList<>();On déclare l'interface, on instancie l'implémentation. Le reste du programme ne dépend
alors que du contrat, et remplacer ArrayList par LinkedList ne touche qu'une ligne. C'est le
polymorphisme du chapitre 6 appliqué à la conception, et c'est la pratique standard.
Derrière chaque nom, une structure connue
C'est ici que le cours d'Algorithmique 2 se rembourse.
ArrayList est un tableau dynamique : accès indexé en , insertion en fin amortie en
— par doublement de capacité, comme au chapitre 8 du cours de programmation —, mais
insertion ou suppression au milieu en , à cause du décalage.
LinkedList est une liste doublement chaînée : insertion et suppression en si l'on
tient déjà la position, accès indexé en .
En pratique, ArrayList est le choix par défaut, et l'argument est celui du chapitre 5
d'Algorithmique 2 : ses éléments sont contigus, donc le cache travaille pour elle, alors que les
cellules d'une LinkedList sont dispersées. Sur les tailles courantes, ArrayList gagne même
là où la complexité annonce le contraire.
HashMap repose sur une table de hachage : get et put en en moyenne, à
condition que les clés respectent le contrat equals/hashCode du chapitre 6. Une clé dont le
hashCode est mal écrit rend l'objet introuvable — sans aucune erreur.
TreeMap repose sur un arbre binaire de recherche équilibré, celui du chapitre 8
d'Algorithmique 2 : opérations en , mais les clés sont triées, ce qu'une
HashMap n'offre pas.
Même partage du côté des ensembles : HashSet est rapide et désordonné, TreeSet est trié.
Généricité
List<Livre> se lit « liste de Livre », et les chevrons ne sont pas décoratifs.
List<Livre> catalogue = new ArrayList<>();catalogue.add(new Livre("Dune"));catalogue.add("une chaîne"); /* REFUSÉ à la compilation */Livre premier = catalogue.get(0); /* pas de transtypage nécessaire */Deux bénéfices, et ils sont du même ordre que ceux du typage en général. Le compilateur
refuse ce qui n'a pas le bon type, donc l'erreur est détectée à l'écriture et non trois
semaines plus tard. Et la lecture ne demande aucun transtypage, donc aucune
ClassCastException possible — le chapitre 6 rappelait qu'un transtypage descendant n'est
qu'une promesse.
Une limite à connaître : la généricité de Java est réalisée par effacement de type. À
l'exécution, une List<Livre> est une List ordinaire — l'information de type n'existe qu'à la
compilation. D'où quelques interdits déroutants, comme l'impossibilité de créer un tableau de
type générique.
Parcourir et trier
for (Livre l : catalogue) { ... } /* la forme à employer */La boucle « pour chaque » fonctionne sur tout ce qui est parcourable, sans indice à gérer donc sans débordement possible. On ne revient à l'indice que si l'on en a réellement besoin.
Pour trier des objets, il faut dire ce que « plus petit » signifie, et Java offre deux voies qui expriment deux choses différentes.
Comparable définit l'ordre naturel de la classe, celui qui va de soi. On implémente
l'interface et sa méthode compareTo, qui rend un négatif, zéro ou un positif :
public class Livre implements Comparable<Livre> { @Override public int compareTo(Livre autre) { return this.titre.compareTo(autre.titre); }}Collections.sort(catalogue);Comparator définit un ordre parmi d'autres, fourni de l'extérieur : trier par auteur
aujourd'hui, par date demain. On le passe à sort, et l'on peut en avoir autant qu'on veut.
Le critère est simple : Comparable pour l'ordre évident et unique, Comparator pour tous les
autres. Et une règle de cohérence, souvent violée : l'ordre naturel devrait être compatible
avec equals — deux objets égaux devraient se comparer à zéro, faute de quoi les collections
triées se comportent bizarrement.
Fichiers
Les entrées/sorties suivent le même principe qu'au chapitre 9 du cours de programmation, avec les exceptions du chapitre 7 en plus.
try (BufferedReader r = Files.newBufferedReader(Path.of("livres.txt"))) { String ligne; while ((ligne = r.readLine()) != null) { String[] champs = ligne.split(";"); catalogue.add(new Livre(champs[0], champs[1])); }} catch (IOException e) { System.err.println("lecture impossible : " + e.getMessage());}Trois choses à noter. Le try avec ressources ferme le fichier automatiquement, y compris en
cas d'exception. La condition teste le retour de la lecture — readLine rend null en fin
de fichier — et non un hypothétique « suis-je à la fin ? » : c'est exactement le piège de feof
du cours de programmation. Et IOException est contrôlée, donc le compilateur exige qu'on
la traite : c'est le cas d'école de l'échec prévisible et extérieur.
Quiz · 1 question
Pourquoi écrit-on List<Livre> catalogue = new ArrayList<>() plutôt que ArrayList<Livre> catalogue = new ArrayList<>() ?
- Par pure convention : les deux écritures sont strictement équivalentes — équivalentes
- Pour que le reste du programme ne dépende que du CONTRAT et non de l'implémentation : remplacer ArrayList par LinkedList ne touche alors qu'une seule ligne. C'est le polymorphisme appliqué à la conception — dépendre du contrat
- Parce que ArrayList ne peut pas être déclarée à gauche d'une affectation — contrainte de syntaxe
Réponse : Déclarer le type le plus général possible est la pratique standard, et c'est une application directe du chapitre 6 : une variable déclarée List n'autorise que les méthodes du contrat List, donc aucun code appelant ne peut dépendre d'une particularité d'ArrayList. Le jour où l'on mesure que les insertions en tête dominent, on remplace new ArrayList par new LinkedList sur UNE ligne, et rien d'autre ne bouge. L'inverse — déclarer ArrayList partout — laisse le code appelant utiliser ensureCapacity ou trimToSize, et le remplacement devient une refonte. Le même principe vaut pour les paramètres de méthode : accepter une List plutôt qu'une ArrayList élargit ce qu'on peut vous passer sans rien vous coûter.
Quiz · 1 question
Une boucle construit une chaîne par resultat = resultat + mot sur 10 000 mots, et le programme rame. Pourquoi ?
- Parce que la concaténation est une opération réseau bufferisée — opération réseau
- Parce que String est IMMUABLE : chaque concaténation recopie tout ce qui précède dans une nouvelle chaîne, soit 1 + 2 + … + n caractères recopiés — un O(n²). Il faut un StringBuilder — immuabilité et recopie
- Parce que le ramasse-miettes ne peut pas récupérer les chaînes intermédiaires — ramasse-miettes
Réponse : Une String ne se modifie jamais : toute opération en fabrique une nouvelle. Concaténer, c'est donc allouer une chaîne de taille croissante et y recopier l'intégralité de ce qui précède, à chaque tour. La somme des recopies vaut 1 + 2 + … + n, soit n(n+1)/2 caractères : c'est le O(n²) du chapitre 4 d'Algorithmique 2, et sur 10 000 mots la différence avec la version linéaire est de plusieurs ordres de grandeur. StringBuilder accumule dans un tampon extensible — le tableau dynamique du cours de programmation, avec son doublement de capacité et son coût amorti — et ne construit la chaîne finale qu'une fois. Le ramasse-miettes récupère bien les intermédiaires, mais il doit d'abord les allouer, ce qui est justement le coût. Note : le compilateur Java optimise une concaténation ISOLÉE en StringBuilder, jamais une concaténation en boucle.
À vous
L'exercice mesure ce que le chapitre affirme, plutôt que de le répéter.
D'abord la concaténation : la version naïve et celle à tampon, avec le nombre de caractères recopiés dans chacune. Le rapport se voit dès quelques centaines de mots, et la courbe est sans appel.
Ensuite les trois familles sur le même jeu de données : la même bibliothèque rangée en List,
en Set et en Map, et ce que chacune répond aux mêmes questions — combien d'éléments après
insertion de doublons, l'ordre est-il conservé, combien de comparaisons pour retrouver un ISBN.
Puis le tri : ordre naturel par titre, puis deux comparateurs — par auteur, par date décroissante — sur la même liste.
Enfin le piège du chapitre 6 qui se paie ici : une clé dont le hashCode est incohérent, et un
livre rangé dans une Map qui devient introuvable.
Exercice de code
Mesurez le coût de la concaténation, opposez List, Set et Map, triez de trois façons, puis cassez une HashMap.
Point de départ
// ── 1. Concaténation : ce que l'immuabilité coûte ─────────────────────────
function concatenationNaive(mots) {
let resultat = "", recopies = 0;
for (const mot of mots) {
recopies += resultat.length; // tout ce qui précède est recopié
resultat = resultat + mot;
}
return { longueur: resultat.length, recopies };
}
function avecTampon(mots) {
const tampon = []; // le StringBuilder : on accumule
let recopies = 0;
for (const mot of mots) tampon.push(mot);
const resultat = tampon.join(""); // une seule construction, à la fin
recopies += resultat.length;
return { longueur: resultat.length, recopies };
}
// ── 2. Les trois familles sur le même jeu ─────────────────────────────────
class Livre {
constructor(isbn, titre, auteur, annee) {
this.isbn = isbn; this.titre = titre; this.auteur = auteur; this.annee = annee;
}
equals(a) { return a instanceof Livre && a.isbn === this.isbn; }
hashCode() { return this.isbn; }
toString() { return this.titre + " (" + this.auteur + ", " + this.annee + ")"; }
}
const CATALOGUE = [
new Livre(3, "Dune", "Herbert", 1965),
new Livre(1, "Ubik", "Dick", 1969),
new Livre(2, "Solaris", "Lem", 1961),
new Livre(3, "Dune", "Herbert", 1965), // doublon d'ISBN
];
// ── 3. Tri ────────────────────────────────────────────────────────────────
// Ordre NATUREL : celui qui va de soi pour la classe.
function compareTo(a, b) { return a.titre.localeCompare(b.titre); }
// Ordres PARMI D'AUTRES, fournis de l'extérieur.
const PAR_AUTEUR = (a, b) => a.auteur.localeCompare(b.auteur);
const PAR_ANNEE_DESC = (a, b) => 0; // ← à écrire
// ── 4. Une Map dont la clé ment ───────────────────────────────────────────
function creerMap(hachage) {
const seaux = new Map();
return {
put(cle, valeur) {
const h = hachage(cle);
if (!seaux.has(h)) seaux.set(h, []);
seaux.get(h).push({ cle, valeur });
},
get(cle) {
let comparaisons = 0;
const seau = seaux.get(hachage(cle)) ?? [];
for (const e of seau) { comparaisons++; if (e.cle.equals(cle)) return { valeur: e.valeur, comparaisons }; }
return { valeur: undefined, comparaisons };
},
};
}
// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Comparez les recopies des deux concaténations sur 100 puis 1000 mots.
// 2. Rangez CATALOGUE en liste, en ensemble (par ISBN) et en map ISBN → livre.
// Combien d'éléments dans chacun, et pourquoi ?
// 3. Écrivez PAR_ANNEE_DESC, et triez selon les trois ordres.
// 4. Construisez une map avec un hachage INCOHÉRENT et cherchez un livre.
const mots = Array.from({ length: 200 }, (_, i) => "mot" + i);
console.log(" naïve :", JSON.stringify(concatenationNaive(mots)));
console.log(" tampon :", JSON.stringify(avecTampon(mots)));
Solution
function concatenationNaive(mots) {
let resultat = "", recopies = 0;
for (const mot of mots) { recopies += resultat.length; resultat = resultat + mot; }
return { longueur: resultat.length, recopies };
}
function avecTampon(mots) {
const tampon = [];
for (const mot of mots) tampon.push(mot);
const resultat = tampon.join("");
return { longueur: resultat.length, recopies: resultat.length };
}
console.log("— 1. ce que l'immuabilité coûte —");
for (const n of [100, 400, 1600]) {
const mots = Array.from({ length: n }, (_, i) => "mot" + i);
const a = concatenationNaive(mots), b = avecTampon(mots);
console.log(" " + String(n).padStart(4) + " mots : naïve " +
String(a.recopies).padStart(8) + " caractères recopiés | tampon " +
String(b.recopies).padStart(6) + " rapport " + Math.round(a.recopies / b.recopies));
}
console.log(" Le rapport CROÎT avec n : c'est un O(n²) contre un O(n). Le");
console.log(" compilateur Java optimise une concaténation isolée, jamais une");
console.log(" concaténation en boucle.");
class Livre {
constructor(isbn, titre, auteur, annee) {
this.isbn = isbn; this.titre = titre; this.auteur = auteur; this.annee = annee;
}
equals(a) { return a instanceof Livre && a.isbn === this.isbn; }
hashCode() { return this.isbn; }
toString() { return this.titre + " (" + this.auteur + ", " + this.annee + ")"; }
}
const CATALOGUE = [
new Livre(3, "Dune", "Herbert", 1965),
new Livre(1, "Ubik", "Dick", 1969),
new Livre(2, "Solaris", "Lem", 1961),
new Livre(3, "Dune", "Herbert", 1965),
];
console.log("");
console.log("— 2. les trois familles, mêmes données —");
const liste = [...CATALOGUE];
const ensemble = [];
for (const l of CATALOGUE) if (!ensemble.some((x) => x.equals(l))) ensemble.push(l);
const map = new Map(CATALOGUE.map((l) => [l.isbn, l]));
console.log(" List : " + liste.length + " éléments — doublons conservés, ordre d'insertion");
console.log(" Set : " + ensemble.length + " éléments — le doublon d'ISBN a été rejeté par equals");
console.log(" Map : " + map.size + " entrées — clé unique, la seconde écrase la première");
console.log(" Choisir entre les trois est une décision de MODÉLISATION : accepte-t-on");
console.log(" deux exemplaires du même ISBN ?");
console.log("");
console.log("— 3. tri —");
const compareTo = (a, b) => a.titre.localeCompare(b.titre);
const PAR_AUTEUR = (a, b) => a.auteur.localeCompare(b.auteur);
// Décroissant : on inverse simplement les opérandes.
const PAR_ANNEE_DESC = (a, b) => b.annee - a.annee;
for (const [nom, ordre] of [["naturel (titre)", compareTo], ["par auteur", PAR_AUTEUR],
["par année décroissante", PAR_ANNEE_DESC]]) {
const tri = [...ensemble].sort(ordre);
console.log(" " + nom.padEnd(24) + tri.map((l) => l.titre).join(", "));
}
console.log(" Un seul ordre naturel (Comparable), autant de comparateurs qu'on veut.");
console.log("");
console.log("— 4. la clé qui ment —");
function creerMap(hachage) {
const seaux = new Map();
return {
put(cle, valeur) {
const h = hachage(cle);
if (!seaux.has(h)) seaux.set(h, []);
seaux.get(h).push({ cle, valeur });
},
get(cle) {
let comparaisons = 0;
const seau = seaux.get(hachage(cle)) ?? [];
for (const e of seau) {
comparaisons++;
if (e.cle.equals(cle)) return { valeur: e.valeur, comparaisons };
}
return { valeur: undefined, comparaisons };
},
};
}
const dune = new Livre(3, "Dune", "Herbert", 1965);
const memeLivre = new Livre(3, "Dune", "Herbert", 1965); // égal, autre objet
const bonne = creerMap((l) => l.hashCode());
for (const l of ensemble) bonne.put(l, "rayon A");
const r1 = bonne.get(memeLivre);
console.log(" contrat respecté : trouvé = " + (r1.valeur !== undefined) +
" en " + r1.comparaisons + " comparaison(s)");
let compteur = 0;
const cassee = creerMap(() => compteur++); // hachage incohérent
for (const l of ensemble) cassee.put(l, "rayon A");
const r2 = cassee.get(memeLivre);
console.log(" contrat violé : trouvé = " + (r2.valeur !== undefined) +
" en " + r2.comparaisons + " comparaison(s)");
console.log(" Le livre EST dans la map. La recherche va simplement dans le mauvais");
console.log(" seau, et rend undefined sans lever la moindre erreur. C'est le");
console.log(" contrat equals/hashCode du chapitre 6 qui se paie ici.");
En travaux pratiques
Travaux pratiques 9 · 3 h
Choisir une collection, et le prouver
Mesurer les collections plutôt que les choisir par habitude, et retrouver dans une bibliothèque toute faite les structures écrites à la main en Algorithmique 2.
Avant de commencer
- Le TP 6 : equals et hashCode
- De quoi chronométrer
Énoncé
- Mesurer — Comparez ArrayList et LinkedList sur : ajout en fin, ajout en tête, accès par indice, parcours complet. Cent mille éléments, quatre mesures chacune.
- La recherche — Cherchez cent mille fois un élément dans une List, puis dans un HashSet, puis dans un TreeSet. Comparez et reliez chaque résultat à une structure du cours d'Algorithmique 2.
- Le piège du hachage — Utilisez comme clé de HashMap un objet dont vous modifiez un champ APRÈS insertion. Essayez ensuite de le retrouver. Indice : La clé a changé de seau sans que la table le sache.
- Ordonné ou pas — Insérez les mêmes éléments dans HashSet, LinkedHashSet et TreeSet, et affichez les trois. Expliquez les trois ordres obtenus.
- Comparable et Comparator — Rendez Document triable par année, puis triez la même liste par titre sans toucher à la classe. Dites quand chacune des deux voies s'impose.
- La modification pendant le parcours — Supprimez un élément d'une liste pendant que vous la parcourez avec une boucle pour-chaque. Lisez l'exception, puis corrigez de deux façons.
- Les flux — Réécrivez avec des flux : filtrer les documents empruntables, les grouper par genre, compter par genre. Comparez à la version en boucles.
- Au fil rouge — Remplacez le tableau de Mediatheque par la collection que vos mesures désignent, et justifiez le choix en trois lignes dans un commentaire.
C'est réussi quand
- Vos mesures contredisent au moins une idée reçue sur LinkedList
- Vous perdez une clé dans une HashMap, et vous savez expliquer où elle est
- Vous triez la même liste de deux façons sans modifier Document
- Votre choix final de collection est justifié par un chiffre, pas par une habitude
Correction
100 000 éléments ArrayList LinkedList ajout en fin 0,003 s 0,004 s ajout en tête 1,8 s 0,004 s ← le seul avantage get(i) aléatoire 0,001 s 12,4 s ← catastrophique parcours complet 0,0004 s 0,003 s ← ×8, même complexité
LinkedList ne gagne que sur l'insertion en tête, et perd partout ailleurs — y compris sur le parcours, à complexité pourtant identique, pour la raison mesurée au TP 5 d'Algorithmique 2 : les maillons sont dispersés, chaque accès coûte un défaut de cache. En pratique, ArrayList est le bon choix par défaut, et LinkedList quasiment jamais.
100 000 recherches temps structure sous-jacente List.contains() 9,8 s parcours linéaire, O(n) HashSet.contains() 0,004 s table de hachage, O(1) en moyenne TreeSet.contains() 0,021 s arbre ROUGE-NOIR équilibré, O(log n) TreeSet donne EN PLUS l'ordre trié, et des requêtes par intervalle
Ce sont les structures d'Algorithmique 2, déjà écrites et éprouvées. TreeSet est l'arbre de recherche du TP 8 — mais AUTO-ÉQUILIBRÉ, donc sans le cas dégénéré que vous aviez provoqué sur entrée triée. On paie ce log n par rapport au hachage, et l'on obtient l'ordre : c'est le compromis à connaître pour choisir.
Document d = new Document("Dune", 1965);
Map<Document, Integer> stock = new HashMap<>();
stock.put(d, 3);
d.setAnnee(2021); /* la clé est MUTÉE après insertion */
stock.get(d) → null /* introuvable par elle-même ! */
stock.containsKey(d) → false
stock.size() → 1 /* elle est pourtant bien là */L'entrée a été rangée dans le seau du hachage d'origine ; la recherche va maintenant chercher dans le seau du nouveau hachage. L'objet est présent et inaccessible — et il le restera. D'où la règle : une clé de table de hachage doit être IMMUABLE. C'est pourquoi String, Integer et les enregistrements font de si bonnes clés.
insertion : Dune, 1984, Ubik, Solaris HashSet → [1984, Solaris, Dune, Ubik] ordre des SEAUX, imprévisible LinkedHashSet → [Dune, 1984, Ubik, Solaris] ordre d'INSERTION TreeSet → [1984, Dune, Solaris, Ubik] ordre NATUREL (trié)
L'ordre d'un HashSet n'est pas aléatoire : il est déterministe et dépend des hachages, donc imprévisible pour le lecteur et susceptible de changer d'une version de Java à l'autre. Écrire du code qui suppose un ordre de HashSet est un bogue qui passe tous les tests jusqu'au jour où il ne les passe plus.
/* Comparable : UN ordre naturel, dans la classe */
class Document implements Comparable<Document> {
@Override public int compareTo(Document a) {
return Integer.compare(this.annee, a.annee);
}
}
Collections.sort(liste);
/* Comparator : autant d'ordres qu'on veut, HORS de la classe */
liste.sort(Comparator.comparing(Document::getTitre));
liste.sort(Comparator.comparing(Document::getAnnee)
.thenComparing(Document::getTitre)
.reversed());Comparable pour l'ordre unique et évident — l'ordre d'un entier, d'une date ; Comparator dès qu'il y a plusieurs critères, ou que la classe ne vous appartient pas. Un point de cohérence souvent oublié : compareTo doit renvoyer 0 exactement quand equals renvoie vrai, faute de quoi TreeSet et HashSet ne s'accordent pas sur ce qu'est un doublon.
for (Document d : liste) if (!d.estDisponible()) liste.remove(d); /* ConcurrentModification */ /* correction 1 : l'itérateur explicite */ Iterator<Document> it = liste.iterator(); while (it.hasNext()) if (!it.next().estDisponible()) it.remove(); /* correction 2 : plus lisible */ liste.removeIf(d -> !d.estDisponible());
L'exception n'est pas un caprice : elle protège d'un parcours devenu incohérent, où des éléments seraient sautés silencieusement. Elle est détectée au mieux, pas garantie — d'où l'importance de ne jamais s'en remettre à elle et d'utiliser removeIf, qui exprime l'intention en une ligne.
Ce que la suite en fait
Le chapitre 10 est le projet, et il ne présente plus aucune notion : il demande de choisir. Quel découpage en classes, quelles relations, quelle collection pour chaque multiplicité du diagramme — et c'est là que le tableau de ce chapitre devient un outil de décision plutôt qu'une liste à connaître.
À retenir
Flashcards · 5 cartes
- Pourquoi String est-elle immuable, et quel piège en découle ?
- Une chaîne ne se modifie jamais : toute opération en fabrique une nouvelle — d'où la nécessité de RÉAFFECTER (s = s.toUpperCase()). Vertus : partage sans risque, mise en cache, emploi comme clé. Piège : concaténer en boucle recopie tout ce qui précède à chaque tour, soit 1 + 2 + … + n caractères, un O(n²). Remède : StringBuilder, qui accumule dans un tampon extensible. Et l'on compare toujours avec equals, jamais avec ==.
- Quelles sont les trois familles de collections, et que garantit chacune ?
- LIST : séquence indexée, doublons autorisés, ordre d'insertion conservé. SET : ensemble, PAS de doublons, ordre selon l'implémentation. MAP : association clé → valeur, clés uniques. Le choix entre elles est une décision de MODÉLISATION — un Set interdit les doublons, une Map impose une clé unique — et pas seulement une question de performance.
- Que se cache-t-il derrière ArrayList, LinkedList, HashMap et TreeMap ?
- ARRAYLIST : un tableau dynamique — accès O(1), ajout en fin amorti O(1) par doublement, insertion au milieu O(n). LINKEDLIST : une liste doublement chaînée — insertion O(1) si l'on tient la position, accès indexé O(n). HASHMAP : une table de hachage, O(1) en moyenne, à condition que les clés respectent le contrat equals/hashCode. TREEMAP : un arbre binaire de recherche équilibré, O(log n) mais clés TRIÉES. En pratique ArrayList est le choix par défaut : ses éléments sont contigus, donc le cache travaille pour elle.
- Pourquoi déclarer List et instancier ArrayList ?
- Pour que le reste du programme ne dépende que du CONTRAT : une variable déclarée List n'autorise que les méthodes de List, donc aucun appelant ne peut s'appuyer sur une particularité d'ArrayList. Remplacer l'implémentation ne touche alors qu'UNE ligne. C'est le polymorphisme appliqué à la conception, et cela vaut aussi pour les paramètres de méthode : accepter une List plutôt qu'une ArrayList élargit ce qu'on peut vous passer sans rien coûter.
- Comparable ou Comparator : quel critère, et quelle règle de cohérence ?
- COMPARABLE définit l'ordre NATUREL de la classe, celui qui va de soi : on implémente compareTo, et il n'y en a qu'un. COMPARATOR définit un ordre PARMI D'AUTRES, fourni de l'extérieur — par auteur aujourd'hui, par date demain — et l'on peut en cumuler. Règle de cohérence souvent violée : l'ordre naturel devrait être compatible avec equals, deux objets égaux se comparant à zéro, faute de quoi les collections triées se comportent bizarrement.