Collections

Pour chaque type de collection (liste, ensemble, etc.), la bibliothèque Java contient généralement :

• une interface, qui décrit les opérations offertes par la collection en question,
• plusieurs classes implémentant l'interface et qui sont les mises en œuvre de la collection, ayant chacune leurs caractéristiques propre.

De plus, il arrive parfois que les classes de mise en œuvre, ou en tout cas certaines d'entre elles, héritent d'une classe abstraite fournissant le code commun.

La figure 1 présente une vision simplifiée de la hiérarchie de collections que nous étudierons. Les classes abstraites fournissant le code commun ont été omises de cette hiérarchie, car elles ne constituent qu'un détail de mise en œuvre.

En plus des méthodes définies dans les interfaces des différentes collections, on trouve des méthodes statiques relatives aux collections dans les classes Collections et Arrays. Ces deux classes ont pour seul but de regrouper des méthodes statiques, et ne sont donc pas instanciables — leur constructeur est privé. Leurs principales méthodes seront présentées en même temps que les collections concernées.

L'interface Collection sert d'interface mère aux interfaces List, représentant les listes, et Set, représentant les ensembles.

Comme nous l'avons vu, les listes sont ordonnées mais les ensembles ne le sont pas. Dès lors, seules les méthodes ne dépendant pas d'une notion d'ordre sont définies dans l'interface Collection. Par exemple, Collection ne contient pas de méthode pour insérer un élément à une position donnée, puisque cette opération n'a un sens que si ceux-ci sont ordonnés. Une telle méthode existe par contre dans l'interface List, comme nous le verrons.

L'interface Collection représente donc une collection dont on ne sait pas si elle est ordonnée ou non. Elle est bien entendu générique, et son paramètre de type E (pour element) représente le type des éléments de la collection :

public interface Collection<E> {
  // … méthodes
}

Ses méthodes les plus importantes sont présentées ci-après, parfois avec un type simplifié pour des raisons pédagogiques.

Le concept de liste est représenté dans la bibliothèque Java par l'interface List du paquetage java.util. Tout comme Collection — dont elle hérite — cette interface est générique et son paramètre de type représentant le type des éléments de la liste :

public interface List<E> extends Collection<E> {
  // … méthodes
}

Les principales méthodes que cette interface ajoute à celles de Collection sont présentées ci-après, parfois avec un type simplifié pour des raisons pédagogiques.

La bibliothèque Java offre deux mises en œuvres principales de l'interface List, à savoir les tableaux-listes, ou tableaux dynamiques, (classe ArrayList) et les listes chaînées (classe LinkedList).

Le choix de l'une ou l'autre de ces mises en œuvre dans une situation donnée dépend de l'utilisation qui est faite de la liste. La table ci-dessous, qui compare les complexités des opérations les plus fréquentes pour les deux mises en œuvre, peut servir de guide. Dans cette table, n est le nombre d'éléments de la liste.

Mais attention : les complexités données ci-dessus ne sont valables que dans des cas bien précis !

En particulier, l'ajout et la suppression d'un élément dans une liste chaînée est en O(1) uniquement s'il n'est pas nécessaire de parcourir la liste en premier lieu pour accéder au point d'ajout ou de suppression. En pratique, cela n'est donc vrai que si on utilise les méthodes add et remove d'un itérateur de liste (voir §8.3), ou si l'ajout ou la suppression se font en début ou en fin de liste (premier ou dernier élément).

D'autre part, l'ajout et la suppression d'un élément dans un tableau-liste sont en O(1) lorsqu'elles se font à la fin de la liste.

En programmation, les files et les deques sont souvent utilisés pour échanger des données entre un producteur — qui produit des valeurs et les place dans une file — et un consommateur — qui utilise les valeurs produites en les obtenant de la file.

Cette organisation permet au producteur et au consommateur de travailler indépendamment l'un de l'autre, chacun à son rythme.

Lorsque producteur et consommateur travaillent à leur rythme et ne communiquent que via une file, le risque existe que le producteur travaille beaucoup plus vite que le consommateur, faisant grossir la file de communication jusqu'à utiliser toute la mémoire à disposition.

Pour éviter ce problème, les files et les deques peuvent être bornées (bounded), c-à-d que leur capacité peut être limitée.

Avec une telle file, le producteur ne place une valeur dans la file que si celle-ci n'est pas pleine, et attend que ce soit le cas sinon. Le consommateur, quant à lui, continue à vider la file à son rythme.

L'interface Queue, qui hérite de l'interface Collection, n'ajoute (ou ne redéfinit) que trois paires de méthodes.

Les deux méthodes formant une paire se distinguent par la manière dont elles signalent une erreur, c-à-d le fait que la file soit pleine ou vide : la première méthode utilise une exception, la seconde une valeur de retour spéciale.

La version utilisant une valeur de retour spéciale est généralement plus facile à utiliser en présence d'une file bornée, car il est alors relativement normal que celle-ci soit pleine ou vide.

L'interface Deque ne fait (presque) que généraliser l'interface Queue en offrant deux variantes de chacune des méthodes de Queue, une par extrémité de la deque.

Ces méthodes ne sont donc pas présentées en détail mais résumées dans la table ci-dessous :

Une liste chaînée peut servir de relativement bonne mise en œuvre d'une file ou d'une deque, raison pour laquelle LinkedList implémente l'interface Deque — et donc Queue.

ArrayList, par contre, serait une très mauvaise mise en œuvre d'une file ou d'une deque, car l'ajout ou la suppression d'élément au début de la liste est en O(n). Pour cette raison, une mise en œuvre légèrement différente mais aussi basée sur un tableau redimensionné au besoin est fournie dans la classe ArrayDeque.

Un itérateur (iterator) ou curseur (cursor) est un objet qui désigne un élément d'une collection.

Un itérateur permet d'une part d'obtenir l'élément qu'il désigne, et sait d'autre part se déplacer efficacement sur l'élément suivant — et parfois précédent — de la collection.

Dans la bibliothèque Java, le concept d'itérateur est décrit par l'interface générique Iterator. Son paramètre de type représente le type des éléments de la collection parcourue par l'itérateur :

public interface Iterator<E> {
  // … méthodes
}

L'interface Iterator est très simple et ne contient que trois méthodes, dont une (remove) est optionnelle :

• boolean hasNext(), retourne vrai ssi il reste au moins un élément à parcourir,
• E next(), retourne l'élément suivant et avance l'itérateur sur son successeur, ou lève une exception s'il ne reste plus d'éléments,
• void remove(), supprime le dernier élément retourné par next, ou lève une exception si next n'a pas encore été appelée, ou si remove a déjà été appelée une fois depuis le dernier appel à next.

Les collections dont on peut parcourir les éléments offrent toutes une méthode iterator permettant d'obtenir un nouvel itérateur désignant le premier élément. Au moyen de cette méthode, la boucle d'impression ci-dessus peut s'écrire également ainsi :

List<String> l = /* … */;
Iterator<String> i = l.iterator();
while (i.hasNext()) {
  String s = i.next();
  System.out.println(s);
}

Nous connaissons maintenant deux techniques (efficaces) pour parcourir une liste : la boucle for-each et les itérateurs. Laquelle préférer ?

En termes d'efficacité, ces deux techniques sont rigoureusement équivalentes, la boucle for-each étant récrite par Java en une boucle basée sur un itérateur.

Par contre, la boucle for-each est plus concise et facile à comprendre. Elle est toutefois moins générale, puisqu'il n'est p.ex. pas possible de supprimer un élément de la collection lors du parcours, comme le permet la méthode remove de l'itérateur.

La boucle for-each peut en fait être utilisée sur n'importe quel objet qui implémente l'interface Iterable, ce qui est entre autre le cas de Collection.

L'interface Iterable, très simple, ne possède qu'une seule méthode abstraite, la méthode iterator vue précédemment :

public interface Iterable<E> {
  public Iterator<E> iterator();
}

Son paramètre de type E représente le type des éléments parcourus par l'itérateur.

En plus de cette méthode abstraite, l'interface Iterable offre une méthode par défaut, forEach(Consumer<E> c), destinée à être utilisée avec une lambda. Cette méthode offre un troisième moyen de parcourir les éléments d'une collection, que nous examinerons dans la leçon consacrée aux lambdas.

En plus de la méthode iterator qui fournit un itérateur de type Iterator, l'interface List définit une méthode nommée listIterator fournissant un itérateur de type ListIterator offrant des méthodes additionnelles pour :

• se déplacer en arrière (hasPrevious et previous),
• connaître l'index des éléments voisins de l'itérateur (nextIndex, previousIndex),
• insérer un élément dans la liste, à l'endroit désigné par l'itérateur (add),
• changer l'élément désigné par l'itérateur (set).

Logiquement, add et set sont optionnelles.

Le concept d'ensemble est représenté dans l'API Java par l'interface Set du paquetage java.util. Tout comme Collection — dont elle hérite — cette interface est générique et son paramètre de type représente le type des éléments de l'ensemble :

public interface Set<E> extends Collection<E> { }

Cette interface n'ajoute aucune méthode à celles héritées de Collection, son seul but étant d'offrir un type distinct pour les ensembles.

Aux principales opérations sur les ensembles mathématiques correspond une méthode de l'interface Set, avec une différence importante : contrairement aux opérations mathématiques, les méthodes modifient l'ensemble auquel on les applique. La table ci-dessous donne les méthodes correspondant aux opérations mathématiques.

Tout comme pour les listes, l'interface Set offre une méthode statique permettant de construire un ensemble immuable :

• <E> Set<E> of(E... es), retourne un ensemble immuable contenant les éléments donnés.

De plus, elle offre une méthode statique permettant de construire un ensemble immuable contenant les mêmes éléments qu'une collection donnée :

• <E> Set<E> copyOf​(Collection<E> c), retourne un ensemble immuable contenant les éléments de la collection donnée.

Tout comme pour les listes, la classe Collections offre une méthode permettant d'obtenir une vue non modifiable sur un ensemble :

• <E> Set<E> unmodifiableSet(Set<E> s)

Comme d'habitude, il faut prendre garde au fait qu'il s'agit d'une vue et que toute éventuelle modification à l'ensemble sous-jacent sera répercutée sur la vue ! Celle-ci est donc non modifiable mais pas forcément immuable.

Dès lors, comme avec les listes, pour obtenir une version immuable d'un ensemble, il faut copier celui-ci (aussi profondément que nécessaire).

Etant donné que l'interface Set implémente (indirectement) l'interface Iterable, les éléments d'un ensemble peuvent être parcourus au moyen d'un itérateur ou de la boucle for-each, comme ceux d'une liste.

On l'a dit, la bibliothèque Java offre deux mises en œuvre principales des ensembles. Avant de les examiner et de les comparer, posons-nous toutefois la question de leur utilité. Ne serait-il pas possible d'utiliser simplement des listes (sans doublons) afin de représenter les ensembles ?

En théorie, oui, et cela est même relativement simple sachant que la seule différence entre une liste « normale » et une liste représentant un ensemble est que cette dernière ne contient pas de doublons. Pour garantir cette propriété, il suffit d'utiliser la méthode contains fournie par l'interface Collection afin de s'assurer de l'absence d'un élément avant de l'ajouter à la liste.

Malheureusement, représenter un ensemble au moyen d'une liste est coûteux, car les principales opérations (ajout, test d'appartenance, etc.) ont une complexité de O(n). Intuitivement, cela est dû au fait que chacune de ces opérations nécessite un parcours de la totalité des éléments de la liste.

D'autres mises en œuvre, plus efficaces, sont donc fournies dans la bibliothèque Java. Néanmoins, chacune d'entre elles exige que certaines opérations puissent être effectuées sur les éléments de l'ensemble, afin de pouvoir les organiser en mémoire. Les deux mises en œuvre que nous examinerons, et leurs exigences concernant les éléments, sont :

• TreeSet, qui exige que les éléments de l'ensemble puissent être triés,
• HashSet, qui exige que les éléments de l'ensemble puissent être « hachés », notion examinée dans une leçon ultérieure.

TreeSet doit son nom au fait qu'elle stocke les éléments de l'ensemble dans un arbre binaire de recherche (binary search tree), tandis que HashSet doit le sien au fait qu'elle les stocke dans une table de hachage (hash table). Ces concepts seront examinés ultérieurement, mais il importe déjà de savoir que grâce à eux, TreeSet peut mettre en œuvre les opérations principales sur les ensembles (ajout, test d'appartenance, etc.) en O(log n), tandis que HashSet fait encore mieux et les met en œuvre en O(1), ce qui est remarquable !

Malgré ses performances moindres, TreeSet offre néanmoins un avantage par rapport à HashSet, déjà mentionné plus haut : étant donné qu'elle stocke les éléments de l'ensemble sous forme triée, ceux-ci sont parcourus dans cet ordre. HashSet, quant à elle, ne donne aucune garantie concernant l'ordre de parcours. Dès lors, malgré ses meilleures performances, HashSet n'est pas forcément toujours préférable à TreeSet.

Le concept de table associative est représenté dans l'API Java par l'interface Map du paquetage java.util. Cette interface est générique et prend deux paramètres de type nommés K et V qui représentent respectivement le type des clefs (keys) et celui des valeurs (values) :

public interface Map<K, V> {
  // … méthodes
}

A noter que contrairement aux interfaces List et Set, l'interface Map n'hérite pas de Collection, ni de Iterable.

Les principales méthodes de cette interface sont présentées ci-après, parfois avec un type simplifié pour des raisons pédagogiques.

L'interface Map.Entry — imbriquée statiquement dans l'interface Map — représente une association entre une clef et une valeur, aussi appelée paire clef/valeur.

Tout comme l'interface Map, l'interface Entry est générique et prend deux paramètres de type : le type K de la clef et le type V de la valeur qui lui est associée.

public interface Map<K, V> {
  public static interface Entry<K, V> {
    // … méthodes
  }
}

L'interface Map.Entry offre deux méthodes permettant respectivement d'accéder à la clef et à la valeur de la paire clef/valeur qu'elle représente :

• K getKey(), retourne la clef de la paire,
• V getValue(), retourne la valeur de la paire.

De plus, elle offre une méthode optionnelle permettant de modifier la valeur associée à la clef :

• void setValue(V v), remplace la valeur de la paire par celle donnée.

Comme les interfaces List et Set, l'interface Map possède une famille de méthodes statiques nommées of et permettant de créer des tables associatives immuables. Les versions à 0, 1 et 2 arguments sont :

• <K, V> Map<K, V> of(), qui retourne une table associative immuable vide,
• <K, V> Map<K, V> of(K k, V v), qui retourne une table associative immuable contenant uniquement la paire clef/valeur donnée,
• <K, V> Map<K, V> of(K k1, V v1, K k2, V v2), qui retourne une table associative immuable contenant les deux paires clef/valeur données.

Des méthodes similaires prenant jusqu'à 10 paires clef/valeur existent.

De plus, l'interface Map offre une méthode statique permettant de construire une table associative immuable contenant les mêmes éléments qu'une autre table donnée :

• <K,V> Map<K,V> copyOf​(Map<K,V> m), retourne une table associative immuable contenant les mêmes éléments que la table donnée.

Tout comme pour les listes, la classe Collections offre une méthode permettant d'obtenir une vue non modifiable sur une table associative :

• <K,V> Map<K, V> unmodifiableMap(Map<K, V> m)

Comme d'habitude, il faut prendre garde au fait qu'il s'agit d'une vue et que toute éventuelle modification à la table sous-jacente sera répercutée sur la vue ! Celle-ci est donc non modifiable mais pas forcément immuable.

L'interface Map n'étend malheureusement pas l'interface Iterable, et il n'est donc pas possible de parcourir directement les paires clef/valeur d'une table associative au moyen d'un itérateur.

Il est par contre possible de parcourir ces paires clef/valeur par l'intermédiaire de la vue fournie par entrySet :

Map<String, Integer> m = /* … */;
for (Map.Entry<String, Integer> e: m.entrySet())
  System.out.println(e.getKey() + "->" + e.getValue());

D'autre part, l'interface Map offre la méthode forEach, qui n'est pas celle de Iterable mais qui a le même but. Elle prend en argument un consommateur de type BiConsumer<K,V>, c-à-d une fonction à deux arguments — ici, la clef et la valeur — ne retournant rien.

La méthode forEach est destinée à être utilisée avec une lambda, et offre une manière particulièrement agréable de parcourir les paires clef/valeur d'une table associative. Par exemple, la boucle ci-dessus peut s'écrire plus simplement ainsi :

Map<String, Integer> m = /* … */;
m.forEach((k, v) -> System.out.println(k + "->" + v));

Attention : comme pour les ensembles, l'ordre de parcours dépend de la mise en œuvre utilisée. Avec TreeSet, le parcours se fait par ordre croissant des clefs, tandis qu'avec HashSet, le parcours se fait dans un ordre quelconque.

La bibliothèque Java offre deux mises en œuvre principales des tables associatives, TreeMap et HashMap. Comme la similarité de leurs noms l'indique, ces mises en œuvres sont basées sur les mêmes techniques que les classes TreeSet et HashSet. Dès lors, elles ont les mêmes caractéristiques principales, à savoir :

• TreeMap exige que ses clefs soient comparables, et utilise cette caractéristique pour offrir les opérations principales en O(log n), tout en garantissant que les paires clef/valeur sont parcourues par ordre croissant des clefs,
• HashMap exige que ses clefs soient hachables, et utilise cette caractéristique pour offrir les opérations principales en O(1), mais ne donne aucune garantie quant à l'ordre de parcours des paires clef/valeur.

Notez que seules les clefs doivent être comparables (pour TreeMap) ou hachables (pour HashMap), aucune exigence n'est placée sur les valeurs d'une table associative.

Le fait que les techniques de mise en œuvre des ensembles et des tables associatives soient similaires peut sembler surprenant au premier abord. Toutefois, à la réflexion, on se rend compte qu'il y a une très grande similarité entre ces deux types de collections :

• un ensemble peut être vu comme une table associative dont seules les clefs importent, les valeurs étant ignorées,
• une table associative peut être vue comme un ensemble de paires clef/valeur — pour peu que la valeur soit ignorée dans les tests d'égalité, les comparaisons et le hachage.

En pratique, la bibliothèque Java tire parti de ces similarités, puisque HashSet est mis en œuvre au moyen de HashMap, tandis que TreeSet est mise en œuvre au moyen de TreeMap.