Bibliothèques et collections

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.

1String s = "bonjour";2s.toUpperCase();          /* ne change PAS s */3s = 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 :

1String resultat = "";2for (String mot : mots) {3    resultat = resultat + mot;      /* QUADRATIQUE */4}

Chaque concaténation recopie tout ce qui précède dans une nouvelle chaîne. Sur $n$ mots, on recopie $1 + 2 + \dots + n$ caractères : c'est le $O(n^2)$ 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.

Le point de méthode le plus important du chapitre tient en une ligne :

1List<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 $O(1)$, insertion en fin amortie en $O(1)$ — par doublement de capacité, comme au chapitre 8 du cours de programmation —, mais insertion ou suppression au milieu en $O(n)$, à cause du décalage.

LinkedList est une liste doublement chaînée : insertion et suppression en $O(1)$ si l'on tient déjà la position, accès indexé en $O(n)$.

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 $O(1)$ 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 $O(\log n)$, 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.

1List<Livre> catalogue = new ArrayList<>();2catalogue.add(new Livre("Dune"));3catalogue.add("une chaîne");        /* REFUSÉ à la compilation */4Livre 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

1for (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 :

1public class Livre implements Comparable<Livre> {2    @Override3    public int compareTo(Livre autre) {4        return this.titre.compareTo(autre.titre);5    }6}7Collections.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.

1try (BufferedReader r = Files.newBufferedReader(Path.of("livres.txt"))) {2    String ligne;3    while ((ligne = r.readLine()) != null) {4        String[] champs = ligne.split(";");5        catalogue.add(new Livre(champs[0], champs[1]));6    }7} catch (IOException e) {8    System.err.println("lecture impossible : " + e.getMessage());9}

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.

À 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.

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

En travaux pratiques

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