Ch. 1 — Collections et Stream

R3.02 Développement efficace commence par un complément de Java : avant de construire piles, files, listes et tables de hachage à la main, il faut connaître les conteneurs déjà fournis par le JDK — et savoir choisir parmi eux. C'est l'objet de ce chapitre 1, Collection et Stream.

Le plan de la ressource compte cinq séances (un cours de 1 h, un TD d'1 h 30, un TP de 2 h) :

1. Complément de Java — Collection et Stream : ce chapitre ;
2. Pile et File — le chapitre 2, mis en œuvre dans les TD 2 et TP 2 ;
3. Liste ;
4. Table de hachage ;
5. Arbres.

L'évaluation de la ressource est un DS noté.

1. Types abstraits et structures de données

Les programmes manipulent des données, et la façon de les organiser décide de tout : comment y accéder, les mettre à jour, les parcourir. Deux notions à distinguer :

• un type abstrait est la spécification des opérations qu'on peut effectuer sur les données — par exemple « une pile : empiler, dépiler, tester si elle est vide » ;
• une structure de données est une mise en œuvre concrète de ce type abstrait — par exemple « une pile implémentée avec un tableau ».

Vous en connaissez déjà beaucoup : tableaux, listes, piles, files, dictionnaires. Le bon choix dépend des besoins de l'application (quelles opérations sont fréquentes ? y a-t-il des doublons ? faut-il trier ?) : il est indispensable de comprendre les spécificités des structures du langage utilisé pour choisir la plus adaptée — et donc d'abord de savoir lesquelles existent.

2. Le Collections Framework

En Java, le Collections Framework propose des interfaces qui spécifient les opérations possibles, et des classes prêtes à l'emploi qui les implémentent. Le parti pris du cours :

En général, il vaut mieux savoir choisir parmi les structures de données existantes que de les implémenter soi-même.

Quatre interfaces principales, à connaître par cœur :

3. L'interface Collection

L'interface Collection<E> unifie les méthodes principales « de stockage d'éléments de type E », avec entre autres : boolean add(E e), boolean contains(Object o), boolean remove(Object o) et int size().

Une question cruciale se cache dans contains : sur quoi se base la comparaison ? Le cours montre le test exact effectué :

if (o == null) {
    return e == null;
} else {
    return o.equals(e);
}

C'est equals qui décide des correspondances — d'où tout ce qui suit.

4. Égalité d'objets : equals et hashCode

Deux objets distincts aux mêmes valeurs doivent-ils être considérés égaux ? Oui, si l'on redéfinit equals.

• == compare l'égalité des références ;
• equals() compare l'égalité tout court ;
• mais par défaut, equals() se base sur les références pour les types non natifs de Java : il faut donc la redéfinir, sinon deux instances aux mêmes propriétés sont considérées comme différentes.

Règle du cours : dès qu'on utilise une Collection<E> où E n'est pas un type natif, il faut redéfinir equals — et donc hashCode.

Du côté du hachage : en Java chaque objet porte une valeur de hachage (hashCode()), qui par défaut référence l'emplacement mémoire. Le contrat à respecter :

Si a.equals(b) alors on doit avoir a.hashCode() == b.hashCode().

Il est donc important de redéfinir conjointement les deux méthodes.

5. Parcourir une collection : Iterable et Iterator

Collection<E> étend Iterable<E>, qui contient une seule méthode : Iterator<E> iterator(). Conséquence : tout objet Iterable fournit un itérateur pour parcourir ses éléments, et le foreach l'utilise implicitement.

Un itérateur est un curseur sur les éléments de la collection :

• boolean hasNext() : vrai s'il reste des éléments ;
• E next() : renvoie l'élément suivant et décale le curseur d'un cran vers la droite.

À l'état initial, l'itérateur est positionné avant le premier élément : un premier appel à next() est nécessaire pour atteindre le premier objet.

Exemple du cours avec un Set<Etudiant> :

Iterator<Etudiant> it = promo.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

la version foreach, strictement équivalente :

for (Etudiant etu : promo) {
    System.out.println(etu);
}

6. L'interface Set

Set<E> étend Collection<E> et correspond au type abstrait ensemble au sens mathématique :

• pas de doublon (la méthode add peut échouer — elle renvoie alors false) ;
• pas d'ordre, donc pas d'accès par indice.

Comme il n'y a pas d'indice, impossible de parcourir un Set avec une boucle get(i) comme pour une liste : il faut un itérateur ou un foreach (ou une version déléguée comme toString(), forEach() ou un Stream — qui restent des parcours).

Deux implémentations principales :

Dans un TreeSet, c'est compareTo qui fait foi — on y reviendra au cours 5, sur les arbres.

7. L'interface Map

Map<K,V> correspond au type abstrait dictionnaire (ou table de correspondance) : une collection de couples (clé, valeur).

• les clés sont uniques (pas de doublon), de type K ;
• les valeurs de type V ne sont pas nécessairement uniques ;
• une clé permet de retrouver rapidement la valeur associée.

Exemples du cours : annuaire, dictionnaire, gestion d'articles.

Les méthodes principales :

Parcours : Map n'étend pas Collection et n'est pas itérable (pas de foreach direct sur une Map). Trois vues permettent de la parcourir :

• Set<K> keySet() — les clés ;
• Collection<V> values() — les valeurs ;
• Set<Map.Entry<K,V>> entrySet() — les couples, via getKey() et getValue().

Exemple du cours — un dictionnaire de moyennes :

Map<Etudiant, Double> resultats = new HashMap<>();

for (Etudiant etu : resultats.keySet()) {                          // les clés
    System.out.println(etu);
}
for (Double note : resultats.values()) {                           // les valeurs
    System.out.println(note);
}
for (Map.Entry<Etudiant, Double> couple : resultats.entrySet()) {  // les couples
    System.out.println(couple.getKey() + " " + couple.getValue());
}

Deux implémentations principales, mêmes rôles que pour Set :

8. Collection et Collections — le piège des noms

• Collection (sans « s ») est l'interface ;
• Collections (avec « s ») est une classe boîte à outils de méthodes static — ne pas les confondre.

Quelques outils très utiles :

Collections.sort(promo, (e1, e2) -> e1.getName().compareTo(e2.getName()));

9. Fonctions lambda

Deux définitions avant de lire la ligne ci-dessus :

• une interface fonctionnelle est une interface qui ne contient qu'une seule méthode abstraite — Comparator en est une ;
• une fonction lambda est une implémentation concise de ce type d'interface.

Le compilateur infère le type : il en déduit les paramètres, le type de retour et les exceptions. Syntaxe : des paramètres, l'opérateur ->, et le corps de la fonction :

(paramètres) -> instruction;
(paramètres) -> { bloc d'instructions; }

Règles d'écriture : parenthèses vides s'il n'y a pas de paramètre, facultatives pour un paramètre unique au type inféré ; accolades facultatives si le corps tient en une instruction.

L'exemple du cours, pour trier une liste d'étudiants par nom — d'abord avec une classe externe :

Collections.sort(promo, new CompEtudiant());

puis sans classe, avec une lambda : plus courte, et la façon de comparer est explicite.

Collections.sort(promo, (e1, e2) -> e1.getName().compareTo(e2.getName()));

10. L'interface Stream

L'API Stream (« flux ») permet la programmation fonctionnelle : un Stream représente une séquence et permet d'effectuer des opérations dessus sans structure de boucle.

Créer un Stream :

Stream<String> deuxMots = Stream.of("Hello", "World");
IntStream de0a99 = IntStream.range(0, 100);
LongStream quiContinue = LongStream.iterate(1, n -> n + 1);
Stream<Etudiant> flux = promo.stream();   // depuis une Collection ou un tableau

Les opérations du cours, avec leur interface fonctionnelle :

promo.stream().forEach(etu -> System.out.println(etu));
promo.stream().filter(etu -> etu.getName().equals("Dupont"));
promo.stream().map(etu -> etu.getName().toUpperCase());
promo.stream().sorted((e1, e2) -> e1.getName().compareTo(e2.getName()));
promo.stream().max((e1, e2) -> e1.getDate().compareTo(e2.getDate()));
IntStream.of(1, 5, 6, 7).sum();

List<Etudiant> liste = promo.stream().collect(Collectors.toList());
Set<Etudiant> ensemble = promo.stream().collect(Collectors.toSet());
Map<LocalDate, List<Etudiant>> anniversaires =
        promo.stream().collect(Collectors.groupingBy(etu -> etu.getDate()));

11. Synthèse : quelle structure choisir ?

Les trois questions du cours :

• ai-je des doublons ?
• dois-je privilégier le parcours ou l'insertion / suppression ?
• peut-on ordonner mes données ? doivent-elles l'être ?

Et la réponse en tableau :