14. Les collections

Niveau :

Elémentaire

Les collections sont des objets qui permettent de gérer des ensembles d'objets. Ces ensembles de données peuvent être définis avec plusieurs caractéristiques : la possibilité de gérer des doublons, de gérer un ordre de tri, etc. ...

Une collection est un regroupement d'objets qui sont désignés sous le nom d'éléments.

L'API Collections propose un ensemble d'interfaces et de classes dont le but est de stocker de multiples objets. Elle propose quatre grandes familles de collections, chacune définie par une interface de base :

• List : collection d'éléments ordonnés qui accepte les doublons
• Set : collection d'éléments non ordonnés par défaut qui n'accepte pas les doublons
• Map : collection sous la forme d'une association de paires clé/valeur
• Queue et Deque : collections qui stockent des éléments dans un certain ordre avant qu'ils ne soient extraits pour traitement

Ce chapitre contient plusieurs sections :

• Présentation du framework collection
• Les interfaces des collections
• Les collections de type List : les listes
• Les collections de type Set : les ensembles
• Les collections de type Map : les associations de type clé/valeur
• Les collections de type Queue : les files
• Le tri des collections
• Les algorithmes
• Les exceptions du framework

14.1. Présentation du framework collection

Les tableaux ne peuvent pas répondre à tous les besoins de stockage d'un ensemble d'objets et surtout ils manquent de fonctionnalités. La large diversité d'implémentations proposées par l'API Collections de Java permet de répondre à la plupart des besoins.

Avant Java 1.2 qui a introduit l'API Collections, seules quelques classes du package java.util permettaient de stocker et de gérer des éléments : Array, Vector, Stack, Hashtable, Properties et BitSet. L'interface Enumeration permet de parcourir le contenu de ces objets.

L'API Collections propose de structurer et de définir un ensemble d'interfaces et de classes de type collection. Les collections sont des conteneurs qui permettent de regrouper des objets en une seule entité.

Java propose l'API Collections qui offre un socle riche et des implémentations d'objets de type collection enrichies au fur et à mesure des versions de Java.

L'API Collections possède deux grandes familles chacune définies par une interface :

• java.util.Collection : pour gérer un groupe d'objets
• java.util.Map : pour gérer des éléments de type paires de clé/valeur

Une collection permet de stocker un groupe d'éléments en respectant certaines fonctionnalités selon l'implémentation : de base, elle permet d'ajouter, de supprimer, d'obtenir et de parcours ses éléments.

Les interfaces et les classes de l'API Collections qui ne proposent pas de gestion des accès concurrents sont dans le package java.util. Java 5 propose plusieurs collections dans le package java.util.concurrent telles que CopyOnWriteArrayList, ConcurrentHashMap ou CopyOnWriteArraySet qui permettent des modifications lors de leur parcours.

Les fonctionnalités des collections sont définies dans cinq interfaces de base : Collection, List, Set, Map, Queue.

Plusieurs interfaces spécialisent certaines fonctionnalités particulières :

• SortedSet
• NavigableSet
• SortedMap
• NavigableMap
• ConcurrentMap
• ConcurrentNavigableMap
• BlockingQueue
• Deque
• BlockingDeque

Elle définit plusieurs classes abstraites qui sont les classes mères de plusieurs implémentations : AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList, AbstractQueue, AbstractMap.

Elle propose plusieurs implémentations à usage généraliste : HashSet, TreeSet, LinkedHashSet, ArrayList, ArrayDeque, LinkedList, PriorityQueue, HashMap, TreeMap, LinkedHashMap.

Elle propose également plusieurs implémentations pour un usage spécifique : WeakHashMap, IdentityHashMap, CopyOnWriteArrayList, CopyOnWriteArraySet, EnumSet, EnumMap.

A partir de Java 5, plusieurs implémentations permettent l'utilisation de collections de manière concurrente dans un environnement multithread : ConcurrentLinkedQueue, LinkedBlockingQueue, ArrayBlockingQueue, PriorityBlockingQueue, DelayQueue, SynchronousQueue, LinkedBlockingDeque, ConcurrentHashMap, ConcurrentSkipListSet, ConcurrentSkipListMap.

Elle définit enfin :

• deux interfaces pour le parcours de certaines collections : Iterator et ListIterator.
• une interface et une classe pour permettre le tri de certaines collections : Comparable et Comparator
• des classes utilitaires : Arrays, Collections

Le framework Collections propose plusieurs implémentations possédant chacune un comportement et des fonctionnalités particulières.

Pour combler le manque d'objets adaptés, la version 2 du J.D.K. apporte un framework complet pour gérer les collections. Cette bibliothèque contient un ensemble de classes et interfaces. Elle fournit également un certain nombre de classes abstraites qui implémentent partiellement certaines interfaces.

Les interfaces à utiliser par des objets qui gèrent des collections sont :

• Collection : interface qui est implémentée par la plupart des objets qui gèrent des collections
• Map : interface qui définit des méthodes pour des objets qui gèrent des collections sous la forme clé/valeur
• Set : interface pour des objets qui n'autorisent pas de doublons dans l'ensemble
• List : interface pour des objets qui autorisent des doublons et un accès direct à un élément
• SortedSet : interface qui étend l'interface Set et permet d'ordonner l'ensemble
• SortedMap : interface qui étend l'interface Map et permet d'ordonner l'ensemble

Certaines méthodes définies dans ces interfaces sont dites optionnelles : leur définition est donc obligatoire mais si l'opération n'est pas supportée alors la méthode doit lever une exception particulière. Ceci permet de réduire le nombre d'interfaces et de répondre au maximum de cas.

Le framework propose plusieurs objets qui implémentent ces interfaces et qui peuvent être directement utilisés :

• HashSet : Hashtable qui implémente l'interface Set
• TreeSet : arbre qui implémente l'interface SortedSet
• ArrayList : tableau dynamique qui implémente l'interface List
• LinkedList : liste doublement chaînée (parcours de la liste dans les deux sens) qui implémente l'interface List
• HashMap : Hashtable qui implémente l'interface Map
• TreeMap : arbre qui implémente l'interface SortedMap

Le framework définit aussi des interfaces pour faciliter le parcours des collections et leur tri :

• Iterator : interface pour le parcours des collections
• ListIterator : interface pour le parcours des listes dans les deux sens et pour modifier les éléments lors de ce parcours
• Comparable : interface pour définir un ordre de tri naturel pour un objet
• Comparator : interface pour définir un ordre de tri quelconque

Deux classes existantes dans les précédentes versions du JDK ont été modifiées pour implémenter certaines interfaces du framework :

• Vector : tableau à taille variable qui implémente maintenant l'interface List
• Hashtable : table de hachage qui implémente maintenant l'interface Map

Le framework propose la classe Collections qui contient de nombreuses méthodes statiques pour réaliser certaines opérations sur une collection. Plusieurs méthodes unmodifiableXXX() (où XXX représente une interface d'une collection) permettent de rendre une collection non modifiable. Plusieurs méthodes synchronizedXXX() permettent d'obtenir une version synchronisée d'une collection pouvant ainsi être manipulée de façon sûre par plusieurs threads. Enfin plusieurs méthodes permettent de réaliser des traitements sur la collection : tri et duplication d'une liste, recherche du plus petit et du plus grand élément, etc. ...

Le framework fournit plusieurs classes abstraites qui proposent une implémentation partielle d'une interface pour faciliter la création d'une collection personnalisée : AbstractCollection, AbstractList, AbstractMap, AbstractSequentialList et AbstractSet.

Les objets du framework stockent toujours des références sur les objets contenus dans la collection et non les objets eux-mêmes. Ce sont obligatoirement des objets qui doivent être ajoutés dans une collection. Il n'est pas possible de stocker directement des types primitifs : il faut impérativement encapsuler ces données dans des wrappers.

Toutes les classes de gestion de collections du framework ne sont pas synchronisées : elles ne prennent pas en charge les traitements multithreads. Le framework propose des méthodes pour obtenir des objets de gestion de collections qui prennent en charge cette fonctionnalité. Les classes Vector et Hashtable étaient synchronisées mais l'utilisation d'une collection ne se fait généralement pas dans ce contexte. Pour réduire les temps de traitement dans la plupart des cas, elles ne sont pas synchronisées par défaut.

Lors de l'utilisation de ces classes, il est préférable de stocker la référence de ces objets sous la forme d'une interface qu'ils implémentent plutôt que sous leur forme objet. Ceci rend le code plus facile à modifier si le type de l'objet qui gère la collection doit être changé.

14.2. Les interfaces des collections

Le framework de Java 2 définit 6 interfaces en relation directe avec les collections qui sont regroupées dans deux arborescences :

Le JDK ne fournit pas de classe qui implémente directement l'interface Collection.

Le tableau ci-dessous présente les différentes classes qui implémentent les interfaces de bases Set, List et Map :

Pour gérer toutes les situations de façon simple, certaines méthodes peuvent être définies dans une interface comme «optionnelles ». Pour celles-ci, les classes qui implémentent une telle interface, ne sont pas obligées d'implémenter du code qui réalise un traitement mais simplement lève une exception si cette fonctionnalité n'est pas supportée. Le nombre d'interfaces est ainsi grandement réduit.

Cette exception est du type UnsupportedOperationException. Pour éviter de protéger tous les appels de méthodes d'un objet gérant les collections dans un bloc try-catch, cette exception hérite de la classe RuntimeException.

Toutes les classes fournies par le J.D.K. qui implémentent une des interfaces héritant de Collection implémentent toutes les opérations optionnelles.

14.2.1. L'interface Collection

L'interface Collection, ajoutée à Java 1.2, définit des méthodes pour des objets qui gèrent des éléments d'une façon assez générale. Elle est la super interface de plusieurs interfaces du framework.

Plusieurs classes qui gèrent une collection implémentent une interface qui hérite de l'interface Collection. Cette interface est une des deux racines de l'arborescence des collections.

Cette interface représente un minimum commun pour les objets qui gèrent des collections : ajout d'éléments, suppression d'éléments, vérification de la présence d'un objet dans la collection, parcours de la collection et quelques opérations diverses sur la totalité de la collection.

Ce tronc commun permet entre autres de définir pour chaque objet gérant une collection, un constructeur pour cet objet demandant un objet de type Collection en paramètre. La collection est ainsi initialisée avec les éléments contenus dans la collection fournie en paramètre.

Il existe de nombreuses implémentations qui proposent différentes fonctionnalités : support des doublons ou non, tri des éléments ou non, support des null.

L'API Collections ne propose pas d'implémentation directe de cette interface : elle propose des implémentations pour des interfaces filles qui définissent les fonctionnalités des grandes familles de collections : List, Set, Map, Queue.

Elle hérite de l'interface Iterable depuis Java 5.

Chaque implémentation de l'interface Collection devrait fournir au moins deux constructeurs :

• un constructeur par défaut (sans argument)
• un constructeur qui attend en paramètre un objet de type collection qui va créer une collection contenant les éléments de la collection fournie en paramètre

L'interface Collection définit plusieurs méthodes :

Attention : il ne faut pas ajouter dans une collection une référence à la collection elle-même.

Certaines méthodes de cette interface peuvent lever une exception de type UnsupportedOperationException car leur implémentation est optionnelle : add(), addAll(), remove(), removeAll, retainAll() et clear(). Cette exception peut aussi être levée si l'opération n'a aucune influence sur l'état de la collection.

Chaque implémentation est libre de :

• gérer ou non les accès concurrents
• utiliser l'algorithme de son choix pour tester l'égalité d'un élément (equals(), hashCode()/equals(), ...)
• utiliser à son avantage les fonctionnalités proposées par les éléments (implémentation de Comparable, ...)

14.2.2. L'interface Iterator

Cette interface définit des méthodes pour des objets capables de parcourir les données d'une collection.

La définition de cette nouvelle interface par rapport à l'interface Enumeration a été justifiée par l'ajout de la fonctionnalité de suppression et la réduction des noms de méthodes.

La méthode hasNext() est équivalente à la méthode hasMoreElements() de l'interface Enumeration.

La méthode next() est équivalente à la méthode nextElement() de l'interface Enumeration.

La méthode next() lève une exception de type NoSuchElementException si elle est appelée alors que la fin du parcours des éléments est atteinte. Pour éviter la levée de cette exception, il suffit d'appeler la méthode hasNext() et selon le résultat de conditionner l'appel à la méthode next().

Iterator iterator = collection.iterator();
while (iterator.hasNext()) {
  System.out.println("objet = "+iterator.next());
}

La méthode remove() permet de supprimer l'élément renvoyé par le dernier appel à la méthode next(). Il est ainsi impossible d'appeler la méthode remove() sans un appel correspondant à next() : on ne peut pas appeler deux fois de suite la méthode remove().

      Iterator iterator = collection.iterator();
      if (iterator.hasNext()) {
            iterator.next();
            itérator.remove();
      }

Si aucun appel à la méthode next() ne correspond à celui de la méthode remove(), une exception de type IllegalStateException est levée

14.3. Les collections de type List : les listes

Une collection de type List est une collection simple et ordonnée d'éléments qui autorise les doublons. La liste étant ordonnée, un élément peut être accédé à partir de son index.

Plusieurs classes de l'API JMX implémentent l'interface List : javax.management.AttributeList, javax.management.relation.RoleList et javax.management.relation.RoleUnresolvedList.

14.3.1. L'interface List

Cette interface, ajoutée à Java 1.2, étend l'interface Collection.

Une collection de type List permet :

• de contenir des doublons
• d'interagir avec un élément de la collection en utilisant sa position
• d'insérer des éléments null

Pour les listes, une interface particulière est définie pour permettre le parcours dans les deux sens de la liste et réaliser des mises à jour : l'interface ListIterator

L'interface List définit plusieurs méthodes qui permettent un accès aux éléments de la liste à partir d'un index, de gérer les éléments, de rechercher la position d'un élément, d'obtenir une liste partielle (sublist) et d'obtenir des Iterator :

La collection de type List obtenue en invoquant la méthode subList() est liée à la collection qui a permis sa création. Une modification faite dans la sous liste est reportée dans la liste originelle. Par contre, si un élément est ajouté ou supprimé dans la liste originelle alors une exception de type ConcurrentModificationException est levée lors d'une utilisation de la sous liste

package fr.jmdoudoux.dej.collections;

import java.util.ArrayList;
import java.util.List;

public class TestSubList {
  public static void afficherListe(final String nom,
    final List<String> sousListe) {
    int i = 0;
    for (String element : sousListe) {
      System.out.format("%s  %2d : %s\n", nom, i, element);
      i++;
    }
  }

  public static void main(final String[] args) {
    List<String> liste = new ArrayList<String>();
    liste.add("1");
    liste.add("2");
    liste.add("3");
    liste.add("4");
    liste.add("5");
    
    List<String> sousListe = liste.subList(1, 4);
    afficherListe("sous liste", sousListe);
    System.out.println("");
   
    sousListe.remove(1);
    afficherListe("liste",liste);
    System.out.println("");
   
    afficherListe("sous liste", sousListe);
   
    System.out.println("");
    liste.remove(1);
    afficherListe("liste", liste);
    System.out.println("");
   
    afficherListe("sous liste", sousListe);
    System.out.println("");
  }
}

sous liste   0 : 2
sous liste   1 : 3
sous liste   2 : 4

liste   0 : 1
liste   1 : 2
liste   2 : 4
liste   3 : 5

sous liste   0 : 2
sous liste   1 : 4

liste   0 : 1
liste   1 : 4
liste   2 : 5

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.SubList.checkForComodification(Unknown Source)
    at java.util.SubList.listIterator(Unknown Source)
    at java.util.AbstractList.listIterator(Unknown Source)
    at java.util.SubList.iterator(Unknown Source)
    at fr.jmdoudoux.dej.collections.TestSubList.afficherListe(TestSubList.java:11)
    at fr.jmdoudoux.dej.collections.TestSubList.main(TestSubList.java:39)

Remarque : il est préférable d'utiliser un Iterator pour parcourir les éléments d'une collection de type List plutôt que de faire une boucle sur son nombre d'éléments et d'obtenir chaque élément en utilisant son indice.

Le framework propose des classes qui implémentent l'interface List : Vector, ArrayList, LinkedList et CopyOnWriteArrayList.

14.3.2. La classe Vector

La classe Vector, présente depuis Java 1.0, est un tableau dont la taille peut varier selon le nombre d'éléments qu'il contient.

Lors de la création d'une instance de type Vector, il est possible de lui préciser une capacité initiale et une taille d'incrémentation en utilisant la surcharge correspondante du constructeur.

Toutes les méthodes de la classe Vector sont synchronized : elle est donc moins performante que la classe ArrayList car elle est thread-safe.

La classe Vector est antérieure à l'API Collections : elle a été mise à jour ultérieurement pour implémenter l'interface Liste. Il y a de ce fait plusieurs méthodes redondantes comme par exemple les méthodes add() et addElement().

Avant l'API Collections la classe Vector était fréquemment utilisée : il est préférable d'utiliser une des implémentations de l'API Collections.

Les éléments sont stockés dans l'ordre dans lequel ils sont ajoutés dans la collection. Un élément peut être ajouté ou supprimé à n'importe qu'elle position dans la collection.

14.3.3. La classe ArrayList

Les tableaux font partis du langage Java et sont faciles à utiliser mais leur taille ne peut pas varier. La classe ArrayList, ajoutée à Java 1.2, est un tableau d'objets dont la taille est dynamique : elle utilise un tableau dont la taille s'adapte automatiquement au nombre d'éléments de la collection. Cette adaptation a cependant un coût car elle nécessite l'instanciation d'un nouveau tableau et la copie des éléments dans ce nouveau tableau.

Elle hérite de la classe AbstractList donc elle implémente l'interface List.

Le fonctionnement de cette classe est similaire à celui de la classe Vector. La différence avec la classe Vector est que cette dernière est multithread (toutes ses méthodes sont synchronisées). Pour une utilisation dans un thread unique, la synchronisation des méthodes est inutile et coûteuse. Il est alors préférable d'utiliser un objet de la classe ArrayList.

La classe ArrayList est l'implémentation la plus simple de l'interface List. Elle présente plusieurs caractéristiques :

• elle n'est pas thread-safe
• elle utilise un tableau pour stocker ses éléments : le premier élément de la collection possède l'index 0
• l'accès à un élément se fait grâce à son index
• elle implémente toutes les méthodes de l'interface List
• elle autorise l'ajout d'éléments null

La classe ArrayList dispose de plusieurs constructeurs :

Elle définit plusieurs méthodes dont les principales sont :

Chaque instance de type ArrayList possède une capacité qui correspond à la taille du tableau de stockage des éléments : c'est donc le nombre total d'éléments qu'il est possible d'insérer avant d'agrandir le tableau. Cette capacité a donc une relation avec le nombre d'éléments contenus dans la collection : elle est toujours au moins supérieure ou égale à la taille de la collection. La capacité de la collection est automatiquement ajustée selon les besoins lors de l'ajout d'un élément. Cette capacité et le nombre d'éléments de la collection déterminent si le tableau doit être agrandi.

Si un nombre important d'éléments doit être ajouté, il est possible de forcer l'agrandissement de cette capacité avec la méthode ensureCapacity() : elle permet de demander que le tableau puisse au moins accepter le nombre d'éléments fourni en paramètre. Cela peut améliorer les performances en changeant la taille une seule fois si de nombreux éléments doivent être ajoutés plutôt que de changer la taille plusieurs fois selon les besoins. Son usage évite une perte de temps liée au recalcul de la taille de la collection. Un constructeur permet de préciser la capacité initiale.

Lors de l'ajout d'un élément dans la collection, si le tableau de stockage est trop petit alors un nouveau, plus grand, est créé pour contenir les éléments courants plus le nouvel élément. Le temps d'ajout d'un élément n'est donc pas constant. Les temps d'exécution de l'insertion ou de suppression d'un élément à une position quelconque est aussi variable puisque cela peut nécessiter l'adaptation de la position d'autres éléments.

Lors de l'ajout ou du retrait d'un élément, la collection doit réindexer ses éléments. Si la taille de la collection est importante et qu'il y a de nombreux ajouts et suppressions d'éléments alors il est préférable d'utiliser une collection de type LinkedList.

Par défaut, les méthodes de la classe ArrayList ne sont pas synchronized : si plusieurs threads doivent modifier le contenu de la collection, il faut utiliser une instance retournée par la méthode synchronizedList() de la classe Collections.

   List liste = Collections.synchronizedList(new ArrayList());

Les Iterator et les ListIterator de la classe ArrayList sont de type fail-fast : ils peuvent lever une exception de type ConcurrentModificationException si une modification du nombre d'éléments intervient durant le parcours sans utiliser leurs méthodes add() ou remove().

L'API Collections propose deux solutions pour convertir un tableau en ArrayList :

• la méthode asList() de la classe Arrays
• la méthode addAll() de la classe Collections : cette méthode fait une copie des éléments. Les deux objets peuvent alors être modifiés de manière indépendante

La méthode Arrays.asList() est facile à utiliser mais les éléments du tableau et de la liste sont liés. Les modifications faites aux éléments du tableau sont propagées dans la liste. Toute tentative de modification de la liste lève une exception de type UnsupportedOperationException.

package fr.jmdoudoux.dej.collections;
      
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ArrayToArrayList {
  public static void main(final String[] args) {
    String[] tableau = { "A", "B", "C", "D" };
    List<String> liste = new ArrayList<String>();

    System.out.println("Contenu du tableau");
    for (String str : tableau) {
      System.out.print(" " + str);
    }

    liste = Arrays.asList(tableau);
    System.out.println("\nContenu de la liste");
    for (String str : liste) {
      System.out.print(" " + str);
    }
    System.out.println("\n");

    tableau[0] = "AA";

    System.out.println("\nContenu de la liste");
    for (String str : liste) {
      System.out.print(" " + str);
    }
    liste.add("E");

    System.out.println("\nContenu du tableau");
    for (String str : tableau) {
      System.out.print(" " + str);
    }
  }
}

Contenu du tableau
 A B C D
Contenu de la liste
 A B C D
Contenu de la liste
 AA B C D
 
Exception in thread "main" java.lang.UnsupportedOperationException
     at java.util.AbstractList.add(AbstractList.java:148)
     at java.util.AbstractList.add(AbstractList.java:108)
     at fr.jmdoudoux.dej.collections.ArrayToArrayList.main(ArrayToArrayList.java:35)

La méthode Collections.addAll() copie les éléments. Les deux objets peuvent alors être modifiés de manière indépendante.

package fr.jmdoudoux.dej.collections;
      
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ArrayToArrayList {
  public static void main(final String[] args) {
    String[] tableau = { "A", "B", "C", "D" };
    List<String> liste = new ArrayList<String>();

    Collections.addAll(liste, tableau);

    System.out.println("Contenu du tableau");
    for (String str : tableau) {
      System.out.print(" " + str);
    }

    System.out.println("\nContenu de la liste");
    for (String str : liste) {
      System.out.print(" " + str);
    }

    tableau[0] = "AA";
    liste.add("E");

    System.out.println("\nContenu du tableau");
    for (String str : tableau) {
      System.out.print(" " + str);
    }

    System.out.println("\nContenu de la liste");
    for (String str : liste) {
      System.out.print(" " + str);
    }
  }
}

Contenu du tableau
 A B C D
Contenu de la liste
 A B C D
Contenu du tableau
 AA B C D
Contenu de la liste
 A B C D E

14.3.4. Les listes chaînées : la classe LinkedList

La classe LinkedList, ajoutée à Java 1.2, est une implémentation d'une liste doublement chaînée dans laquelle les éléments de la collection sont reliés par des pointeurs. La suppression ou l'ajout d'un élément se fait simplement en modifiant des pointeurs.

Elle hérite de la classe AbstractSequentialList et implémente toutes les méthodes, même celles optionnelles, de l'interface List. Elle implémente l'interface Deque à partir de Java 6.

Elle présente plusieurs caractéristiques :

• elle n'a pas besoin d'être redimensionnée quelque soit le nombre d'éléments qu'elle contient
• elle permet l'ajout d'un élément null.

La classe LinkedList possède plusieurs constructeurs :

      LinkedList listeChainee = new LinkedList();
      listeChainee.add("element 1");
      listeChainee.add("element 2");
      listeChainee.add("element 3");
      Iterator iterator = listeChainee.iterator();
      while (iterator.hasNext()) {
            System.out.println("objet = "+iterator.next());
      }

La méthode toString() renvoie une chaîne qui contient tous les éléments de la liste.

Plusieurs méthodes pour ajouter, supprimer ou obtenir le premier ou le dernier élément de la liste permettent d'utiliser cette classe pour gérer une pile ou une file :

Une liste chaînée gère une collection de façon ordonnée : l'ajout d'un élément peut se faire au début ou à la fin de la collection. L'utilisation d'une LinkedList est plus avantageuse par rapport à une ArrayList lorsque des éléments doivent être ajoutés ou supprimés de la collection en dehors de son début ou de sa fin. Dans ce cas, le temps d'exécution des opérations se fait toujours de manière constant puisqu'elles consistent simplement en la manipulation de pointeurs.

De par les caractéristiques d'une liste chaînée, il n'existe pas de moyen d'obtenir un élément de la liste directement. Pourtant, la méthode contains() permet de savoir si un élément est contenu dans la liste et la méthode get() permet d'obtenir l'élément à la position fournie en paramètre. Il ne faut toutefois pas oublier que ces méthodes parcourent la liste jusqu'à obtention du résultat, ce qui peut être particulièrement gourmand en terme de temps de réponse surtout si la méthode get() est appelée dans une boucle. Pour cette raison, il ne faut surtout pas utiliser la méthode get() pour parcourir la liste.

Les méthodes de la classe LinkedList ne sont pas synchronized. Si plusieurs threads doivent accéder à la collection avec au moins un d'entre-eux qui modifie la structure de la liste (ajout ou suppression d'un élément) alors il faut créer une instance de type List en invoquant la méthode synchronizedList() de la classe Collections en lui passant l'instance de type List.

List liste = Collections.synchronizedList(new LinkedList());

Les Iterator obtenus en invoquant les méthodes iterator() ou listIterator() sont de type fail-fast : une exception de type ConcurrentModificationException est généralement levée lors du parcours des Iterator si la structure de la collection est modifiée.

L'ajout d'un élément après n'importe quel élément est lié à la position courante lors d'un parcours : pour répondre à ce besoin, l'interface qui permet le parcours de la collection est une sous-classe de l'interface Iterator : l'interface ListIterator.

Comme les Iterator sont utilisés pour faire des mises à jour dans la liste, une exception de type ConcurrentModificationException est levée si un iterator parcourt la liste alors qu'une mise à mises à jour est faite (ajout ou suppression d'un élément dans la liste). Pour gérer facilement cette situation, il est préférable si l'on sait qu'il y a des mises à jour à faire de n'avoir qu'un seul iterator qui soit utilisé.

      LinkedList listeChainee = new LinkedList();
      Iterator iterator = listeChainee.iterator();
      listeChainee.add("element 1");
      listeChainee.add("element 2");
      listeChainee.add("element 3");
      while (iterator.hasNext()) {
            System.out.println("objet = "+iterator.next());
      }

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
	at java.util.LinkedList$ListItr.next(LinkedList.java:696)
	at snippet.Snippet.main(Snippet.java:14)

Il existe plusieurs différences entre une ArrayList et une LinkedList :

• une ArrayList stocke ses éléments en interne dans un tableau à taille fixe alors qu'une LinkedList stocke ses éléments dans une liste doublement chaînée
• une ArrayList permet un accès direct à un élément alors qu'une LinkedList doit parcourir ses éléments pour obtenir celui désiré, ce qui est particulièrement contre performant
• le coût de variation de la capacité d'une collection de type ArrayList est important car il implique une copie du tableau de stockage interne de ses éléments
• l'ajout d'un élément en début ou en fin d'une collection de type LinkedList est particulièrement performant et son temps d'exécution est constant dans le temps (LinkedList implémente aussi l'interface Deque)

14.3.5. L'interface ListIterator

L'interface ListIterator définit des fonctionnalités d'un Iterator permettant aussi le parcours en sens inverse de la collection, l'ajout d'un élément ou la modification du courant.

En plus des méthodes définies dans l'interface Iterator dont elle hérite, l'interface ListIterator définit plusieurs méthodes :

La méthode add() de cette interface ne retourne pas un booléen indiquant que l'ajout a réussi.

Pour ajouter un élément en début de liste, il suffit d'appeler la méthode add() sans avoir appelé une seule fois la méthode next(). Pour ajouter un élément en fin de la liste, il suffit d'appeler la méthode next() autant de fois que nécessaire pour atteindre la fin de la liste et d'appeler la méthode add(). Plusieurs appels à la méthode add() successifs, ajoutent les éléments à la position courante dans l'ordre d'appel de la méthode add().

14.3.6. La classe CopyOnWriteArrayList

L'utilisation d'un wrapper synchronized d'une ArrayList n'est pas toujours indiquée lorsqu'il y a beaucoup de lectures car celles-ci sont aussi synchronized dans ce cas, ce qui peut introduire de la contention si plusieurs threads effectuent des lectures concurrentes.

La classe CopyOnWriteArrayList, ajoutée à Java 1.5, est une variante thread-safe de la classe ArrayList dans laquelle toutes les opérations de modification du contenu de la liste recréent une nouvelle copie du tableau utilisé pour stocker les éléments de la collection.

En interne, les opérations de modification du contenu de la collection s'effectuent sur une nouvelle copie du tableau des éléments, ce qui permet à d'autres threads de lire le contenu de la collection sans surcoût de synchronisation.

Elle implémente les interfaces List et RandomAccess.

Elle présente plusieurs caractéristiques :

• Son mode de fonctionnement est généralement coûteux car il crée de nombreux objets lors de la mise à jour du contenu de la collection
• Il est possible d'ajouter des éléments null

Elle possède trois constructeurs :

La méthode addIfAbsent() permet d'ajouter de manière atomique un élément qui n'appartient pas à la collection.

La méthode addAllAbsent(Collection< ? extends E>) permet d'ajouter de manière atomique les éléments de la collection en paramètre qui n'appartiennent pas déjà à la collection.

package fr.jmdoudoux.dej.collections;

import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.concurrent.CopyOnWriteArrayList;

public class TestCopyOnWriteArrayList {
  static Thread modifThread;
  static Thread parcoursThread;
  private static void lancerModifThread(final CopyOnWriteArrayList<String> list) {
    modifThread = new Thread(new Runnable() {
      long compteur = 0;
      @Override
      public void run() {
        while (!Thread.interrupted()) {
          int taille = list.size();
          Random random = new Random();
          if (random.nextBoolean()) {
            if (taille > 1) {
              list.remove(random.nextInt(taille - 1));
            }
          } else {
            if (taille < 10) {
              list.addIfAbsent("Element " + compteur);
            }
          }
          compteur++;
        }
        System.out.println("Arret du thread modif");
      }
    });
    modifThread.start();
  }

  private static void lancerParcoursThread(final List<String> list) {
    parcoursThread = new Thread(new Runnable() {
      @Override
      public void run() {
        while (!Thread.interrupted()) {
          Iterator<String> iter = list.iterator();
          while (iter.hasNext()) {
            String element = iter.next();
            System.out.println(element);
          }
          System.out.println("");
        }
        System.out.println("Arret du thread parcours");
      }
    });
    parcoursThread.start();
  }

  public static void main(final String[] args) {
    CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();

    lancerParcoursThread(list);
    lancerModifThread(list);

    try {
      Thread.sleep(10000);
    } catch (InterruptedException ie) {
      ie.printStackTrace();
    }

    modifThread.interrupt();
    parcoursThread.interrupt();
  }
}

Les Iterator créés par cette collection parcourent une copie du tableau au moment de la création de leurs instances. Le contenu de ce tableau ne peut pas être modifié : les méthodes de l'Iterator qui permettent de modifier le contenu de la collection comme la méthode remove() lèvent une exception de type UnsupportedOperationException. Un Iterator ne peut donc pas lever d'exception de type ConcurrentModificationException.

L'utilisation de la classe CopyOnWriteArrayList, s'il y a de nombreuses mises à jour de ses éléments, implique un surcoût de mémoire et de temps d'exécution. Son usage est limité ; un bon exemple d'utilisation de la classe CopyOnWriteArrayList est pour stocker les listeners d'un JavaBean pour lequel il y a beaucoup de lectures et peu d'écritures normalement.

14.3.7. Le choix d'une implémentation de type List

S'il n'y a aucun accès concurrent sur la collection, le choix doit se faire entre les classes ArrayList et LinkedList. Ce choix dépendant de l'utilisation qui sera faite de la collection :

• Si l'ajout ou la suppression d'éléments se font essentiellement à la fin de la collection, alors il faut utiliser la classe ArrayList
• Si les ajouts ou la suppression d'éléments se font à une position aléatoire dans la collection, alors il faut utiliser la classe LinkedList

Un élément peut être accédé directement par son index dans une ArrayList, ce qui n'est pas possible avec une LinkedList sauf pour le premier et le dernier élément.

Si les accès concurrents doivent être gérés alors il y a deux cas de figure :

• Si la collection est peu fréquemment mise à jour alors il faut utiliser la classe copyOnWriteArrayList qui permet des lectures non bloquantes mais les mises à jour impliquent une duplication de la collection
• Sinon il faut utiliser l'instance retournée par la méthode synchronizedList() de la classe Collections en lui passant en paramètre une instance de type ArrayList ou LinkedList. Les accès à la collection sont alors thread safe mais pas concurrents.

Le tableau ci-dessous compare les performances de certaines fonctionnalités de base de différentes implémentations de type List.

14.4. Les collections de type Set : les ensembles

Une collection de type Set ne permet pas l'ajout de doublons ni l'accès direct à un élément de la collection. Les fonctionnalités de base de ce type de collection sont définies dans l'interface java.util.Set.

L'interface Set possède deux interfaces filles : SortedSet et NavigableSet.

L'API Collections propose plusieurs implémentations de l'interface Set:

14.4.1. L'interface Set

L'interface Set définit les fonctionnalités d'une collection qui ne peut pas contenir de doublons dans ses éléments.

Les éléments ajoutés dans une collection de type Set doivent réimplémenter leurs méthodes equals() et hashCode(). Ces méthodes sont utilisées lors de l'ajout d'un élément pour déterminer s'il est déjà présent dans la collection. La valeur retournée par hashCode() est recherchée dans la collection :

• si aucun objet de la collection n'a la même valeur de hachage alors l'objet n'est pas encore dans la collection et peut être ajouté
• si un ou plusieurs objets de la collection ont la même valeur de hachage alors la méthode equals() de l'objet à ajouter est invoquée sur chacun des objets pour déterminer si l'objet est déjà présent ou non dans la collection

Le comportement d'une collection de type Set n'est pas spécifié si des objets mutables lui sont ajoutés notamment si des modifications changent le résultat des méthodes equals() et hashCode().

Une collection de type Set peut contenir un objet null mais cela dépend des implémentations. Certaines d'entre-elles ne permettent pas l'ajout de null.

L'interface définit plusieurs méthodes :

Il est possible d'utiliser un Iterator pour parcourir les éléments de la collection.

L'invocation de la méthode add() avec en paramètre un élément déjà présent dans la collection n'aucun effet.

L'interface Set possède deux interfaces filles : SortedSet et NavigableSet.

L'API Collections propose plusieurs implémentations de l'interface Set : ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, LinkedHashSet et TreeSet.

Il faut choisir judicieusement l'implémentation à utiliser selon ses besoins de performance des méthodes add(), contains(), de l'itération sur la collection et l'ordre dans lequel les éléments sont retournés.

14.4.2. L'interface SortedSet

L'interface SortedSet, ajoutée à Java 1.2, définit les fonctionnalités pour une collection de type Set qui garantit l'ordre ascendant du parcours de ses éléments.

L'interface SortedSet hérite de l'interface Set et propose plusieurs méthodes :

L'ordre des éléments peut être défini de deux manières :

• l'ordre naturel des éléments qui doivent alors implémenter l'interface Comparable
• une instance de type Comparator qui sera invoquée pour définir l'ordre de tri

L'interface SortedSet ne précise pas comment la collection va utiliser l'une ou l'autre de ces options. Généralement, les implémentations définissent un constructeur particulier qui attend en paramètre une instance de type Comparator. Si une telle instance n'est pas fournie alors c'est l'ordre naturel des objets contenus dans la collection qui est utilisé.

Un collection de type Set utilise la méthode equals() pour vérifier si un élément est déjà présent ou non dans la collection. Une collection de type SortedSet utilise la méthode compareTo() lors de l'utilisation de l'ordre naturel de ses éléments. Il est donc important que l'implémentation des méthodes equals() et compareTo() soient cohérentes.

Java 6 propose deux implémentations de l'interface SortedSet : java.util.TreeSet et java.util.concurrent.ConcurrentSkipListSet.

14.4.3. L'interface NavigableSet

L'interface NavigableSet qui hérite de l'interface SortedSet définit des fonctionnalités qui permettent le parcours de la collection dans l'ordre ascendant ou descendant et d'obtenir des éléments proches d'un autre élément.

Il est recommandé aux implémentations de cette interface de ne pas permettre d'accepter la valeur null dans la collection pour éviter l'ambiguité lorsque certaines méthodes renvoient null.

L'API Collections propose deux implémentations de cette interface : TreeSet et ConcurrenSkipListSet.

package fr.jmdoudoux.dej.collections;
      
import java.util.Iterator;
import java.util.NavigableSet;
import java.util.Set;
import java.util.TreeSet;

public class TestNavigableSet {

  public static void afficherSet(final Set<String> set) {
    Iterator<String> iterator = set.iterator();
    while (iterator.hasNext()) {
      String element = iterator.next();
      System.out.print(element);
      if (iterator.hasNext()) {
        System.out.print(", ");
      } else {
        System.out.println("");
      }
    }
  }

  public static void main(final String[] args) {
    NavigableSet<String> set = new TreeSet<String>();
    for (int i = 1; i < 10; i++) {
      set.add("" + i);
    }
    
    System.out.println(set);
    System.out.println("ceiling(5)=" + set.ceiling("5"));
    System.out.println("floor(5)" + set.floor("5"));
    System.out.println("higher(5)=" + set.higher("5"));
    System.out.println("lower(5)=" + set.lower("5"));
    System.out.print("Ordre descendant=");
    afficherSet(set.descendingSet());
   
    System.out.print("headSet(5)=");
    afficherSet(set.headSet("5"));

    System.out.print("headSet(5,true)=");
    afficherSet(set.headSet("5", true));

    System.out.print("subSet(3,5)=");
    afficherSet(set.subSet("3", "5"));

    System.out.print("subSet(3,true,5,true)=");
    afficherSet(set.subSet("3", true, "5", true));

    System.out.print("tailSet(5)=");
    afficherSet(set.tailSet("5"));

    System.out.print("tailSet(5,true)=");
    afficherSet(set.tailSet("5", true));

    System.out.println("pollFirst()=" + set.pollFirst());
    System.out.println("pollLast()=" + set.pollLast());
    System.out.println(set);
  }
}

[1, 2, 3, 4, 5, 6, 7, 8, 9]
ceiling(5)=5
floor(5)5
higher(5)=6
lower(5)=4
Ordre descendant=9, 8, 7, 6, 5, 4, 3, 2, 1
headSet(5)=1, 2, 3, 4
headSet(5,true)=1, 2, 3, 4, 5
subSet(3,5)=3, 4
subSet(3,true,5,true)=3, 4, 5
tailSet(5)=5, 6, 7, 8, 9
tailSet(5,true)=5, 6, 7, 8, 9
pollFirst()=1
pollLast()=9
[2, 3, 4, 5, 6, 7, 8]

14.4.4. La classe HashSet

La classe HashSet, ajoutée à Java 1.2, est une implémentation simple de l'interface Set qui utilise une HashMap. La clé de la HashMap est la valeur de hachage de l'élément.

La classe HashSet présente plusieurs caractéristiques :

• elle ne propose aucune garantie sur l'ordre de parcours lors de l'itération sur les éléments qu'elle contient
• elle ne permet pas d'ajouter des doublons mais elle permet l'ajout d'un élément null

La classe HashSet utilise en interne une HashMap dont la clé est l'élément et dont la valeur est une instance d'Object identique pour tous les éléments.

La classe HashSet possède plusieurs constructeurs :

Il est possible de préciser, dans la surcharge de certains constructeurs, la capacité initiale de la collection et le facteur de charge (par défaut, la taille est 16 et le facteur de charge est 0,75). Le facteur de charge est une valeur qui précise le pourcentage de remplissage de la collection à atteindre avant d'augmenter sa taille.

Les classes des éléments qui sont insérés dans la collection doivent impérativement définir les méthodes equals() et hashCode() pour respecter la cohérence entre ces deux méthodes qui est imposée par contrat par Java.

La méthode add() permet d'ajouter un élément dans la collection : elle renvoie un booléen qui précise si l'opération a réussi ou non. Elle échoue par exemple si l'élément est déjà présent dans la collection.

import java.util.*;
public class TestHashSet {
  public static void main(String args[]) {
    Set set = new HashSet();
    set.add("CCCCC");
    set.add("BBBBB");
    set.add("DDDDD");
    set.add("BBBBB");
    set.add("AAAAA");

    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
      System.out.println(iterator.next());
    }
  }
}

AAAAA
DDDDD
BBBBB
CCCCC

14.4.5. La classe TreeSet

La classe TreeSet, ajoutée à Java 1.2, stocke ses éléments de manière ordonnée en les comparant entre-eux. Cette classe permet d'insérer des éléments dans n'importe quel ordre et de restituer ces éléments dans un ordre précis lors de son parcours.

Elle implémente l'interface NavigableSet depuis Java 6

L'ordre des éléments de la collection peut être défini par deux moyens :

• l'ordre naturel des éléments s'ils implémentent l'interface Comparable
• l'ordre obtenu par l'utilisation d'une instance de type Comparator fournie en paramètre du constructeur de la collection

Le mécanisme utilisé pour la comparaison lors de la définition de l'ordre (Comparable ou Comparator) doit être cohérent avec l'implémentation de la méthode equals() : si element1.compareTo(element2) == 0 alors obligatoirement element1.equals(element2) == true.

Cela implique que l'algorithme de comparaison des éléments soit suffisamment discriminant pour éviter les égalités qui seraient alors interprétés comme des doublons qui n'en sont pas en réalité.

Par exemple : pour des personnes, il n'est pas possible de comparer uniquement le nom et le prénom car dans ce cas, il ne pourrait pas y avoir d'homonymes dans la collection. Il faut en plus comparer un élément discriminant ou faire la comparaison sur une valeur unique comme un numéro de sécurité sociale ou un identifiant.

En interne, la classe TreeSet utilise un arbre binaire pour stocker ses éléments. Chaque élément est encapsulé dans un noeud (node). Chaque noeud peut faire référence à aucun, un ou deux autres noeuds.

Si un noeud fait référence à un ou deux autres noeuds alors il est le noeud parent de ses noeuds fils : ceci permet de construire l'arborescence des éléments de l'arbre. Si un noeud n'a pas de fils alors c'est une feuille de l'arbre.

L'ajout d'un noeud fils suit toujours les mêmes règles :

• un des deux noeuds contient toujours un élément dont la valeur est plus petite
• l'autre noeud contient toujours un élément dont la valeur est supérieure
• c'est toujours le même noeud qui doit contenir la valeur la plus petite et l'autre la valeur la plus grande

Un seul noeud dans l'arbre ne possède pas de parent : le noeud racine.

La recherche d'un élément dans un arbre binaire est rapide : elle nécessite généralement un temps proportionnel à log(n) où n est le nombre d'éléments dans la collection.

Le parcours commence par le noeud racine qui est comparé à l'élément recherché.

S'il est égal, l'élément est trouvé sinon la branche de l'arbre selon que la valeur est plus petite ou plus grande est parcourue.

A chaque noeud la valeur est testée par rapport à l'élément recherché

Si le dernier parcouru ne correspond pas à la valeur recherchée, alors l'élément n'est pas dans la collection.

Ce mode de fonctionnement est efficace si l'ordre d'insertion des éléments est aléatoire : si tous les éléments sont ajoutés dans leur ordre alors le parcours reviendra à parcourir tous les éléments un par un jusqu'à trouver la bonne valeur ou une valeur supérieure auquel cas la valeur n'est pas trouvée.

Pour pallier à cette problématique, la classe TreeSet met en oeuvre un algorithme complexe qui va permettre d'équilibrer l'arbre. Un arbre est équilibré lorsque les feuilles de l'arbre sont à peu près à la même distance de la racine de l'arbre. La distance est le nombre de noeuds parent entre la feuille et le noeud racine.

La mise en oeuvre de ce type d'algorithme peut imposer de réorganiser la structure de l'arbre à chaque ajout ou suppression d'un élément. Le maintient d'un arbre parfaitement équilibré peut être très coûteux. Certains algorithmes maintiennent un arbre partiellement équilibré jusqu'à une certaine limite clairement définie par l'algorithme.

Il est intéressant que l'arbre soit parfaitement équilibré si les recherches sont beaucoup plus nombreuses que les opérations d'ajouts ou de suppressions d'éléments. La classe TreeSet ayant pour vocation un usage généraliste, elle met en oeuvre un algorithme nommé Red-Black Tree qui équilibre partiellement l'arbre en garantissant que la distance entre la racine et la feuille la plus éloignée n'est pas plus importante que deux fois la distance entre la racine et la feuille la plus proche. Cet algorithme met en oeuvre plusieurs règles pour réorganiser les éléments de l'arbre pour le maintenir équilibré :

• chaque noeud est noir ou rouge
• le noeud racine est généralement noir
• si un noeud est rouge alors ses noeuds enfants sont noirs
• pour chaque noeud de l'arbre, les chemins vers les noeuds de type feuille doivent contenir le même nombre de noeuds noirs

La classe TreeSet stocke en interne ses éléments dans une collection de type TreeMap.

La classe TreeSet possède plusieurs constructeurs :

package fr.jmdoudoux.dej.collections;

import java.util.Iterator;
import java.util.TreeSet;

public class TestTreeSet {
  public static void main(final String[] args) {
    TreeSet<String> set = new TreeSet<String>();
    set.add("CCCCC");
    set.add("BBBBB");
    set.add("DDDDD");
    set.add("BBBBB");
    set.add("AAAAA");
    
    Iterator<String> iterator = set.iterator();
    while (iterator.hasNext()) {
      System.out.print(iterator.next() + " ");
    }
  }
}

AAAAA BBBBB CCCCC DDDDD 

La classe TreeSet n'est pas thread-safe : comme aucune de ses méthodes n'est synchronized, un seul thread doit pouvoir modifier le contenu de la collection. Si plusieurs threads doivent pouvoir modifier la collection, il faut invoquer la méthode synchronizedSortedSet() de la classe Collections qui va créer un wrapper dont les méthodes sont synchronized.

SortedSet set = Collections.synchronizedSortedSet(new TreeSet());

Avec cette solution, plusieurs threads peuvent modifier la collection mais un seul à la fois, ce qui peut engendrer des dégradations de performances en cas de forte concurrence d'accès. Dans ce cas, il est préférable d'utiliser une autre implémentation de type Set comme la classe ConcurrentSkipListSet.

14.4.6. La classe ConcurrentSkipListSet

La classe ConcurrentSkipListSet, ajoutée à Java 1.6, permet de mettre en oeuvre un ensemble ordonné d'éléments capable de gérer une forte concurrence d'accès.

Elle implémente l'interface NavigableSet et utilise en interne une instance de type ConcurrentSkipListMap.

Elle présente plusieurs caractéristiques :

• les éléments sont ordonnés dans leur ordre naturel s'ils implémentent l'interface Comparable ou selon un ordre défini par l'instance de type Comparator fournie au constructeur de l'instance de la collection.
• le parcours ascendant des éléments est plus rapide que le parcours descendant.
• elle ne permet pas de contenir un objet null.
• les opérations de la classe ConcurrentSkipListSet sont de types CAS (Compare And Swap) : elles ne posent aucun verrou qui pourrait introduire de la contention.
• elle implémente toutes les méthodes optionnelles de l'interface Set

La classe ConcurrentSkipListSet utilise une structure de données de type skip list. Contrairement à un arbre binaire, dans une structure de type skip list, l'organisation n'a pas besoin d'être réajustée lors de l'ajout ou la suppression d'un élément.

La classe ConcurrentSkipListSet possède plusieurs constructeurs :

package fr.jmdoudoux.dej.collections;
      
import java.util.Iterator;
import java.util.concurrent.ConcurrentSkipListSet;

public class TestConcurrentSkipListSet {
  public static void main(final String[] args) {
    final ConcurrentSkipListSet<MaTache> set = new ConcurrentSkipListSet<MaTache>();
    System.out.println("debut");
    final Thread modificateur = new Thread(new Runnable() {
      @Override
      public void run() {
        MaTache[] MesTaches = new MaTache[5];
        for (int i = 1; i <= 5; i++) {
          MesTaches[i - 1] = new MaTache(6 - i, "Tache " + i);
        }
        for (int j = 1; j <= 100; j++) {
          if (j % 2 == 0) {
            for (int i = 1; i <= 5; i++) {
              MaTache element = MesTaches[i - 1];
              System.out.println("insertion element " + element);
              set.add(element);
            }
            System.out.println("taille de la queue=" + set.size());
          } else {
            for (int i = 1; i <= 5; i++) {
              MaTache element = MesTaches[i - 1];
              System.out.println("retirer element " + element);
              set.remove(element);
            }
          }
        }
      }
    }, "Modificateur");
    
    modificateur.start();
    
    Thread iterateur = new Thread(new Runnable() {
      @Override
      public void run() {
        int i = 0;
        while (modificateur.isAlive()) {
          Iterator<MaTache> iterator = set.iterator();
          StringBuilder contenu = new StringBuilder("[");
          while (iterator.hasNext()) {
            contenu.append(iterator.next().getDescription());
            if (iterator.hasNext()) {
              contenu.append(", ");
            }
          }
          
          contenu.append("]");
          System.out.println("Contenu=" + contenu);
          i++;
        }
      }
    }, "iterateur");
   
    iterateur.start();
    try {
      modificateur.join();
      iterateur.join();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    
    System.out.println("fin");
  }
}

La classe ConcurrentSkipListSet est particulièrement utile pour gérer un ensemble ordonné d'éléments qui peut être accédé et modifié par plusieurs threads. L'ajout, la suppression et l'obtention d'un élément de la collection se font de manière concurrente par plusieurs threads.

Les méthodes qui effectuent des opérations sur plusieurs éléments comme addAll(), removeAll() et containsAll() n'offrent aucune garantie de s'exécuter de manière atomique.

Les performances des opérations de base de la classe ConcurrentSkipListSet sont moins bonnes que celles de la classe TreeSet pour une utilisation mono-thread : dans ce cas, il est préférable d'utiliser une instance de type TreeSet.

Le temps d'exécution de la méthode size() n'est pas constant : il est proportionnel au nombre d'éléments de la collection car celle-ci doit reparcourir tous les éléments pour calculer le nombre d'éléments qu'elle contient. Elle ne pose aucun verrou pour maintenir fraîche la valeur du nombre d'éléments dans la collection.

Les Iterator ne lèvent jamais d'exception de type ConcurrentModificationException : il est possible de les utiliser alors que d'autres threads modifient la collection car l'itération se fait sur l'état de la collection au moment de la création de l'instance de l'Iterator.

Les itérations sur les éléments dans l'ordre ascendant sont plus rapides que les itérations dans l'ordre descendant.

14.4.7. La classe CopyOnWriteArraySet

La classe CopyOnWriteArraySet, ajoutée à Java 1.5, est une implémentation de type Set qui est thread safe et offre de bonnes performances en lecture.

Elle implémente les interfaces Collection, Set et Iterable.

Elle utilise en interne une instance de type CopyOnWriteArrayList pour stocker les éléments de la collection. Elle présente plusieurs caractéristiques :

• elle est thread safe
• les opérations de mises à jour de la collection sont coûteuses en ressources car elles impliquent une copie intégrale des éléments du tableau : la collection doit donc de préférence être de petite taille et ne pas être trop fréquemment modifiée
• le parcours grâce à un Iterator ne peut être influencé par une opération d'un autre thread : l'itération se fait sur une copie dédiée des éléments du tableau
• les Iterator ne proposent pas de support pour la méthode remove()

La classe CopyOnWriteArraySet possède plusieurs constructeurs :

14.4.8. Le choix d'une implémentation de type Set

Certaines implémentations sont spécialisées pour être utilisées dans des situations particulières.

C'est notamment le cas de la classe EnumSet qui ne doit être utilisée que pour gérer un ensemble d'énumérations.

La classe CopyOnWriteArraySet ne doit être utilisée que pour des collections thread-safe de petites tailles, où les opérations réalisées sont essentiellement des lectures et où les Iterator ne peuvent pas modifier le contenu de la collection.

Le JDK contient plusieurs implémentations généralistes de l'interface Set qui peuvent selon les besoins :

• maintenir un ordre des clés
• gérer des accès concurrents

Si la collection n'est pas utilisée par plusieurs threads, il est possible d'utiliser les classes HashSet, LinkedHashSet et TreeSet. Si les données doivent être triées, il faut utiliser la classe TreeSet. Si les données de la collection doivent être fréquemment parcourues, il est préférable d'utiliser la classe LinkedHashSet.

Si la collection doit être utilisée par plusieurs threads, il faut utiliser la classe ConcurrentSkipListSet ou CopyOnWriteArraySet uniquement si les accès sont essentiellement des lectures. Il est aussi possible d'utiliser une version synchronized d'une implémentation de type Set en utilisant la méthode synchronizedSet() de la classe Collections.

Si les éléments de la collection doivent être triés, il faut utiliser les classes TreeSet ou ConcurrentSkipListSet. Si en plus les accès concurrents doivent être gérés, seule la classe ConcurrentSkipListSet doit être utilisée. Sinon il est préférable d'utiliser la classe TreeSet pour des collections de grandes tailles ou si de nombreuses opérations de suppressions d'éléments doivent être réalisées.

Indépendamment des fonctionnalités, les performances peuvent être un critère important dans le choix d'une implémentation de type Set.

Remarque : dans le tableau ci-dessus, h est la capacité de la collection

14.5. Les collections de type Map : les associations de type clé/valeur

Les collections de type Map sont définies et implémentées comme des dictionnaires sous la forme d'associations de paires de type clés/valeurs. La clé doit être unique. En revanche, la même valeur peut être associée à plusieurs clés différentes.

Avant l'apparition du framework Collections, la classe dédiée à cette gestion était la classe Hashtable.

Un objet de type Map permet de lier un objet avec une clé qui peut être un type primitif ou un autre objet. Il est ainsi possible d'obtenir un objet à partir de sa clé.

Au fur et à mesure des versions de Java, des classes et interfaces de type Map ont été ajoutées :

L'interface Map possède plusieurs interfaces filles : SortedMap, NavigableMap, ConcurrentMap et ConcurrentNavigableMap.

L'API Collections propose plusieurs implémentations de l'interface Map :

14.5.1. L'interface Map

L'interface java.util.Map<K,V> , ajoutée à Java 1.2, définit les fonctionnalités pour une collection qui associe des clés à des valeurs. Chaque clé ne peut être associée qu'à une seule valeur. Chaque clé d'une Map doit être unique.

L'interface Map de l'API Collections remplace la classe abstraite Dictionary de Java 1.0.

Elle définit plusieurs méthodes pour agir sur la collection :

La méthode keySet() permet d'obtenir un ensemble contenant toutes les clés.

La méthode values() permet d'obtenir une collection contenant toutes les valeurs. La valeur de retour est une Collection et non un ensemble car il peut y avoir des doublons (plusieurs clés peuvent être associées à la même valeur).

Il est recommandé d'utiliser des objets immuables comme clés.

Une collection de type Map ne propose pas directement d'Iterator sur ses éléments : la collection peut être parcourue de trois manières :

• parcours de l'ensemble des clés
• parcours des valeurs
• parcours d'un ensemble de paires clé/valeur

L'API Collections propose plusieurs implémentations de l'interface Map notamment HashMap, Hashtable, TreeMap, LinkedHashMap, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap et WeakHashMap.

14.5.2. L'interface SortedMap

L'interface java.util.SortedMap<K,V>, ajoutée à Java 1.2, définit les fonctionnalités d'une Map dont les clés sont triées. Elle hérite de l'interface Map.

L'ordre dans les clés est assuré en utilisant l'ordre naturel des éléments (en implémentant l'interface Comparable) ou en fournissant un Comparator à la création de l'instance de la collection. Tous les éléments insérés dans la collection doivent donc implémenter l'interface Comparable ou pouvoir être utilisés par le Comparator associé à la Map selon la solution utilisée. Ils doivent aussi avoir une implémentation de la méthode equals() qui soit en accord avec cette solution car elle est invoquée pour déterminer si la clé est déjà dans la collection.

L'ordre des éléments est respecté lors de l'invocation des méthodes entrySet(), keySet() et values().

Les implémentations de l'interface SortedMap doivent garantir que les Iterator parcourent la collection dans l'ordre des clés.

L'interface SortedMap définit plusieurs méthodes :

Chaque implémentation de l'interface SortedMap devrait fournir au moins quatre constructeurs (ceci ne peut être qu'une recommandation puisque les constructeurs ne peuvent pas être définis dans une interface) :

• un constructeur par défaut (sans argument) qui créé une Map vide qui utilisera l'ordre naturel des objets
• un constructeur qui attend un objet de type Comparator qui créé une Map vide qui utilisera l'ordre obtenu grâce au paramètre
• un constructeur qui attend en paramètre un objet de type Map qui créé une Map contenant les éléments fournis en paramètres, triés selon leur ordre naturel
• un constructeur qui attend en paramètre un objet de type SortedMap qui créé une Map contenant les éléments fournis en paramètres, triés dans le même ordre

Elle possède deux interfaces filles depuis Java 6 : NavigableMap et ConcurrentNavigableMap.

L'API Collections propose deux implémentations de l'interface SortedMap : TreeMap et ConcurrentSkipListMap.

14.5.3. La classe Hashtable

La classe Hashtable, présente depuis Java 1.0, permet d'associer dans une collection des éléments sous la forme de paires clé/valeur.

La classe Hashtable hérite de la classe Dictionary qui n'appartient pas à l'API Collections et a été modifiée, à partir de Java 1.2, pour implémenter l'interface Map et ainsi devenir une classe de l'API Collections.

La classe Hashtable présente plusieurs caractéristiques :

• contrairement aux autres classes de l'API Collections, elle est thread-safe car toutes les méthodes sont synchronized.
• il n'est pas possible d'utiliser la valeur null comme clé ou valeur

Tous les objets qui sont utilisés comme clés doivent obligatoirement redéfinir les méthodes equals() et hashCode() en respectant le contrat portant sur l'implémentation de ces deux méthodes.

La classe Hashtable est composée de buckets : en fonction de la valeur de hachage de la clé, l'élément est inséré dans un bucket particulier. Plusieurs objets ayant la même valeur de hachage seront dans le même bucket.

La classe Hashtable possède deux propriétés qui affectent ses performances :

• la capacité initiale (initial capacity) : le nombre d'éléments que peut contenir la collection à sa création
• le facteur de charge (load factor) : ce facteur précise le pourcentage de remplissage de la collection avant son agrandissement pour être capable de contenir plus d'éléments. La valeur par défaut est 0.75.

Il est important de ne pas utiliser une capacité initiale trop importante ou un facteur de charge trop petit pour ne pas dégrader les performances lors du parcours de la collection.

Lorsque le nombre d'éléments de la collection est supérieur à la taille de la collection multiplié par le facteur de charge alors la collection est agrandie. Cette opération est coûteuse car elle impose un rehash de la collection (reconstruction de sa structure de données liée à un accroissement du nombre de buckets). L'invocation de la méthode rehash() est spécifique à l'implémentation.

La capacité estimée et le facteur de charge de la collection doivent être pris en compte pour définir la capacité initiale afin d'éviter au maximum le nombre d'opérations de type rehash effectué lors de l'agrandissement de la taille de la collection.

Si la collection doit contenir de nombreux éléments, il est donc intéressant de créer son instance avec une capacité initiale suffisament élevée pour contenir les éléments plus une marge correspondant à la capacité multipliée par le facteur de charge. Les performances seront améliorées car cela évitera une ou plusieurs opérations d'agrandissement de la collection.

package fr.jmdoudoux.dej.collections;
      
import java.util.Hashtable;

public class TestHashtable {

  public static void main(final String[] args) {
    Hashtable<Integer, String> numbers = new Hashtable<Integer, String>();
    numbers.put(1, "Element1");
    numbers.put(2, "Element2");
    numbers.put(3, "Element3");
    String n = numbers.get(2);
    if (n != null) {
      System.out.println("2 = " + n);
    }
  }
}

2 = Element2

Les Iterator de cette classe sont de type fail-fast : les instances de type Iterator retournées par la méthode iterator() lèvent généralement une exception de type ConcurrentModificationException si une modification est effectuée dans la collection durant le parcours (exception faite des modifications réalisées avec la méthode remove() de l'Iterator).

14.5.4. La classe HashMap

La classe HashMap, ajoutée à Java 1.2, est une implémentation de l'interface Map qui utilise une Hashtable. La classe HashMap est similaire à la classe Hashtable sauf qu'elle n'est pas synchronized et qu'elle autorise l'utilisation de la valeur null.

La classe HashMap utilise un tableau de listes chaînées pour le stockage de ses éléments. L'index d'une clé dans le tableau est déterminé grâce à un algorithme utilisant la valeur de hachage de l'objet.

La valeur de hachage n'est pas utilisée directement : l'algorithme fait appel à la méthode hash() de la classe HashMap qui utilise la valeur de hachage pour en déterminer une autre, ceci afin de réduire les risques de collision.

Si deux objets possèdent la même valeur de hachage, il y a une collision car les deux objets doivent être insérés dans le même bucket. Pour gérer les problèmes, le bucket contient une liste chaînée : chaque élément (sa clé et sa valeur) est encapsulé dans une instance de type Entry.

Toutes les méthodes optionnelles de l'interface Map sont implémentées.

La classe HashMap présente plusieurs caractéristiques :

• Elle permet l'utilisation de la valeur null comme clé et comme valeur.
• Elle n'est pas thread-safe.
• Elle ne garantit aucun ordre lors du parcours des éléments de la collection.

La classe HashMap possède deux propriétés :

• la capacité initiale
• le facteur de charge (load factor)

Il est important que la valeur de la capacité initiale soit une puissance de 2 : si ce n'est pas le cas la capacité initiale sera la valeur 2ⁿ supérieure. Si la capacité c fournie est 2^n-1 > c < 2ⁿ alors la capacité sera 2ⁿ. La valeur de la capacité doit être une puissance de 2 pour permettre à l'algorithme qui détermine l'index dans le tableau à partir de la valeur de hachage de fonctionner.

Le facteur de charge définit le pourcentage de remplissage maximum de la collection avant que celle-ci ne soit agrandie. Si le pourcentage du nombre d'éléments contenus dans la collection par rapport à la capacité de la collection est supérieur au facteur de charge, alors la capacité maximale de la collection est doublée.

La classe HashMap propose plusieurs constructeurs dont certains peuvent préciser la capacité initiale et le facteur de charge.

Pour pouvoir correctement mettre en oeuvre la classe HashMap, il est nécessaire de connaître son mode de fonctionnement.

En interne, une HashMap stocke les paires clé/valeur dans des buckets qui peuvent être vus comme un index de premier niveau. Lors de l'ajout d'un élément ou la recherche d'un élément dans la collection, la valeur de hachage de la clé est utilisée pour déterminer un index dans le tableau des buckets.

Chaque bucket possède une liste chaînée qui stocke les éléments dont la clé possède la même valeur de hachage. Comme deux objets égaux doivent avoir la même valeur de hachage mais que deux objets ayant la même valeur de hachage ne sont pas forcément égaux, une liste chaînée est utilisée pour stocker les éléments ayant la même valeur de hachage.

La classe HashMap possède la classe interne Entry qui implémente l'interface Map.Entry et encapsule une paire clé/valeur. La liste chaînée du bucket contient donc des objets de type Entry qui encapsulent la clé et la valeur. La méthode next() permet d'obtenir l'élément suivant dans la liste.

Lors de l'invocation de la méthode put(), plusieurs opérations sont réalisées :

• invocation de la méthode hashCode() sur l'objet qui encapsule la clé
• la méthode hash() de la classe HashMap utilise son propre algorithme pour déterminer un index à partir de la valeur de hachage de la clé
• un objet de type Entry qui encapsule la clé et la valeur est instancié
• si l'index du bucket est vide alors l'instance de type Entry est ajoutée
• si l'index n'est pas vide, la liste chainée est parcourue en commençant par l'élément stocké à l'index puis en invoquant successivement sa méthode next(). La clé de l'élément est comparée à la clé de l'élément Entry courant en utilisation la méthode equals()
• si la même clé est trouvée alors la valeur est remplacée par celle de l'élément à ajouter sinon le nouvel élément de type Entry est ajouté à la fin de la liste chaînée

La classe HashMap accepte la valeur null comme clé : dans ce cas, la clé est placée à l'index 0 dans le tableau.

Plusieurs éléments pouvant être stockés à un même index, il est nécessaire de parcourir ses éléments qui sont dans une liste chaînée, encapsulés dans des objets de type Entry. Le parcours se fait en invoquant la méthode next(). La clé de l'élément courant est comparée à la clé recherchée en utilisant la méthode equals() si les instances sont différentes.

Pour obtenir un élément de la collection grâce à la méthode get(), le mode de fonctionnement est similaire à l'ajout. Lors de l'invocation de la méthode get() :

• l'index du bucket dans le tableau est déterminé en utilisant la valeur de hachage de la clé : elle est utilisée par la méthode hash() pour calculer une valeur de hachage, elle-même utilisée pour déterminer l'index dans le tableau
• si l'index du bucket est vide alors l'élément n'est pas trouvé
• si le bucket ne contient qu'un seul élément, c'est la valeur de cet élément qui est retournée
• si la liste chaînée du bucket contient plusieurs éléments alors chaque élément est parcouru en commençant par l'élément stocké à l'index puis invoquant successivement sa méthode next() pour en trouver un dont la clé soit égale à la clé recherchée en invoquant la méthode equals()
• si un élément est trouvé alors c'est la valeur de cet élément qui est retournée
• si aucun élément n'est trouvé alors la valeur retournée est null

L'implémentation des méthodes equals() et hashCode() d'objets utilisés comme clés doit respecter les spécifications qui sont imposées par Java. La valeur de hachage de la clé obtenue en invoquant sa méthode hashCode() est utilisée pour calculer l'index du bucket. La méthode equals() des clés est utilisée pour assurer l'unicité des clés dans la collection et pour retrouver le bon élément.

Comme une HashMap repose sur l'utilisation de la valeur de hachage des clés, l'idéal est d'utiliser des instances immuables d'objets dont les méthodes equals() et hashCode() sont correctement implémentées. L'utilisation d'objets immuables comme clés assure, si l'implémentation de la méthode hashCode() est bien faite, que la valeur de hachage de l'objet ne change pas. Ainsi des objets de type String ou des classes de type wrapper de primitives sont de bons candidats pour les clés de la collection.

Il est très important que la valeur de hachage d'un objet utilisé comme clé ne change pas car cette valeur est utilisée pour déterminer le bucket de la collection qui contient l'élément. Si un élément est ajouté dans la collection avec une clé ayant une certaine valeur de hachage et que cette valeur de hachage est différente lors de la recherche de clé dans la collection, l'élément ne sera probablement pas retrouvé alors qu'il est bel et bien dans la collection. Cette recherche échoue car la valeur de hachage à l'ajout place l'élément dans un bucket et la recherche avec une autre valeur de hachage détermine un autre bucket qui ne contient pas l'élément.

Si le facteur de charge est atteint, alors la taille de la collection est agrandie : la taille du tableau contenant les buckets est doublée en recréant une nouvelle instance du tableau. Cette opération implique un recalcul de tous les buckets : cette fonctionnalité est appelée rehash car elle redéfinit toutes les valeurs des index.

Lorsque la collection est redimensionnée, chaque élément est déplacé du tableau initial dans le nouveau tableau dont la taille est doublée. Lors de ce transfert, l'index de l'élément dans le bucket est recalculé, ce qui fait qu'il peut rester le même ou être modifié.

Le temps d'exécution de cette opération est proportionnel à la taille de la collection : pour limiter ses occurrences, il est possible de préciser la capacité initiale de la collection si l'on possède une idée plus ou moins précise du nombre d'éléments que contiendra la collection.

La classe HashMap n'est pas synchronized, elle n'est donc pas thread-safe. Si plusieurs threads doivent ajouter ou supprimer des éléments dans la collection, il faut gérer manuellement la concurrence d'accès. Il est par exemple possible d'utiliser une instance de la collection retournée par la méthode synchronizedMap() de la classe Collections.

   Map m = Collections.synchronizedMap(new HashMap());

Une collection de type HashMap n'est pas prévue pour être utilisée par plusieurs threads. Par exemple, une invocation de la méthode get() peut déclencher une boucle infinie si une opération de rehash() est réalisée en même temps que l'insertion d'un élément. Durant l'agrandissement de la collection, les éléments de la liste chaînée d'un bucket sont déplacés dans un nouveau bucket dans leur sens inverse de la liste courante. Si un accès est fait à ce moment là, une boucle infinie peut être engendrée. Ceci peut aussi arriver si deux threads effectuent en même temps une opération de type rehash().

package fr.jmdoudoux.dej.collections;
      
import java.util.HashMap;
import java.util.Map;

class MonElement {
  private final int valeur;
  public MonElement(final int valeur) {
    this.valeur = valeur;
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    MonElement other = (MonElement) obj;
    if (valeur != other.valeur) {
      return false;
    }
    return true;
  }

  @Override
  public int hashCode() {
    return valeur / 100;
  }
}

public class TestHashMapBoucleInfinie {
  /**
   * Attention : cette application engendre généralement une boucle infinie
   * qui consomme toute la CPU de la machine
   */
  public static void main(final String[] args) {
    final Map<MonElement, String> map = new HashMap<MonElement, String>(2, 0.2f);
    
    System.out.println("debut");
    for (int j = 0; j < 10; j++) {
      Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
          for (int i = 1; i <= 100000; i++) {
            map.put(new MonElement(i), "element " + i);
          }
        }
      }, "Thread 0" + j);
      t1.start();
    }

    for (int j = 0; j < 10; j++) {
      Thread t2 = new Thread(new Runnable() {
        @Override
        public void run() {
          for (int i = 1; i <= 10000; i++) {
            map.get(i);
          }
        }
      }, "Thread 1" + j);
      t2.start();
    }
  }
}

Les Iterator de cette classe sont de type fail-fast : ils lèvent généralement une exception de type ConcurrentModificationException si une modification de la structure de la collection est réalisée (ajout ou suppression d'un élément) durant le parcours sauf si cette modification est faite grâce à l'Iterator.

Comme l'index est calculé à partir de la valeur de hachage de l'objet, l'ordre de parcours des clés n'est pas garanti. Il peut même changer au cours du temps si de nouveaux éléments sont ajoutés dans la collection.

package fr.jmdoudoux.dej.collections;
      
import java.util.HashMap;

public class TestHashMapIterator {
  public static void main(final String[] args) {
    HashMap<String, String> map = new HashMap<String, String>(34);
    map.put("1", "un");
    map.put("2", "deux");
    map.put("3", "trois");
    map.put("4", "quatre");
    map.put("5", "cinq");
    for (String s : map.keySet()) {
      System.out.print(s + " ");
    }
  }
}

3 2 1 5 4

Les performances des opérations get() et put() sont constantes sous réserve que la répartition des éléments dans les différents buckets grâce à leur valeur de hachage soit équitable.

La valeur de hachage doit être la plus discriminante possible pour permettre notamment de réduire les collisions (objets différents ayant la même valeur de hachage). Si tous les éléments de la collection possèdent la même valeur de hachage, alors ils sont tous dans le même bucket et les performances pour retrouver un élément sont de type O(n). Si la répartition des valeurs de hachage est équilibrée alors ces performances peuvent être de type O(log n).

Il existe plusieurs différences entre les classes Hashtable et HashMap bien qu'elles implémentent toutes les deux l'interface Map et ont un mode de fonctionnement similaire :

• La classe HashMap n'est pas synchronized contrairement à la classe Hashtable : dans un contexte monothread la classe HashMap est plus performante
• la classe HashMap autorise l'utilisation de null comme clé et comme valeur contrairement à la classe Hashtable
• Java 5 a introduit la classe ConcurrentHashMap comme une alternative plus performante à la classe Hashtable
• les Iterator de la classe HashMap sont de type fail-fast : une exception ConcurrentModificationException est levée si une modification de la structure de la collection est effectuée par un autre thread sans utiliser l'Iterator

14.5.5. La classe LinkedHashMap

La classe LinkedHashMap, ajoutée à Java 1.4, est une implémentation de type Map qui utilise une liste doublement chaînée pour maintenir par défaut ses éléments dans leur ordre d'insertion.

Cette collection permet de garantir l'ordre de ses éléments sans avoir un subir un surcoût comme par exemple lors de l'utilisation d'une classe TreeSet.

La classe LinkedHashMap possède plusieurs constructeurs :

package fr.jmdoudoux.dej.collections;
      
import java.util.LinkedHashMap;
import java.util.Map;

public class TestLinkedHashMap {
  private static void afficherMap(final LinkedHashMap<String, String> map) {
    for (String s : map.keySet()) {
      System.out.print(s + " ");
    }
    
    System.out.println("");
    for (Map.Entry<String, String> s : map.entrySet()) {
      System.out.print(s.getKey() + " ");
    }
  }

  public static void main(final String[] args) {
    LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
    map.put(null, "");
    for (int i = 10; i < 19; i++) {
      map.put("" + i, "");
    }
    afficherMap(map);
  }
}

null 10 11 12 13 14 15 16 17 18 
null 10 11 12 13 14 15 16 17 18

La surcharge du constructeur qui attend en paramètre le booléen accessOrder permet de préciser l'ordre des éléments :

• true : les éléments sont triés du moins accédés au plus accédés
• false : les éléments sont triés dans leur ordre d'insertion

Cette fonctionnalité peut être intéressante pour créer un cache de type LRU.

package fr.jmdoudoux.dej.collections;
      
import java.util.LinkedHashMap;
import java.util.Map;

public class TestLinkedHashMap {
  private static void afficherMap(final LinkedHashMap<String, String> map) {
    for (String s : map.keySet()) {
      System.out.print(s + " ");
    }
   
    System.out.println(""); 
    for (Map.Entry<String, String> s : map.entrySet()) {
      System.out.print(s.getKey() + " ");
    }
  }

  public static void main(final String[] args) {
    LinkedHashMap<String, String> map = new LinkedHashMap<String, String>(16, 0.75f, true);
    map.put(null, "");
    for (int i = 10; i < 19; i++) {
      map.put("" + i, "");
    }
    map.get("11");
    map.get("14");
    map.get("14");
    map.get("11");
    map.get("16");
    map.get("11");
    afficherMap(map);
  }
}

null 10 12 13 15 17 18 14 16 11 
null 10
12 13 15 17 18 14 16 11

La classe LinkedHashMap peut être utilisée pour créer une copy d'une autre collection de type Map qui permettra son parcours toujours de la même façon.

  Map copie = new LinkedHashMap(m);

L'ordre des éléments n'est pas modifié si un élément est de nouveau ajouté dans la collection alors qu'il est déjà présent dans cette dernière.

La méthode removeEldestEntry(Map.Entry<K,V>) peut être surchargée pour renvoyer un booléen qui précise si les éléments les plus anciens doivent être retirés de la collection.

La méthode containsValue(Object value) renvoie un booléen qui précise si une ou plusieurs de ses clés sont associées à la valeur fournie en paramètre.

Elle présente plusieurs caractéristiques :

• Elle implémente toutes les opérations optionnelles du type Map
• Elle permet l'ajout d'éléments null

La classe LinkedHashMap n'est pas synchronized, elle n'est donc pas thread-safe. Si plusieurs threads doivent ajouter ou supprimer des éléments dans la collection, il faut gérer manuellement la concurrence d'accès. Il est par exemple possible d'utiliser une instance de la collection retournée par la méthode synchronizedMap() de la classe Collections.

   Map m = Collections.synchronizedMap(new LinkedHashMap());

Les Iterator de la classe LinkedHashMap sont de type fail-fast : les instances de type Iterator retournées par la méthode iterator() lèvent généralement une exception de type ConcurrentModificationException si une modification est effectuée dans la collection durant le parcours (exception faite des modifications réalisées avec la méthode remove() de l'Iterator).

Une LinkedHashMap, comme la classe HashMap, possède deux paramètres qui peuvent affecter ses performances lors de son utilisation : capacité initiale et facteur de charge. Cependant, contrairement à une HashMap, l'utilisation d' une capacité initiale largement surestimée est moins importante car le temps d'itération de cette collection n'est pas proportionnel à sa capacité.

Si la répartition dans les différents buckets réalisée grâce à la valeur de hachage de ses éléments est équitable, les méthodes add(), contains() et remove() sont exécutées avec des performances constantes. Le temps requis pour parcourir la collection est proportionnel à sa taille.

14.5.6. La classe TreeMap

La classe TreeMap, ajoutée à Java 1.2, est une Map qui stocke des éléments de manière triée dans un arbre de type rouge-noir (Red-black tree).

Les éléments de la collection sont triés selon l'ordre naturel de leur clé (s'is implémentent l'interface Comparable) ou en utilisant une instance de type Comparator fournie au constructeur de la collection.

Elle implémente les interfaces Map et SortedMap. Elle implémente aussi l'interface NavigableMap depuis Java 6.

La classe TreeMap propose plusieurs constructeurs dont un qui permet de préciser l'objet Comparable pour définir l'ordre dans la collection :

package fr.jmdoudoux.dej.collections;
      
import java.util.Map;
import java.util.TreeMap;

public class TestTreeMap {
  public static void main(final String[] args) {
    TreeMap<String, String> map = new TreeMap<String, String>();

    map.put("cle3", "valeur3");
    map.put("cle2", "valeur2");
    map.put("cle1", "valeur1");

    for (Map.Entry<String, String> element : map.entrySet()) {
      System.out.println(element.getKey() + " : " + element.getValue());
    }
  }
}

La classe TreeMap n'est pas synchronized. Pour obtenir une instance synchronized, il faut invoquer la méthode synchronizedSortedMap() de la classe Collections.

   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

Toutes les instances de type Map.Entry retournées par les méthodes d'une TreeMap représente une vue des éléments de l'instance au moment où elles sont créées. La méthode setValue() de la classe Map.Entry lève une exception de type UnsupportedOperationException si elle est invoquée.

package fr.jmdoudoux.dej.collections;
      
import java.util.Map;
import java.util.TreeMap;

public class TestTreeMap {
  public static void main(final String[] args) {
    TreeMap<String, String> map = new TreeMap<String, String>();

    map.put("cle1", "valeur1");
    map.put("cle2", "valeur2");
    map.put("cle3", "valeur3");

    Map.Entry<String, String> dernier = map.lastEntry();
    dernier.setValue("valeur3 modifie");
    
    for (Map.Entry<String, String> element : map.entrySet()) {
      System.out.println(element.getKey() + " : " + element.getValue());
    }
  }
}

Exception in thread "main" java.lang.UnsupportedOperationException
       at java.util.AbstractMap$SimpleImmutableEntry.setValue(Unknown Source)
       at fr.jmdoudoux.dej.collections.TestTreeMap.main(TestTreeMap.java:15)

Pour changer la valeur associer à une clé, il faut utiliser la méthode put().

package fr.jmdoudoux.dej.collections;
      
import java.util.Map;
import java.util.TreeMap;

public class TestTreeMap {
  public static void main(final String[] args) {
    TreeMap<String, String> map = new TreeMap<String, String>();

    map.put("cle1", "valeur1");
    map.put("cle2", "valeur2");
    map.put("cle3", "valeur3");
    map.put("cle3", "valeur3 modifie");

    for (Map.Entry<String, String> element : map.entrySet()) {
      System.out.println(element.getKey() + " : " + element.getValue());
    }
  }
} 

cle1 : valeur1
cle2 : valeur2
cle3 : valeur3 modifie

Les opérations basiques get(), put() et remove() s'exécutent dans un délai de type O(log n).

Les Iterator sont de type fail-fast.

14.5.7. La classe WeakHashMap

La classe WeakHashMap, ajoutée dans Java 1.2, est une implémentation d'une collection de type Map dont les clés sont stockées avec des références faibles (WeakReference). La classe WeakHashMap retire automatiquement les éléments dont la clé a été récupérée par le ramasse-miettes.

Elle hérite de la classe AbstractMap et implémente l'interface Map<K,V>.

Cette collection présente plusieurs caractéristiques :

• elle permet d'utiliser des valeurs null comme clé et valeur
• des éléments peuvent être supprimés sans avertissement par la collection

Une clé n'est pas stockée directement dans une WeakHashMap : c'est une référence faible sur l'instance qui est stockée. Un objet qui encapsule une valeur est stocké dans la WeakHashMap avec une référence forte. Il ne doit pas faire référence à sa clé sinon celle-ci ne sera pas récupérée par le ramasse-miettes en cas de besoin.

Si l'objet utilisé comme clé n'est plus référencé par d'autres objets, le ramasse-miettes va le récupérer et l'élément sera retiré de la collection.

Il faut être sûr de n'utiliser comme clés que des objets qui puissent être récupérés par le ramasse-miettes : par exemple, il ne faut surtout pas utiliser des chaînes de caractères dont la valeur est codée en dur.

Seules les clés sont stockées avec des références faibles : la valeur associée à l'élément est stockée sous la forme d'une référence forte.

La classe WeakHashMap possède quatre constructeurs :

package fr.jmdoudoux.dej.collections;
      
import java.util.Map;
import java.util.WeakHashMap;

public class TestWeakHashMap {
  public static void main(final String args[]) {
    String maCle = new String("1");

    Map<String, String> map = new WeakHashMap<String, String>();
    map.put(maCle, "Element1");
    map.put(new String("2"), "Element2");
    map.put(new String("3"), "Element3");

    System.out.println("map.size()=" + map.size());
    System.out.println("Demande d'execution du ramasse-miettes");
    System.gc();
    try {
      Thread.sleep(1000);
    } catch (InterruptedException ignored) {
    }
   
    System.out.println("map.size()=" + map.size());
    maCle = null;
   
    System.out.println("Demande d'execution du ramasse-miettes");
    System.gc();
    try {
      Thread.sleep(1000);
    } catch (InterruptedException ignored) {
    }
   
    System.out.println("map.size()=" + map.size());
  }
}

map.size()=3
Demande d'execution du ramasse-miettes
map.size()=1
Demande d'execution du ramasse-miettes
map.size()=0 

Le fonctionnement d'un objet de type WeakHashMap repose en partie sur l'activité du ramasse-miettes qui peut détruire des objets utilisés comme clés : ces objets seront alors supprimés de la collection. Ainsi le contenu de la collection peut être modifié alors qu'aucune opération n'est explicitement invoquée : ce comportement est spécifique pour une collection de type WeakHashMap.

Il est préférable que l'implémentation de la méthode equals() des objets utilisés comme clés utilise un test d'égalité sur l'identité des objets avec l'opérateur ==. Ceci garantit qu'un objet ne puisse pas être recréé et être égal à l'instance détruite par le ramasse-miettes.

La classe WeakHashMap n'est pas synchronized. Pour obtenir une instance synchronized, il faut invoquer la méthode synchronizedMap() de la classe Collections.

   WeakHashMap m = Collections.synchronizedMap(new WeakHashMap(...));

Les performances de cette collection sont similaires à celles de la classe HashMap.

Les Iterator de la classe WeakHashMap sont de type fail-fast.

Il est tentant d'utiliser la classe WeakHashMap comme implémentation d'un cache.

Il est préférable d'utiliser la classe WeakHashMap pour associer des données à un objet : dans ce cas, la clé est l'objet et la valeur contient les informations associées. La classe WeakHashMap va garantir qu'il n'y aura pas de fuites de mémoire liées à l'oubli de suppression de l'élément dans la collection lorsque l'objet n'est plus utilisé.

Ceci peut par exemple être pratique si l'objet est accédé par plusieurs threads. Une WeakHashMap est bien adaptée lorsqu'il n'est pas facile de connaitre le moment où les threads n'auront plus besoin des informations et pourront retirer l'objet les contenant de la collection.

14.5.8. La classe EnumMap

La classe java.util.EnumMap<K extends Enum<K>, V>, ajoutée à Java 5, est une implémentation de l'interface Map qui ne peut utiliser comme clés que les éléments d'une énumérations. Les traitements de la classe sont optimisés en fonction de cette particularité.

Elle hérite de la classe AbstractMap(K, V)

Elle présente plusieurs caractéristiques :

• toutes les valeurs utilisables comme clés doivent appartenir à la même énumération
• il n'est pas possible d'utiliser la valeur null comme clé sinon une exception de type NullPointerException est levée lors de l'ajout de l'élément
• la valeur associée à la clé peut être null.

En interne, le stockage des éléments de la collection se fait dans un tableau.

Les Iterator obtenus par les méthodes keySet(), entrySet() et values() sont ordonnés dans l'ordre de définition des éléments de l'énumération. Ces itérateurs ne lèvent jamais d'exception de type ConcurrentModificationException.

package fr.jmdoudoux.dej.collections;

import java.util.EnumMap;
import java.util.Iterator;

public class TestEnumMap {
  public enum ETAT {
    NOUVEAU, EN_COURS, EN_PAUSE, INDETERMINE, TERMINE;
  }

  public static void main(final String args[]) {
    EnumMap<ETAT, String> etatLibelle = new EnumMap<ETAT, String>(ETAT.class);

    etatLibelle.put(ETAT.NOUVEAU, "Nouvelle tache");
    etatLibelle.put(ETAT.EN_COURS, "Tache en cours d'exécution");
    etatLibelle.put(ETAT.EN_PAUSE, "Execution de la tache en pause");
    etatLibelle.put(ETAT.TERMINE, "Tache terminée");

    System.out.println("etatLibelle : " + etatLibelle);
    System.out.println("EnumMap cle : " + ETAT.NOUVEAU + ", valeur : "
        + etatLibelle.get(ETAT.NOUVEAU));
    Iterator<ETAT> enumKeySet = etatLibelle.keySet().iterator();
    while (enumKeySet.hasNext()) {
      ETAT currentState = enumKeySet.next();
      System.out.println("cle : " + currentState + ", valeur : "
          + etatLibelle.get(currentState));
    }

    if (etatLibelle.containsKey(ETAT.NOUVEAU)) {
      System.out.println("etatLibelle contient la cle : " + ETAT.NOUVEAU);
    }
    if (!etatLibelle.containsKey(ETAT.INDETERMINE)) {
      System.out.println("etatLibelle ne contient pas la cle : "
          + ETAT.INDETERMINE);
    }
  }
}

etatLibelle : {NOUVEAU=Nouvelle tache, EN_COURS=Tache en cours
d'exécution, EN_PAUSE=Execution de la tache en pause, TERMINE=Tache terminée}
EnumMap cle : NOUVEAU, valeur : Nouvelle tache
cle : NOUVEAU, valeur : Nouvelle tache
cle : EN_COURS, valeur : Tache en cours d'exécution
cle : EN_PAUSE, valeur : Execution de la tache en pause
cle : TERMINE, valeur : Tache terminée
etatLibelle contient la cle : NOUVEAU
etatLibelle ne contient pas la cle : INDETERMINE

La classe EnumMap n'est pas synchronized. Si plusieurs threads doivent accéder à la collection et qu'au moins l'un d'entre-eux modifie la collection, il faut utiliser une instance de la collection retournée par la méthode synchronizedMap() de la classe Collections.

     Map<MonEnum, String> map = Collections.synchronizedMap(new EnumMap<MonEnum, String>());

Les opérations de base s'exécutent en temps constant. Les performances des opérations d'une EnumMap sont généralement meilleures que leur équivalent de la classe HashMap avec les mêmes éléments.

Il existe plusieurs différences entre les classes EnumMap et HashMap :

• avec la classe EnumMap seuls les éléments d'une énumération sont utilisables comme clés alors que la class HashMap accepte n'importe quels types d'objets
• dans une instance de type EnumMap, toutes les clés sont différentes : elle n'utilise pas la méthode hashCode() car il ne peut pas y avoir de collision sur les clés
• la classe EnumMap est plus performante qu'une classe HashMap qui possède les mêmes éléments

14.5.9. La classe IdentityHashMap

La classe java.util.IdentityHashMap<K extends Enum<K>, V>, ajoutée à Java 1.4, est une implémentation de l'interface Map qui utilise un test d'égalité sur les références (habituellement les implémentations de l'interface Map utilise l'égalité des objets). Deux clés cle1 et cle2 sont donc égales si cle1==cle2.

De ce fait, la classe IdentityHashMap est une implémentation particulière de l'interface Map dont elle ne respecte pas le contrat qui précise que le test d'égalité sur des objets doit se faire en utilisant la méthode equals(). Ce n'est donc pas une implémentation à usage générale mais son utilisation est limitée à quelques cas bien particuliers comme par exemple conserver une trace des objets utilisés lors d'opérations de sérialisation ou de clonage.

Elle hérite de la classe AbstractMap(K, V) et implémente toutes les méthodes optionnelles de l'interface Map.

Elle possède plusieurs caractéristiques :

• en interne, le stockage des éléments de la collection se fait dans une Hashtable
• elle permet d'utiliser null comme clé et comme valeur
• elle ne garantit pas l'ordre dans lequel les éléments sont parcourus
• la valeur de hachage retournée par la méthode identityHashCode() de la classe System est utilisée pour calculer l'index du bucket dans la Hashtable interne

La classe IdentityHashMap a une propriété qui peut agir sur ses performances : le nombre maximum d'éléments prévus dans la collection. Cette propriété est utilisée pour définir le nombre de buckets. Si la taille de la collection devient insuffisante pour contenir les éléments, le stockage interne de la collection est agrandi et la méthode rehash() est invoquée. Cet agrandissement est coûteux.

La classe IdentityHashMap possède trois constructeurs :

package fr.jmdoudoux.dej.collections;
      
import java.util.IdentityHashMap;

public class TestIdentityHashMap {
  public static void main(final String[] args) {
    IdentityHashMap<String, String> identityMap = new IdentityHashMap<String, String>();
    identityMap.put("1", "Element 1");
    identityMap.put(new String("1"), "Element 1_2");

    System.out.println("identityHashMap.size() = " + identityMap.size());
    System.out.println("identityHashMap = " + identityMap);

    identityMap.put("1", "Element 1 modifie");
    System.out.println("identityHashMap.size() = " + identityMap.size());
    System.out.println("identityHashMap = " + identityMap);
  }
}

identityHashMap.size() = 2
identityHashMap = {1=Element 1_2, 1=Element 1}
identityHashMap.size() = 2
identityHashMap = {1=Element 1_2, 1=Element 1 modifie}

La classe IdentityHashMap n'est pas synchronized. Si plusieurs threads doivent accéder à la collection et qu'au moins un d'entre-eux modifie la collection, il faut utiliser une instance de la collection retournée par la méthode synchronizedMap() de la classe Collections.

    Map map = Collections.synchronizedMap(new IdentityHashMap());

Les Iterator de la classe IdentityHashMap sont de type fail-fast : les instances de type Iterator retournées par la méthode iterator() lèvent généralement une exception de type ConcurrentModificationException si une modification est effectuée dans la collection durant le parcours (exception faite des modifications réalisées avec la méthode remove() de l'Iterator).

Il existe plusieurs différences entre les classes IdentityHashMap et HashMap :

• la classe HashMap est une implémentation généraliste, la classe IdentityHashMap est une implémentation particulière
• la classe IdentityHashMap utilise l'opérateur == pour tester l'égalité des clés alors que la classe HashMap utilise la méthode equals()
• la classe HashMap utilise la méthode hashCode() des clés pour déterminer leur bucket alors que la classe IdentityHashMap utilise la méthode identityHashCode() de la classe System
• si les clés utilisées ne redéfinissent pas les méthodes equals() et hashCode(), le fonctionnement des classes IdentityHashMap et HashMap est similaire
• comme la classe IdentityHashMap n'utilise pas les méthodes equals() et hashCode(), ses performances sont meilleures que celles de la classe HashMap
• les clés utilisées dans une instance de type IdentityHashMap n'ont pas besoin d'être immuables puisqu'elles n'utilisent pas la méthode equals()

package fr.jmdoudoux.dej.collections;
      
import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;

public class TestIdentityMapHashMap {
  public static void main(final String[] args) {
    Map<String, Integer> identityMap = new IdentityHashMap<String, Integer>();
    Map<String, Integer> hashMap = new HashMap<String, Integer>();

    identityMap.put("1", 1); 
    identityMap.put(new String("1"), 2);
    identityMap.put("1", 3);

    hashMap.put("1", 1);
    hashMap.put(new String("1"), 2);
    hashMap.put("1", 3);
   
    System.out.println("identityMap.keySet().size() = "
        + identityMap.keySet().size());
    System.out.println("hashMap.keySet().size()     = "
        + hashMap.keySet().size());
  }
}

identityMap.keySet().size() = 2
hashMap.keySet().size()     = 1

14.5.10. L'interface NavigableMap

L'interface NavigableMap, ajoutée dans Java 6, hérite de l'interface SortedMap. Elle définit des fonctionnalités qui permettent le parcours de la collection dans l'ordre ascendant ou descendant grâce à plusieurs méthodes.

L'interface définit plusieurs méthodes qui peuvent être regroupées selon leur rôle :

• obtenir le premier ou le dernier élément : firstEntry(), lastEntry(), pollFirstEntry(), pollLastEntry()
• obtenir un sous-ensemble de la collection : subMap(), headMap(), tailMap()
• obtenir l'élément dont la clé est la plus approchante : ceilingEntry(), ceilingKey(), floorEntry(), floorKey(), higherEntry(), higherKey(), lowerEntry(), lowerKey()
• parcours de la collection en sens inverse : descendingMap(), descendingKeySet(), navigableKeySet()

L'API Collections propose plusieurs implémentations de l'interface NavigableMap : ConcurrentSkipListMap et TreeMap

14.5.11. L'interface ConcurrentNavigableMap

L'interface java.util.concurrent.ConcurrentNavigableMap, ajoutée à Java 1.6, définit les fonctionnalités d'une NavigableMap avec une gestion des accès concurrents pour elle-même et pour ses sous Map.

L'interface NavigableMap hérite des interfaces ConcurrentMap et NavigableMap.

L'API Collections ne propose qu'une seule implémentation de cette interface : la classe ConcurrentSkipListMap.

14.5.12. La classe ConcurrentSkipListMap

La classe ConcurrentSkipListMap, ajoutée à Java 6, est une implémentation de l'interface ConcurrentNavigableMap en utilisant un algorithme de type SkipList. Les fonctionnalités offertes par la classe ConcurrentSkipListMap peuvent être vues comme une fusion des fonctionnalités des classes ConcurrentHashMap et TreeMap.

Les éléments de cette collection sont triés selon leur ordre naturel en implémentant l'interface Comparable ou en utilisant une instance de type Compator fournie en paramètre du constructeur de la collection.

La classe ConcurrentSkipListMap présente plusieurs caractéristiques :

• elle permet la modification concurrente de la collection sans la bloquer dans son intégralité
• elle est optimisée pour les opérations de lectures qui sont non bloquantes
• par défaut les éléments sont triés selon leur ordre naturel ou selon l'ordre défini par l'instance de Comparator associée à la collection
• l'utilisation de null n'est pas possible ni pour la clé ni pour la valeur d'un élément

La classe java.util.ConcurrentSkipMap hérite de la classe abstraite AbstractMap et implémente l'interface ConcurrentNavigableMap. Elle implémente toutes les méthodes optionnelles des interfaces Map et Iterator.

La classe propose plusieurs constructeurs :

Les opérations de la classe ConcurrentSkipListMap sont thread-safe.

Les Iterator obtenus de la collection reflètent la liste des éléments à un instant donné, généralement le moment de la création de l'instance de type Iterator. Le parcours ne lève jamais d'exception de type ConcurrentModificationException. Le parcours ascendant est plus rapide que le parcours descendant.

Les opérations groupées proposées par les méthodes clear(), equals() et putAll() ne garantissent pas que leurs exécutions seront atomiques.

Toutes les instances de type Map.Entry retournées par les méthodes de classe ConcurrentSkipListMap sont une représentation des données au moment où l'instance est créée. Il n'est pas possible d'utiliser leur méthode setValue(). Pour modifier une valeur, il faut invoquer une des méthodes put(), putIfAbsent() ou replace().

package fr.jmdoudoux.dej.collections;
      
import java.util.Iterator;
import java.util.concurrent.ConcurrentSkipListMap;

public class TestConcurrentSkipListMap {
  public static void main(final String[] args) {
    final ConcurrentSkipListMap<MaTache, String> map = 
      new ConcurrentSkipListMap<MaTache, String>();
    
    System.out.println("debut");
    final Thread modificateur = new Thread(new Runnable() {
      @Override
      public void run() {
        MaTache[] MesTaches = new MaTache[5];
        for (int i = 1; i <= 5; i++) {
          MesTaches[i - 1] = new MaTache(6 - i, "Tache " + i);
        }

        for (int j = 1; j <= 100; j++) {
          if (j % 2 == 0) {
            for (int i = 1; i <= 5; i++) {
              MaTache element = MesTaches[i - 1];
              System.out.println("insertion element " + element);
              map.putIfAbsent(element, "description " + i);
            }
            System.out.println("taille de la queue=" + map.size());
          } else {
            for (int i = 1; i <= 5; i++) {
              MaTache element = MesTaches[i - 1];
              System.out.println("retirer element " + element);
              map.remove(element);
            }
          }
        }
      }
    }, "Modificateur");
    
    modificateur.start();
    
    Thread iterateur = new Thread(new Runnable() {
      @Override
      public void run() {
        int i = 0;
        while (modificateur.isAlive()) {
          Iterator<MaTache> iterator = null;

          if (i % 2 == 0) {
            iterator = map.navigableKeySet().iterator();
          } else {
            iterator = map.descendingKeySet().iterator();
          }

          StringBuilder contenu = new StringBuilder("[");

          while (iterator.hasNext()) {
            contenu.append(iterator.next().getDescription());
            if (iterator.hasNext()) {
              contenu.append(", ");
            }
          }
          contenu.append("]");
          
          System.out.println("Contenu=" + contenu);
          i++;
        }
      }
    }, "iterateur");

    iterateur.start();
    try {
      modificateur.join();
      iterateur.join();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    System.out.println("fin");
  }
}

Les performances des opérations basiques se situent en moyenne dans un temps dont l'expression est en log(n).

Le temps d'exécution de la méthode size() est variable car le nombre d'éléments de la collection doit être recalculé en la reparcourant.

La classe ConcurrentSkipListMap offre une meilleure scalabilité face aux accès concurrents que la classe ConcurrentHashMap mais en contrepartie les temps d'accès aux éléments ne sont pas constants. Cette contrepartie est liée au fait que la collection soit une SortedMap.

14.5.13. L'interface ConcurrentMap

L'interface ConcurrentMap, ajoutée à Java 1.5, définit les méthodes d'une collection qui est capable de gérer les accès concurrents lors des opérations de modifications de ces éléments.

Une collection de type Map est fréquemment utilisée dans un contexte multithread comme par exemple pour implémenter un cache d'objets simple.

Utiliser une instance synchronized de type Map retournée par la méthode synchronizedMap() de la classe Collections ne permet pas d'obtenir de bonnes performances en cas de nombreux accès concurrents car c'est l'instance de la collection elle-même sur laquelle se fait le verrou lors de l'invocation d'une méthode.

De plus, une Map synchronized ne garantit pas non plus l'atomicité de ses opérations qui nécessitent l'invocation de plusieurs méthodes : par exemple, pour ajouter un élément dans la collection, il est nécessaire de vérifier au préalable qu'elle ne contient pas déjà la clé en utilisant la méthode containsKey() ou get(). Comme le verrou est posé durant l'invocation de chaque méthode, il est possible que deux threads qui tentent d'ajouter un élément entraînent une race condition.

Par exemple, le premier thread obtient le verrou en invoquant la méthode containsKey() qui renvoie false, le second obtient à son tour le verrou en invoquant la méthode containsKey() qui renvoie false, le premier thread obtient le verrou en invoquant la méthode put() pour ajouter l'élément, le premier thread obtient le verrou en invoquant la méthode put() pour écraser l'élément ajouté par le premier thread.

Ce type de problématique est difficile à détecter et à reproduire : l'interface ConcurrentMap, ajoutée dans Java 5, hérite de l'interface Map. Elle définit quatre méthodes dont le comportement est atomique

L'API Collections propose deux implémentations de l'interface ConcurrentMap : ConcurrentHashMap et ConcurrentSkipListMap.

14.5.14. La classe ConcurrentHashMap

La classe ConcurrentHashMap, ajoutée à Java 1.5, implémente l'interface ConcurrentMap qui utilise une HashMap en garantissant les accès concurrents et les performances. Son but est de remplacer la classe Hashtable car elle est similaire à celle-ci avec une meilleure gestion des accès concurrents.

La classe ConcurrentHashMap implémente toutes les méthodes optionnelles des interfaces Map et Iterator.

Elle présente plusieurs caractéristiques :

• le mode de fonctionnement de cette collection est similaire à celui d'une Hashtable
• elle gère la concurrence d'accès et offre de très bonnes performances notamment dans le cas de forte concurrence
• les accès pour obtenir un élément ne sont pas bloquants
• la collection ne permet pas l'utilisation de null comme clé ou valeur.

Les accès pour retrouver un élément ne sont pas bloquants. Les mises à jour de la collection ne bloquent pas l'intégralité de la HashMap utilisée en interne car elle utilise des segments. Ce paramètre influe sur les performances lors des mises à jour concurrentes : il correspond au nombre de segments dans lesquels la collection va être découpée. Chaque thread qui effectue une mise à jour le fait dans son propre segment pour éviter la contention.

Idéalement, la valeur du paramètre concurrencyLevel doit être au moins égale au nombre de threads qui peuvent mettre à jour la collection de manière concurrente. Si la valeur est trop petite, il y a un risque d'avoir de la contention. Si la valeur est vraiment trop grande, il y a une consommation excessive de la mémoire requise. Par exemple, la valeur 1 est utilisable si un seul thread peut mettre à jour la collection et que les autres threads accèdent à la collection en lecture seulement.

Un des constructeurs attend un paramètre nommé concurrencyLevel qui correspond à ce nombre de segments. La valeur par défaut du paramètre concurrencyLevel est 16.

Deux autres paramètres influent sur les performances de la collection :

• la capacité initiale (initialCapacity) dont la valeur par défaut est 16
• le facteur de charge (loadFactor) dont la valeur par défaut est 0,75

Plusieurs surcharges du constructeur permettent de préciser ces paramètres afin d'optimiser les performances.

Généralement les opérations qui permettent d'obtenir un élément de la collection ne sont pas bloquantes et peuvent être réalisées en concurrence avec des opérations de mises à jour : la valeur retournée est alors le résultat de la dernière opération unitaire de mise à jour entièrement terminée. Si les opérations de mises à jour concernent plusieurs éléments (clear() ou putAll() par exemple), alors la ou les valeurs retournées peuvent ne contenir que tout ou partie des mises à jour en cours de réalisation.

package fr.jmdoudoux.dej.collections;
      
import java.util.Map;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

public class TestConcurrentHashMap {
  private final ConcurrentMap<String, AtomicInteger> cache      = 
    new ConcurrentHashMap<String, AtomicInteger>(3, 0.75f, NB_THREADS);

  private final CyclicBarrier                        barriere   = 
    new CyclicBarrier(NB_THREADS);
  private static final int                           NB_THREADS = 50;

  public static void main(final String[] args) {
    System.out.println("debut");
    TestConcurrentHashMap tchm = new TestConcurrentHashMap();
    tchm.exec();
    System.out.println("fin");
  }

  private void ajouter(final String cle) {
    AtomicInteger value;
    value = cache.putIfAbsent(cle, new AtomicInteger(1));
    if (value != null) {
      value.incrementAndGet();
    }
  }

  private void exec() {
    final ExecutorService executor = Executors.newFixedThreadPool(NB_THREADS);
    try {
      for (int i = 0; i < NB_THREADS; i++) {
        executor.submit(new Runnable() {
          @Override
          public void run() {
            try {
              barriere.await();
              for (int i = 0; i < 1000000; i++) {
                ajouter("chaine1");
                ajouter("chaine2");
                ajouter("chaine3");
              }
            } catch (InterruptedException e) {
              e.printStackTrace();
            } catch (BrokenBarrierException e) {
              e.printStackTrace();
            }
          }
        });
      }
    } finally {
      executor.shutdown();
    }
    while (!executor.isTerminated()) {
      try {
        Thread.sleep(100);
      } catch (InterruptedException e) {
        e.printStackTrace();
      }
    }
    for (Map.Entry<String, AtomicInteger> entry : cache.entrySet()) {
      System.out.println("[" + entry.getKey() + ", " +
        entry.getValue() + ']');
    }
  }
}

debut
[chaine1, 50000000]
[chaine3, 50000000]
[chaine2, 50000000]
fin

La classe ConcurrentHashMap est optimisée pour les opérations courantes mais certaines opérations peuvent être coûteuses : c'est notamment le cas de la méthode size() qui pose un verrou sur tous les segments pour calculer le nombre d'éléments que chacun contient.

Les parcours de la collection avec un Iterator reflètent l'état de la collection à un instant donné ou au moment de la création de l'Iterator. Les Iterator créés par cette collection ne lève jamais d'exception de type ConcurrentModificationException si une modification de structure est réalisée dans la collection durant son parcours. Ces Iterator ne sont toutefois pas prévus pour être utilisés par plusieurs threads.

14.5.15. Le choix d'une implémentation de type Map

Le JDK contient plusieurs implémentations de l'interface Map pour un usage spécifique :

• la classe EnumMap ne doit être utilisée que si les clés sont des éléments d'une énumérations
• la classe WeakHashMap stocke les clés avec des références faibles
• la classe IdentityHashMap utilise un test d'égalité sur les références de ses clés

Le JDK contient plusieurs implémentations de l'interface Map pour un usage généraliste qui peuvent selon les besoins :

• maintenir un ordre des clés
• gérer des accès concurrents

Pour une Map triée, il faut utiliser la classe TreeMap s'il n'y a pas d'utilisation concurrente sinon il faut utiliser la classe ConcurrentSkipListMap.

Trois classes sont utilisables dans un contexte généraliste et non concurrentiel. Le critère de choix est essentiellement l'ordre de tri des éléments que la collection doit utiliser :

• HashMap : aucun ordre précis pour les éléments qui doivent avoir l'implémentation de leurs méthodes hashCode() et equals() correctement codées
• TreeMap : l'ordre naturel des éléments ou l'ordre défini par l'instance de type Comparator associée à la collection
• LinkedHashMap : l'ordre des éléments est leur ordre d'insertion

Si la collection peut être utilisée de manière concurrente, plusieurs classes peuvent être mises en oeuvre :

• Hashtable : les méthodes de cette classe étant synchronized, les performances ne sont pas trop bonnes sous forte concurrence. De plus, certaines opérations qui nécessitent l'invocation de deux ou plusieurs méthodes ne sont pas atomiques
• ConcurrentHashMap : les verrous sont uniquement posés sur les éléments en cours de modification et la méthode get() n'est pas bloquante
• ConcurrentSkipListMap : maintient l'ordre de ses éléments et propose un parcours rapide au prix d'un surcoût lors de l'insertion

Le tableau ci-dessous compare les performances relatives de trois opérations permettant d'obtenir des données de plusieurs instances de type Map.

Dans le tableau ci-dessus, h représente la capacité de la collection et n le nombre d'éléments.

14.6. Les collections de type Queue : les files

Une Queue est une collection qui stocke des éléments dans un certain ordre avant d'être consommés pour être traités.

La plupart des implémentations proposées par le framework Collection utilise l'ordre FIFO (First In, First Out) mais l'ordre peut être différent.

La majorité des implémentations sont dans le package java.util.concurrent

14.6.1. L'interface Queue

L'interface Queue, ajoutée dans Java 5, définit les fonctionnalités pour une file d'objets (une collection qui permet de stocker des éléments avant leur traitement).

Une file propose trois opérations standard :

• ajouter un élément
• obtenir un élément
• consulter le prochain élément disponible : cette opération ne le retire pas de la collection

L'interface Queue propose des méthodes pour deux comportements différents en cas d'échec de ses opérations par exemple si la collection est vide ou pleine : le renvoie d'un booléen qui indique le succès de l'opération ou la levée d'une exception.

L'interface Queue définit plusieurs méthodes :

Les méthodes pour ajouter un élément à la fin de la collection ou obtenir l'élément au début de la collection peuvent être classées en deux catégories selon qu'elles lèvent une exception ou retournent une valeur spéciale en cas d'échec :

La méthode add() est héritée de l'interface collection : elle renvoie un booléen qui ne peut valoir false que si l'ajout est impossible car l'élément est déjà présent dans la collection. Dans les autres cas d'erreurs, la méthode add() doit lever une exception. C'est la différence avec la méthode offer() qui ne lève pas d'exceptions.

Il n'y a que la classe LinkedList qui permet l'ajout d'éléments null dans les implémentations de l'interface Queue proposées par l'API Collections.

14.6.2. La classe AbstractQueue

La classe abstraite AbstractQueue, ajoutée à Java 5.0, est la classe mère de la plupart des collections de type Queue. Ces collections ne doivent pas accepter de valeur null.

Elle implémente les interfaces Collection, Iterable et Queue.

L'API Collections propose plusieurs classes filles : ArrayBlockingQueue, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, PriorityBlockingQueue, PriorityQueue et SynchronousQueue.

14.6.3. L'interface TransferQueue

L'interface TransferQueue, ajoutée dans Java 7, définit les fonctionnalités d'une collection dans laquelle les producteurs peuvent attendre qu'un consommateur reçoive un élément avant de pouvoir ajouter un nouvel élément dans la collection.

L'interface TransferQueue hérite de l'interface BlockingQueue.

Lors de l'utilisation d'une collection de type TransfertQueue, il est possible de choisir si l'ajout d'un nouvel élément doit être bloquant en utilisant la méthode transfert() ou non bloquant en utilisant la méthode put().

Si des éléments sont déjà dans la collection l'invocation de la méthode transfer() sera bloquante jusqu'à ce que tous les éléments aient été consommés.

Java 7 ne propose qu'une seule implémentation de cette interface : LinkedTransfertQueue.

14.6.4. La classe LinkedTransferQueue

La classe LinkedTransferQueue, ajoutée dans Java 7, est une implémentation d'une collection de type TransferQueue qui utilise en interne une LinkedList.

Elle présente plusieurs caractéristiques :

• c'est une queue de type FIFO
• la taille de la collection n'est pas bornée
• elle utilise des opérations de type CAS pour être non bloquante

Elle hérite de la classe AbstractQueue et implémente l'interface TransferQueue. Elle implémente toutes les méthodes optionnelles des interfaces Collection et Iterator.

La classe LinkedTransferQueue possède deux constructeurs :

package fr.jmdoudoux.dej.collections;
      
import java.util.concurrent.LinkedTransferQueue;

public class TestLinkedTransferQueue {
  private static final int NB_TACHES = 5;
  public static void main(final String[] args) {
    final LinkedTransferQueue<MaTache> queue = new
      LinkedTransferQueue<MaTache>();
    
    final Thread producteur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= NB_TACHES; i++) {
          MaTache maTache = new MaTache(NB_TACHES - i, "Tache " + i);
          try {
            System.out.println("Ajout de " + maTache);
            queue.transfer(maTache);
          } catch (InterruptedException e) {
            e.printStackTrace();
          }
        }
      }
    }, "Producteur");
    
    Thread consommateur = new Thread(new Runnable() {
      @Override
      public void run() {
        while (true) {
          MaTache maTache = null;
          try {
            maTache = queue.take();
            System.out.println("Traitement de " + maTache);
          } catch (InterruptedException e) {
            e.printStackTrace();
          }
        }
      }
    }, "Consommateur");
    
    producteur.start();
    consommateur.start();
  }
}

Ajout de MaTache [priorite=4, description=Tache 1]
Traitement de MaTache [priorite=4, description=Tache 1]
Ajout de MaTache [priorite=3, description=Tache 2]
Ajout de MaTache [priorite=2, description=Tache 3]
Traitement de MaTache [priorite=3, description=Tache 2]
Traitement de MaTache [priorite=2, description=Tache 3]
Ajout de MaTache [priorite=1, description=Tache 4]
Traitement de MaTache [priorite=1, description=Tache 4]
Ajout de MaTache [priorite=0, description=Tache 5]
Traitement de MaTache [priorite=0, description=Tache 5]

Le temps d'exécution de la méthode size() n'est pas constant : toute la collection doit être parcourue pour déterminer le nombre d'éléments.

Les opérations groupées (addAll(), removeAll(), retainAll(), containsAll(), equals() et toArray()) n'offrent aucune garantie de s'exécuter de manière atomique. Par exemple, le parcours des éléments de la collection durant leur exécution peut ne voir qu'une partie des éléments impactés.

14.6.5. La classe PriorityQueue

La classe PriorityQueue, ajoutée à Java 1.5, hérite de la classe AbstractQueue. Les éléments de la collection sont ordonnés soit par leur ordre naturel soit par l'utilisation par la collection d'une instance de type Comparator fournie en paramètre du constructeur.

Si la collection utilise l'ordre naturel alors tous les éléments qu'elle contient doivent implémenter l'interface Comparable sinon une exception de type ClassCastException est levée.

Les opérations pour obtenir un élément (poll(), remove(), peek() et element()) renvoie le premier élément de la collection. Le premier élément de la collection est le plus petit selon l'ordre de classement des éléments par la collection.

Une collection de type PriorityQueue ne peut pas contenir d'élément null.

Elle implémente toutes les méthodes optionnelles des interfaces Collection et Iterator.

La taille d'une collection de type PriorityQueue n'est pas bridée mais elle possède une capacité interne initiale qui correspond à la taille du tableau dans lequel les éléments vont être stockés. La taille de ce tableau peut évoluer selon le nombre d'éléments contenu dans la collection.

La classe PriorityQueue possède plusieurs constructeurs :

L'obtention d'un élément se fait dans l'ordre dans lequel la collection gère ses éléments : soit en utilisant l'ordre naturel des objets (en implémentant l'interface Comparable) soit en utilisant l'instance de type Comparator fournie au constructeur qui a créé l'instance de la collection.

Une collection de type PriorityQueue accepte d'avoir des doublons ou des éléments qui possèdent la même priorité. Il n'y a aucune garantie sur l'ordre d'obtention de ces éléments : la seule solution est d'être suffisamment discriminant dans l'algorithme de comparaison utilisé par la collection pour déterminer l'ordre des éléments.

package fr.jmdoudoux.dej.collections;
      
import java.util.PriorityQueue;

public class TestPriorityQueue {
  public static void main(final String[] args) {
    PriorityQueue<MaTache> queue = new PriorityQueue<MaTache>();
    for (int i = 1; i <= 5; i++) {
      MaTache element = new MaTache(6 - i, "Tache" + i);
      System.out.println("insertion element " + element);
      queue.add(element);
    }
    
    System.out.println("taille de la queue=" + queue.size());
    for (int i = 1; i <= 5; i++) {
      MaTache element = queue.poll();
      System.out.println(element);
    }
  }
}

insertion element MaTache [priorite=5, description=Tache1]
insertion element MaTache [priorite=4, description=Tache2]
insertion element MaTache [priorite=3, description=Tache3]
insertion element MaTache [priorite=2, description=Tache4]
insertion element MaTache [priorite=1, description=Tache5]
taille de la queue=5
MaTache [priorite=1, description=Tache5]
MaTache [priorite=2, description=Tache4]
MaTache [priorite=3, description=Tache3]
MaTache [priorite=4, description=Tache2]
MaTache [priorite=5, description=Tache1]

Les Iterator de la classe PriorityQueue sont de type fail-fast. L'ordre de parcours des éléments avec un Iterator obtenu en invoquant la méthode iterator() n'est pas garanti.

La classe PriorityQueue n'est pas thread-safe : si plusieurs threads doivent pouvoir modifier cette collection, il faut utiliser la classe PriorityBlockingQueue.

14.6.6. La classe ConcurrentLinkedQueue

La classe ConcurrentLinkedQueue, ajoutée à Java 5, est une collection de type FIFO implémentée sous la forme d'une LinkedList.

La classe ConcurrentLinkedQueue possède plusieurs caractéristiques :

• l'ordre des éléments est de type FIFO (First In, First Out) : un nouvel élément est toujours ajouté à la fin de la collection et l'élément obtenu est le premier. Ainsi, le premier élément est celui qui est le plus ancien dans la collection et le dernier élément est celui qui est le plus récent dans la collection.
• la collection gère les accès concurrents qui sont faits sur elle
• elle ne permet pas l'ajout d'un élément null
• la taille de la collection n'est pas bridée.

L'implémentation de la classe ConcurrentLinkedQueue utilise un algorithme de type CAS pour gérer les opérations concurrentes.

La classe ConcurrentLinkedQueue possède deux constructeurs :

Cette classe implémente toutes les méthodes optionnelles de l'interface Queue et les instances de type Iterator obtenues implémentent toutes les méthodes optionnelles de l'interface Iterator.

Un Iterator obtenu à partir de la collection permet le parcours des éléments de la collection à un moment donné ou au moment de la création de l'Iterator. Ce parcours peut se faire en concurrence avec des modifications dans le contenu de la collection. Ce parcours ne lèvera jamais d'exceptions de type ConcurrentModificationException et un même élément ne pourra être obtenu qu'une seule fois lors du parcours.

Le temps d'exécution de la méthode size() n'est pas constant car elle doit parcourir les éléments pour déterminer le nombre d'éléments contenus dans la collection. La valeur renvoyée peut alors être inexacte si une modification du contenu de la collection est réalisée de manière concurrente lors de ce parcours.

L'exécution de manière atomique des opérations de type bulk comme addAll(), removeAll(), retainAll(), containsAll(), equals() et toArray() n'est pas garantie. Il est par exemple possible que le parcours avec un Iterator ne voit qu'une partie des éléments qui sont en cours d'ajout par la méthode addAll() dont l'exécution se fait de manière concurrente.

14.6.7. Les files utilisables par les deux bouts (Deque)

Le terme anglais deque vient de la contraction de «double ended queue». Une Deque est une file dans laquelle il est possible de réaliser des opérations à ses deux extrémités.

14.6.7.1. L'interface java.util.Deque

L'interface java.util.Deque, ajoutée dans Java 6, définit des fonctionnalités permettant l'ajout et la suppression d'éléments par les deux bouts dans une file.

L'interface Deque hérite de l'interface Queue. Une collection de type Deque diffère en plusieurs points d'une collection de type Queue :

• contrairement à une Queue dans laquelle un élément ne peut être ajouté qu'à la fin et consulté ou retiré du début de la liste, une Deque permet d'ajouter ou de retirer un élément en début ou en fin de liste
• utilisé comme une Queue, une Deque est toujours de type FIFO
• il n'est pas possible de gérer une priorité dans les éléments d'une Deque

L'interface définit des méthodes pour manipuler les éléments de la collection par les deux bouts : à chacune de ces actions, une méthode est proposée pour lever une exception ou renvoyer une valeur particulière en cas d'échec de son exécution.

Il n'est pas possible d'accéder à un élément particulier de la collection hormis le premier et le dernier.

Il n'est pas recommandé d'insérer la valeur null dans une collection de type Deque essentiellement parce que la valeur null est retournée par plusieurs méthodes pour indiquer qu'elles ont échouées.

Il est préférable d'utiliser les méthodes offerFirst() et offerLast() pour ajouter un élément car elles permettent de gérer les cas ou l'ajout n'est pas possible.

Les méthodes removeFirstOccurence() et removeLastOccurence() agissent comme la méthode remove() mais elles précisent le sens de la recherche de l'élément à supprimer.

Une collection de type Deque peut être utilisé dans le mode FIFO (First In First Out) pour agir comme une file : dans ce cas, les éléments sont insérés à la fin de la collection et sont retirés du début de la collection. Plusieurs méthodes de l'interface Queue sont équivalentes aux méthodes de l'interface Deque :

Une collection de type Deque peut être utilisée dans le mode LIFO (Last In First Out) pour agir comme une pile : dans ce cas, les éléments sont insérés et retirés uniquement en tête de la collection. Il est d'ailleurs recommandé d'utiliser une instance de type Deque plutôt qu'une collection de type Stack pour implémenter une pile.

Trois méthodes facilitent l'utilisation de la collection de type Deque comme une pile :

• la méthode pop() est équivalente à la méthode removeFirst()
• la méthode push() est équivalente à la méthode addFirst()
• la méthode peek() est équivalente à la méthode peekFirst()

L'API Collections propose plusieurs implémentations de l'interface Deque : ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

14.6.7.2. La classe ArrayDeque

La classe ArrayDeque, ajoutée dans Java 6, est une implémentation de l'interface Deque sous la forme d'un tableau dont les dimensions peuvent évoluer.

La classe ArrayDeque est l'implémentation de choix pour une file de type FIFO.

Les performances lors de l'ajout d'un élément en début ou en fin de la collection restent constantes.

La classe ArrayDeque présente plusieurs caractéristiques :

• elle n'est pas thread-safe : elle ne propose aucune gestion des accès concurrents
• elle n'impose pas de restriction sur sa taille et peut grossir selon les besoins
• elle ne permet pas d'ajouter un élément null

La classe ArrayDeque propose plusieurs constructeurs :

La classe ArrayDeque implémente toutes les méthodes optionnelles des interfaces Collection et Iterator.

La classe ArrayDeque peut remplacer la classe Stack pour une utilisation comme pile et la classe LinkedList pour une utilisation comme file.

Les Iterator obtenus à partir de la collection sont de type fail-fast : si une modification est effectuée dans le contenu de la collection durant le parcours avec l'Iterator alors une exception de type ConcurrentModificationException peut être levée sauf si cette modification est faite avec la méthode remove() de l'Iterator.

14.6.8. Les files d'attente

Il est parfois utile pour des questions de performances d'implémenter le modèle de conception producteur/consommateur (producer/consumer). Dans ce modèle, un ou plusieurs threads sont utilisés pour produire des objets et un ou plusieurs autres threads sont utilisés pour les consommer.

Avant Java 5, l'implémentation de ce modèle devait être faite manuellement, le plus souvent en utilisant les méthodes wait() et notify() sur un objet partagé en fonction de l'état de la file d'attente.

Le modèle producteur/consommateur définit trois acteurs :

• un producteur qui produit des éléments
• un consommateur qui consomme les éléments
• une file d'attente qui permet de stocker les éléments échangés

Ce modèle permet de réduire le couplage entre la production d'éléments et leur traitement. Une file d'attente est utilisée pour gérer les échanges des éléments entre le producteur et le consommateur.

Le modèle permet une coordination et une collaboration entre un ou plusieurs producteurs et un ou plusieurs consommateurs.

Ce modèle présente plusieurs avantages :

• le producteur et le consommateur sont développés séparément : ils ont juste besoin de connaître le type de l'élément échangé
• le producteur n'a pas besoin de connaitre le ou les consommateurs et inversement
• le producteur et le consommateur peuvent effectuer leurs traitements à différentes vitesses : la file d'attente se charge alors de faire le tampon
• la séparation des rôles permet de réduire le couplage en rendant le code de chacun plus facile à maintenir

La file d'attente gère les accès de manière concurrente et bloquante : si la file est pleine, alors l'opération d'ajout attend qu'un élément soit consommé et inversement si la file est vide, l'opération d'obtention d'un élément attend qu'un nouvel élément soit ajouté.

Ce modèle permet de gérer le flux des éléments et de s'adapter selon les besoins :

• en utilisant plusieurs consommateurs si le temps de traitement est plus long que le temps de création
• en utilisant plusieurs producteurs si le temps de création est plus long que le temps de traitement ou s'il existe plusieurs sources de création
• en utilisant plusieurs producteurs et plusieurs consommateurs

Il est important en cas de forte charge sur les échanges d'éléments de surveiller la capacité de la file d'attente pour éviter que celle-ci ne devienne un goulet d'étranglement. Comme les accès concurrents sont gérés par la file d'attente, il n'y a, par exemple, aucun inconvénient à ajouter un ou plusieurs autres consommateurs.

L'interface BlockingQueue facilite la mise en oeuvre de motifs de conception en proposant directement des méthodes bloquantes pour ajouter ou retirer des éléments de la file. L'API Collections propose plusieurs implémentations de l'interface BlockingQueue qui permettent de répondre à différents besoins.

14.6.8.1. L'interface java.util.concurrent.BlockingQueue

Une collection de type BlockingQueue stocke des éléments et gère la façon dont un élément est ajouté ou retiré éventuellement de manière bloquante lorsque la collection est pleine ou vide.

Les objets de type BlockingQueue permettent facilement d'échanger des objets entre des threads sans avoir à gérer explicitement la synchronisation des échanges par exemple en utilisant les méthodes wait() et notifyAll().

L'interface BlockingQueue, ajoutée dans Java 5, hérite des interfaces Collection, Queue et Iterable. Elle définit notamment des opérations :

• qui attendent que la collection soit non vide pour pouvoir obtenir un élément
• qui attendent que la collection possède l'espace nécessaire pour ajouter un nouvel élément

L'interface BlockingQueue propose pour certaines méthodes des paramètres pour indiquer un temps d'attente avant de retourner un échec plutôt que d'attendre indéfiniment lors de l'ajout ou l'obtention d'un élément dans la collection. Ceci peut permettre de gérer des situations de blocages.

La principale utilisation des implémentations de l'interface BlockingQueue est pour mettre en oeuvre le paradigme producer/consumer mais les méthodes de l'interface Collection sont aussi implémentées. Il est par exemple possible d'invoquer la méthode remove() même si son invocation devrait être rare.

L'interface BlockingQueue définit plusieurs méthodes :

Les méthodes put() et take() sont bloquantes :

• la méthode take() attend qu'un nouvel élément soit inséré dans la collection si celle-ci est vide
• la méthode put() attend qu'un élément soit enlevé si la collection est pleine

Les collections de type BlockingQueue ne permettent pas l'ajout d'un élément null : dans ce cas, une exception de type NullPointerException est levée.

Une collection de type BlockingQueue peut avoir :

• une taille maximale déterminée (bounded) : lorsque la capacité maximale est initialisée et que le nombre maximum d'objets est ajouté, l'invocation de la méthode put() pour ajouter un élément supplémentaire est bloquante
• une taille maximale non définie (unbounded) : la capacité maximale n'est pas initialisée, sa valeur est MAX_VALUE.

Les fonctionnalités de l'interface BlockingQueue sont prévues pour être exécutées dans un contexte concurrent (multithread). Les implémentations de type BlockingQueue sont thread-safe : il n'y a aucun soucis pour avoir plusieurs producteurs et plusieurs consommateurs sur la file.

L'interface BlockingQueue hérite de l'interface Queue pour ajouter le support d'opérations bloquantes. Les opérations d'ajout et d'obtention d'un élément dans la collection proposent quatre comportements :

• lever une exception en cas d'échec : la méthode lève une exception si l'opération n'a pas été immédiatement exécutée
• renvoyer une valeur particulière en cas d'échec : la méthode renvoie une valeur particulière si l'opération n'a pas été immédiatement exécutée
• bloquante : l'invocation de la méthode est bloquée indéfiniment tant que l'opération n'a pas pu être réalisée
• bloquante avec un timeout : l'invocation de la méthode est bloquée tant que l'opération n'a pas pu être réalisée ou que le délai du timeout n'est pas écoulé. La méthode renvoie une valeur qui permet de savoir si l'opération a été exécutée ou non

Attention : l'aspect bloquant de certaines fonctionnalités des implémentations de l'interface BlockingQueue peut induire des problèmes de contention et donc limiter la montée en charge.

Il n'est pas possible d'ajouter un élément null dans une collection de type BlockingQueue : l'invocation des méthodes add(), offer() et put() avec null en paramètre lève une exception de type NullPointerException.

Les implémentations de type BlockingQueue ne proposent en standard aucun mécanisme qui permettrait d'empêcher l'ajout de nouveaux éléments. Ainsi chaque thread qui consomme des éléments de la queue doit proposer son propre mécanisme pour s'arrêter. Le ou les threads qui ajoutent des éléments dans la collection doivent mettre en oeuvre ce mécanisme pour permettre l'arrêt des threads de consommation. Ce mécanisme peut par exemple mettre en oeuvre un élément particulier (poison object) qui, une fois consommé et identifié par le thread, lui permettra de se terminer proprement.

14.6.8.2. La classe java.util.concurrent.ArrayBlockingQueue

La classe ArrayBlockingQueue implémente l'interface BlockingQueue en utilisant un tableau d'objets.

La classe ArrayBlockingQueue utilise le mode de fonctionnement FIFO (First In First Out) : le premier élément de la file est le plus ancien et le dernier élément est le plus récent.

Son implémentation utilise un tableau ce qui lui impose une taille maximale. La capacité maximale d'un ArrayBlockingQueue doit donc être obligatoirement fixée en paramètre de l'invocation du constructeur et ne peut plus être changée ultérieurement.

package fr.jmdoudoux.dej.collections;
      
import java.util.Date;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ArrayBlockingQueueMain {
  private static final int NB_ELEMENTS = 5;

  public static void main(final String[] args) {
    final BlockingQueue<String> queue = new ArrayBlockingQueue<String>(2);
    Thread producteur = new Thread(new Runnable() {
      @Override 
      public void run() {
        for (int i = 1; i <= NB_ELEMENTS; i++) {
          String element = "Element " + i;
          try {
            System.out.println(new Date() + " insertion element " +
              element);
            queue.put(element);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Producteur");
   
    producteur.start();
    Thread consommateur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= NB_ELEMENTS; i++) {
          try {
            String element = queue.take();
            System.out.println(new Date() + " obtention element : " +
              element);
            Thread.sleep(2000);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Consommateur");
    
    consommateur.start();
  }
}

Mon Mar 11 18:27:54 CET 2013 insertion element Element 1
Mon Mar 11 18:27:54 CET 2013 insertion element Element 2
Mon Mar 11 18:27:54 CET 2013 insertion element Element 3
Mon Mar 11 18:27:54 CET 2013 obtention element : Element 1
Mon Mar 11 18:27:54 CET 2013 insertion element Element 4
Mon Mar 11 18:27:56 CET 2013 obtention element : Element 2
Mon Mar 11 18:27:56 CET 2013 insertion element Element 5
Mon Mar 11 18:27:58 CET 2013 obtention element : Element 3
Mon Mar 11 18:28:00 CET 2013 obtention element : Element 4
Mon Mar 11 18:28:02 CET 2013 obtention element : Element 5

14.6.8.3. La classe java.util.concurrent.LinkedBlockingQueue

La classe LinkedBlockingQueue implémente l'interface BlockingQueue en utilisant une LinkedList pour stocker les éléments en interne.

Il est possible de préciser une taille maximale pour le nombre d'éléments que peut contenir la collection : par défaut, la capacité maximale d'une LinkedBlockingQueue est fixée à la valeur Integer.MAX_VALUE sauf si une valeur différente est fournie en paramètre du constructeur.

Dans une LinkedBlockingQueue, les éléments sont stockés selon le mode FIFO (First In, First Out) : le premier élément de la liste est celui qui est dans la file depuis le plus longtemps. Le dernier élément de la liste est celui qui est arrivé le plus récemment dans la file.

L'avantage d'une LinkedBlockingQueue par rapport à une ArrayBlockingQueue est de ne pas être obligé de limiter la taille de la collection : les producteurs ne sont pas bloqués en attendant que la file se vide. Ceci peut cependant engendrer d'autres difficultés comme un manque de mémoire si la collection se remplit beaucoup plus vite qu'elle ne se vide.

Une LinkedBlockingQueue offre généralement de meilleurs performances qu'une ArrayBlockingQueue notamment si la file doit contenir de nombreux objets mais elle requiert plus d'objets en mémoire.

package fr.jmdoudoux.dej.collections;
      
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class LinkedBlockingQueueMain {
  public static void main(final String[] args) {
    final BlockingQueue<String> queue = new LinkedBlockingQueue<String>();
    Thread producteur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= 5; i++) {
          String element = "Element " + i;
          try {
            System.out.println("insertion element " + element);
            queue.put(element);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Producteur");
    producteur.start();
    
    Thread consommateur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= 5; i++) {
          try {
            String element = queue.take();
            System.out.println("element : " + element);
            Thread.sleep(2000);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Consommateur");
    
    consommateur.start();
  }
}

Les éléments sont consommés dans l'ordre FIFO.

insertion element Element 1
insertion element Element 2
insertion element Element 3
insertion element Element 4
insertion element Element 5
element : Element 1
element : Element 2
element : Element 3
element : Element 4
element : Element 5

14.6.8.4. La classe java.util.concurent.PriorityBlockingQueue

La classe PriorityBlockingQueue est une collection de type Queue qui renvoie en premier les éléments les plus prioritaires.

La classe PriorityBlockingQueue implémente l'interface BlockingQueue, Queue, Collection et Iterable.

Elle implémente toutes les méthodes optionnelles des interfaces Collection et Iterator.

Le parcours des éléments en utilisant la méthode iterator() se fait dans un ordre quelconque.

Par défaut, la capacité maximale d'un PriorityBlockingQueue est fixée à la valeur Integer.MAX_VALUE sauf si une valeur différente est fournie en paramètre du constructeur

Il n'est pas possible d'ajouter un élément null dans la collection.

La classe PriorityBlockingQueue stocke ses éléments de manière ordonnée en utilisant une instance de Comparator fournie en paramètre du constructeur ou à défaut en utilisant la méthode de l'interface Comparable implémentée par les éléments de la collection.

Si aucune instance de Comparator n'est fournie en paramètre du constructeur, alors les éléments ajoutés dans la collection doivent implémenter l'interface Comparable sinon une exception de type ClassCastException est levée.

La classe PriorityBlockingQueue n'impose rien concernant des éléments qui possèdent la même priorité : c'est l'implémentation de la méthode compareTo() qui peut gérer ce cas selon les besoins.

package fr.jmdoudoux.dej.collections;

public class MaTache implements Comparable<MaTache> {
  private final int    priorite;
  private final String description;

  public MaTache(final int priorite, final String description) {
    this.priorite = priorite;
    this.description = description;
  }

  @Override
  public int compareTo(final MaTache tache) {
    Integer prioriteCourante = getPiorite();
    Integer prioriteAutre = tache.getPiorite();
    if (prioriteCourante != prioriteAutre) {
      return prioriteCourante.compareTo(prioriteAutre);
    } else {
      return getDescription().compareTo(tache.getDescription());
    }
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    MaTache other = (MaTache) obj;
    if (description == null) {
      if (other.description != null) {
        return false;
      }
    } else if (!description.equals(other.description)) {
      return false;
    }
    if (priorite != other.priorite) {
      return false;
    }
    return true;
  }

  public String getDescription() {
    return description;
  }

  public int getPiorite() {
    return priorite;
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result
        + ((description == null) ? 0 : description.hashCode());
    result = prime * result + priorite;
    return result;
  }

  @Override public String toString() {
    return "MaTache [priorite=" + priorite + ", description=" + description
        + "]";
  }
}

La classe PriorityBlockingQueue agit comme la classe PriorityQueue avec une gestion des accès concurrents.

package fr.jmdoudoux.dej.collections;
      
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueMain {
  public static void main(final String[] args) {
    final BlockingQueue<MaTache> queue = new PriorityBlockingQueue<MaTache>();
    Thread producteur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= 5; i++) {
          MaTache element = new MaTache(6 - i, "Tache " + i);
          try {
            System.out.println("insertion element " + element);
            queue.put(element);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
        System.out.println("taille de la queue=" + queue.size());
      }
    }, "Producteur");

    producteur.start();
    try {
      // on attend que tous les éléments soient insérés

      // uniquement pour vérifier l'ordre d'obtention

      producteur.join();
    } catch (InterruptedException e) {
      e.printStackTrace();
    }
    MaTache elt = queue.peek();
    System.out.println("peek=" + elt);

    Thread consommateur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= 5; i++) {
          try {
            MaTache element = queue.take();
            System.out.println("element : " + element);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Consommateur");
    consommateur.start();
  }
}

insertion element MaTache [priorite=5,
description=Tache 1]
insertion element MaTache [priorite=4, description=Tache 2]
insertion element MaTache [priorite=3, description=Tache 3]
insertion element MaTache [priorite=2, description=Tache 4]
insertion element MaTache [priorite=1, description=Tache 5]
taille de la queue=5 peek=MaTache [priorite=1, description=Tache 5]
element : MaTache [priorite=1, description=Tache 5]
element : MaTache [priorite=2, description=Tache 4]
element : MaTache [priorite=3, description=Tache 3]
element : MaTache [priorite=4, description=Tache 2]
element : MaTache [priorite=5, description=Tache 1]

Si l'on supprime le temps d'attente de la fin du thread de production, les tâches obtenues tiennent toujours compte de l'ordre des éléments présents dans la collection au moment où l'on souhaite obtenir un élément.

peek=null
insertion element MaTache [priorite=5, description=Tache 1]
insertion element MaTache [priorite=4, description=Tache 2]
element : MaTache [priorite=5, description=Tache 1]
element : MaTache [priorite=4, description=Tache 2]
insertion element MaTache [priorite=3, description=Tache 3]
insertion element MaTache [priorite=2, description=Tache 4]
insertion element MaTache [priorite=1, description=Tache 5]
element : MaTache [priorite=3, description=Tache 3]
taille de la queue=1 element : MaTache [priorite=1, description=Tache 5] 
element : MaTache [priorite=2, description=Tache 4]

14.6.8.5. La classe java.util.concurrent.DelayQueue

La classe DelayQueue, ajoutée à Java 1.5, permet de conserver un élément jusqu'à l'expiration d'un délai.

La classe DelayQueue implémente l'interface BlockingQueue

Les éléments insérés dans une DelayQueue doivent implémenter l'interface java.util.concurrent.Delayed. Cette interface ne définit qu'une seule méthode :

Si la valeur retournée par la méthode getDelay() est négative ou nulle alors le délai est considéré comme expiré et l'élément est immédiatement retirable. Le paramètre de type TimeUnit permet de préciser l'unité de temps dans laquelle la valeur doit être retournée.

L'interface Delayed hérite de l'interface Comparable<Delayed>.

Chaque implémentation doit donc redéfinir la méthode compareTo() qui est utilisée par le DelayQueue pour déterminer l'ordre de renvoie d'un élément.

package fr.jmdoudoux.dej.collections;
      
import java.util.Date;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

public class MonElementDelayed implements Delayed {
  private final String donnees;
  private final long   momentDeLiberation;
  public MonElementDelayed(final String donnees, final long delai) {
    this.donnees = donnees;
    this.momentDeLiberation = System.currentTimeMillis() + delai;
  }

  @Override
  public int compareTo(final Delayed o) {
    int resultat = -1;
    if (o instanceof MonElementDelayed) {
      MonElementDelayed med = (MonElementDelayed) o;
      if (this.momentDeLiberation < med.momentDeLiberation) {
        resultat = -1;
      } else {
        if (this.momentDeLiberation > med.momentDeLiberation) {
          resultat = 1;
        } else {
          resultat = 0;
        }
      }
    }
    return resultat;
  }

  @Override
  public boolean equals(final Object obj) {
    if (this == obj) {
      return true;
    }
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    MonElementDelayed other = (MonElementDelayed) obj;
    if (donnees == null) {
      if (other.donnees != null) {
        return false;
      }
    } else if (!donnees.equals(other.donnees)) {
      return false;
    } 
    if (momentDeLiberation != other.momentDeLiberation) {
      return false;
    }
    return true;
  }

  @Override
  public long getDelay(final TimeUnit unit) {
    long diff = momentDeLiberation - System.currentTimeMillis();
    return unit.convert(diff, TimeUnit.MILLISECONDS);
  }

  @Override
  public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((donnees == null) ? 0 : donnees.hashCode());
    result = prime * result
        + (int) (momentDeLiberation ^ (momentDeLiberation >>> 32));
    return result;
  }

  @Override
  public String toString() {
    return "donnees='" + donnees + "', momentDeLiberation="
        + new Date(momentDeLiberation);
  }
}

Attention : l'implémentation de la méthode compareTo() doit tenir compte du délai restant lié à l'objet. Cette implémentation nest donc pas cohérente avec la méthode equals() ce qui exclut l'utilisation des objets de type Delayed dans certaines collections notamment celles de type SortedXXX.

Les implémentations de plusieurs méthodes de la classe DelayQueue assurent les comportements spécifiques de cette collection :

La taille d'un DelayQueue ne peut pas être limitée : l'ajout d'un nouvel élément en utilisant la méthode put() n'est donc jamais bloquante. Par contre, l'invocation de la méthode take() est bloquante tant que le délai d'attente d'un élément n'est pas atteint (dans ce cas, la valeur retournée par la méthode getDelay() est inférieure ou égale à zéro).

Si plusieurs éléments ont leur délai d'attente atteint lors de l'invocation de la méthode take() alors celle-ci renvoie l'élément dont le délai d'attente est le plus dépassé.

package fr.jmdoudoux.dej.collections;
      
import java.util.Date;
import java.util.concurrent.DelayQueue;

public class DelayQueueMain {
  public static void main(final String[] args) {
    DelayQueue<MonElementDelayed> queue = new
      DelayQueue<MonElementDelayed>();
    for (int i = 1; i <= 5; i++) {
      MonElementDelayed element = new MonElementDelayed("Message" + i, 2000 * i);
      System.out.println("insertion element " + element);
      queue.put(element);
    }
   
    System.out.println("taille de la queue=" + queue.size());
    try {
      for (int i = 1; i < 5; i++) {
        MonElementDelayed element = queue.take();
        System.out.println("element obtenu le" + new Date());
        System.out.println("  " + element);
      }
    } catch (InterruptedException ie) {
      ie.printStackTrace();
    }
  }
}

insertion element donnees='Message1',
momentDeLiberation=Fri Mar 01 22:34:04 CET 2013
insertion element donnees='Message2', momentDeLiberation=Fri Mar 01 22:34:06 CET 2013
insertion element donnees='Message3', momentDeLiberation=Fri Mar 01 22:34:08 CET 2013
insertion element donnees='Message4', momentDeLiberation=Fri Mar 01 22:34:10 CET 2013
insertion element donnees='Message5', momentDeLiberation=Fri Mar 01 22:34:12 CET 2013
taille de la queue=5 element obtenu leFri Mar 01 22:34:04 CET 2013
  donnees='Message1', momentDeLiberation=Fri Mar 01 22:34:04 CET 2013
element obtenu leFri Mar 01 22:34:06 CET 2013
  donnees='Message2', momentDeLiberation=Fri Mar 01 22:34:06 CET 2013
element obtenu leFri Mar 01 22:34:08 CET 2013
  donnees='Message3', momentDeLiberation=Fri Mar 01 22:34:08 CET 2013
element obtenu leFri Mar 01 22:34:10 CET 2013
  donnees='Message4', momentDeLiberation=Fri Mar 01 22:34:10 CET 2013

14.6.8.6. La classe java.util.concurrrent.SynchronousQueue

La classe SynchronousQueue, ajoutée à Java 1.5 implémente l'interface BlockingQueue pour proposer un moyen facile d'échanger un élément entre deux threads et de synchroniser ces échanges.

Elle ne possède pas de capacité de stockage : elle ne peut contenir qu'un seul élément au plus. L'insertion d'un nouvel élément en invoquant la méthode put() est bloquée jusqu'à ce que l'élément inséré soit retiré. De façon similaire, si la collection est vide alors l'invocation de la méthode take() reste bloquée jusqu'à ce qu'un nouvel élément soit ajouté dans la collection.

package fr.jmdoudoux.dej.collections;

import java.util.concurrent.BlockingQueue;

public class MonProducer implements Runnable {
  private final BlockingQueue<String> queue;
  
  public MonProducer(final BlockingQueue<String> queue) {
    this.queue = queue;
  }
 
  @Override
    public void run() {
      try {
      for (int i = 1; i < 6; i++) {
        queue.put("Message" + i);
        System.out.println("Producer envoie Message" + i);
      }
      queue.put("Stop");
      } catch (InterruptedException ie) {
      ie.printStackTrace();
    }
  }
}

package fr.jmdoudoux.dej.collections;

import java.util.concurrent.BlockingQueue;

public class MonConsumer implements Runnable {
 
  private final BlockingQueue<String> queue;
 
  public MonConsumer(final BlockingQueue<String> queue) {
    this.queue = queue;
  }
 
  @Override
    public void run() {
      try {
        String msg = null;
        boolean stop = false;
        while (!stop) {
          msg = queue.take();
          if (msg.equals("Stop")) {
            stop = true;
          } else {
            Thread.sleep(2000);
            System.out.println("Consumer traite " + msg);
          }
        }
     } catch (InterruptedException ie) {
       ie.printStackTrace();
     }
  }
}

package fr.jmdoudoux.dej.collections;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.SynchronousQueue;

public class SynchronousQueueMain {
 
  public static void main(final String[] args) {
    BlockingQueue<String> queue = new SynchronousQueue<String>();
      (new Thread(new MonProducer(queue))).start();
   
    try {
      Thread.sleep(1000);
    } catch (InterruptedException ie) {
      ie.printStackTrace();
    }
   
    (new Thread(new MonConsumer(queue))).start();
 
  }
}

Producer envoie Message1
Consumer traite Message1
Producer envoie Message2
Consumer traite Message2
Producer envoie Message3
Consumer traite Message3
Producer envoie Message4
Consumer traite Message4
Producer envoie Message5
Consumer traite Message5

Remarque : les temps d'attente dans l'exemple sont uniquement présents pour faciliter la compréhension du fonctionnement de la classe SynchronousQueue.

14.6.8.7. L'interface java.util.concurrent.BlockingDeque

L'interface BlockingDeque, ajoutée à Java 6.0, implémente les interfaces Deque et BlockingQueue avec des opérations bloquantes :

• qui attendent que la collection soit non vide pour pouvoir obtenir un élément
• qui attendent que la collection possède l'espace nécessaire pour ajouter un nouvel élément

L'utilisation d'un BlockingDeque est particulièrement intéressante :

• si un thread peut à la fois produire et consommer des éléments dans une file d'attente.
• si plusieurs threads doivent pouvoir ajouter ou retirer des éléments au début ou à la fin de la collection

Le comportement des méthodes de l'interface BlockingQueue d'un BlockingDeque est de respecter le mode de fonctionnement prévu par cette interface

L'interface BlockingDeque propose quatre comportements différents pour les opérations d'ajout, de retrait et de consultation d'un élément dans la collection si celles-ci ne peuvent pas être réalisées immédiatement :

• lever une exception si l'opération n'est pas réalisable immédiatement
• renvoie une valeur particulière si l'opération n'est pas réalisable immédiatement
• l'invocation de la méthode est bloquée jusqu'à ce que l'opération soit réalisée
• l'invocation de la méthode est bloquée jusqu'à ce que l'opération soit réalisée ou qu'un timeout soit atteint. La méthode renvoie une valeur qui précise si l'opération a été exécutée

L'API Collections propose une seule implémentation de l'interface BlockingDeque : la classe java.util.concurrent.LinkedBlockingDeque.

14.6.8.8. La classe LinkedBlockingDeque

La classe LinkedBlockingDeque, ajoutée à Java 6.0, implémente l'interface BlockingDeque.

La classe LinkedBlockingDeque utilise en interne une liste chaînée de type LinkedList pour stocker ses éléments.

Un des constructeurs de la classe LinkedBlockingDeque attend en paramètre une valeur qui précise la capacité maximale de la collection.

package fr.jmdoudoux.dej.collections;
      
import java.util.Date;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;

public class TestLinkedBlockingDequeMain {
  private static final int NB_ELEMENTS = 5;
  public static void main(final String[] args) {
    // final BlockingDeque<String> queue = new LinkedBlockingDeque<String>();

    final BlockingDeque<String> queue = new LinkedBlockingDeque<String>(2);
    Thread producteur = new Thread(new Runnable() {
      @Override
      public void run() {
        for (int i = 1; i <= NB_ELEMENTS; i++) {
          String element = "Element " + i;
          try {
            System.out.println(new Date() + " insertion element " + element);
            queue.putFirst(element);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Producteur");
    
    producteur.start();
    Thread consommateur = new Thread(new Runnable() {
      @Override 
      public void run() {
        for (int i = 1; i <= NB_ELEMENTS; i++) {
          try {
            String element = queue.takeLast();
            System.out.println(new Date() + " obtention element : " + element);
            Thread.sleep(2000);
          } catch (InterruptedException ie) {
            ie.printStackTrace();
          }
        }
      }
    }, "Consommateur");
   
    consommateur.start();
  }
}

Fri Mar 15 21:06:34 CET 2013 insertion element
Element 1 Fri Mar 15 21:06:34 CET 2013 insertion element
Element 2 Fri Mar 15 21:06:34 CET 2013 insertion element
Element 3 Fri Mar 15 21:06:34 CET 2013 obtention element :
Element 1 Fri Mar 15 21:06:34 CET 2013 insertion element
Element 4 Fri Mar 15 21:06:36 CET 2013 insertion element
Element 5 Fri Mar 15 21:06:36 CET 2013 obtention element :
Element 2 Fri Mar 15 21:06:38 CET 2013 obtention element :
Element 3 Fri Mar 15 21:06:40 CET 2013 obtention element :
Element 4 Fri Mar 15 21:06:42 CET 2013 obtention element :
Element 5

Les performances d'insertion et de suppression d'un élément sont similaires à celles d'une collection de type LinkedBlockingQueue puisqu'elles utilisent toutes les deux une LinkedList pour la gestion de leurs éléments.

14.6.9. Le choix d'une implémentation de type Queue

Plusieurs implémentations de type Queue et BlockingQueue sont particulièrement utiles pour gérer des échanges d'objets entre threads par exemple en mettant en oeuvre le motif de conception producteur/consommateur.

Plusieurs implémentations de type Queue ne peuvent être utilisées que pour des cas bien particuliers :

• si la collection doit gérer ses éléments par ordre de priorité et que les accès concurrents n'ont pas besoin d'être gérés alors il faut utiliser la classe PriorityQueue
• si la collection doit gérer ses éléments par ordre de priorité et que les accès concurrents ont besoin d'être gérés alors il faut utiliser la classe PriorityBlockingQueue
• si la collection doit gérer un élément avant qu'un élément ne soit retirable alors il faut utiliser la classe DelayQueue
• la classe SynchronousQueue est particulièrement utile pour échanger un objet entre deux threads (elle n'a aucune capacité de stockage)

Le choix d'une implémentation d'une collection de type Queue pour un usage général doit se faire selon les fonctionnalités qu'elle doit supporter :

• la gestion des accès concurrents ou non
• les opérations sont bloquantes ou non
• la taille de la collection est bornée ou non

Si la collection de type Queue n'a pas besoin de gérer d'accès concurrents alors il faut utiliser la classe LinkedList.

Si les accès concurrents doivent être gérés alors il faut utiliser la classe ConcurrentLinkedList.

Si la taille de la collection de type Queue doit être bornée, alors il faut utiliser la classe ArrayBlockingQueue.

14.7. Le tri des collections

L'ordre de tri est défini grâce à deux interfaces :

• Comparable
• Comparator

14.7.1. L'interface Comparable

Tous les objets qui doivent définir un ordre naturel utilisé par le tri d'une collection doivent implémenter cette interface.

Cette interface ne définit qu'une seule méthode : int compareTo(Object).

Cette méthode doit renvoyer :

• une valeur entière négative si l'objet courant est inférieur à l'objet fourni
• une valeur entière positive si l'objet courant est supérieur à l'objet fourni
• une valeur nulle si l'objet courant est égal à l'objet fourni

Les classes wrappers, String et Date implémentent cette interface.

14.7.2. L'interface Comparator

Cette interface représente un ordre de tri quelconque. Elle est utile pour permettre le tri d'objets qui n'implémentent pas l'interface Comparable ou pour définir un ordre de tri différent de celui défini avec Comparable ( l'interface Comparable représente un ordre naturel : il ne peut y en avoir qu'un)

Cette interface ne définit qu'une seule méthode : int compare(Object, Object).

Cette méthode compare les deux objets fournis en paramètres et renvoie :

• une valeur entière négative si le premier objet est inférieur au second
• une valeur entière positive si le premier objet est supérieur au second
• une valeur nulle si les deux objets sont égaux

14.8. Les algorithmes

La classe Collections propose plusieurs méthodes statiques pour effectuer des opérations sur des collections. Ces traitements sont polymorphiques car ils demandent en paramètre un objet qui implémente une interface et retournent une collection.

Si la méthode sort(List) est utilisée, il faut obligatoirement que les éléments inclus dans la liste implémentent tous l'interface Comparable sinon une exception de type ClassCastException est levée.

La classe Collections propose aussi plusieurs méthodes pour obtenir une version multithread ou non modifiable des principales interfaces des collections : Collection, List, Map, Set, SortedMap, SortedSet

• XXX synchronizedXXX(XXX) pour obtenir une version multithread des objets implémentant l'interface XXX
• XXX unmodifiableXXX(XXX) pour obtenir une version non modifiable des objets implémentant l'interface XXX

import java.util.*;

public class TestUnmodifiable{
    public static void main(String args[]) {
      List list = new LinkedList();

      list.add("1");
      list.add("2");
      list = Collections.unmodifiableList(list);

      list.add("3");
    }
}

C:\>java TestUnmodifiable
Exception in thread "main" java.lang.UnsupportedOperationException
        at java.util.Collections$UnmodifiableCollection.add(Unknown Source)
        at TestUnmodifiable.main(TestUnmodifiable.java:13)

L'utilisation d'une méthode synchronizedXXX() renvoie une instance de l'objet qui supporte la synchronisation pour les opérations d'ajout et de suppression d'éléments. Pour le parcours de la collection avec un objet Iterator, il est nécessaire de synchroniser le bloc de code utilisé pour le parcours. Il est important d'inclure aussi dans ce bloc l'appel à la méthode pour obtenir l'objet de type Iterator utilisé pour le parcours.

import java.util.*;

public class TestSynchronized{
    public static void main(String args[]) {
      List maList = new LinkedList();

      maList.add("1");
      maList.add("2");
      maList.add("3");
      maList = Collections.synchronizedList(maList);

      synchronized(maList) {
          Iterator i = maList.iterator();
          while (i.hasNext())
               System.out.println(i.next());
          }
     }
}

14.9. Les exceptions du framework

L'exception de type UnsupportedOperationException est levée lorsqu'une opération optionnelle n'est pas supportée par l'objet qui gère la collection.

L'exception ConcurrentModificationException est levée lors du parcours d'une collection avec un objet Iterator et que cette collection subit une modification structurelle.

78 commentaires