Les collections

Chapitres traités    Les tableaux pour gérer des ensembles d'éléments Les collections pour gérer des ensembles d'objets Les interfaces de collection Les collections concrètes Listes chaînées - java.util.LinkedList Les vecteurs (tableaux dynamiques) - Listes de tableaux - ArrayList Ensembles d'objets uniques - HashSet, TreeSet, EnumSet et LinkedHashSet Comparaison d'objets Les queues - ArrayDeque, LinkedList et PriorityQueue Dictionnaires - Cartes - Tables associatives La structure des collections Les algorithmes

Nous allons ici faire l'étude du regroupement mémoire d'éléments de même type que nous appelons collections. Nous en profiterons pour revoir les tableaux classiques pour mieux cerner l'intérêt de proposer d'autres alternatives.

Les collections que vous choisirez peut engendrer une grande différence, à la fois au moment de l'implémentation des méthodes et en termes de performances. Faut-il rechercher rapidement parmi des miliers (voire des millions) d'éléments triés ? Devez-vous rapidement insérer et supprimer des éléments au milieu d'une suite triée ? Devez-vous établir des associations entre clés et valeurs ?

Cette étude met en évidence la façon dont la bibliothèque Java peut vous aider à trouver une structure de données adaptée à une programmation sérieuse, et par là, choisir la collection équivalente.

Attention : afin de bien maîtriser les différents concepts mis en oeuvre sur ces collections, il est important de connaître la généricité qui est expliquée dans l'étude précédente.

Les tableaux pour gérer des ensembles d'éléments

Un tableau (array en anglais) est le type d'objet le plus simple à programmer pour gérer un ensemble d'éléments :

1. Les éléments d'un tableau sont tous du même type.
2. Ces éléments peuvent être des données de type primitif ou des références d'une classe donnée.
3. La taille d'un tableau est déterminée lors de sa création et ne peut être modifiée par la suite.
4. Le tableau est considéré comme un objet et possède un attribut public length qui donne la taille du tableau.
5. La position d'un élément dans un tableau est déterminée par un indice entier.
6. L'indice du prmier élément du tableau est toujours 0 et l'indice du dernier élément d'un tableau est le nombre d'éléments moins 1.
7. La JVM vérifie à l'exécution que les indices utilisés pour accéder à un élément figurent bien dans l'intervalle autorisé et que le type d'un objet est compatible avec le type du tableau.

Les tableaux permettent donc de regrouper une suite de variables de même type. Chaque élément du tableau est une variable que vous pouvez utiliser comme n'importe quelle variable de ce type. Il est possible de définir des tableaux pour les types primaires ou les classes. Cependant, tous les éléments doivent être du même type. En Java, les tableaux sont des objets.

Pour pouvoir utiliser un tableau, vous devez respecter les trois étapes suivantes :

1. Déclarer une variable pour référencer le tableau.
2. Créer un objet de type tableau en initialisant la référence à ce tableau.
3. Utiliser et manipuler les éléments de ce tableau.

Déclaration d'un tableau

Effectivement, comme un tableau est un objet, la création d'un tableau commence par la mise en place de sa référence afin de pointer ultérieurement vers l'objet tableau lui-même. Voici comment se déclare une telle référence t de type tableau d'entiers :

int t[];

Elle précise que t est destiné à contenir la référence à un tableau d'entiers. Vous constatez qu'aucune dimension ne figure dans cette déclaration et, pour l'instant, aucune valeur n'a été attribuée à t. Comme toute référence, une référence de type tableau peut être égale à null ou désigner un objet tableau.

Voici quelques exemples de déclarations :

int t[]; // peut s'écrire int[] t ;
int [] t1, t2; // t1 et t2 sont des références à des tableaux d'entiers
int t3[], t4[]; // écritures équivalentes
int t5[], n, t6[]; // t5 et t6 sont des tableaux d'entiers, n est entier
Point tp[]; // tp est une référence à un tableau d'objets de type Point
Point a, tp[]; // a est une référence à un objet de type Point, 
tp est une référence à un tableau d'objets de type Point
int tab[5]; // erreur : nous ne pouvons pas indiquer de dimension ici.

Création et initialisation d'un tableau

Nous pouvons effectuer la création et l'initialisation d'un tableau de trois façons différentes :

Création par l'opérateur new

Après avoir déclaré la variable tableau, il faut allouer les éléments de ce tableau. On utilise pour ce faire l'opérateur new. Vous avez déjà mis en oeuvre cet opérateur pour créer des objets. A ce niveau, il est obligatoire de préciser le nombre d'éléments du tableau. Ces derniers sont initialisés automatiquement en fonction du type de tableau (0 pour les numériques, '\0' pour les caractères, false pour les boolean et null pour les éléments de type objet).

package test;

import java.awt.*;

public class Main {
  public static void main(String[] args) {
    int[] tabEntier = new int[30]; 
    // tableau de 30 entiers de valeur nulle
    String[] semaine = new String[7];
    /* tableau de 7 références vers des objets
     *  de type String. Par la suite, il sera nécessaire
     * pour chaque élément du tableau de 
     * créer un objet de type String
    */
  }
}

Utilisation d'un initialiseur

Lors de la déclaration d'une référence, il est possible de fournir la valeur à chacune des cases du tableau. Il suffit de donner la liste entre accolades sans utiliser l'opérateur new. Java se sert du nombre de valeurs figurant dans l'initialiseur pour en déduire la taille du tableau à créer.

int[] t = {1, 3, 5, 7}; 
/* création d'un tableau de 4 entiers de
  * valeurs respectives 1, 3, 5, 7 et place
  * la référence dans t. Elle remplace les 
  * instructions suivantes :
*/
int t[];
t = new int[4];
t[0]=1;  t[1]=3;  t[2]=5; t[3]=7;

tableau anonyme

A tout moment en utilisant l'opérateur new et une liste entre accolades de valeurs. Cette notation est très pratique pour passer un tableau en paramètres à une méthode sans qu'il faille créer une variable locale pour ce tableau. En imaginant la déclaration de la méthode suivante :

afficheSemaine(String[] joursSemaine);

Voici un exemple de tableau anonyme que nous pouvons passer en argument de la méthode :

afficheSemaine(new String[] {"Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche"});

Cette écriture est à la fois un raccourci et évite d'utiliser une variable intermédiaire :

String[] jours = {"Lundi", "Mardi", "Mercredi", "Jeudi", "Vendredi", "Samedi", "Dimanche"} ;
afficheSemaine(jours);

Utilisation d'un tableau

Nous pouvons manipuler un élément de tableau comme nous le ferions avec n'importe quelle variable ou n'importe quel objet de ses éléments. On désigne un élément particulier en plaçant entre crochets, à la suite du nom du tableau, une expression entière nommée indice indiquant sa position. Le premier élément correspond à l'indice 0 (et non 1).

int t[] = new int[5], a; 
t[0] = 15; // place la valeur 15 dans le premier élément du tableau
t[2]++; // incrémente de 1 le troisième élément de t
a = t[4]+23; // utilisation dans un calcul
t[1] = t[0]+5; // initialisation d'un élément à partir d'un autre
t[a-20] = -85; // calcul sur l'indice

Affectation de tableaux

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    String[] liste = {"Salut", "Bonjour"};
    String[] copie = new String[2];
    System.arraycopy(liste, 0, copie, 0, 2);
    Arrays.sort(liste);    
    boolean test = Arrays.equals(copie, liste);
  }
}

Java permet aussi de manipuler globalement des tableaux, par le biais d'affectations de leurs références.

Exécutons maintenant l'affectation :

t1 = t2; // la référence contenue dans t2 est recopiée dans t1

Nous aboutissons à la situation présentée ci-dessous. Dorénavant, t1 et t2 désigne le même tableau.

Ainsi, avec :

t1[1] = 5;
System.out.println (t2[1]);

on obtiendra l'affichage de la valeur 5, et non 11.

Si l'objet que constitue le tableau de trois entiers anciennement désigné par t1 n'est plus référencé par ailleurs, il deviendra candidat au ramasse-miettes.

Il est très important de noter que l'affectation de références de tableaux n'entraine aucune recopie des valeurs des éléments du tableau. On retrouve exactement le même phénomène que pour l'affectation d'objets.

Nombre d'éléments d'un tableau

Pour connaître le nombre d'éléments d'un tableau, vous pouvez utiliser l'attribut public length. Cet attribut peut être utilisé pour tous les types de tableaux. Considérez le code suivant :

int tab[] = new int [10];
int taille = tab.length; // taille est égal à 10

Après avoir déclaré un tableau, utilisez length pour récupérer le nombre d'éléments du tableau (ici 10).

Le mot length désigne en quelque sorte un attribut du tableau, attribut que l'on peut d'ailleurs uniquement lire ; ce n'est pas un attribut au même titre que les attributs d'une classe. Remarquons qu'il n'y a pas d'autre attribut pour une variable de type tableau.

Manipuler un tableau d'objets

Attention : Pour définir un tableau d'objets, il faut commencer par définir un tableau de références, puis, pour chaque référence, créer l'objet associé. Un tableau d'objets est en fait un tableau de références, et chaque référence pointe vers l'objet associé.

Le résultat est le suivant :

Point : 1, 2
Point : 4, 5
Point : 8, 9

Il est possible d'avoir une écriture plus concise de la classe TabPoint en utilisant l'initialiseur de tableau.

Afficher un tableau dans la sortie standard

Il existe une méthode très très simple pour afficher toutes les valeurs d'un tableau dans la sortie standard, et ce grâce à la méthode toString() de la classe Arrays. L'appel Arrays.toString(tableau) renvoie une chaîne de caractères contenant les éléments du tableau, insérés entre crochets et séparés par des virgules :

System.out.println(Arrays.toString(tableau)); // affichepar exemple à l'écran "[2, 3, 5, 7, 11, 13]"

Copie des tableaux

Il est possible de copier une variable tableau dans une autre, mais attention, comme nous l'avons vu plus haut, les deux variables feront alors référence au même tableau :

int[ ] suite = {17, 19, 23, 29, 31, 37};
int[ ] entier = suite;
entier[3] = 12; // suite[3] vaut maintenant 12

• Si vous voulez effectivement copier toutes les valeurs d'un tableau dans un autre, il faut employer la méthode copyTo() de la classe Arrays :

  int[ ] suite = {17, 19, 23, 29, 31, 37};
  int[ ] entier = Arrays.copyOf(suite, suite.length);

• Le second paramètre correspond à la longueur du nouveau tableau. Cette méthode est souvent employée pour augmenter la taille d'un tableau :

  int[ ] suite = {17, 19, 23, 29, 31, 37};
  suite = Arrays.copyOf(suite, 2 * suite.length);

  Les autres éléments sont remplis de 0 si le tableau contient des nombres, false si le tableau contient des valeurs booléennes. A l'inverse, si la longueur est inférieure à celle du tableau initial, seules les valeurs initiales sont copiées.

Tri d'un tableau

Si vous voulez trier un tableau de nombres, utilisez une des méthodes sort() de la classe Arrays :

int[ ] nombre = new int[100];
...
Arrays.sort(nombre);

Cette méthode utilise une version adaptée de l'algorithme QuickSort qui se révèle très efficace sur la plupart des ensembles de données.
§

Parcourt et affichage d'un tableau multidimentionnel

Une boucle "for each" ne traverse pas automatiquement toutes les entrées d'un tableau multidimensionnel. Elle parcourt plutôt les lignes, qui sont elles-mêmes des tableaux à une dimension. Pour visiter tous les éléments d'un tableau bidimensionnel, imbriquer deux boucles :

int[ ][ ] tableau =
  {
     {16, 3, 2, 13},
     {5, 10, 11, 8},
     {9, 6, 7, 12},
     {4, 15, 14, 1}
  };
...

for (int[ ] ligne : tableau)
   for (int élément : ligne)
     // faire quelque chose avec élément

Les collections pour gérer des ensembles d'objets

Les tableaux sont inadéquats pour gérer une quantité importante d'informations du même type quand leur nombre n'est pas connu à l'avance. Par exemple, le nombre de messages postés dans un forum n'étant pas limité, il existe des solutions plus simples que des tableaux pour stocker ces messages. Le paquetage java.util contient plusieurs classes de collection utilisées pour gérer un ensemble d'éléments de type d'objet et résoudre les limitations inhérentes aux tableaux, ce que nous allons aborder dans les chapitres qui suivent.

Les interfaces de collection

Comme pour la plupart des bibliothèques de données récentes, la bibliothèque de collections Java fait la distinction entre les interfaces et les implémentations. Intéressons-nous à cette distinction avec une structure de données familière, la queue de données.

Interface de queue de données

Une interface de queue indique que vous pouvez :

1. ajouter des éléments à la fin d'une queue,
2. supprimer des éléments au début d'une queue,
3. et déterminer le nombre d'éléments contenus dans une queue.

Les queues sont utilisées si vous devez enregistrer des objets et les récupérer selon la règle "premier entré, premier sortie" (FIFO - First In First Out)

Une forme minimaliste d'interface pour les queues pourrait ressembler à ceci :

interface Queue<E> {
  void add(E élément);
  E remove();
  int size();
}

L'interface n'indique en aucune manière la façon dont la queue est implémentée.
§

En réalité, il existe deux implémentations courantes de queues :

1. La première implémentation, représentée par la classe ArrayDeque, se sert d'un tableau circulaire :
   
   
2. La seconde implémentaiton, représentée par la classe LinkedList, se sert d'une liste chaînée :
   
   

Queue<String> textes = new ArrayDeque<String>();
textes.add("Premier texte");

Queue<String> textes = new LinkedList<String>();
textes.add("Premier texte"); 

Pourquoi choisir une implémentation plutôt qu'une autre ? Une interface ne fournit aucun détail quant à l'efficacité de son implémentation. De manière générale, un tableau circulaire est plus efficace qu'une liste chaînée, et il est donc préférable à cette dernière. Toutefois, comme d'habitude, il y a un prix à payer. Les tableaux circulaires font partie d'une collection bornée, qui a une capacité déterminée. Si vous ne connaissez pas la limite maximale du nombre d'objets stockés par votre programme, vous préférerez probablement une implémentation en liste chaînée.

En étudiant la documentation de l'API, vous découvrirez un autre jeu de classes dont le nom commence par Abstract, comme AbstractQueue. Ces classes sont destinées aux implémentations de bibliothèque. Pour implémenter votre propre classe de queue, il sera plus facile d'étendre AbstractQueue que d'implémenter toutes les méthodes de l'interface Queue.

Interface de collection

En réalité, l'interface fondamentale des classes de collection de la bibliothèque Java est l'interface Collection.

• Cette interface possède deux méthode essentielles (il existe d'autres méthodes que nous aborderons plus loin dans ce chapitre) :

  public interface Collection<E> {
    boolean add(E élément);
    Iterator<E> iterator();
    ...
  }

• La méthode add() ajoute un élément dans la collection. La méthode add() renvoie true si l'ajout de l'élément a effectivement modifié la collection. Elle renvoie false si la collection n'a pas été modifiée.

  Par exemple, si vous essayez d'ajouter un objet dans un ensemble et que cet objet en fasse déjà partie, la requête add() est sans effet parce que les ensembles de données ne peuvent pas accepter deux fois la même donnée.

• La méthode iterator() renvoie un objet qui implémente l'interface Iterator. Un objet d'itération permet de parcourir les différents éléments d'une collection, un par un.

L'interface Iterator

Les itérateurs permettent de parcourir la collection d'un début vers une fin en ne passant qu'une seule fois sur chacun des éléments. Associé à une collection donnée, l'itérateur possède les propriétés suivantes :

1. Â un instant donné, un itérateur indique ce que nous nommons une position courante désignant soit un élément donné de la collection, soit la fin de la collection (la position courante se trouvant alors en quelque sorte après le dernier élément). Comme nous pouvons nous y attendre, le premier appel de la méthode iterator() sur une collection donnée fournit comme position courante, le début de la collection.
2. Nous pouvons obtenir l'objet désigné par un itérateur en appelant la méthode next() de l'itérateur, ce qui, en outre, avance l'itérateur d'une position. Ainsi deux appels successifs de next() fournissent deux objets différents (consécutifs).
3. La méthode hasNext() de l'itérateur permet de savoir si l'itérateur est ou non en fin de collection, c'est-à-dire si la position courante dispose ou non d'une position suivante, autrement dit si la postion courante désigne ou non un élément.

public interface Iterator<E> {
  E next();
  boolean hasNext();
  void remove();
}

1. Par conséquent, si vous souhaitez parcourir tous les éléments d'un conteneur, il suffit de demander un objet Iterator et d'appeler la méthode next() tant que la méthode hasNext() renvoie true. Par exemple :

   Collection<String> textes = ...;
   Iterator<String> it = textes.iterator();
   while (it.hasNext()) {
     String élément = it.next();
     // utilisation de élément
   } 

2. Heureusement, depuis Java SE 5.0, nous pouvons utiliser un raccourci élégant et bien plus concis au moyen de la boucle "foreach" :

   Collection<String> textes = ...;
   for (String élément : textes)  {
     // utilisation de élément
   } 

   Le compilateur se contente de traduire la boucle "for each" en boucle avec un itérateur.
   §

L'interface Iterable

La boucle "for each" fonctionne comme tout objet qui implémente l'interface Iterable, une interface avec une seule méthode, la méthode iterator() :

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

L'interface Collection étend l'interface Iterable. Vous pouvez donc utiliser la boucle "for each" avec n'importe quelle collection de la bibliothèque standard.
§

Retour à l'interface Collection

L'ordre de visite des éléments dépend du type de la collection. Si vous parcourez un ArrayList, l'itérateur démarre à l'indice 0 et l'incrémente à chaque pas. Toutefois, si vous visitez les éléments dans un HashSet, vous les rencontrerez dans un ordre aléatoire.

Vous pouvez être sûr de rencontrer tous les éléments d'un collection lors de l'itération, mais vous ne pouvez pas savoir dans quel ordre. Cela ne pose généralement pas de problème car l'ordre importe peu pour des calculs comme les totaux ou les concordances.

Suppression d'éléments à l'aide de l'interface Iterator

L'interface Iterator prévoit la méthode remove() qui supprime de la collection le dernier objet envoyé par la méthode next(). Dans de nombreux cas, cette méthode est pratique si vous avez besoin d'examiner chaque élément avant de savoir si vous devez le supprimer ou non. Mais, si vous souhaitez effacer un élément en fonction de sa position, il faut malgré tout le dépasser.

Par exemple, voici comment supprimer le premier élément d'une collection de chaînes :

Iterator<String> it = textes.iterator();
it.next();
it.remove();

it.remove();
it.remove(); // erreur

it.remove();
it.next();
it.remove(); // Ok

On notrera bien que l'interface Iterator ne comporte pas de méthode d'ajout d'un élément à une position déterminée (c'est-à-dire en général entre deux éléments). En effet, un tel ajout n'est réalisable que sur des collections disposant d'informations permettant de localiser, non seulement l'élément suivant, mais aussi l'élément précédent d'un élément donné. Ce ne sera le cas que de certaines collections seulement, disposant précisément d'itérateurs bidirectionnels.

En revanche, nous verrons que toute collection disposera d'une méthode d'ajout d'un élément à un emplacement (souvent sa fin) indépendant de la valeur d'un quelconque itérateur. C'est d'ailleurs cette démarche qui sera le plus souvent utilisée pour créer effectivement une collection.

Les itérateurs bidirectionnels : l'interface ListIterator

Certaines collections (listes chaînées, vecteurs dynamiques) peuvent, par nature, être parcourues dans les deux sens. Elles disposent d'une méthode nommée listIterator() qui fournit un itérateur bidirectionnel. Il s'agit, cette fois, d'un objet d'un type implémentant l'interface ListIterator<E> (qui dérive de l'interface Iterator<E>). Il dispose bien sûr des méthodes next(), hasnext() et remove() héritées de Iterator. Mais il dispose d'autres méthodes permettant d'exploiter son caractère bidirectionnel, à savoir :

1. Comme nous pouvons nous y attendre, des méthodes previous() et hasPrevious(), complémentaires des méthodes next() et hasNext() :

   Nous pouvons obtenir l'élément précédent la position courante à l'aide de la méthode previous() de l'iterateur, laquelle, en outre, recule l'itérateur sur la position précédente. Ainsi, deux appels successifs de previous() fournissent deux objets différents.

   La méthode hasPrevious() de l'itérateur permet de savoir si nous sommes ou non en début de collection, c'est-à-dire si la position courante dispose ou non d'une position précédente.

   LinkedList<String> textes = ...;
   ListIterator<String> it = textes.listIterator(texte.size());
   while (it.hasPrevious()) {
     String élément = it.previous();
     // utilisation de élément
   } 

   Un appel à la méthode previous() annule, en quelque sorte, l'action réalisée sur le pointeur de déplacement, par un précédent appel à la méthode next().

2. Mais aussi, des méthodes d'addition d'un élément à la position courante - add() (en générale, une telle opération est plutôt nommée insertion, mais ici, la méthode se nomme add() et non insert())- ou de modification de l'élément courant - set().

   L'interface ListIterator prévoir une méthode add() qui ajoute un élément à la position courante de l'itérateur. Si ce dernier est en fin de collection, l'ajout se fait tout naturellement en fin de collection (y compris si la collection est vide). Si l'itérateur désigne le premier élément, l'ajout se fera avant ce premier élément. Par exemple, si textes est une collection disposant d'un itérateur bidirectionnel, les instructions suivantes ajouterons l'élément avant le deuxième élément (en supposant qu'il existe) :

   LinkedList<String> textes = ...;
   ListIterator<String> it = textes.listIterator(texte.size());
   it.next();
   it.next();
   it.add(élément);    

   Nous noterons bien ici, quelle que soit la position courante, l'ajout par add() est toujours possible. De plus, contrairement à remove(), cet ajout ne nécessite pas que l'élément courant soit défini (il n'est pas nécessaire qu'un quelconque élément ait déjà été renvoyé par next() ou previous()).

   Par ailleurs, add() déplace la position courante après l'élément que nous venons d'ajouter. Plusieurs appels consécutifs de add() sans intervention explicite sur l'itérateur introduisent donc des éléments consécutifs.

   L'appel à la méthode set(élément) remplace l'élément courant, c'est-à-dire le dernier renvoyé par next() et previous(), à condition que la collection n'ait pas été modifiée entre temps (par exemple par add() ou remove()). N'oubliez pas que les éléments ne sont que de simples références ; la modification opérée par set() n'est donc qu'une simple modification de référence (les objets concernés n'étant pas modifiés).

   La position courante de l'itérateur n'est pas modifiée (plusieurs appels successifs de set(), sans action sur l'itérateur, reviennent à ne retenir que la dernière modification).

   N'oubliez pas que set(), comme remove(), s'applique à un élément courant (et non comme add() à une position courante).
   §

Méthodes utilitaires génériques de l'interface Collection

Comme les interfaces Iterator et Collection sont générales, il est possible d'écrire des méthodes pratiques pouvant travailler sur n'importe quel type de collection.

Par exemple, voici une méthode générale qui teste si une collection arbitraire contient un élément donné :

public static<E> boolean contains(Collection<E> collection, Object objet)
  for (E élément : collection) if (élément.eguals(objet)) return true;
  return false;
}

Les concepteurs de la bibliothèque Java ont décidé que certaines de ces méthodes générales étaient tellement pratiques qu'elles devaient faire partie de la bibliothèque. De cette façon, les utilisateurs n'ont pas besoin de réinventer la roue en permanence. La méthode contains() en constitue un bon exemple.

L'interface java.util.Collection<E>

Collection<E> iterator()

Renvoie un itérateur pouvant être utilisé pour parcourir les éléments d'une collection

int size()

Renvoie le nombre courant d'éléments stockés dans une collection.

boolean isEmpty()

Renvoie true si la collection ne contient aucun élément.

boolean contains(Object objet)

Renvoie true si la collection contient l'objet correspondant à celui qui est passé en argument.

boolean containsAll(Collection<?> autre)

Renvoie true si cette collection contient tous les éléments de l'autre collection.

boolean add(Object élément)

Ajoute un élément à la fin de la collection. Renvoie true si la collection a été modifié par cet appel.

boolean addAll(Collection<? extends E> autre)

Ajoute tous les éléments de l'autre collection à cette collection. Renvoie true si la collection a été modifié par cet appel.

boolean remove(Object élément)

Supprime cet élément de la collection. Renvoie true si l'objet correspondant a été trouvé.

boolean removeAll(Collection<?> autre)

Supprime de cette collection tous les éléments de l'autre collection. Renvoie true si la collection a été modifié par cet appel.

Handler[] getHandlers()

Récupère tous les gestionnaires de cet enregistreur.

void clear()

Supprime tous les éléments de la collection.

boolean retainAll(Collection<?> autre)

Supprime dans cette collection tous les éléments qui ne figure pas dans l'autre collection. Renvoie true si la collection a été modifié par cet appel.

Object[] toArray()

Renvoie un tableau contenant tous les objets de la collection.

L'interface java.util.Iterator<E>

boolean hasNext()

Renvoie true s'il reste un élément à parcourir.

E next()

Renvoie le prochain objet à parcourir. Déclenche une exception NoSuchElementException si la fin de la collection est atteinte.

void remove()

Supprime le dernier objet lu. Cette méthode doit impérativement être appelée après une lecture. Si la collection a été modifiée depuis la dernière lecture, cette méthode renvoie une IllegalStateException.

L'interface java.util.ListIterator<E> qui hérite de l'interface java.util.Iterator<E>

void add(E élément)

Ajoute (insère) un élément avant la position courante.

void set(E élément)

Remplace le dernier élément renvoyé par next() ou previous() par un nouvel élément. Déclenche une IllegalStateException si la structure de la liste a été modifiée depuis le dernier appel à next() ou à previous().

boolean hasPrevious()

Renvoie true s'il existe un élément avant la position courante..

E previous()

Renvoie l'objet précédent. Déclenche une exception NoSuchElementException lorsque le début de la liste est atteinte.

int nextIndex()

Renvoie l'indice de l'élément qui serait renvoyé par le prochain appel à next().

int previousIndex()

Renvoie l'indice de l'élément qui serait renvoyé par le prochain appel à previous().

public abstract class AbstractCollection<E> implements Collection<E> {
...
  public abstract Iterator<E> iterator();
...
  public static<E> boolean contains(Collection<E> collection, Object objet)
    for (E élément : collection) if (élément.eguals(objet)) return true;
    return false;
  }

Les collections concrètes

Maintenant que nous avons pris connaissance avec les interfaces principales pour gérer les collections et plutôt que de voir en détail chaque interface, il est plus utile dès lors de commencer par aborder les structures de données concrètes implémentées dans la bibliothèque Java. Une fois que nous aurons correctement décrit les classes que nous pouvons utiliser, nous reviendrons à des considérations abstraites et nous verrons comment la structure des collections organise toutes ces classes.

Le tableau ci-dessous présente les collections de la bibliothèque Java et décrit brièvement l'objectif de chaque classe de collection (pour des raisons de simplicité, nous ne parlerons pas des collections compatibles avec les Threads qui seront traitées dans une autre étude).

Pour en savoir plus sur les collections compatibles avec les threads.
§

Toutes les classes du tableau implémente l'interface Collection, à l'exception de celles dont le nom se termine par Map. Celles-ci implémentent plutôt l'interface Map (nous la traiterons un peu plus loin).

Listes chaînées - java.util.LinkedList

Nous avons déjà abordé les tableaux et, dans de nombreux exemples, leur cousin dynamique, la classe ArrayList (qui sera abordée dans le chapitre suivant). Voici recensés ci-dessous les différents critères relatifs à leur structure :

1. Le tableau classique en Java, comme nous l'avons découvert au début de cette étude, fait parti des collections d'éléments ordonnés accessible par indice. L'utilisation des tableaux impose cependant de spécifier une taille avant de pouvoir être utilisé. En java, il est possible de préciser la taille juste au moment où nous en avons besoin. En contre partie, une fois que la taille est prise en compte, il n'est pas facile de la changer.
2. La classe ArrayList est semblable à un tableau, mais elle ajuste automatiquement sa capacité à mesure que vous ajoutez et supprimez des éléments, sans que vous n'ayez rien à faire.

   En fait, en interne, la classe ArrayList mémorise ses éléments dans un tableau Java. Si ce tableau interne est trop petit lors de l'ajout d'un nouvel élément à la collection, il est automatiquement remplacé par un nouveau tableau, plus grand, initialisé avec les références de l'ancien tableau.
   
   
   
   
   
   
   
   
   
   
   
   

   La classe ArrayList est très séduisante. Il s'agit ni plus ni moins d'un tableau dynamique. Elle est totalement adaptée lorsque nous devons ajouter ou supprimer des éléments en fin de tableau.

Mais ces deux structures possèdent un inconvénient majeur. La suppression d'un élément au milieu d'un tableau nécessite beaucoup de temps machine, car tous les éléments situés après l'élément supprimé doivent être décalés d'une case. Le même problème se pose pour insérer des éléments au milieu d'un tableau.

Il existe une autre structure de données très répandue, la liste chaînée, qui permet de résoudre ces problèmes. Alors que les objets d'un tableau occupent des emplacements mémoires successifs, une liste chaînée stocke chaque objet avec un lien qui y fait référence. Chaque lien possède également une référence vers le lien suivant de la liste. Avec Java, chaque élément d'une liste chaînée possède en fait deux liens, c'est-à-dire que chaque élément est aussi relié à l'élément précédent. La bibliothèque Java possède la classe LinkedList prète à l'emploi et qui implémente donc la liste "doublement chaînée".

La classe LinkedList mémorise ses éléments avec une liste doublement chaînée, ce qui permet d'insérer plus rapidement un élément dans la collection, mais par contre, ralentit l'accès à un élément par son indice.

LinkedList<String> textes = ...;
ListIterator<String> it = textes.listIterator();  

Les méthodes de ListIterator

1. La méthode add() ajoute le nouvel élément avant la position de l'itérateur. Par exemple, le code suivant saute le premier élément de liste et ajoute la chaîne "Juliette" avant le deuxième élément :

   List<String> prénoms = new LinkedList<String>();
   prénoms.add("Claire");  
   prénoms.add("Laurent");   
   prénoms.add("Adrien");    
   ListIterator<String> itérateur = prénoms.listIterator(); 
   itérateur.next(); // ignorer le premier élément
   itérateur.add("Juliette");   

   Si vous appelez la méthode add() de ListIterator plusieurs fois, les éléments sont simplement ajoutés dans l'ordre dans lequel vous les passez. Ils sont tous ajoutés avant la position courante de l'itérateur.

   Comme pour toutes les classes concrètes, la classe LinkedList implémente une interface particulière (ou plusieurs), ici List, qui correspond à la fonctionnalité globale d'une liste. L'intérêt de déclarer une interface plutôt que la classe elle-même, je le rappelle, c'est qu'il est plus facile de changer ensuite le type de collection si le choix initial ne s'avère pas des plus judicieux à terme. Par exemple, si nous nous rendons compte que dans notre application, nous faisons très peu d'insertion ou de suppression d'éléments dans la liste, nous pourrions tout à fait prendre la classe ArrayList à la place de LinkedList puisque toutes les deux implémentent l'interface List.

2. Lorsque vous utilisez l'opération add() avec un itérateur qui vient juste d'être renvoyé par la méthode listIterator() et qui fait référence au début de la liste chaînée, les éléments sont ajoutés au début de liste chaînée. Lorsque l'itérateur dépasse le dernier élément de la liste (c'est-à-dire que la méthode hasNext() renvoie false), l'élément est ajouté à la fin de la liste.
3. Si la liste chaînée possède n éléments, il existe n+1 emplacements pour ajouter un nouvel élément. Ces emplacements correspondent aux n+1 positions possibles de l'itérateur. Par exemple, si une liste chaînée contient trois éléments, A, B et C, alors il existe quatre positions possibles pour insérer un nouvel élément (représentées par | ) :

   |ABC
   A|BC
   AB|C
   ABC|

   Faites attention à l'analogie avec un curseur de texte. L'opération remove() de ListIterator ne fonctionne pas exactement comme la touche Retour-arrière. Juste après un appel à la méthode next(), la méthode remove() supprime en fait l'élément à gauche de l'itérateur, exactement comme la touche Retour-arrière. Cependant, si vous venez d'appler la méthode previous(), l'élément situé à droite de l'itérateur sera supprimé. De plus, il n'est pas possible d'appeler la méthode remove() deux fois de suite.
   
   Contrairement à la méthode add(), qui ne dépend que de la position de l'itérateur, la méthode remove() dépend de l'état de l'itérateur.
   

4. De plus, il existe la méthode set() qui remplace le dernier élément renvoyé par next() ou previous() par un nouvel élément. Par exemple, le code suivant remplace le premier élément d'une liste par une nouvelle valeur :

   List<String> prénoms = new LinkedList<String>();  
   ListIterator<String> itérateur = prénoms.listIterator(); 
   String ancienneValeur = itérateur.next(); 
   itérateur.set("Justine");   // affecte une nouvelle valeur au premier élément

5. Comme vous pouvez l'imaginer, si un itérateur parcourt une liste alors qu'un autre itérateur est en train de la modifier, il peut en résulter une certaine confusion. Par exemple, supposons qu'un itérateur fasse référence à un élément qu'un autre itérateur vient juste de supprimer. L'itérateur est désormais invalide et ne devrait donc plus être utilisé. Les itérateurs de listes chaînées ont été conçus pour détecter de telles modifications. Si un itérateur se rend compte que sa liste a été modifié par un autre itérateur ou par une méthode de la collection, il déclenche une exception ConcurrentModificationException :

   List<String> prénoms = new LinkedList<String>();  
   ListIterator<String> itérateur1 = prénoms.listIterator(); 
   ListIterator<String> itérateur2 = prénoms.listIterator();
   itérateur1.next();
   itérateur1.remove();
   itérateur2.next();  // déclenche une exception de type ConcurrentModificationException

   Afin d'éviter ce type d'exception, il suffit de suivre une règle simple : vous pouvez attacher autant d'itérateurs à une collection que vous le souhaitez, tant qu'ils effectuent uniquement des lectures dans la liste. Sinon, vous pouvez attacher un seul itérateur qui peut à la fois lire et écrire.

   Le déclenchement de ce type d'exception observe aussi une règle simple. La collection garde une trace du nombre d'opérations de transformations (comme l'ajout ou la suppression d'un élément). Chaque itérateur compte le nombre de transformations dont il est responsable. Au début de chaque méthode d'itérateur, ce dernier vérifie que son nombre de transformations est bien égal à celui de la collection. Dans le cas contraire, il déclenche l'exception ConcurrentModificationException.

   Il existe une curieuse exception à la règle permettant de détecter une modification simultanée. La liste chaînée garde uniquement la trace des modifications structurelles de la liste, comme l'ajout et la suppression de liens. La méthode set() n'est pas comptée comme une modification structurelle. Vous pouvez attacher plusieurs itérateurs à une liste chaînée, et ils peuvent tous appeler set() pour modifier le contenu des liens existants. Cette capacité est en fait nécessaire pour un certain nombre d'algorithmes de la classe Collections que nous aborderons plus loin dans cette étude.

Retour aux méthode de la classe LinkedList

Vous connaissez désormais les méthodes fondamentales de la classe LinkedList. Vous pouvez vous servir d'un ListIterator pour parcourir les éléments d'une liste chaînée dans n'importe quelle direction et pour ajouter ou supprimer des éléments.

Comme nous l'avons vu dans la section précédente, plusieurs autres méthodes pratiques manipulent les listes chaînées, qui sont déclarées dans l'interface Collection. Ces méthodes, pour la plupart, sont implémentées dans la superclasse AbstractCollection de la classe LinkedList.

1. La méthode toString() invoque les méthodes toString() de chaque élément et renvoie une seule longue chaîne au format [A, B, C]. Cela est très pratique pour déboguer.
2. Utilisez la méthode contains() pour vérifier si un élément est présent dans une liste chaînée.

La bibliothèque fournit aussi un certain nombre de méthodes qui sont quelque peu douteuses.

Les listes chaînées ne permettent pas d'accéder rapidement à n'importe quel élément. Si vous voulez connaître le n-ième élément d'une liste chaînée, il faut commencer par le début de la liste et sauter les n-1 premiers éléments. Il n'existe aucun moyen plus rapide. Pour cette raison, les programmeurs n'utilisent généralement pas les listes chaînées dans des situations où les éléments doivent être référencés par un index entier.

1. Néanmoins, la classe LinkedList fournit une méthode get() qui vous permet d'accéder à un élément particulier :

   List<String> prénoms = new LinkedList<String>();
   String valeur = prénoms.get(n); 

   Bien sûr, cette technique n'est pas très efficace. Si vous vous rendez compte que vous l'utilisez, c'est probablement que vous utilisez une structure de données qui n'est pas adaptée à votre problème.

   Il ne faudrait jamais avoir recours à cette méthode pour parcourir les éléments d'une liste chaînée. L'efficacité du code suivant doit donc être vivement remise en question :

   List<String> prénoms = new LinkedList<String>();
   for (int i=0; i < prénoms.size(); i++)
      utilisation de prénoms.get(i); 

   Chaque fois que vous recherchez un élément, vous parcourez à nouveau la liste depuis le début. L'objet LinkedList ne fait aucun effort pour se rappeler la position courante du dernier élément lu.

   La méthode get() possède une légère optimisation ; si l'indice vaut au moins size()/2, la recherche commence par la fin de la liste.
   §
2. L'interface de l'itérateur de liste possède en outre une méthode renvoyant l'indice de la position courante. En fait, comme les itérateurs Java pointent entre les éléments, il en existe deux :
   • la méthode nextIndex() renvoie l'indice de l'élément qui serait renvoyé par la méthode next(),
   • et la méthode previousIndex() retourne l'indice de l'élément qui serait renvoyé par la méthode previous(). Cette méthode correspond naturellement à celui de la méthode nextIndex() moins un.

   Ces méthodes sont assez efficaces, car l'itérateur garde en mémoire sa position courante.
   §

3. Enfin, si vous possédez un indice n, la méthode listIterator(n) de la classe LinkedList renvoie un itérateur qui pointe juste avant l'élément dont l'indice vaut n. C'est-à-dire qu'un appel à next() donnera le même élément que get(n).

   L'obtention de cet itérateur reste assez peu efficace.
   §

Si l'une de vos listes chaînées ne possède que quelques éléments, vous n'avez pas trop de soucis à vous faire à propos de l'efficacité des méthode get() et set(). Mais dans ce cas, quel est l'avantage d'une liste chaînée ? La seule motivation permettant de choisir une liste chaînée consiste à minimiser le coût d'une insertion ou d'une suppression d'un élément en plein milieu de la liste. Si vous n'avez que quelques éléments à traiter, il vaut mieux utiliser une ArrayList.

Nous conseillons d'ailleurs d'éviter toutes les méthodes qui utilisent un indice d'entier permettant de noter la position dans une liste chaînée. Pour obtenir un accès direct dans une collection, mieux vaut utiliser un tableau ou encore un ArrayList.

L'interface java.util.List<E> qui hérite de l'interface java.util.Collection<E>

ListIterator<E> listIterator()

Renvoie un itérateur bidirectionnel de liste permettant de parcourir les éléments de la liste.

ListIterator<E> listIterator(int index)

Renvoie un itérateur bidirectionnel de liste permettant de parcourir les éléments de la liste dont le premier appel à next() doit renvoyer l'élément correspondant.

void add(int index, E élément)

Ajoute un élément à la position spécifiée.

void addAll(int index, Collection<? extends E> éléments)

Ajoute tous les éléments d'une collection à la position spécifiée.

E remove(int index)

Supprime et renvoie l'élément à la position spécifiée.

E get(int index)

Récupère l'élément à la position spécifiée.

E set(int index, E élément)

Remplace l'élément à la position spécifiée par un nouvel élément et renvoie l'ancien élément.

int indexOff(Object élément)

Renvoie la position de la première occurence d'un élément égal à l'élément spécifié, ou -1 si cet élément n'a pu être trouvé.

int lastIndexOff(Object élément)

Renvoie la position de la dernière occurence d'un élément égal à l'élément spécifié, ou -1 si cet élément n'a pu être trouvé.

La classe java.util.LinkedList<E> qui implémente l'interface java.util.List<E>

LinkedList()

Construit une liste chaînée vide.

LinkedList(Collection<? extends E> éléments)

Construit une liste chaînée et y ajoute tous les éléments de la collection.

void addFirst(E élément)
void addLast(E élément)

Ajoute un élément au début ou à la fin d'une liste.

E getFirst()
E getLast()

Renvoie l'élément situé au début ou à la fin d'une liste.

E removeFirst()
E removeLast()

Supprime et renvoient l'élément situé au début ou à la fin d'une liste.

Exemple de mise en oeuvre

A titre d'exemple, je vous propose de créer une application qui permet de gérer (surtout de visualiser) une liste de prénoms. Je profite de cette application pour voir comment effectuer les différents cas d'utilisations : ajout, suppression, changement de prénom, se déplacer dans la liste et tout effacer.

codage correspondant

package listes;

import java.awt.*;
import java.awt.event.ActionEvent;
import javax.swing.*;
import java.util.*;

public class Prénoms extends JFrame {
   private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 18);
   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JTextField prénomActuel = new JTextField("(Vide)",18);
   private JTextField nombre = new JTextField("0");
   
   private LinkedList<String> prénoms = new LinkedList<String>();
   private ListIterator<String> itérateur = prénoms.listIterator();

   public Prénoms() {
      super("Liste de prénoms");
      prénomActuel.setEditable(false);
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      barre.add(new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            itérateur.add(nouveauPrénom.getText());
            analysePrénoms();                        
         }
      });
      barre.add(new AbstractAction("Change") {
         public void actionPerformed(ActionEvent e) {
            if (itérateur.hasNext()) itérateur.set(nouveauPrénom.getText());
            analysePrénoms(); 
         }
      }); 
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            if (itérateur.hasNext()) itérateur.remove();
            analysePrénoms(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            prénoms.clear();
            itérateur = prénoms.listIterator();
            analysePrénoms();
         }
      });       
      barre.add(new AbstractAction("<<") {
         public void actionPerformed(ActionEvent e) {
            itérateur = prénoms.listIterator();
            analysePrénoms();
         }
      });
      barre.add(new AbstractAction("<") {
         public void actionPerformed(ActionEvent e) {
            if (itérateur.hasPrevious()) itérateur.previous();
            analysePrénoms();
         }
      });
      barre.add(new AbstractAction(">") {
         public void actionPerformed(ActionEvent e) {
            if (itérateur.hasNext()) itérateur.next();
            analysePrénoms();
         }
      });      
      barre.add(new AbstractAction(">>") {
         public void actionPerformed(ActionEvent e) {
            itérateur = prénoms.listIterator(prénoms.size());
            analysePrénoms();
         }
      }); 
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      panneau.add(nouveauPrénom);
      panneau.add(new JLabel("Actuel :"));
      panneau.add(prénomActuel);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(470, 135);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analysePrénoms() {
      liste.repaint();
      if (prénoms.isEmpty()) prénomActuel.setText("(Vide)");
      else if (itérateur.hasNext()) {
         prénomActuel.setText(itérateur.next());
         itérateur.previous();
      }
      else prénomActuel.setText("(Fin de liste)");
      nombre.setText(""+prénoms.size());
   }

   public static void main(String[] args) { new Prénoms(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Liste"));
      }
      @Override
      public void paint(Graphics g) {
           setText(prénoms.toString());
           super.paint(g);
      }
   }
}

1. Vous remarquez que dans le cas d'une liste, nous nous servons presque essentiellement de l'itérateur bidirectionnel.
2. Le bouton ajout correspond finalement à une insertion.

Les vecteurs (tableaux dynamiques) - Listes de tableaux - java.util.ArrayList

Dans la section précédente, nous avons abordé l'interface List et la classe LinkedList qui l'implémente. L'interface List décrit une collection classée dans laquelle la position des éléments a une importance.

Il existe deux protocoles pour parcourir ces éléments : avec un itérateur ou avec les méthodes d'accès direct get() et set(). Ces deux méthodes ne sont pas vraiment adaptées à une structure de liste chaînée, mais get() et set() prennent toute leur importance avec les tableaux.

La bibliothèque de collections fournit une classe ArrayList qui implémente aussi l'interface List. Une ArrayList encapsule un tableau dynamique relogeable d'objets.

1. La classe ArrayList offre des fonctionnalités d'accès rapide comparables à celles d'un tableau d'objets. Bien qu'elle implémente, comme LinkedList, l'interface List, sa mise en oeuvre est différente et prévue pour permettre des accès efficaces à un élément de rang donné, c'est-à-dire un accès direct vers l'objet désiré, au travers d'un indice, comme dans le cas d'un tableau d'objets.
2. En outre, cette classe offre plus de souplesse que les tableaux d'objets dans la mesure où sa taille (son nombre d'éléments) peut varier au fil de l'exécution (comme celle de n'importe quelle collection).
3. Mais pour que l'accès direct à un élément de rang donné soit possible, il est nécessaire que les emplacements des objets (plutôt leurs références) soient contigus en mémoire (à la manière de ceux d'un tableau). Aussi cette classe souffrira d'une lacune inhérente à sa nature : l'insertion ou la suppression d'un objet à une position donnée ne pourra plus se faire aussi rapidement que dans le cas d'une liste chaînée puisque toutes les cases suivantes du tableau devront être décallées.

   En définitive, les vecteurs (tableaux dynamiques) seront bien adaptés à l'accès direct à condition que les insertions et les suppressions restent limitées.

Il n'existe pas de méthodes réellement spécifiques à la classe ArrayList. Tout ce que nous connaissons déjà peut donc être pris en compte. Finalement, il suffit juste de connaître l'efficacité des méthodes utilisées. Suivant le cas, il peut être judicieux de choisir entre la classe ArrayList et la classe LinkedList.

Exemple de mise en oeuvre

A titre d'exemple, je vous propose de reprendre l'application précédente et d'implémenter la classe ArrayList à la place de la classe LinkedList. Cette fois-ci, je passerai par un indice plutôt que de passer par un itérateur.

codage correspondant

package listes;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
import java.util.*;
import javax.swing.event.*;

public class Prénoms extends JFrame {
   private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 19);
   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JTextField prénomActuel = new JTextField("(Vide)",19);
   private JTextField nombre = new JTextField("0");
   private JSpinner position = new JSpinner();
   
   private ArrayList<String> prénoms = new ArrayList<String>();
   private int indice;

   public Prénoms() {
      super("Liste de prénoms");
      prénomActuel.setEditable(false);
      position.setPreferredSize(new Dimension(45, 22));
      position.addChangeListener(new ChangeListener() {
         public void stateChanged(ChangeEvent e) {
            int index = (Integer)position.getValue();
            if (index>=0 && index<prénoms.size()) indice = index;
            else position.setValue(indice);
            analysePrénoms(); 
         }
      });
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      AbstractAction ajout = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            prénoms.add(nouveauPrénom.getText());
            analysePrénoms();    
         }
      };
      barre.add(ajout);
      nouveauPrénom.addActionListener(ajout);
      barre.add(new AbstractAction("Change") {
         public void actionPerformed(ActionEvent e) {
            prénoms.set(indice, nouveauPrénom.getText());
            analysePrénoms(); 
         }
      }); 
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            prénoms.remove(indice--);
            position.setValue(indice);
            analysePrénoms(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            prénoms.clear();
            position.setValue(indice = 0);
            analysePrénoms();
         }
      });       
      barre.addSeparator();
      barre.add(new JLabel("Position : "));
      barre.add(position);
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      panneau.add(nouveauPrénom);
      panneau.add(new JLabel("Actuel :"));
      panneau.add(prénomActuel);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(490, 135);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analysePrénoms() {
      liste.repaint();
      if (prénoms.isEmpty()) prénomActuel.setText("(Vide)");
      else   prénomActuel.setText(prénoms.get(indice));
      nombre.setText(""+prénoms.size());
   }

   public static void main(String[] args) { new Prénoms(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Tableau"));
      }
      @Override
      public void paint(Graphics g) {
           setText(prénoms.toString());
           super.paint(g);
      }
   }
}

Lorsque nous consultons ce code en regard du même exemple traité par une liste chaînée, nous remarquons tout de suite que nous travaillons plus directement avec le tableau dynamique (ArrayList) sans passer systématiquement par un itérateur, ce qui etait très souvent le cas avec la classe LinkedList. Je préfère très nettement cette approche puiqu'elle me paraît plus intuitive.

Autre exemple de mise en oeuvre

Ci-dessous se trouve un exemple où nous prenons comme collection un tableau dynamique ArrayList. Les méthodes utilisées sont les méthodes communes aux deux types de collection. Remplacez, d'ailleurs, la classe ArrayList par LinkedList, vous remarquerez que votre programme vous donnera le même résultat. Le choix entre les deux types de collection doit correspondre uniquement au critère de performance. Si vous devez insérer ou supprimer des éléments n'importe où dans la collection, il faut alors choisir LinkerList. Si vous n'avez pas ce genre de contrainte et que vous voulez juste remplacer un tableau statique par un tableau dynamique, n'hésitez pas à prendre le conteneur ArrayList.

Codage avec résultats en correspondance

import java.util.*;
import static java.lang.System.*;

public class TableauDynamique {
   public static void main(String[] args) {
      // tableau d'entier par la classe enveloppe Integer
      ArrayList<Integer> tableau = new ArrayList<Integer>();
      out.println("Tableau vide ? "+tableau.isEmpty());
      tableau.add(-45);
      tableau.add(13);
      tableau.add(24);
      afficheTableau(tableau);
      // ajout de la valeur 89 à la position 1
      tableau.add(1, 89);
      afficheTableau(tableau);
      // remplacer la valeur 89 par la valeur 3
      tableau.set(1, 3);
      afficheTableau(tableau);
      // enlève la valeur 13
      if (tableau.contains(13))
         tableau.remove((Integer)13);
      afficheTableau(tableau);
      //ajout d'une nouvelle valeur et affichage en ligne
      tableau.add(-45); out.print("tableau[] = { ");
      for(Integer valeur : tableau) out.print(valeur+" ");
      out.println("}");
      // position de la valeur -45
      out.println("Position de la valeur -45 : "+tableau.indexOf(-45));
      out.println("Position de la valeur -45 : "+tableau.lastIndexOf(-45));
      // effacer le tableau en entier
      tableau.clear();
      out.println("Taille du tableau : "+tableau.size());
   }
   public static void afficheTableau(ArrayList<Integer> tableau) {
      out.println("Taille du tableau : "+tableau.size());
      for (int i=0; i<tableau.size(); i++)
         out.println("tableau["+i+"] = "+tableau.get(i));      
   }
}

Ensembles d'objets uniques - HashSet, TreeSet, EnumSet et LinkedHashSet

Les listes chaînées et les tableaux vous permettent de spécifier l'ordre dans lequel vous voulez organiser vos éléments. Cependant, si vous recherchez un élément particulier et que vous ne vous rappeliez pas sa position, vous aurez besoin de parcourir tous les éléments jusqu'à ce que vous trouviez l'élément recherché. Cela requiert beaucoup de temps, surtout lorsque la collection contient pas mal d'éléments. Si l'ordre des éléments n'a pas d'importance, il existe des structures de données qui vous permettent de retrouver un élement très rapidement. L'inconvénient est que ces structures de données ne vous permettent pas de contrôler l'ordre des éléments. En effet, elles les organisent plutôt selon l'ordre qui leur permet de les retrouver facilement. Ces structures de données correspondent tout-à-fait à la théorie des ensembles.

Trois classes implémentent la notion d'ensemble : HashSet, TreeSet et EnumSet. Rappelons que, théoriquement, un ensemble est une collection non ordonnée d'éléments, aucun élément ne pouvant apparaître plusieurs fois dans un même ensemble. Chaque fois que nous introduisons un nouvel élément dans une collection de ce type, il est donc nécessaire de s'assurer qu'il n'y figure pas déjà, autrement dit que l'ensemble ne contient pas un autre élément qui lui soit égal.

Attention : Dès que nous nous écartons des types String, File ou classe enveloppe de type primitif, il est généralement nécessaire de se préoccuper des méthodes equals() ou compareTo() (ou d'un comparateur - voir plus loin) ; si nous ne le faisons pas, il faut alors accepter que deux objets de références différentes ne soient jamais identiques, quelles que soit leurs valeurs !

Par ailleurs, bien qu'en théorie un ensemble ne soit pas ordonné, des raisons évidentes d'efficacité de méthodes de test d'appartenance nécessite une certaine organisation de l'information. Dans le cas contraire, un tel test d'appartenance ne pourrait se faire qu'en examinant un à un les éléments de l'ensemble (ce qui conduirait à une efficacité moyenne).

Quatre démarches différentes ont été employées par les concepteurs des collections, d'où l'existence de quatre classes différentes :

1. HashSet : qui recourt à une technique dite de hachage, qui mémorise ses éléments dans un ordre quelconque (et donc plus rapide si l'ordre n'a pas d'importance).
2. TreeSet : qui utilise un arbre binaire pour ordonner complètement les éléments. TreeSet mémorise ses éléments dans l'ordre ascendant avec un arbre, pour maintenir plus rapidement le tri des éléments stockées.
3. EnumSet : est une implémentation efficace d'un ensemble, dont les éléments appartiennent à un type énuméré. Un type énuméré ayant un nombre fini d'instances, EnumSet est implémenté en interne sous la forme d'une suite de bits. Un bit est activé si la valeur correspondante est présente dans l'ensemble.
4. LinkedHashSet : Un ensemble tout à fait particulier qui se souvient de l'ordre d'insertion des éléments.

En définitive, dans tous les cas, les éléments sont ordonnées même si cet ordre est moins facile à appréhender ; avec TreeSet, il s'agit de l'ordre induit par compareTo() ou un éventuel comparateur personnalisé.

Phase de création d'un ensemble pour les quatre types de collection

Comme toute collection, un ensemble peut être construit vide ou à partir d'une autre collection :

La classe java.util.HashSet<E>

HashSet()

Construit un ensemble vide.

HashSet(Collection<? extends E> éléments)

Construit un nouvel ensemble et y ajoute tous les éléments de la collection.

HashSet(int capacité)

Construit un ensemble vide avec la capacité spécifiée.

La classe java.util.TreeSet<E>

TreeSet()

Construit un ensemble trié vide pour stocker les objets de type Comparable.

TreeSet(Comparator<? super E> éléments)

Construit un ensemble trié vide et se sert du comparateur spécifié pour trier ses éléments.

TreeSet(SortedSet<? extends E> éléments)

Construit un ensemble trié vide, ajoute tous les éléments d'un ensemble trié et se sert du même comparateur que celui de l'ensemble spécifié.

La classe java.util.EnumSet<E extends Enum<E>>

static <E extends Enum<E>> EnumSet<E> allOf(Class<E> typeEnumération)

Renvoie un ensemble contenant toutes les valeurs du type énuméré donné.

static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> typeEnumération)

Renvoie un ensemble vide capable de contenir des valeurs du type énuméré donné.

static <E extends Enum<E>> EnumSet<E> range(E de, E à)

Renvoie un ensemble contenant toutes les valeurs comprises entre de et à (compris).

static <E extends Enum<E>> EnumSet<E> of(E valeur)
static <E extends Enum<E>> EnumSet<E> of(E valeur, E... valeurs)

Renvoie un ensemble contenant les valeurs données.

La classe EnumSet ne possède pas de constructeurs publics. Utilisez une méthode de fabrique statique (qui génère une instance appropriée) pour construire l'ensemble désiré.

La classe java.util.LinkedHashSet<E>

LinkedHashSet()

Construit un ensemble vide.

LinkedHashSet(Collection<? extends E> éléments)

Construit un nouvel ensemble et y ajoute tous les éléments de la collection.

LinkedHashSet(int capacité)

Construit un ensemble vide avec la capacité spécifiée.

Méthodes communes à ces différents ensembles

Ces ensembles disposent tous de méthodes communes puisque, comme pour les autres collections, elles implémentent l'interface Collection. Je rappelle, ci-dessous les méthodes bien utiles

1. Parcourir la collection : iterator() : cette méthode fournit un itérateur monodirectionnel (Iterator) permettant de parcourir les différents éléments de la collection :

   HashSet<Interger> loto = ...; // TreeSet<Integer> loto = ...;
   Iterator<Integer> it = loto.iterator();
   while (it.hasNext()) {
     int élément = it.next();
     // utilisation de élément
   } 

2. Ajout d'un élément - add() : Rappelons qu'il est impossible d'ajouter un élément à une position donnée puisque les ensembles ne disposent pas d'itérateur bidirectionnel.

   D'ailleurs, comme au niveau de leur implémentation, les ensembles sont organisés en fonction des valeurs de leurs éléments, l'opération ne serait pas réalisable.

   La seule façon d'ajouter un élément à un ensemble est d'utiliser la méthode add() prévue par l'interface Collection. Elle assure en effet que l'élément en question n'existe pas déjà :

   HashSet<Interger> loto = ...; // TreeSet<Integer> loto = ...;
   ...
   boolean existe = loto.add(23);
   if (existe) System.out.println(23 + " existe déjà");
   else  System.out.println(23 + " a été ajouté");

   Nous ne pouvons pas dire que add() ajoute l'élément en "fin d'ensemble" (comme dans le cas des collections étudiées précédemment). En effet, comme nous l'avons déjà évoqué, les ensembles sont organisés au niveau de leur implémentation, de sorte que l'élément devra quand même être ajouté à un endroit bien précis de l'ensemble (endroit qui se concrétisera lorsque nous utiliserons un itérateur). Pour l'instant, nous le devinons déjà, cet endroit sera imposé par l'ordre induit par compareTo() (ou par un comparateur personnalisé) dans le cas de TreeSet ; en ce qui concerne HashSet, nous verrons bientôt comment l'emplacement est déterminé.

3. Suppression d'un élément - remove() : Nous avons vu que pour les autres collections, la méthode remove() de suppression d'une valeur donnée est d'une efficacité très moyenne. Un des grands avantages des ensembles est d'effectuer cette opération avec une très grand efficacité. Ici, la méthode remove() renvoie true si l'élément a été trouvé (et donc supprimé) et false dans le cas contraire :

   TreeSet<Personnel> employés = ...;
   ...
   boolean trouvé = employés.remove(employé);
   if (trouvé) System.out.println(employé + " a été supprimé");
   else  System.out.println(employé + " n'existe pas");

   Par ailleurs, la méthode remove() de l'itérateur monodirectionnel permet de supprimer l'élément courant (le dernier renvoyé par next()) le cas échéant :

   HashSet<Interger> loto = ...;
   Iterator<Integer> it = loto.iterator();
   it.next();
   it.next();
   it.remove(); // supprime le deuxième élément
   } 

4. Teste l'existence d'un élément - contains() : cette méthode permet de tester l'existence d'un élément avec, pour les ensembles, une très grande efficacité.
5. Opérations ensemblistes : Les méthodes removeAll(), addAll() et retainAll(), applicables à toutes les collections, prennent un intérêt tout particulier avec les ensembles. Elles bénificient de l'efficacité de l'accès à une valeur donnée. Ainsi si e1 et e2 sont deux ensembles :
   • Union : e1.addAll(e2) : place dans e1 tous les éléments présents dans e2. Après exécution, la réunion de e1 et e2 se trouve dans e1 (dont le contenu a généralement été modifié).
   • Intersection : e1.retainAll(e2) : garde dans e1 ce qui appartient à e2. Après exécution, nous obtenons l'intersection de e1 et de e2 dans e1 (dont le contenu a généralement été modifié).
   • Complément de e2 : e1.removeAll(e2) : supprime de e1 tout ce qui appartient à e2. Après exécution, nous obtenons le complémentaire de e2 par rapport à e1 dans e1 (dont le contenu a généralement été modifié).

Les ensembles de type HashSet

La classe HashSet représente un ensemble d'éléments non ordonnés. De ce fait, elle offre une solution de recherche extrêmement efficace. Cette efficacité est dû à sa structure interne et à sa méthode d'enregistrement des données. La structure de données classique pour retrouver simplement un élément est "la table de hachage".

1. Table de hachage : Une table de hachage est une organisation des éléments d'une collection qui permet de retrouver facilement un élément de valeur donnée. Pour cela, la table de hachage calcule, à l'aide de la méthode spécifique hashCode() dite "fonction de hachage", un entier, appelé "code de hachage", pour chacun des éléments. Un même entier peut correspondre à plusieurs valeurs différentes. En revanche, deux éléments de même valeur doivent toujours fournir le même code de hachage.
2. Code de hachage : Un code de hachage est un entier dérivé des champs d'instance d'un objet, pour que les objets contenant différentes données produisent des codes différents. Le tableau ci-dessous présente quelques exemples de codes de hachage nés de la méthode hashCode() de la classe String :

   Chaîne	Code de hachage
   "Emmanuel"	1162033930
   "emmanuel"	1097389802
   "manu"	3343963

   méthode hashCode() de la classe String

   int hashCode() {
         int hash = 0;
         for (int i=0;  i<length(); i++)  hash = 31 * hash  + charAt(i); 
         return hash;
   }

   Jusqu'ici, nous n'avons considéré que des ensembles dont les éléments étaient d'un type String ou de classes enveloppes (comme Integer, Double, etc.) pour lesquels, nous n'avions pas à nous préoccuper des détails d'implémentation. Dès que nous cherchons à utiliser des éléments d'un autre type d'objet, il est nécessaire de connaître quelques conséquences de la manière dont les ensembles sont effectivement implémentés. Plus précisément, dans le cas de HashSet, vous devrez définir convenablement :
   - la méthode equals() : c'est toujours elle qui sert à définir l'appartenance d'un élément à l'ensemble. si a.equals(b), a et b doivent avoir le même code de hachage.
   - la méthode hashCode() dont nous allons voir comment elle est exploitée pour ordonnancer les éléments d'un ensemble.

   Les codes de hachage peuvent être calculés très rapidement et ce calcul ne dépend que de l'état de l'objet à hacher, et non des autres objets de la table de hachage.

3. Code hachage par défaut : La méthode hashCode() est définie dans la classe Object. Chaque objet possède donc un code de hachage par défaut, extrait de l'adresse mémoire de l'objet. Etudions l'exemple suivant :

   String s = "Ok";
   StringBuilder sb = new StringBuilder(s);
   System.out.println(s.hashCode() + " " + sb.hashCode());
   String t = new String("Ok");
   StringBuilder tb = new StringBuilder(t);
   System.out.println(t.hashCode() + " " + tb.hashCode());

   Chaîne	Code de hachage
   s	2556
   sb	20526976
   t	2556
   tb	20527144

   Sachez que les chaînes s et t présentent le même code de hachage car, pour les chaînes, ces codes sont dérivés de leur contenu. Par contre, les constructeurs de chaînes sb et tb disposent de code de hachage différents car aucune méthode hashCode() n'a pas été redéfinie pour la classe StringBuilder et la méthode hashCode() de la classe Object dérive le code de hachage de l'adresse mémoire de l'objet.

   Si vous redéfinissez la méthode equals(), vous devrez aussi redéfinir la méthode hashCode() pour les objets que l'utilisateur pourraient insérer dans une table de hachage afin qu'il soit facile par la suite de les retrouver rapidement et surtout que deux objets de valeurs identiques puissent produire le même code de hachage, ce que ne fait pas la méthode hashCode() de Object.

   La méthode hashCode() doit renvoyer un entier. Associez simplement les codes de hachage des attributs de l'objet, de sorte que les codes des différents objets soient plus largement répartis.

4. Structure de la table de hachage : En Java, les tables de hachage, sont relativement sophistiquées, et sont implémentées sous forme de tableaux de listes chaînées. Chaque case du tableau dispose ainsi d'une liste qui est souvent appelée un seau (ou panier, en encore bucket). Initialement les seaux sont vides. A chaque ajout d'un élément dans la collection, elle lui attribut un emplacement dans un des seaux dont le rang n (dans le tableau de seaux) est défini en fonction de son code de hachage et réduit par le modulo du nombre total de seaux :

   seau = codeHachage % NombreDeSeaux

   Par exemple, si un objet possède un code de hachage de 76268 et qu'il existe 128 seaux, l'objet sera placé dans le seau 108 (car le reste de la division entière 76268/128 est 108). Avec un peu de chance, il n'existe aucun autre élément dans ce seau. Il suffit alors d'insérer l'élément dans le seau. Naturellement, il est inévitable de trouver parfois un seau déjà utilisé. Cela s'appelle une collision de hachage. Dans ce cas, vous comparez le nouvel objet avec tous les autres objet du seau pour déterminer s'il en fait déjà partie. S'il existe effectivement des éléments dans le seau, le nouvel élément est ajouté à la fin de la liste chaînée correspondante.
   
   

   En se fondant sur le fait que les codes de hachage sont distribués aléatoirements et que le nombre de seaux est suffisament grand, il suffit généralement d'effectuer que quelques petites comparaisons.

   Si vous désirez contrôler plus finement les performances d'une table de hachage, il est possible de spécifier le nombre initial de seaux. Si trop d'éléments sont insérés dans la table de hachage, le nombre de collisions augmente et les performances de recherche baissent. Comme nous pouvons nous y attendre, le choix du nombre initial de seaux sera fait en fonction du nombre d'éléments prévus pour la collection. On nomme "facteur de charge" le rapport entre le nombre d'éléments de la collection et le nombre de seaux. Plus ce facteur est grand, moins statistiquement, nous obtenons des seaux contenant plusieurs éléments ; par contre, plus il est grand, plus le tableau de références des seaux occupe de l'espace. Généralement, nous choisissons un facteur de charge de l'ordre de 75%. Bien entendu, la méthode de hachage joue également un rôle important dans la bonne répartition des codes des éléments dans les différents seaux.

   Pour retrouver un élément de la collection (ou pour savoir s'il est présent), on détermine d'abord son code de hachage. Ensuite la formule seau = codeHachage % NombreDeSeaux donne la valeur du seau dans lequel l'élément est succeptible de se trouver. Il ne reste plus qu'à parcourir les différents éléments du seau pour vérifier si la valeur donnée s'y trouve (à l'aide de la méthode equals()). Notez que nous utilisons cette méthode equals() que pour les seuls éléments qui sont dans le même seau.

   Avec Java, les tables de hachage sont automatiquement agrandies dès que leur facteur de charge devient trop grand (supérieur à 75%). Elles sont automatiquement réorganisées avec le double de seaux.

5. Ajout et vérification d'un élément dans l'ensemble : Les tables de hachage peuvent servir à implémenter plusieurs structures de données importantes. La plus simple d'entre elles est la classe qui implémente directement l'interface Set. Un Set correspond simplement à une collection d'éléments ne figurant qu'une seule fois chacun dans la collection. La méthode add() d'un Set commence par essayer de retrouver l'objet à ajouter et ne l'ajoute que s'il n'est pas encore présent.

   La bibliothèque de collections Java fournit une classe HashSet qui implémente un Set à partir d'une table de hachage. Les éléments sont ajoutés avec la méthode add(). La méthode contains(), que nous connaissons déjà, est redéfinie pour effectuer une recherche rapide et vérifier si un des éléments fait déjà partie du Set. Elle ne vérifie les éléments que d'un seul seau et non tous les éléments de la collection.

   L'itérateur d'un Set parcourt tous les seaux un par un. Comme les éléments d'une table de hachage sont dispersés dans toute la table, les seaux sont parcourus dans un ordre pseudo aléatoire. C'est pourquoi, il ne faut utiliser un HashSet que si l'ordre des éléments dans la collection n'a aucune importance.

   Exemple d'application d'un ensemble de prénoms

   Après toutes ces considérations techniques, il est temps de prendre un exemple. Je vais reprendre l'application précédente et placer une collection de type HashSet à la place de ArrayList et prévoir ainsi les fonctionnalités justes nécessaires à la gestion de l'ensemble des prénoms. Cette fois-ci, dans cette nouvelle application, un prénom doit être exclusif.

   Remarquez bien que les prénoms se place à priori de façon tout à fait aléatoirement dans la collection.
   §

   Vu que nous utilisons comme éléments de collection des chaînes de caractères, il n'est pas nécessaire de se préoccuper des méthodes equals() et hashCode().
   
   
   

   package ensemble;
   
   import java.awt.*;
   import java.awt.event.ActionEvent;
   import javax.swing.*;
   import java.util.*;
   
   public class Prénoms extends JFrame {
      private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 18);
      private JCheckBox existe = new JCheckBox("Existe");
      private Résultat liste = new Résultat();
      private JPanel panneau = new JPanel();
      private JToolBar barre = new JToolBar();   
      private JTextField nombre = new JTextField("0");
      
      private HashSet<String> prénoms = new HashSet<String>();
   
      public Prénoms() {
         super("Ensemble de prénoms");
         nombre.setEditable(false);
         nombre.setHorizontalAlignment(JLabel.CENTER);
         Action ajouter = new AbstractAction("Ajout") {
            public void actionPerformed(ActionEvent e) {
               prénoms.add(nouveauPrénom.getText());
               analysePrénoms();                        
            }
         };
         barre.add(ajouter);
         barre.add(new AbstractAction("Suppression") {
            public void actionPerformed(ActionEvent e) {
               prénoms.remove(nouveauPrénom.getText());
               analysePrénoms(); 
            }
         }); 
         barre.add(new AbstractAction("Tout effacer") {
            public void actionPerformed(ActionEvent e) {
               prénoms.clear();
               analysePrénoms();
            }
         });  
         barre.add(new AbstractAction("Existe ?") {
            public void actionPerformed(ActionEvent e) {
               existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
            }
         });
         barre.addSeparator();
         barre.add(new JLabel("Nombre : "));
         barre.add(nombre);
         add(barre, BorderLayout.NORTH);
         nouveauPrénom.addActionListener(ajouter);
         panneau.add(nouveauPrénom);
         panneau.add(existe);
         add(panneau);
         add(liste, BorderLayout.SOUTH);
         setSize(470, 135);
         setLocationRelativeTo(null);
         setResizable(false);
         setDefaultCloseOperation(EXIT_ON_CLOSE);
         setVisible(true);
      }
   
      public void analysePrénoms() {
         liste.repaint();
         nombre.setText(""+prénoms.size());
         existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
      }
   
      public static void main(String[] args) { new Prénoms(); }
   
      private class Résultat extends JLabel {
         public Résultat() {
            setForeground(Color.RED);
            setBorder(BorderFactory.createTitledBorder("Liste"));
         }
         @Override
         public void paint(Graphics g) {
              setText(prénoms.toString());
              super.paint(g);
         }
      }
   }
   

6. La méthode hashCode() : Elle est donc utilisée pour calculer le code de hachage d'un objet. Les classe String, File et les classes enveloppes définissent une méthode hashCode() utilisant la valeur effective des objets. En revanche, les autres classes ne redéfinissent pas hashCode() et recourent à la méthode hashCode() héritée de la classe Object, laquelle se contente d'utiliser comme "valeur" la simple adresse des objets. Dans ces conditions, deux objets différents de même valeur auront toujours des codes de hachage différents.

   Si nous souhaitons pouvoir définir une égalité des éléments basée sur leur valeur effective, il va donc falloir redéfinir dans la classe correspondante la méthode hashCode(). Elle doit effectivement fournir le code de hachage correspondant à la valeur intrinsèque de l'objet et non plus de son adresse.

   Dans la définition de cette méthode hashCode(), il ne faudra pas oublier que le code de hachage doit être compatible avec equals(). Deux objets égaux pour equals() doivent absolument fournir le même code, sinon ils risquent d'aller dans des seaux différents ; dans ce cas, il n'apparaîtrons plus comme égaux (puisque le système recourt à la méthode equals() qu'à l'intérieur d'un même seau). De même, nous ne pouvons nous permettre de redéfinir seulement equals() sans redéfinir la méthode hashCode().

Exemple d'application d'un ensemble de coordonnées

Cette fois-ci, nous allons mettre en oeuvre une nouvelle application qui stocke un ensemble de coordonnées. Ici aussi chaque point doit être exclusif. Je décris une nouvelle classe Coordonnées qui enregistre la valeur de x et de y de la position d'un point.

Remarquez bien également que les coordonnées du point se placent à priori de façon tout à fait aléatoirement dans la collection.
§

Cette fois-ci, vu que je crée une nouvelle classe, cette dernière doit redéfinir respectivement les méthodes equals(), hashCode() et toString().




package ensemble;

import java.awt.*;
import java.awt.event.ActionEvent;
import javax.swing.*;
import java.util.*;

public class EnsemblePoints extends JFrame {
   private JFormattedTextField abscisse = new JFormattedTextField(0);
   private JFormattedTextField ordonnée = new JFormattedTextField(0);
   private JCheckBox existe = new JCheckBox("Existe");
   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JFormattedTextField nombre = new JFormattedTextField(0);
   
   private HashSet<Coordonnées> ensemble = new HashSet<Coordonnées>();

   public EnsemblePoints() {
      super("Ensemble de prénoms");
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      Action ajouter = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            ensemble.add(new Coordonnées((Integer)abscisse.getValue(), (Integer)ordonnée.getValue()));
            analyse();                        
         }
      };
      barre.add(ajouter);
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            ensemble.remove(new Coordonnées((Integer)abscisse.getValue(), (Integer)ordonnée.getValue()));
            analyse(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            ensemble.clear();
            analyse();
         }
      });  
      barre.add(new AbstractAction("Existe ?") {
         public void actionPerformed(ActionEvent e) {
            existe.setSelected(ensemble.contains(new Coordonnées((Integer)abscisse.getValue(), (Integer)ordonnée.getValue())));
         }
      });
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      panneau.add(new JLabel("x : "));
      abscisse.setColumns(4);
      panneau.add(abscisse);
      panneau.add(new JLabel("y : "));
      ordonnée.addActionListener(ajouter);
      ordonnée.setColumns(4);
      panneau.add(ordonnée);
      panneau.add(existe);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(470, 135);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analyse() {
      liste.repaint();
      nombre.setValue(ensemble.size());
      existe.setSelected(ensemble.contains(new Coordonnées((Integer)abscisse.getValue(), (Integer)ordonnée.getValue())));
   }

   public static void main(String[] args) { new EnsemblePoints(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Liste"));
      }
      @Override
      public void paint(Graphics g) {
           setText(ensemble.toString());
           super.paint(g);
      }
   }
   
   private class Coordonnées {
      private int x, y;
      
      public Coordonnées(int x, int y) { this.x = x;  this.y = y; }

      @Override
      public boolean equals(Object obj) {
         Coordonnées c = (Coordonnées) obj;
         return x==c.x && y==c.y;
      }

      @Override
      public int hashCode() {
         return x*10001+y;
      }

      @Override
      public String toString() {
         return "("+x+", "+y+")";
      }      
   }
}

Les ensembles de type TreeSet

Nous venons de voir comment les ensembles HashSet organisent leurs éléments en table de hachage, en vue de les retrouver rapidement. La classe TreeSet propose une autre organisation utilisant un arbre binaire, lequel permet d'ordonner totalement les éléments. Nous utilisons, cette fois-ci, la relation d'ordre ususelle induite par la méthode compareTo() ou par un comparateur personnalisé.

Dans ces conditions, la recherche dans cet arbre d'un élément particulier est généralement moins rapide que dans la table de hachage mais tout de même plus rapide qu'une recherche séquentielle, comme avecun ArrayList ou avec un LinkedList. Par ailleurs, l'utilisation d'un arbre binaire permet de disposer en permanence d'un ensemble totalement ordonné (trié).

Nous noterons d'ailleurs que la classe TreeSet dispose de deux méthodes spécifiques : first() et last() fournissant respectivement le premier et le dernier élément de l'ensemble.

Nous noterons bien que, dans un ensemble TreeSet, la méthode equals() n'intervient ni dans l'organisation de l'ensemble, ni dans le test d'appartenance d'un élément. L'égalité est définie uniquement à l'aide de la méthode compareTo() (ou d'un comparateur personnalisé). Dans un ensemble HashSet, la méthode equals() intervenait (mais uniquement pour des éléments de même numéro de seau).

La classe TreeSet ressemble beaucoup à la classe HashSet, avec une amélioration supplémentaire. Les arbres de hachage représentent des collections triées. Vous pouvez insérer des éléments dans la collection dans n'importe quel ordre, et lorsque vous parcourez ces éléments, ils sont automatiquement présentés selon un ordre croissant. Comme le nom de la classe le laisse entendre, le tri est accompli par une structure de données en arbre.

Exemple d'application d'un ensemble de prénoms ordonnés

Reprenons tout de suite l'exemple sur la gestion des prénoms. Cette fois-ci, notre ensemble de prénoms sera ordonné dans la collection. Pour aboutir à ce résultat, il suffit tout simplement de remplacer la classe HashSet par la classe TreeSet lors de la déclaration de la collection. Pour le reste, nous pouvons conserver la même gestion.

Vu que nous utilisons comme éléments de collection des chaînes de caractères, la méthode compareTo() de la classe String a été redéfinie pour connaître si une chaîne doit être placée avant ou après une autre dans la collection, ce qui justifie cette simplicité d'écriture.

package ensemble;

import java.awt.*;
import java.awt.event.ActionEvent;
import javax.swing.*;
import java.util.*;

public class Prénoms extends JFrame {
   private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 18);
   private JCheckBox existe = new JCheckBox("Existe");
   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JTextField nombre = new JTextField("0");
   
   private TreeSet<String> prénoms = new TreeSet<String>();

   public Prénoms() {
      super("Ensemble de prénoms");
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      Action ajouter = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            prénoms.add(nouveauPrénom.getText());
            analysePrénoms();                        
         }
      };
      barre.add(ajouter);
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            prénoms.remove(nouveauPrénom.getText());
            analysePrénoms(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            prénoms.clear();
            analysePrénoms();
         }
      });  
      barre.add(new AbstractAction("Existe ?") {
         public void actionPerformed(ActionEvent e) {
            existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
         }
      });
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      nouveauPrénom.addActionListener(ajouter);
      panneau.add(nouveauPrénom);
      panneau.add(existe);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(470, 135);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analysePrénoms() {
      liste.repaint();
      nombre.setText(""+prénoms.size());
      existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
   }

   public static void main(String[] args) { new Prénoms(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Liste"));
      }
      @Override
      public void paint(Graphics g) {
           setText(prénoms.toString());
           super.paint(g);
      }
   }
}

Depuis Java SE 6, les ensembles TreeSet implémentent en outre l'interface NavigableSet qui prévoit des méthodes exploitant l'ordre total induit par l'organisation de l'ensemble (en un arbre binaire). Ces méthodes peuvent retrouver et, éventuellement, de supprimer l'élément le plus petit ou le plus grand au sens de cet ordre, ou encore de trouver l'élément le plus proche (avant ou après) d'une valeur donnée. Il est possible de parcourir les éléments dans l'ordre inverse de l'ordre naturel. Enfin, certaines méthodes permettent d'obtenir une vue (cette notion sera présentée ultérieurement) d'une partie de l'ensemble, formée des éléments de valeur supérieure ou inférieure à une valeur donnée.

L'interface java.util.NavigableSet<E>

E higher(E valeur)
E lower(E valeur)

Renvoie la > valeur du plus petit élément ou la < valeur du plus grand élément ou encore null si cet élément n'existe pas.

E ceiling(E valeur)
E floor(E valeur)

Renvoie la >= valeur du plus petit élément ou la <= valeur du plus grand élément ou encore null si cet élément n'existe pas.

E pollFirst()
E pollLast()

Suppriment et renvoient le plus petit ou le plus grand élément de cet ensemble ou encore null si l'ensemble est vide.

Iterator<E> descendingIterator()

Renvoie un itérateur qui parcourt cet ensemble par ordre décroissant.

Comparaison d'objets

Comment TreeSet (ou TreeMap dans le chapitre suivant) sait-il dans quel ordre trier les éléments ? Par défaut, cette structure de données part de l'hypothèse que vous insérez des éléments qui implémentent l'interface Comparable, ce qui est d'ailleurs le cas des classes que nous avons déjà utilisé comme la classe Integer ou la classe String.

import java.util.*;
import static java.lang.System.*;

public class Liste {
   public static void main(String[] args) {
      Personne schmidt, lagafe;    
      TreeSet<Personne> ensemble = new TreeSet<Personne>();
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(lagafe = new Personne("LAGAFE", "Gaston", 23));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(schmidt = new Personne("SCHMIDT", "Jules", 30));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(new Personne("TALON", "Achille", 13));
      afficheEnsemble(ensemble);
      if (ensemble.contains(schmidt))
         ensemble.remove(schmidt);
      afficheEnsemble(ensemble);
      ensemble.add(lagafe); 
      afficheEnsemble(ensemble);
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Personne> ensemble) {
      out.print("ensemble = { ");
      for(Personne valeur : ensemble) out.println(valeur+" ");
      out.println("} : nombre = "+ensemble.size());
   }
}

class Personne {
   private String nom, prénom;
   private int âge;  
   public Personne(String nom, String prénom, int âge) {
      this.nom = nom;
      this.prénom = prénom;
      this.âge = âge;
   }
   public String getNom() { return nom; }
   public String getPrénom() { return prénom; }
   public int getÂge() { return âge; } 
}

import java.util.*;
import static java.lang.System.*;

public class Liste {
   public static void main(String[] args) {
      Personne schmidt, lagafe;     
      TreeSet<Personne> ensemble = new TreeSet<Personne>();
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(lagafe = new Personne("LAGAFE", "Gaston", 23));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(schmidt = new Personne("SCHMIDT", "Jules", 30));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(new Personne("TALON", "Achille", 13));
      afficheEnsemble(ensemble);
      if (ensemble.contains(schmidt))
         ensemble.remove(schmidt);
      afficheEnsemble(ensemble);
      ensemble.add(lagafe); 
      afficheEnsemble(ensemble);
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Personne> ensemble) {
      out.println("ensemble { ");
      for(Personne p : ensemble) 
         out.println("..."+p.getNom()+" "+p.getPrénom()+" : "+p.getÂge());
      out.println("} : nombre = "+ensemble.size());
   }
}

class Personne implements Comparable<Personne> {
   private String nom, prénom;
   private int âge;  
   public Personne(String nom, String prénom, int âge) {
      this.nom = nom;
      this.prénom = prénom;
      this.âge = âge;
   }
   public String getNom() { return nom; }
   public String getPrénom() { return prénom; }
   public int getÂge() { return âge; } 

   public int compareTo(Personne p) {
      if (!nom.equalsIgnoreCase(p.nom)) return nom.compareToIgnoreCase(p.nom);
      if (!prénom.equalsIgnoreCase(p.prénom)) return prénom.compareToIgnoreCase(p.prénom);   
      return âge - p.âge;
   }
}

import java.util.*;
import static java.lang.System.*;

public class Liste {
   public static void main(String[] args) {
      Personne schmidt, lagafe;     
      TreeSet<Personne> ensemble = new TreeSet<Personne>(new TrierPersonne());
      out.println("ensemble vide ? "+ensemble.isEmpty());
      ensemble.add(lagafe = new Personne("LAGAFE", "Gaston", 23));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(schmidt = new Personne("SCHMIDT", "Jules", 30));
      ensemble.add(new Personne("GUILLEMET", "Virgule", 13));
      ensemble.add(new Personne("TALON", "Achille", 13));
      afficheEnsemble(ensemble);
      if (ensemble.contains(schmidt))
         ensemble.remove(schmidt);
      afficheEnsemble(ensemble);
      ensemble.add(lagafe); 
      afficheEnsemble(ensemble);
      ensemble.clear();
      out.println("Taille de ensemble : "+ensemble.size());
   }
   public static void afficheEnsemble(TreeSet<Personne> ensemble) {
      out.println("ensemble { ");
      for(Personne p : ensemble) 
         out.println("..."+p.getNom()+" "+p.getPrénom()+" : "+p.getÂge());
      out.println("} : nombre = "+ensemble.size());
   }
}

class Personne {
   private String nom, prénom;
   private int âge;  
   public Personne(String nom, String prénom, int âge) {
      this.nom = nom;
      this.prénom = prénom;
      this.âge = âge;
   }
   public String getNom() { return nom; }
   public String getPrénom() { return prénom; }
   public int getÂge() { return âge; } 
}

class TrierPersonne implements Comparator<Personne> {
   public int compare(Personne p1, Personne p2) {
      if (!p1.getNom().equalsIgnoreCase(p2.getNom())) 
         return p1.getNom().compareToIgnoreCase(p2.getNom());
      if (!p1.getPrénom().equalsIgnoreCase(p2.getPrénom())) 
         return p1.getPrénom().compareToIgnoreCase(p2.getPrénom());
      return p1.getÂge() - p2.getÂge();
   }
}

Les ensembles de type EnumSet

EnumSet est une implémentation efficace d'un ensemble, dont les éléments appartiennent à un type énuméré. Un type énuméré ayant un nombre fini d'instances, EnumSet est implémenté en interne sous la forme d'une suite de bits. Un bit est activé si la valeur correspondante est présente dans l'ensemble.

La classe java.util.EnumSet<E extends Enum<E>>

static <E extends Enum<E>> EnumSet<E> allOf(Class<E> typeEnumération)

Renvoie un ensemble contenant toutes les valeurs du type énuméré donné.

static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> typeEnumération)

Renvoie un ensemble vide capable de contenir des valeurs du type énuméré donné.

static <E extends Enum<E>> EnumSet<E> range(E de, E à)

Renvoie un ensemble contenant toutes les valeurs comprises entre de et à (compris).

static <E extends Enum<E>> EnumSet<E> of(E valeur)
static <E extends Enum<E>> EnumSet<E> of(E valeur, E... valeurs)

Renvoie un ensemble contenant les valeurs données. Il peut y en avoir un nombre quelconque.

enum Semaine {LUNDI, MARDI, MERCREDI, JEUDI, VENDREDI, SAMEDI, DIMANCHE};
EnumSet<Semaine> touslesjours = EnumSet.allOf(Semaine.class);
EnumSet<Semaine> aucunjours = EnumSet.noneOf(Semaine.class);
EnumSet<Semaine> jourstravail = EnumSet.range(Semaine.LUNDI, Semaine.VENDREDI);
EnumSet<Semaine> weekend = EnumSet.of(Semaine.SAMEDI, Semaine.DIMANCHE);

Pour modifier un EnumSet, vous pouvez utiliser les méthodes habituelles de l'interface Set.
§

Pour en savoir plus sur les énumérations.
§

Exemple d'application d'un ensemble qui enregistre les jours de la semaine

A titre d'exemple, nous allons mettre en oeuvre un ensemble qui stoque les jours de la semaine.

La zone d'édition est remplacée par une boîte combo avec la liste des jours qu'il suffit alors de sélectionner. Remarquez au passage qu'un ensemble d'énumération est systématiquement ordonné. L'ordre proposé correspond à la suite des indices donné par chaque énumérateur.

package ensemble;

import java.awt.*;
import java.awt.event.ActionEvent;
import javax.swing.*;
import java.util.*;

public class Semaine extends JFrame {   
   private JCheckBox existe = new JCheckBox("Existe");
   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JTextField nombre = new JTextField("0");
   
   private enum Jours {Lundi, Mardi, Mercredi, Jeudi, Vendredi, Samedi, Dimanche};
   private JComboBox nouveauJour = new JComboBox(Jours.values());
   private EnumSet<Jours> jours = EnumSet.noneOf(Jours.class);

   public Semaine() {
      super("Les jours de la semaine");
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      Action ajouter = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            jours.add((Jours) nouveauJour.getSelectedItem());
            analyseJours();                        
         }
      };
      barre.add(ajouter);
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            jours.remove((Jours) nouveauJour.getSelectedItem());
            analyseJours(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            jours.clear();
            analyseJours();
         }
      });  
      barre.add(new AbstractAction("Existe ?") {
         public void actionPerformed(ActionEvent e) {
            existe.setSelected(jours.contains((Jours) nouveauJour.getSelectedItem()));
         }
      });
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      nouveauJour.addActionListener(ajouter);
      panneau.add(nouveauJour);
      panneau.add(existe);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(400, 135);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analyseJours() {
      liste.repaint();
      nombre.setText(""+jours.size());
      existe.setSelected(jours.contains((Jours) nouveauJour.getSelectedItem()));
   }

   public static void main(String[] args) { new Semaine(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Liste"));
      }
      @Override
      public void paint(Graphics g) {
           setText(jours.toString());
           super.paint(g);
      }
   }
}

Les ensembles de type LinkedHashSet

Il reste un dernier ensemble, un peu particulier, qui se souvient de l'ordre d'insertion des éléments. De cette manière, vous évitez l'ordre assez aléatoire des éléments dans la table de hachage. A mesure que des entrées sont insérées dans la table, elles sont simplement reliées ensemble dans une liste doublement chaînée. Cet ensemble est implémenté par la classe LinkedHashSet.

Exemple d'application d'un ensemble de prénoms

Nous allons tout de suite prendre un exemple puisque cette collection ne présente rien de bien nouveau si ce n'est sa petite particularité. Je vais reprendre l'application précédente sur la gestion des prénoms et placer une collection de type LinkedHashSet à la place de HashSet. Comme toujours, dans les ensembles, un prénom doit être exclusif.

Remarquez bien que cette fois-ci les prénoms se place dans la collection suivant l'ordre d'insertion.
§

Vu que nous utilisons comme éléments de collection des chaînes de caractères, il n'est pas nécessaire de se préoccuper des méthodes equals() et hashCode().

package ensemble;

import java.awt.*;
import java.awt.event.ActionEvent;
import javax.swing.*;
import java.util.*;

public class Prénoms extends JFrame {
   private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 18);
   private JCheckBox existe = new JCheckBox("Existe");
   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JTextField nombre = new JTextField("0");
   
   private LinkedHashSet<String> prénoms = new LinkedHashSet<String>();

   public Prénoms() {
      super("Ensemble de prénoms");
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      Action ajouter = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            prénoms.add(nouveauPrénom.getText());
            analysePrénoms();                        
         }
      };
      barre.add(ajouter);
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            prénoms.remove(nouveauPrénom.getText());
            analysePrénoms(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            prénoms.clear();
            analysePrénoms();
         }
      });  
      barre.add(new AbstractAction("Existe ?") {
         public void actionPerformed(ActionEvent e) {
            existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
         }
      });
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      nouveauPrénom.addActionListener(ajouter);
      panneau.add(nouveauPrénom);
      panneau.add(existe);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(470, 135);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analysePrénoms() {
      liste.repaint();
      nombre.setText(""+prénoms.size());
      existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
   }

   public static void main(String[] args) { new Prénoms(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Liste"));
      }
      @Override
      public void paint(Graphics g) {
           setText(prénoms.toString());
           super.paint(g);
      }
   }
}

Les queues - ArrayDeque, LinkedList et PriorityQueue

Les queues implémentent les files d'attente.

Les queues sont utilisées si vous devez enregistrer des objets et les récupérer selon la règle "premier entré, premier sortie" (FIFO - First In First Out)

Il en existe de plusieurs sortes :

1. Les queues à simple entrées,
2. Les queues à doubles entrées,
3. et les queues de priorité qui récupèrent des éléments triés.

Interface de queue de données - Queue

Comme nous l'avons déjà découvert au tout début de l'étude des collections, il existe une interface Queue, dérivée de l'interface Collection, destinée à la gestion des files d'attente (ou queues). Il s'agit d'une structure dans laquelle nous pouvons :

1. Introduire un nouvel élément à la fin de la queue, si la queue n'est pas pleine : L'introduction d'un nouvel élément dans la queue se fait à l'aide d'une nouvelle méthode offer(), qui présente, sur la méthode add() de l'interface Collection, l'avantage de ne pas déclencher d'exception quand la queue est pleine ; dans ce cas, offer() renvoie simplement la valeur false.
2. Prélever le premier élément de la queue (début de queue) : Le prélèvement du premier élément de la queue peut se faire :
   • de façon destructive : à l'aide de la méthode poll() : l'élément ainsi prélevé est supprimé de la queue ; la méthode renvoie null si la queue est vide.
   • de façon non destructive : à l'aide de la méthode peek().
3. Déterminer le nombre d'éléments contenus dans une queue.

Il est impossible d'ajouter ou de supprimer des éléments au milieu de la file d'attente.
§

L'interface java.util.Queue<E>

boolean add(E élément)
boolean offer(E élément)

Ajoute l'élément à la fin de la queue et renvoie true, à condition que la queue ne soit pas pleine. Si la queue est pleine, la première méthode déclenche une exception IllegalStateException, tandis que la seconde renvoie false.

E remove()
E poll()

Suppriment et renvoient l'élément au début de cette queue, à condition que la queue ne soit pas vide. Si la queue est vide, la première méthode déclenche une exception NoSuchElementException, tandis que la seconde renvoie null.

E element()
E peek()

Renvoient l'élément au début de cette queue sans le supprimer, à condition que la queue ne soit pas vide. Si la queue est vide, la première méthode déclenche une exception NoSuchElementException, tandis que la seconde renvoie null.

Interface de queue à double entrée - Deque

Une queue à deux extrémités permet d'ajouter ou de supprimer efficacement des éléments en début et à la fin. Java 6 a introduit une nouvelle interface Deque, dérivée de Queue, destinée à gérer les files d'attente à double entrée, c'est-à-dire dans lesquelles nous pouvons réaliser l'une des opérations suivantes à l'une des extrémités de la queue :

1. ajouter un élément,
2. examiner un élément,
3. supprimer un élément.

Il est impossible d'ajouter ou de supprimer des éléments au milieu de la file d'attente.
§

Pour chacune de ces possibilités (3 actions, 2 extrémités), il existe deux méthodes :

1. l'une déclenchant une exception quand l'opération échoue (pile pleine ou vide, selon le cas),
2. l'autre renvoyant une valeur particulière (null pour une méthode de prélèvement ou d'examen, false pour une méthode d'ajout).

A noter que les méthodes de l'interface Queue restent utilisables, sachant que celles d'ajout agissent sur la queue, tandis que celles d'examen ou de suppression agissent sur la tête.

L'interface java.util.Deque<E>

void addFirst(E élément)
void addLast(E élément)
boolean offerFirst(E élément)
boolean offerLast(E élément)

Ajoute l'élément au début ou à la fin de la queue. Si la queue est pleine, les deux premières méthodes déclenchent une exception IllegalStateException, tandis que les deux dernières renvoient false.

E removeFirst()
E removeLast()
E pollFirst()
E pollLast()

Suppriment et renvoient l'élément au début ou à la fin de cette queue, à condition que la queue ne soit pas vide. Si la queue est vide, les deux premières méthodes déclenchent une exception NoSuchElementException, tandis que les deux dernières méthodes renvoient null.

E getFirst()
E getLast()
E peekFirst()
E peekLast()

Renvoient l'élément au début ou à la fin de cette queue sans le supprimer, à condition que la queue ne soit pas vide. Si la queue est vide, les deux premières méthodes déclenchent une exception NoSuchElementException, tandis que les deux dernières méthodes renvoient null.

Les classes qui implémentent ces deux interfaces spécifiques aux files d'attente

Il existe trois classes qui sont capables d'implémenter l'une de ces interface :

1. La première implémentation, que nous connaissons bien, est représentée par la classe LinkedList, se sert d'une liste chaînée :
   
   

   Cette classe LinkedList a été modifiée par le Java 5, pour y intégrer les nouvelles méthodes de l'interface Queue. Depuis Java 6, cette classe implémente également l'interface Deque disposant de méthodes d'action à la fois sur le début et la fin de la liste.

2. La deuxième implémentation, représentée par la classe ArrayDeque, se sert d'un tableau circulaire :
   
   

   Comme son non l'indique, la classe ArrayDeque implément l'interface Deque. Il s'agit donc d'une implémentation d'une queue à double entrée sous forme d'un tableau (éléments contigus en mémoire) redimensionnable à volonté (comme l'est l'ArrayList). On notera bien que, malgré son nom, cette classe n'est pas destinée à concurencer ArrayList, car elle ne dispose pas d'opérateur d'accès direct à un élément. Il s'agit simplement d'une impémentation plus efficace que LinkedList pour une queue à double entrée.

   Pourquoi choisir une implémentation plutôt qu'une autre ? Une interface ne fournit aucun détail quant à l'efficacité de son implémentation. De manière générale, un tableau circulaire est plus efficace qu'une liste chaînée, et il est donc préférable à cette dernière. Toutefois, comme d'habitude, il y a un prix à payer. Les tableaux circulaires font partie d'une collection bornée, qui a une capacité déterminée. Si vous ne connaissez pas la limite maximale du nombre d'objets stockés par votre programme, vous préférerez probablement une implémentation en liste chaînée.

   En étudiant la documentation de l'API, vous découvrirez un autre jeu de classes dont le nom commence par Abstract, comme AbstractQueue. Ces classes sont destinées aux implémentations de bibliothèque. Pour implémenter votre propre classe de queue, il sera plus facile d'étendre AbstractQueue que d'implémenter toutes les méthodes de l'interface Queue.

   La classe java.util.ArrayDeque<E>

   ArrayDeque()
   ArrayDeque(int capacité)

   Construisent des queues sans limites avec une capacité initiale de 16 ou la capacité initiale donnée.

   Exemple d'application d'une file d'attente de prénoms

   Pour éviter de mettre en oeuvre une nouvelle application, je reprends l'application précédente pour gérer une simple queue de prénoms. La file d'attente est implémentée par la classe ArrayDeque mais je ne me sert que d'une queue à simple entrée. Cette fois-ci, lorsque que nous supprimons un prénom de la queue, elle s'affiche dans la zone d'édition.

   Remarquez bien que les prénoms se place dans la collection suivant l'ordre d'insertion. La suppression se fait uniquement sur les premiers entrés
   §

   

   ...
   
   public class Prénoms extends JFrame {
      private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 18);
      private JCheckBox existe = new JCheckBox("Existe");
      private Résultat liste = new Résultat();
      private JPanel panneau = new JPanel();
      private JToolBar barre = new JToolBar();   
      private JTextField nombre = new JTextField("0");
      
      private ArrayDeque<String> prénoms = new ArrayDeque<String>();
   
      public Prénoms() {
         super("Ensemble de prénoms");
         nombre.setEditable(false);
         nombre.setHorizontalAlignment(JLabel.CENTER);
         Action ajouter = new AbstractAction("Ajout") {
            public void actionPerformed(ActionEvent e) {
               prénoms.offer(nouveauPrénom.getText());
               analysePrénoms();                        
            }
         };
         barre.add(ajouter);
         barre.add(new AbstractAction("Suppression") {
            public void actionPerformed(ActionEvent e) {
               nouveauPrénom.setText(prénoms.poll());
               analysePrénoms(); 
            }
         }); 
         barre.add(new AbstractAction("Tout effacer") {
            public void actionPerformed(ActionEvent e) {
               prénoms.clear();
               analysePrénoms();
            }
         });  
         barre.add(new AbstractAction("Existe ?") {
            public void actionPerformed(ActionEvent e) {
               existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
            }
         });
   ...
   }

3. La troisième implémentation est représentée par la classe PriorityQueue, introduite par Java 5, qui permet de choisir une relation d'ordre ; dans ce cas, le type des éléments doit implémenter l'interface Comparable ou être doté d'un comparateur approprié. Les éléments de la queue sont alors ordonnés par cette relation d'ordre et le prélèvement d'un élément porte alors sur le "premier" au sens de cette relation (on parle du "plus prioritaire", d'où le nom de PriorityQueue).

   Une queue de priorité récupère des éléments triés, après qu'ils ont été insérés dans un ordre arbitraire. Ainsi, dès que vous appelez la méthode remove(), vous obtenez le plus petit élément se trouvant dans la queue. Celle-ci ne trie toutefois pas tous ses éléments. Si vous parcourez les éléments, ils ne sont pas nécessairement triés. La queue de priorité fait usage d'une structure de données efficace et élégante, appelée un tas. Il s'agit d'une arborescence binaire dans laquelle les opérations add() et remove() amènent l'élément le plus petit à graviter autour de la racine, sans perdre de temps à trier tous les éléments.

   A l'instar d'un TreeSet, une queue de priorité peut contenir soit les éléments d'une classe qui implémente l'interface Comparable, soit un objet Comparator que vous fournissez dans le constructeur.

   Ces queues servent généralement à planifier les tâches. Chaque tâche se voit attribuer une priorité et elles sont ajoutées dans un ordre aléatoire. Dès le démarrage possible d'une nouvelle tâche, celle ayant la plus haute priorité est supprimée de la queue (la priorité 1 étant généralement la plus forte, l'opération de suppression concerne le plus petit élément).

   La classe java.util.PiorityQueue<E>

   PriorityQueue()
   PriorityQueue(int capacité)

   Construisent une queue de priorité pour stocker des objets Comparable.

   PriorityQueue(int capacité, Comparator<? super E> comparateur)

   Construit une queue de priorité et utilise le comparateur spécifié pour trier ses éléments.

   Exemple d'application d'une file d'attente de prénoms

   Je reprends de nouveau l'application sur la file d'attente des prénoms. Cette fois-ci toutefois, la file d'attente est implémentée par la classe PriorityQueue. Ainsi, lorsque que nous supprimons un prénom de la queue, il s'agit toujours de celui qui est le premier dans l'ordre alphabétique.

   Au moment de l'insertion, tous les prénoms ne sont pas spécialement dans l'ordre alphabétique, sauf pour le premier. Lorsque nous commençons à supprimer des éléments, un arrangement s'effectue pour être sûr que le suivant soit bien le nouveau premier dans l'ordre alphabétique.

   

   ...
   
   public class Prénoms extends JFrame {
      private JTextField nouveauPrénom = new JTextField("Nouveau prénom", 18);
      private JCheckBox existe = new JCheckBox("Existe");
      private Résultat liste = new Résultat();
      private JPanel panneau = new JPanel();
      private JToolBar barre = new JToolBar();   
      private JTextField nombre = new JTextField("0");
      
      private PriorityQueue<String> prénoms = new PriorityQueue<String>();
   
      public Prénoms() {
         super("Ensemble de prénoms");
         nombre.setEditable(false);
         nombre.setHorizontalAlignment(JLabel.CENTER);
         Action ajouter = new AbstractAction("Ajout") {
            public void actionPerformed(ActionEvent e) {
               prénoms.offer(nouveauPrénom.getText());
               analysePrénoms();                        
            }
         };
         barre.add(ajouter);
         barre.add(new AbstractAction("Suppression") {
            public void actionPerformed(ActionEvent e) {
               nouveauPrénom.setText(prénoms.poll());
               analysePrénoms(); 
            }
         }); 
         barre.add(new AbstractAction("Tout effacer") {
            public void actionPerformed(ActionEvent e) {
               prénoms.clear();
               analysePrénoms();
            }
         });  
         barre.add(new AbstractAction("Existe ?") {
            public void actionPerformed(ActionEvent e) {
               existe.setSelected(prénoms.contains(nouveauPrénom.getText()));
            }
         });
   ...
   }

Dictionnaires - Cartes - Tables associatives

Un Set (ensemble) est une collection qui vous permet de retrouver rapidement un élément. Pour cela, il faut le connaître exactement, ce qui n'est pas souvent le cas. En fait, nous disposons généralement de certaines informations importantes sur l'élément à rechercher, et il faut le retrouver à partir de ces informations.

Implémentation

Comme pour les ensembles, l'intérêt des tables associatives est de pouvoir retrouver rapidement une clé donnée pour en obtenir l'information associée. Java dispose de plusieurs classes, avec les deux que nous venons de découvrir, qui implémentent ces différents dictionnaires, chacune ayant sa propre particularité. Dans tous les cas, seule la clé sera utilisée pour ordonnancer les informations.

La classe HashMap mémorise ses entrées dans un ordre quelconque, tandis que la classe TreeMap mémorise ses entrées dans l'ordre ascendant avec un arbre, pour maintenir plus rapidement le tri des éléments stockées. Vous avez ci-dessous d'autres classes qui implémentent également l'interface Map.

1. HashMap : Carte de hachage : Une structure de données en forme de table de hachage qui stocke les associations clé / valeur. Cette implémentation se sert d'un code de hachage pour les objets formant les clés.
   
   

   La classe java.util.HashMap<Key, Value>

   HashMap()
   HashMap(int capacité)
   HashMap(int capacité, float facteurDeCharge)

   Construisent une carte de hachage vide avec la capacité et le facteur de charge spécifiés (un nombre compris entre 0,0 et 1,0) qui détermine le pourcentage de remplissage au-dela duquel la table de hachage sera réorganisée). Le facteur de charge par défaut vaut 0,75.

2. TreeMap : Carte triée : Une concordance dans laquelle les clés sont triées. Cette implémentation se sert d'un ordre total pour organiser les clés dans un arbre de recherche. Il s'agit donc d'un arbre binaire qui prend en compte l'ordre induit par la méthode compareTo() ou par un comparateur fixé à la construction.

   Les fonctions de hachage ou de comparaison ne sont appliquées qu'aux clés. Les valeurs associées ne sont ni comparées ni réparties.
   §

   
   

   La classe java.util.TreeMap<Key, Value>

   TreeMap(Comparator<? super Key> carte)

   Construit une carte en arbre et se sert du comparateur pour trier ses clés.

   TreeMap(Map<? extends Key, ? extends Value> entrées)

   Construit une carte en arbre et y ajoute toutes les entrées de la carte spécifiée.

   TreeMap(SortedMap<? extends Key, ? extends Value> entrées)

   Construit un arbre, ajoute toutes les entrées de la carte triée et se sert du même comparateur d'éléments que la carte triée.

   L'interface java.util.SortedMap<Key, Value>

   Comparator<? super Key> comparator()

   Renvoie le comparateur servant à trier les clés ou null si les clés sont comparées à l'aide de la méthode compareTo() de l'interface Comparable.

   Key firstKey()
   Key lastKey()

   Renvoie la plus petite ou la plus grande clé de la carte.

3. EnumMap : Carte d'énumération : Une concordance dans laquelle les clés appartiennent à un type énuméré. Il est implémenté de manière simple et efficace sous forme de tableau de valeurs. Le type de la clé doit être spécifié dans le constructeur :

   enum Semaine {LUNDI, MARDI, MERCREDI, JEUDI, VENDREDI, SAMEDI, DIMANCHE};
   EnumMap<Semaine, String> alertes = new EnumMap<Semaine, String>(Semaine.class);

   
   

   La classe java.util.EnumMap<Key extends <Key>, Value>

   EnumMap(Class<Key> typeDeClé)

   Construit une carte vide dont les clés ont le type spécifié.
   

4. LinkedHashMap : Carte de hachage liée : Une concordance qui se souvient de l'ordre d'ajout des entrées. Une carte de hachage liée peut utiliser l'ordre d'accès, et non l'ordre d'insertion, pour parcourir les entrées de la carte. Chaque fois que vous appelez get() et put(), l'entrée affectée est supprimée de sa position et placée à la fin de la liste chaînée des entrées (seule la position dans la liste chaînée est concernée, et non le seau de la table de hachage. Une entrée reste toujours dans le seau qui correspond au code de hachage de la clé).
   
   

   La classe java.util.LinkedHashMap<Key, Value>

   LinkedHashMap()
   LinkedHashMap(int capacité)
   LinkedHashMap(int capacité, float facteurDeCharge)
   LinkedHashMap(int capacité, float facteurDeCharge, boolean ordreD'accès)

   Construisent une carte de hachage liée vide avec la capacité, le facteur de charge et l'ordre spécifiés. Le paramètre ordreD'accès vaut true pour l'ordre d'accès, false pour l'ordre d'insertion.

   protected boolean removeEdestEntry(Map.Entry<Key, Value> ancien)

   Doit être surchargé pour renvoyer true si vous souhaitez supprimer l'entrée la plus ancienne. Le paramètre le plus ancien correspond à l'entrée dont on envisage la suppression. Cette méthode est appelée après qu'une entrée a été ajoutée à la carte. L'implémentation par défaut renvoie false, les anciens éléments ne sont pas supprimés par défaut. Vous pouvez toutefois redéfinir cette méthode pour renvoyer de manière sélective true, par exemple si l'entrée la plus ancienne répond à une certaine condition ou si la carte dépasse une certaine taille.

   L'ordre d'accès est utile pour implémenter le système de "la dernière utilisée" pour un cache. Par exemple, vous voulez conserver les entrées fréquemment lues en mémoire et lire des objets lus moins souvent à partir d'une base de données. Lorsqu'une entrée d'une table est introuvable et que la table est déjà assez pleine, vous pouvez obtenir un itérateur dans la table, puis supprimer les premiers éléments qu'elle énumère. Ces entrées étaient les dernières utilisées.

   Vous pouvez même automatiser cette procédure. Formez une sous-classe de LinkedHashMap et surcharchez la méthode removeEldestEntry(). Ajoutez ensuite une nouvelle entrée pour supprimer l'entrée la plus ancienne lorsque votre méthode renvoie true. Par exemple, le cache suivant est conservé à une taille maximale de 100 éléments :

   Map<Key, Value> cache = new LinkedHashMap<Key, Value>(64, 0.75F, true) {
      protected boolean  removeEdestEntry(Map.Entry<Key, Value> ancien) {
         return size() > 100;
      }
   }

   Vous pouvez également envisager de prendre en compte l'élément ancien pour décider si vous devez le supprimer. Par exemple, vous devrez peut-être vérifier une indication de la date et de l'heure stockée avec l'entrée.

   
   
5. WeakHashMap : Carte de hachage faible : Une concordance avec des valeurs pouvant être réclamées par le ramasse-miettes si elles ne sont pas utilisées ailleurs.

   La classe WeakHashMap a été conçue dans le but de résoudre un problème intéressant. Que se passe-t-il avec une valeur lorsque sa clé n'est plus utilisée nulle part dans le programme ? Supposons que la dernière référence à une clé ait disparu. Il n'y a alors plus aucune manière de se référer à l'objet de la valeur. Toutefois, étant donné qu'aucune partie du programme ne possède plus la clé, la paire clé/valeur ne peut être supprimée de la carte. Pourquoi alors le ramasse-miettes ne peut-t-il pas la supprimer ? Ce serait en effet son rôle de supprimer les objets inutilisés.

   Malheureusement, la situation n'est pas aussi simple. Le ramasse-miettes suit les objets vivants. Tant que l'objet de carte est vivant, tous les seaux qu'il contient sont également vivants et ils ne seront pas réclamés. Ainsi, votre programme doit supprimer les valeurs inutilisées des cartes vivantes. Vous pouvez également utiliser à la place WeakHashMap. Cette structure de données coopère avec le ramasse-miettes pour supprimer les paires clé/valeur lorsque la seule référence à la clé est la référence de l'entrée de la table de hachage.
   

   Voici en fait le fonctionnement interne de ce mécanisme. WeakHashMap utilise des références faibles pour conserver les clés. Un objet WeakReference contient une référence à un autre objet, dans notre cas, une clé de table de hachage. Les objets de ce type sont considérés de manière particulière par le ramasse-miettes. Normalement, s'il découvre qu'un objet particulier ne possède pas de références vers lui, il réclame simplement l'objet. Toutefois, si l'objet peut être atteint uniquement par un WeakReference, le ramasse-miettes réclame toujours l'objet, mais place la référence faible qui y menait dans une queue. Les opérations du WeakHashMap vérifient périodiquement cette queue pour y retrouver des références faibles nouvellement arrivées. L'arrivée d'une référence faible dans la queue signifie que la clé n'est plus utilisée par personne et qu'elle a été collectée. WeakHashMap supprime alors l'entrée associée.

   La classe java.util.WeakHashMap<Key, Value>

   WeakHashMap()
   WeakHashMap(int capacité)
   WeakHashMap(int capacité, float facteurDeCharge)

   Construisent une carte de hachage vide avec la capacité et le facteur de charge spécifiés.
   

6. IdentityHashMap : Carte de hachage d'identité : Une concordance avec des clés comparées par ==, et non par equals().

   Java 1.4 a ajouté une autre classe IdentyHashMap pour un autre objectif assez spécialisé, où les valeurs de hachage pour les clés ne doivent pas être calculées par la méthode hashCode() mais par la méthode System.identityHashCode(). C'est la méthode utilisée par Object.hashCode() pour calculer le code de hachage à partir de l'adresse mémoire de l'objet. De même, pour la comparaison des objets, IdentityHashMap utilise ==, et non equals().

   En d'autres termes, différents objets de clé sont considérés comme distincts, même s'ils ont un contenu égal. Cette classe est utile pour implémenter des algorithmes object transversal (comme la sérialisation des objets), dans lesquels vous souhaitez effectuer le suivi des objets auxquels on a déjà appliqué traversed.

   La classe java.util.IdentityHashMap<Key, Value>

   WeakHashMap()
   WeakHashMap(int capacité)

   Construisent une carte de hachage d'identité vide dont la capacité est la plus petite puissance de 2 dépassant 1,5 x capacité (le paramètre par défaut pour capacité vaut 21).

   La classe java.lang.System

   static int identityHashCode(Object objet)

   Renvoie le même code de hachage (dérivée de l'adresse mémoire de l'objet) que Object.hashCode(), même si la classe à laquelle appartient objet a redéfini la méthode hashCode().

Fonctionnalités des cartes

Toutes les classes que nous venons de décourvrir implémentent l'interface Map qui proposent des fonctionnalités communes et que nous allons maintenant étudier.

1. Ajout d'information : La plupart des constructeurs créent une table vide. Pour ajouter une clé à une carte, nous devons utiliser la méthode put() à laquelle nous fournissons la clé et la valeur associée.

   Map<String, String> téléphones = new TreeMap<String, String>();
   téléphones.put("Virgule GUILLEMET", "08-71-63-18-08");

   Les clés doivent être uniques. Il n'est pas permis d'associer deux valeurs à la même clé. Si vous appelez la méthode put() deux fois avec la même clé, la seconde valeur remplace la première. En fait, put() renvoie la dernière valeur correspondant à la clé fournie.

   Notez que, comme pour les autres collections, les clés et les valeurs doivent être des objets. Il n'est théoriquement pas nécessaire que toutes les clés soient du même type, pas plus que les éléments. En pratique, ce sera presque toujours le cas pour des questions évidentes de facilité d'exploitation de la table.

2. Recherche d'information : Pour retrouver un élément, il faut se servir de la clé (et par conséquent, il faut la connaître). Nous obtenons la valeur à une clé donnée à l'aide de la méthode get() :

   String nom = "Virgule GUILLEMET";
   String téléphone = téléphones.get(nom);
   il (téléphone == null) System.out.println("Aucun numéro de téléphone");
   else System.out.println("Le numéro de "+nom+" est "+téléphone);

   Si aucune information n'est stockée dans la carte pour une clé spécifiée, get() renvoie null.
   §

   La méthode containsKey() permet de savoir si une clé est présente dans la carte. De la même façon, il est possible de contrôler si une valeur existe dans la carte au moyen de la méthode containsValue().

3. Suppression d'information : Nous pouvons supprimer un élément d'une carte, ayant une clé donnée, en utilisant la méthode remove(), laquelle fournit en retour l'ancienne valeur associée si la clé existe ou la valeur null dans le cas contraire.

   String ancienNuméro = téléphones.remove(nom);
   il (ancienNuméro == null) System.out.println("Ce nom "+nom+" n'existe pas");
   else System.out.println("Le numéro de "+ancienNuméro+" est supprimé");

4. Méthodes classiques : Comme pour toutes les autres collections, nous retrouvons les méthodes classiques : clear(), isEmpty(), size().

L'interface java.util.Map<Key, Value>

Value get(Key clé)

Cherche la valeur associée à une clé, puis renvoie l'objet associé ou null si la clé n'a pas été trouvée dans la carte. La clé peut être nulle.

Value put(Key clé, Value valeur)

Associe une clé et une valeur dans une carte. Si la clé est déjà présente dans la carte, le nouvel objet remplace celui qui était associé à la clé. Cette méthode renvoie l'ancienne valeur associée à la clé ou null si la clé n'existait pas dans la carte. La clé peut être nulle, mais la valeur doit être non nulle.

int size()

Retourne le nombre de clé/valeur présentes dans la carte.

Value remove(Object clé)

Supprime la valeur correspondante à la clé spécifiée (si elle est présente).

boolean isEmpty()

Indique si la carte est vide de tout élément clé/valeur.

void clear()

Enlève toutes les occurences clé/valeur de la carte.

void putAll(Map<? extends Key, ? extends Value>)

Ajoute toutes les entrées d'une carte spécifiée à cette carte.

boolean containsKey(Object clé)

Renvoie true si la clé spécifiée est présente dans la carte.

boolean containsValue(Object valeur)

Renvoie true si la valeur spécifiée est présente dans la carte.

Set<Map, Entry<Key, Value>> entrySet()

Renvoie une vue des objets Map.Entry, contenant les paires clé / valeur de la carte. Vous pouvez supprimer des éléments de cette vue (ils sont alors éliminés de la carte), mais vous ne pouvez pas en ajouter de nouveaux.

Set<Key> keySet()

Renvoie une vue de toutes les clés de la carte. Lorsque vous supprimez des éléments de cet ensemble, la clé et la valeur associée sont supprimées de la carte. En revanche, vous ne pouvez pas ajouter de nouveaux éléments.

Collection<Value> values()

Renvoie une vue de toutes les valeurs de la carte. Vous pouvez supprimer des éléments de cet ensemble (la clé et la valeur associée sont supprimées de la carte), mais vous n'avez pas le droit d'y ajouter de nouveaux éléments.

Il est souvent plus confortable de déclarer la structure de données cartes au travers de l'interface Map<K, V> plutôt que d'utiliser directement les classes HashMap, TreeMap, etc. Effectivement, au travers de cette procédure, il est plus facile ensuite de récupérer chaque entrée séparément.

Parcours d'une table - notion de vue

Les cartes ne sont pas vraiment considérées comme des collections. Effectivement, les classes qui implémentent les cartes ne disposent pas d'itérateurs. Il reste néanmoins possible d'obtenir une vue d'une carte, c'est-à-dire un objet qui implémente l'interface Collection ou l'une de ses sous-interfaces.

Il existe trois vues différentes :

1. Set<Key> keySet() : procure l'ensemble des clés,
2. Collection<Key> values() : délivre l'ensemble des valeurs,
3. Set<Map.Entry<Key, Value>> entrySet() : L'ensemble des paires clé / valeur.

Notons que la méthode keySet() ne délivre pas un HashSet ou un TreeSet, mais il s'agit d'un objet d'une autre classe qui implémente l'interface Set, laquelle étend l'interface Collection. Vous pouvez donc utiliser le résultat de cette méthode comme n'importe quelle autre collection.

L'ensemble des clés et des paires clé / valeur forme un Set parce qu'il ne peut exister qu'un seul exemplaire d'une clé dans une carte. Les éléments de la troisième méthode font partie de la classe interne statique Map.Entry.

L'interface java.util.Map.Entry<Key, Value>

Key getKey()
Value getValue()

Renvoie la clé ou la valeur de cette entrée.

Value setValue(Value valeur)

Modifie la valeur de la carte associée avec la nouvelle valeur spécifiée et renvoie l'ancienne valeur.

void putAll(Map<? extends Key, ? extends Value>)

Ajoute toutes les entrées d'une carte spécifiée à cette carte.

A l'aide de la méthode entrySet(), nous pouvons donc facilement voir une carte comme un ensemble de "paire", une paire n'étant rien d'autre qu'un élément de type Map.Entry réunissant deux objets (de types a priori quelconques). Les méthodes getKey() et getValue() de Map.Entry permettent d'extraire respectivement la clé et la valeur d'une paire.

Notez que l'ensemble fourni par la méthode entrySet() n'est pas une copie des informations figurant dans la carte. Il s'agit de ce que nous nommons une "vue". Si nous opérons des modifications dans la carte, elles seront directement perceptibles sur la vue associée. De plus si nous appliquons la méthode remove() à un élément courant (paire) de la vue, nous supprimons du même coup l'élément de la carte. En revanche, il n'est pas permis d'ajouter directement des éléments dans la vue elle-même.

Manipuler la classe TreeMap à l'aide de l'interface NavigableMap

Depuis Java 6, les tables de TreeMap implémentent également l'interface NavigableMap qui prévoit des méthodes exploitant l'ordre total induit sur les clés, par l'organisation en arbre binaire.

Ces méthodes permettent de retrouver et, éventuellement, de supprimer des éléments correspondant à la plus petite ou la plus grande des clés, ou encore de trouver un élément ayant la clé la plus proche (avant ou après) d'une valeur donnée. Il est possible de parcourir les éléments dans l'ordre inverse de l'ordre naturel des clés. Enfin, nous pouvons obtenir une vue d'une partie du map, en se fondant sur la valeur d'une clé qui sert en quelque sorte de "délimiteur".

L'interface java.util.NavigableMap<Key, Value> qui hérite de java.util.SortedMap<Key, Value>

Map.Entry<Key, Value> ceilingEntry(Key clé)

Fournit la "paire" correspondant à la plus petite clé supérieure ou égale à clé (null si aucune).

NavigableSet<Key> descendingKeySet()

Fournit une vue de l'ensemble des clés dans l'ordre inverse.

NavigableMap<Key, Value> descendingMap(Key clé)

Fournit une vue dans l'ordre inverse.

Map.Entry<Key, Value> firstEntry()

Fournit la "paire" correspondant à la plus petite clé (null si la carte est vide).

Map.Entry<Key, Value> floorEntry(Key clé)

Fournit la "paire" correspondant à la plus grande clé inférieure ou égale à clé (null si aucune).

Key floorKey(Key clé)

Fournit la plus grande clé inférieure ou égale à clé (null si aucune).

SortedMap<Key, Value> headMap(Key cléMaxi)

Fournit une vue formée des éléments dont la clé est inférieure à cléMaxi.

NavigableMap<Key, Value> headMap(Key cléMaxi, boolean inclus)

Fournit une vue formée des éléments dont la clé est inférieure (ou égale si inclus est vrai) à cléMaxi.

Map.Entry<Key, Value> higherEntry(Key clé)

Fournit la "paire" correspondant à la plus petit clé supérieure à clé (null si aucune).

Key higherKey(Key clé)

Fournit la plus petit clé supérieure à clé (null si aucune).

Map.Entry<Key, Value> lastEntry()

Fournit la "paire" correspondant à la plus grande clé (null si la carte est vide).

Map.Entry<Key, Value> lowerEntry(Key clé)

Fournit la "paire" correspondant à la grande clé inférieure à clé (null si aucune).

Key lowerKey(Key clé)

Fournit la plus grande clé inférieure à clé (null si aucune).

NavigableSet<Key> navigableKeySet()

Fournit une vue de l'ensemble des clés dans l'ordre naturel.

Map.Entry<Key, Value> pollFirstEntry(Key clé)

Fournit, en la supprimant, la "paire" correspondant à la plus petite clé (null si la carte est vide).

Map.Entry<Key, Value> pollLastEntry(Key clé)

Fournit, en la supprimant, la "paire" correspondant à la plus grande clé (null si la carte est vide).

NavigableMap<Key, Value> subMap(Key cléDébut, boolean inclusDébut, Key cléFin, boolean inclusFin)

Fournit une vue formée de la partie de la carte formée des éléments dont la clé est supérieure (ou égale si inclusDébut est vrai) à cléDébut et inférieure (ou égale si inclusFin est vrai) à cléFin.

SortedMap<Key, Value> tailMap(Key cléDébut)

Fournit une vue formée de la partie de la carte dont les éléments ont une clé supérieure à cléDébut.

NavigableMap<Key, Value> tailMap(Key cléDébut, boolean inclus)

Fournit une vue de la partie de la carte dont les éléments ont une clé supérieure (ou égale si inclus est vrai) à cléDébut.

L'interface java.util.SortedMap<Key, Value>

Comparator<? super Key> comparator()

Fournit le comparateur prévu à la construction, null sinon.

Key firstKey()

Fournit la première clé si elle existe, null sinon.

SortedMap<Key, Value> headMap(Key cléMaxi)

Fournit une vue des éléments de clé inférieure à cléMaxi.

Key lastKey()

Fournit la dernière clé si elle existe, null sinon.

SortedMap<Key, Value> subMap(Key cléMini, Key cléMaxi)

Fournit une vue des éléments de clé supérieure ou égale à cléMini et inférieure à cléMaxi.

SortedMap<Key, Value> tailMap(Key cléMini)

Fournit une vue des éléments de clé supérieure ou égale à cléMini.

Exemple d'application d'un répertoire téléphonique (un seul numéro par personne)

A titre d'exemple, je vous propose de mettre en oeuvre un répertoire téléphonique dans l'ordre alphabétique. Pour cela j'utilise la classe TreeMap.

Cette classe TreeMap est intéressante à plus d'un titre puisque je peux utiliser toutes ses compétences de navigations à l'aide des méthodes redéfinies issues de l'interface NavigableMap.

package carte;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.text.ParseException;
import javax.swing.*;
import java.util.*;
import javax.swing.text.MaskFormatter;

public class Répertoire extends JFrame {
   private JTextField nom = new JTextField("Nouveau nom", 18);
   private JFormattedTextField téléphone; 

   private Résultat liste = new Résultat();
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();   
   private JTextField nombre = new JTextField("0");
   
   private TreeMap<String, String> répertoire = new TreeMap<String, String>();
   private JComboBox déjàIntroduit = new JComboBox(répertoire.entrySet().toArray());
   
   public Répertoire() throws ParseException {
      super("Répertoire téléphonique");
      téléphone = new JFormattedTextField(new MaskFormatter("##-##-##-##-##"));
      téléphone.setValue("06-00-00-00-00");
      nombre.setEditable(false);
      nombre.setHorizontalAlignment(JLabel.CENTER);
      Action ajouter = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            répertoire.put(nom.getText(),(String) téléphone.getValue());
            déjàIntroduit.addItem(répertoire.floorEntry(nom.getText()));
            analyseCarte();                        
         }
      };
      barre.add(ajouter);
      barre.add(new AbstractAction("Recherche") {
         public void actionPerformed(ActionEvent e) {
            téléphone.setValue(répertoire.get(nom.getText()));
            analyseCarte(); 
         }
      });       
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            déjàIntroduit.removeItem(répertoire.ceilingEntry(nom.getText()));
            répertoire.remove(nom.getText());           
            analyseCarte(); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            répertoire.clear();
            déjàIntroduit.removeAllItems();
            analyseCarte();
         }
      });  
      barre.addSeparator();
      barre.add(new JLabel("Nombre : "));
      barre.add(nombre);
      add(barre, BorderLayout.NORTH);
      téléphone.addActionListener(ajouter);
      panneau.add(new JLabel("Nom : "));
      panneau.add(nom);
      panneau.add(new JLabel("Téléphone : "));
      panneau.add(téléphone);
      panneau.add(new JLabel("Liste du répertoire : "));
      panneau.add(déjàIntroduit);
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(470, 170);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public void analyseCarte() {
      liste.repaint();
      nombre.setText(""+répertoire.size());
   }

   public static void main(String[] args) throws ParseException { new Répertoire(); }

   private class Résultat extends JLabel {
      public Résultat() {
         setForeground(Color.RED);
         setBorder(BorderFactory.createTitledBorder("Liste"));
      }
      @Override
      public void paint(Graphics g) {
           setText(répertoire.toString());
           super.paint(g);
      }
   }
}

Autre exemple d'un répertoire téléphonique (plusieurs numéros pour la même personne)

Nous allons reprendre le répertoire téléphonique dans l'ordre alphabétique, mais cette fois-ci, il sera possible d'associer plusieurs numéros pour la même personne.

package carte;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.text.ParseException;
import javax.swing.*;
import java.util.*;
import javax.swing.text.MaskFormatter;

public class Répertoire extends JFrame {
   private JTextField prénom = new JTextField("Nouveau prénom", 12);
   private JFormattedTextField téléphone; 
   private JPanel panneau = new JPanel();
   private JToolBar barre = new JToolBar();    
   private JComboBox liste = new JComboBox();
   
   private enum TypeTéléphone {Mobile, Domicile, Travail};
   private TreeMap<String, EnumMap<TypeTéléphone, String>> répertoire = new TreeMap<String, EnumMap<TypeTéléphone, String>>();
   private JComboBox type = new JComboBox(TypeTéléphone.values());   
      
   public Répertoire() throws ParseException {
      super("Répertoire téléphonique");
      téléphone = new JFormattedTextField(new MaskFormatter(" ##-##-##-##-## "));
      téléphone.setValue(" 06-00-00-00-00 ");
      liste.setForeground(Color.RED);
      Action ajouter = new AbstractAction("Ajout") {
         public void actionPerformed(ActionEvent e) {
            EnumMap<TypeTéléphone, String> téléphones;
            if (répertoire.containsKey(prénom.getText())) {
               téléphones = répertoire.get(prénom.getText()); 
               téléphones.put((TypeTéléphone)type.getSelectedItem(),(String)téléphone.getValue());
            }
            else {
               téléphones = new EnumMap<TypeTéléphone, String>(TypeTéléphone.class);              
               répertoire.put(prénom.getText(), téléphones);
            }
            téléphones.put((TypeTéléphone)type.getSelectedItem(),(String)téléphone.getValue());
            liste.removeAllItems();
            for (Map.Entry<String, EnumMap<TypeTéléphone, String>> carte : répertoire.entrySet()) 
                liste.addItem(carte);
         }
      };
      barre.add(ajouter);
      barre.add(new AbstractAction("Suppression") {
         public void actionPerformed(ActionEvent e) {
            liste.removeItem(répertoire.ceilingEntry(prénom.getText()));
            répertoire.remove(prénom.getText()); 
         }
      }); 
      barre.add(new AbstractAction("Tout effacer") {
         public void actionPerformed(ActionEvent e) {
            répertoire.clear();
            type.removeAllItems();
         }
      });  
      barre.addSeparator();
      add(barre, BorderLayout.NORTH);
      téléphone.addActionListener(ajouter);
      panneau.add(new JLabel("Prénom : "));
      panneau.add(prénom);
      panneau.add(new JLabel("Téléphone : "));      
      panneau.add(type);
      panneau.add(téléphone);  
      add(panneau);
      add(liste, BorderLayout.SOUTH);
      setSize(480, 130);
      setLocationRelativeTo(null);
      setResizable(false);
      setDefaultCloseOperation(EXIT_ON_CLOSE);
      setVisible(true);
   }

   public static void main(String[] args) throws ParseException { new Répertoire(); }
} 

La structure des collections

Les classes sont regroupées dans une structure appelée cadre (ou framework), qui constitue la base commune pour créer des fonctionnalités avancées. Un cadre contient des superclasses renfermant des fonctionnalités pratiques, des méthodes et des mécanismes. L'utilisateur d'un cadre crée des sous-classes pour étendre les fonctionnalités sans devoir réinventer les mécanismes de base. Par exemple, Swing est un cadre pour les interfaces utilisateurs.

La bibliothèque de collection Java forme un cadre pour les classes de collection. Ce cadre définit un certain nombre d'interfaces et de classes abstraites pour des implémentations de collections et il propose certains mécanismes, comme un protocole d'itération.

Vous pouvez vous servir des classes de collection sans connaître grand-chose au cadre. C'est exactement ce que nous avons fait dans les chapitres précédents. En revanche, si vous souhaitez implémenter des algorithmes généraux qui fonctionnent sur plusieurs types de collection ou si vous voulez créer un nouveau type de collection, il vaut mieux comprendre le fonctionnement du cadre.

Les hiérarchies des interfaces de type Collection et de type Map

Il existe deux interfaces fondamentales pour les collections : Collection et Map. Suivant le type de collection, nous pouvons :

1. Insertion d'un élément :
• Des éléments peuvent être insérés dans une collection avec la méthode : boolean add(E élément).
• Les cartes renferment des paires clé/valeur, et la méthode put() sert à les ajouter dans une carte : Value put(Key clé, Value valeur)
2. Lecture d'un élément : Pour lire les éléments dans une collection, il faut les parcourir avec un itérateur. Pour lire les valeurs d'une carte, il faut avoir recours à la méthode : Value get(Key clé).
3. L'interface List : Une List est une collection triée. Les éléments sont ajoutés à une position particulière du conteneur. Un objet peut être inséré à la position adéquate de deux manières : par un indice entier ou par un itérateur de liste. L'interface List définit des méthodes pour accéder à n'importe qu'elle donnée d'une liste :
• void add(int index, E élément)
• E get(int index)
• void remove(int index)
4. Accès direct (aléatoire) : Comme nous l'avons déjà indiqué, l'interface List fournit ces méthodes d'accès aléatoires (directs) qu'elles soient ou non efficaces pour une implémentation particulière. Pour éviter de réaliser des opérations d'accès coûteuses, Java 1.4 a introduit une interface de balisage RandomAccess. Cette interface ne possède pas de méthodes, mais vous pouvez l'utiliser pour tester si une collection particulière prend en charge un accès direct efficace :

   if (c instanceof RandomAccess) {
      utiliser un algorithme d'accès direct (aléatoire)
   
   }
   else {
      utiliser un alogorithme d'accès séquentiel
   
   }

   Les classes ArrayList et Vector implémentent l'interface RandomAccess. Les élément de ces deux classes sont justement contigües en mémoire et permettent d'avoir ainsi un accès direct aléatoire) efficace.

5. L'interface ListIterator : cette interface définit une méthode pour ajouter un élément juste avant la position de l'itérateur : void add(E élément).
6. L'interface Iterator : Pour lire et supprimer des éléments à une position particulière, il suffit d'utiliser les méthodes next() et remove() de l'interface Iterator.
7. L'interface Set : cette interface est identique à l'interface Collection, mais le comportement des méthodes y est défini de manière plus précise. La méthode add() d'un ensemble doit rejeter les valeurs doubles. La méthode equals() d'un ensemble doit être redéfinie de telle sorte que deux ensembles sont identiques s'ils possèdent les mêmes éléments, mais pas nécessairement disposé dans le même ordre. La méthode hashCode() doit être redéfinie pour que deux ensembles possédant les mêmes éléments soient associés au même code de hachage.

   Pourquoi définir une interface séparée si les signatures des méthodes sont les mêmes ? Conceptuellement, toutes les collections ne sont pas des ensembles. La définition d'une interface Set permet aux programmeurs d'écrire des méthodes qui n'acceptent que des ensembles.

8. Les interfaces SortedSet et SortedMap : Ces interfaces mettent en évidence l'objet de comparaison utilisé pour triéer les éléments et elles définissent des méthodes pour obtenir des vues des sous-ensembles des collections.
9. Les interfaces NavigableSet et NavigableMap : Java SE 6 a introduit ces interfaces contenant des méthodes supplémentaires pour rechercher er parcourir des ensembles et des cartes triées (dans l'idéal, vous devez simplement avoir inclus ces méthodes dans les interfaces SortedSet et SortedMap). Les classes TreeSet et TreeMap implémentent ces interfaces.

Les classes qui implémentent ces différentes interfaces

Passons maintenant des interfaces aux classes qui les implémentent. Nous avons déjà vu que les interfaces de collections possèdent quelques méthodes qui peuvent être implémentées très simplement à partir d'un nombre plus important de méthodes fondamentales. Les classes abstraites fournissent certaines implémentations de ces routines :

1. AbstractCollection
2. AbstractList
3. AbstractSequenceList
4. AbstractSet
5. AbstractQueue
6. AbstractMap

Si vous implémentez votre propre classe de collection, vous voudrez probablement étendre l'une de ces classes pour récupérer les implémentation de ces opérations.

En tout cas, la bibliothèque Java fournit des classes concrètes associées :

1. LinkedList
2. ArrayList
3. ArrayDeque
4. HashSet
5. TreeSet
6. PriorityQueue
7. HashMap
8. TreeMap

Les vues et les emballages

Lorsque nous regardons les deux diagrammes de classes précédents, vous trouverez peut-être qu'il est exagéré d'avoir de nombreuses interfaces et classes abstraites pour implémenter un nombre modeste de collections concrètes. Mais ces diagrammes n'expliquent pas tout. En ayant recours à des vues, vous pouvez obtenir d'autres objets qui implémentent les interfaces Collection ou Map. Nous avons vu un exemple dans le chapitre précédent au moyen de la méthode keySet() des classes de cartes.

Au premier abord, il apparaît que la méthode crée un nouvel ensemble, le remplit avec toutes les clés de la carte, puis renvoie l'ensemble. Mais ce n'est pas exactement ce qui se passe. En fait, la méthode keySet() renvoie un objet d'une classe qui implémente l'interface Set et dont les méthodes permettent de manipuler la carte d'origine. Ce type de collection est appelée une vue.

La technique des vues possède un certain nombre d'applications pratiques dans le cadre des collections. Nous verrons ces applications dans les sections suivantes.

Emballages légers de collection

1. Méthode asList() : La méthode asList() de la classe Arrays renvoie un emballage List autour d'un tableau Java brut. Cette méthode vous permet de passer le tableau à une méthode qui attend un argument de liste ou de collection :

   String[] prénoms = new String[52];
   List<String> listePrénoms = Arrays.asList(prénoms);

   L'objet renvoyé n'est pas un ArrayList, c'est un objet vue avec des méthodes get() et set() qui accèdent au tableau sous-jacent. Toutes les méthodes capables de modifier la taille du tableau (comme add() et la méthode remove() de l'itérateur associé) déclenchent une UnsupportedOperationException.

   Depuis Java SE 5.0, la méthode asList() est déclarée comme ayant un nombre variable d'arguments. Au lieu de passer un tableau, vous pouvez passer des éléments individuels :

   List<String> listePrénoms = Arrays.asList("Bruno", "Alain", "Emmanuel");

2. Méthode nCopies() : L'appel de la méthode nCopies(n, unObjet) de la classe Collections renvoie un objet inaltérable qui implémente l'interface List et donne l'illusion de posséder n éléments, chacun apparaissant comme unObjet. Par exemple, l'appel suivant crée une liste contenant 100 chaînes, toutes définies sur "Défaut" :

   List<String> réglages = Collections.nCopies(100, "Défaut");

   Le stockage se révèle peu coûteux, l'objet n'est stocké qu'une fois. C'est une bonne application de la technique d'affichage.
   §

   La classe Collections contient un certain nombre de méthodes commodes dont les paramètres ou les valeurs renvoyées constituent des collections. Attention à ne pas les confondre avec l'interface Collection.

3. Méthode singleton() : L'appel à la méthode singleton(unObjet) de la classe Collections renvoie un objet vue qui implémente l'interface Set (à la différence de nCopies(), qui produit une List). L'objet renvoyé implémente un ensemble d'éléments uniques inaltérables, sans avoir la charge de la structure de données.

   Les méthodes singletonList() et singletonMap() se comportent de la même manière.
   §