Fiche 8 : Collections

Principe

Les collections Java sont un ensemble de classes définissant des structures de données efficaces pour stocker, rechercher et manipuler des objets. De nombreuses structures existent couvrant les besoins les plus courants :

• séquences d'éléments (listes) ;
• ensembles quelconques, ensembles ordonnés ;
• queues (files, piles, files à priorité) ;
• des dictionnaires associatifs entre des clés et des valeurs ;
• et d'autres conteneurs plus spécifiques...

Le choix d'une collection dépend de l'utilisation recherchée et des coûts des opérations principalement réalisées.

Organisation

Ces différents « types de données abstraits » sont spécifiés dans des interfaces de haut niveau, puis implantés dans différentes classes concrètes. Voir la fiche dédiée à l'abstraction et aux interfaces Java.

Il existe en fait deux hiérarchies de classes :

1. celle des collections proprement dites qui permettent de stocker des éléments. Elles sont filles de l'interface Collection<E>.
2. celle des dictionnaires associatifs contenant des couples (clé, valeur), dont la racine est l'interface Map<K,V>.

Nous ne décrirons ici que les collections usuelles principales. De nombreuses ressources sont également disponibles, notamment :

• l'API (indispensable!). Toutes les classes et interfaces discutées ici sont dans le paquetage java.util ;
• les Java tutorials

Ci-dessous, voici la hiérarchie des principales collections et dictionnaires JAVA. En grisé les classes concrètes, qui réalisent les interfaces abstraites de haut niveau.

Parcours d'une collection : itérateur et for each

Toutes les collections possèdent au moins un point commun : le parcours de leur contenu.

Le mécanisme d'itération permet de parcourir séquentiellement tous les éléments d'une collection, de manière uniforme et efficace. Il existe dans plusieurs langages, notamment Python ou C++.

En Java toute collection possède une méthode Iterator<E> iterator() qui retourne un itérateur permettant d'accéder aux éléments un par un en « avançant » dans la collection. Initialement, l'itérateur est placé « avant » le premier élément. A chaque accès, le prochain élément est retourné et l'itérateur avance à l'élément suivant. Lors du parcours complet d'une collection, chaque élément est retourné une et une seule fois, dans un ordre dépendant en fait du type de la collection.

Les deux méthodes principales d'un itérateur sont :

• public boolean hasNext() qui retourne true s'il reste des éléments dans l'itération ;
• public E next() qui retourne le prochain élément et avance dans l'itération. S'il n'y a plus d'élément, une NoSuchElementException est levée.

Le schéma d'utilisation est toujours le même, quelle que soit la collection :

  Collection<E> coll = new ...;       // Collection existante, de type quelconque
                                      // Elle contient des éléments de type E

  Iterator<E> it = coll.iterator();   // Crée un nouvel itérateur sur la collection,
                                      // initialisé AVANT le 1er élément
  while (it.hasNext()) {              // Tant qu'il reste des éléments
      E e = it.next();                // Récupère le prochain élément et avance
      ...                             // Traiter e ici
  }

Les collections, comme les tableaux, peuvent aussi être parcourues à l'aide du mécanisme de for each :

    for (E e: coll) {                   // Pour tout élément e de coll
        ...                             // Traiter e ici
    }

Par rapport au parcours avec un itérateur, un for each traite systématiquement tous les éléments de la collection. L'itérateur permet aussi d'enlever un élément pendant le parcours (la classe Iterator possède une méthode remove(), optionnelle, qui retire de la collection le dernier élément retourné par next().

Les séquences : List

L'interface List<E> définit une séquence d'éléments, indexés du 1er au dernier par leur position dans la séquence : un entier de 0 à size() - 1. Les méthodes permettent d'insérer au début, à la fin, ou à une position précise. Lors d'une itération, les éléments sont naturellement parcourus dans l'ordre de la séquence. Les deux principales classes réalisant cette interface sont LinkedList<E> et ArrayList<E>.

LinkedList

Fondée sur une liste doublement chaînée, cette classe est intéressante en cas d'ajouts et suppressions en début ou en fin de séquence. En ce qui concerne les ajouts et suppressions en milieu de séquence, elles se font également en temps constant, mais nécessite d'accéder à la position de la cellule à ajouter ou supprimer, ce qui prend un temps $\frac{n}{2}$ (donc un temps linéaire) si la cellule est en milieu de liste. Un tel ajout / suppression n'est donc efficace que s'il se fait en cours de parcours (par exemple en supprimant la cellule à laquelle on est en train d'accéder avec un itérateur).

  // Exemple: une LinkedList de points
  LinkedList<Point> points = new LinkedList<Point>();
  points.add(new Point(0, 0));         // par défaut, ajout en fin
  points.addFirst(new Point(1, 1));
  points.add(new Point(2, 2));
  System.out.println(points);          // [(1,1), (0,0), (2,2)]
  System.out.println(points.get(2));   // Attention : la complexité de la méthode get(int i)
                                       // de la classe LinkedList<> est en O(n) !
                                       // Car il faut parcourir la liste
  points.remove(1);                    // enlève la valeur en position 1
  System.out.println(points);          // [(1,1), (2,2)]
  points.remove(0);                    // Suppression en tête. Coût : O(1).
  System.out.println(points);          // [((2,2)]

Voici un exemple d'utilisation de la collection LinkedList. Suppression de l'élément d'indice 1 (le deuxième donc) de la liste :

Ici, le coût est en $\Theta(n)$ pire cas car :

1. parcourir la liste pour accéder à l'élément d'indice i : $\Theta(i)$ ;
2. supprimer cet élément : $\Theta(1)$.

ArrayList

Fondée sur un tableau redimensionnable et donc à coût constant pour les accès direct à un élément en fonction de sa position (ième). Par contre, les coûts des insertions/suppressions en position quelconque sont linéaires (décalage des valeurs aux indices suivants).

  // Exemple: un ArrayList de caractères
  //  => notez le ArrayList<Character> et pas ArrayList<char>
  //     Pour les types de base, il faut utiliser des classes "wrapper"
  //     (Integer, Float, Double ...) dans la déclaraton
  //  => le mécanisme d'"auto-boxing" permet d'utiliser des char normalement:
  //     - lettres.add('a')  est wrappé par lettres.add(new Character('a'))
  //     - lettres.remove(i) retourne lettres.remove(i).getValue()
  ArrayList<Character> lettres = new ArrayList<Character>();
  for (char c = 'a'; c <= 'z'; c++) {
      lettres.add(c);             // ajout en fin
  }
  lettres.set(4, 'E');            // remplace la 5ème lettre par sa majuscule. Coût : 0(1)
  System.out.println("La 25eme lettre est " + lettres.get(24));
  System.out.println(lettres.get(5));   // accès par indice en 0(1) dans une ArrayList<>
  lettres.remove(6);              // coût! (decalages)

  // On affiche les 10 premières lettres
  Iterator<Character> it = lettres.iterator();
  int n = 0;
  while (it.hasNext() && n++ < 10) {
      char c = it.next();
      System.out.print(c + " ");
  }                               // affichage: a b c d E f h i j k

Voici un exemple d'utilisation de la collection ArrayList. Suppression d'un élément de la collection.

Ici, le coût est en $\Theta(n)$ pire cas car :

1. accéder à l'élément d'indice i : $\Theta(1)$ ;
2. supprimer cet élément, puis décaler des éléments qui suivent : $\Theta(n)$.

Files et piles: Queue, Deque

L'interface Queue<E> définit typiquement une file (FIFO, First In First Out), avec deux méthodes add(E e) qui ajoute en fin et E remove() qui enlève et retourne le premier élément.

L'interface Deque<E> (Double Ended Queue) spécialise une Queue<E> avec des méthodes d'insertion, d'accès et de retrait en tête et queue de liste : addFirst, addLast, removeFirst, removeLast, getFirst, getLast. Ces méthodes permettent notamment d'utiliser Deque comme une pile (LIFO, Last In First Out), en considérant par exemple la tête comme le sommet de la pile.

La classe de référence réalisant ces interfaces est LinkedList<E>. Les opérations principales sont à coût constant $O(1)$.

  // La queue du Pangolin, bien sûr!
  Queue<Pangolin> file = new LinkedList<Pangolin> ();
  file.add(new Pangolin("Gérard", 1542));
  file.add(new Pangolin("Pierre", 1939));
  file.add(new Pangolin("Heckel", 1);
  System.out.println(file.remove());       // c'est Gérard
  file.add(new PangolinALongueQueue("Jeckel", 2);
  while (!file.isEmpty()) {
      System.out.println(file.remove());   // Pierre, Heckel puis Jeckel
  }

File à priorités

PriorityQueue<E> est une file à priorité : l'ordre de sortie des éléments ne dépend plus de leur date d'insertion, comme une FIFO ou LIFO, mais d'une priorité entre éléments.

L'implantation de la classe PriorityQueue<E> repose sur un tas binaire. Les coûts des opérations d'insertion et de retrait de l'élément le plus prioritaire sont en $O(\log(n))$. L'opération d'accès à l'élément le plus prioritaire sans le retirer peek() est l'opération la plus efficace : elle est en $O(1)$ (ce qui fait tout l'intérêt de cette structure par rapport à un TreeSet). Attention par contre, la recherche ou la suppression d'un élément quelconque sont possibles mais en $\Theta(n)$.

En pratique les éléments doivent être munis d'une relation d'ordre, et l'élément le plus prioritaire (le prochain à sortir) est le plus petit selon cet ordre.

Deux solutions sont possibles pour définir cette relation d'ordre.

Avec l'interface Comparable

La classe E des éléments peut réaliser l'interface Comparable<E>, qui définit l'ordre dit « naturel » entre des instances de E. Elle doit donc redéfinir la méthode public int compareTo(E e) qui retourne une valeur négative/nulle/positive si this est plus petit/égal/ plus grand que e.

// Exemple: une PriorityQueue avec l'implémentation de l'interface Comparable
public class Etudiant implements Comparable<Etudiant> {
    private String name;
    private int note;

    public Etudiant(String name, int note) {
        this.name = name;
        this.note = note;
    }
    @Override
    public String toString() {
        return "Je m'appelle " + name + " et j'ai eu une note de " + note;
    }
    // On implémente la méthode compareTo qui prend en paramètre
    // un autre objet Etudiant à comparer avec this
    @Override
    public int compareTo(Etudiant e) {
        // On retourne un nombre positif
        // si la note de this est supérieur à celle de e
        if(this.note > e.note) {
            return 1;
        }
        if(this.note < e.note) {
            return 1;
        }
        return 0;
    }
    // equals(Object o) doit etre cohérent avec compareTo(Etudiant e),
        // comme expliqué dans la Javadoc de l'interface Comparable<E>.
    // Ici, donc, 2 étudiants doivent être égaux au sens de equals()
    //  si et seulement si ils se comparent à 0 au sens de compareTo()
    @Override
    public boolean equals(Object other) {
        if(other instanceof Etudiant) {
            Etudiant et = (Etudiant) other;
            return et.note == this.note;
        }
        return false;
    }
}

public class ExemplePriorityQueueComparable {
    public static void main(String argc[]) {
        // Création d'une PriorityQueue, comme on implémente l'interface Comparable
        // il n'y a pas besoin de spécifier avec quelle méthode on veut comparer,
        // Le tri var directement appeler la méthode compareTo de la classe Etudiant
        Queue<Etudiant> etudiants = new PriorityQueue<Etudiant>();
        etudiants.add(new Etudiant("Pauline", 14));
        etudiants.add(new Etudiant("Julia", 10));
        etudiants.add(new Etudiant("Théo", 16));
        etudiants.add(new Etudiant("Alphonse", 12));
        etudiants.add(new Etudiant("Pierre", 8));
        etudiants.add(new Etudiant("Isabelle", 20));
        etudiants.add(new Etudiant("Olivier", 15));

        // Remarque : puisqu'une PriorityQueue repose sur un tas,
                // un itérator sur une PriorityQueue
        // ne parcourt pas dans l'ordre définit par le compararateur.

        // Par contre, principe du tas :
        // l'élément en tête est toujours le plus grand
        // (méthodes peek() et poll())

        // Utilisation de la méthode peek pour accéder à l'élément en tête de la file triée
        while(etudiants.peek() != null) { // on peut aussi écrire if( etudiants.size() > 0 )
            // On retire l'élément en tête de la file triée
            Etudiant e = etudiants.poll();
            System.out.println(e);
            // Affiche :
                        // Je m'appelle Pierre et j'ai eu une note de 8
                        // Je m'appelle Julia et j'ai eu une note de 10
            // Je m'appelle Alphonse et j'ai eu une note de 12
            // Je m'appelle Pauline et j'ai eu une note de 14
            // Je m'appelle Théo et j'ai eu une note de 16
                        // etc.
                        // c'est à dire les étudiants, par ordre croissant de leur note.
                        // Complexité de toute la boucle boucle : O( n * log(n) )
        }
        // maintenant, la file de priorité est vide...
    }
}

Voici l'état final du tas binaire après l'ajout des éléments lors de l'exécution du code ci-dessus :

Avec une instance de Comparator

Il est aussi possible de déléguer la comparaison de deux objets E à une tierce classe qui réalise l'interface Comparator<E>. Celle-ci définit une seule méthode : public int compare(E e1, E e2) qui retourne une valeur négative/nulle/positive si e1 est plus petit/égal/plus grand que e2. Si une classe fille de Comparator est donné à la PriorityQueue, c'est elle qui effectue la comparaison des éléments même si le type E réalise Comparable<E>.

Cette seconde approche est surtout utilisée pour pouvoir comparer des éléments selon des critères différents. Il est par exemple possible de créer deux classes qui comparent des étudiants selon leur nom ou selon leur note de POO.

// Exemple: une PriorityQueue avec l'implémentation de l'interface Comparator
// L'ordre choisi pour cet exemple est l'odre alphabétique des noms.
// Il faut implémenter l'interface Comparator dans une classe tierce, nommée par exemple EtudiantComparator
class EtudiantComparator implements Comparator<Etudiant> {
    // On implémente la méthode compare(),
        // qui est la seule méthode définie dans l'interface Comparator.
    // Elle prend en entrée deux objets Etudiant e1 et e2 à comparer
    public int compare(Etudiant e1, Etudiant e2)    {
        // On retourne un nombre positif
        // si le nom de e1 est plus grand alphabétiquement à celle de e2
        if(e1.getName().compareToIgnoreCase(e2.getName()) > 0) {
            return 1;
        }
        else if(e1.getName().compareToIgnoreCase(e2.getName()) < 0) {
            return -1;
        }
        else {
            return 0;
        }
    }
}

class Etudiant {
    private String name;
    private int note;

    public Etudiant(String name, int note) {
        this.name = name;
        this.note = note;
    }
    public String getName() {
        return name;
    }
    @Override
    public String toString() {
        return "Je m'appelle " + name + " et j'ai eu une note de " + note;
    }
    // equals(Object o) doit etre cohérent avec compare(Etudiant e1, Etudiant e2)
        // Ici, donc 2 étudiants doivent être égaux au sens de equals()
        //  si et seulement si ils se comparent à 0 au sens du comparateur
    @Override
    public boolean equals(Object other) {
        if(other instanceof Etudiant) {
            Etudiant et = (Etudiant) other;
            return et.name.equals(this.name);
        }
        return false;
    }
}

public class ExemplePriorityQueueComparator {
    public static void main(String argc[]) {
        // Création d'une PriorityQueue, comme on implémente l'interface Comparator
        // dans une classe tierce, il faut spécifier avec quelle méthode on veut comparer.
        // Il faut donc donner une instance de la classe
        // qui implémente la méthode de comparaison à la PriorityQueue
        Comparator comparator = (Comparator)(new EtudiantComparator());
        Queue<Etudiant> etudiants = new PriorityQueue<Etudiant>(comparator);
        etudiants.add(new Etudiant("Pauline", 14));
        etudiants.add(new Etudiant("Julia", 10));
        etudiants.add(new Etudiant("Théo", 16));
        etudiants.add(new Etudiant("Alphonse", 12));
        etudiants.add(new Etudiant("Pierre", 8));
        etudiants.add(new Etudiant("Isabelle", 20));
        etudiants.add(new Etudiant("Olivier", 15));

               // le cout de l'ajout de tous les étudiants est en O(n * log(n))


        // Utilisation de la méthode peek pour accéder à l'élément en tête de la file triée
        while(etudiants.peek() != null) {
            // On retire l'élément en tête de la file triée
            Etudiant e = etudiants.poll();
            System.out.println(e);
            // Affiche :
            // Je m'appelle Alphonse et j'ai eu une note de 12
            // Je m'appelle Isabelle et j'ai eu une note de 20
            // Je m'appelle Julia et j'ai eu une note de 10
            // Je m'appelle Olivier et j'ai eu une note de 15
            // Je m'appelle Pauline et j'ai eu une note de 14
            // Je m'appelle Pierre et j'ai eu une note de 8
            // Je m'appelle Théo et j'ai eu une note de 16
        }
        // maintenant, la file de priorité est vide...
    }
}

Ensembles : Set

A la différence des séquences ou queues, un ensemble défini par l'interface Set<E> n'admet pas de doublons : un élément ne peut pas être présent deux fois dans la collection. Cette égalité entre éléments est testée via la méthode public boolean equals(Object o) héritée de la super classe Object, qui doit de ce fait être correctement redéfinie dans la classe E des éléments du Set.

Ensemble quelconque

La classe HashSet<E> réalise l'interface Set<E> avec une implémentation de type table de hachage. Le coût amorti des opérations principales (ajout, retrait, recherche) est en O(1). L'itération retourne bien toutes les valeurs mais dans un ordre quelconque.

En plus de redéfinir equals, les éléments doivent aussi redéfinir une autre méthode de la classe Object : public int hashCode(), qui doit retourner une clé de hachage entière. Cette méthode doit être cohérente avec la redéfinition de l'égalité : si deux objets sont égaux au sens de equals, alors leur méthode hashCode doit retourner la même valeur.

Voici un exemple d'utilisation de HashSet :

class Fleur {
    private String name;
    public Fleur(String name) {
        this.name = name;
    }
    // la méthode equals à redéfinir pour que l'ajout
    // dans un HashSet se passe bien
    @Override
    public boolean equals(Object o) {
        if(o instanceof Fleur) {
            Fleur f = (Fleur)o;
            if(name.equals(f.name)) {
                return true;
            }
        }
        return false;
    }
    @Override
    public int hashCode() {
        // Dans la vraie vie, il suffirait de dire que le code de hachage d'une Fleur
        // est le code de hachage de son nom.
        // Bien sur, la classe String redéfinit la méthode hashCode() !
        // Donc on écrirait donc :
        //        return name.hashCode();

        // Dans notre exemple, on implante une méthode de hachage un peu bête,
        // pour bien expliquer comment les fleurs vont être
        // rangées dans la table de hachage.
        // Bien sûr, cette méthode de hachage n'est pas recommandable,
        // car elle génère beaucoup de collisions.
        int hashCode = 0;
        for(int i = 0; i < name.length(); i++) {
            hashCode += (int)name.charAt(i);
        }
        return hashCode;
    }
    public String toString() {
        return name + " a un hash code qui vaut : " + hashCode();
    }
}

public class ExempleHashSet {
    public static void main(String args[]) {

        // On utilise un HashSet<Fleur>, il faut implémenter :
        //    - la redéfinition de la méthode boolean equals(Object o)
        //    - la redéfinition de la méthode int hashCode()

        // Capacité initiale (optionnelle) : 16 cases dans le tableau de hachage
        Set<Fleur> bouquetFleurs = new HashSet<Fleur>(16);

        bouquetFleurs.add(new Fleur("tulipe"));
        Fleur rose = new Fleur("rose");
        bouquetFleurs.add(rose);
        bouquetFleurs.add(new Fleur("coquelicot"));
        bouquetFleurs.add(new Fleur("quecolicot"));
        bouquetFleurs.add(new Fleur("lantana"));
        bouquetFleurs.add(new Fleur("litupe"));
        bouquetFleurs.add(new Fleur("lantana"));

        // le cout de l'ajout de toutes les fleurs est en O(n) seulement
        // car l'ajout d'un élément dans un HashSet est en O(1) coût amorti

        System.out.println("Taille du HashSet : " + bouquetFleurs.size());
        // Affiche :
        // Taille du HashSet : 6
        // Ah, la dernière fleur "lantana" n'a pas été ajoutée.
        // Pourquoi ?

        // Comme dans un HashSet, les éléments sont uniques (au sens de equals()),
        // l'ajout a échoué.

        // le parcours est fait dans un ordre apparemment "quelconque"
        for(Fleur fleur: bouquetFleurs) {
            System.out.println(fleur);
            // affiche :
            // tulipe a un hash code qui vaut : 659
            // litupe a un hash code qui vaut : 659
            // coquelicot a un hash code qui vaut : 1080
            // quecolicot a un hash code qui vaut : 1080
            // rose a un hash code qui vaut : 441
            // lantana a un hash code qui vaut : 735
        }

        // Utilisation de la méthode contains avec un objet rose en entrée
        System.out.println("Le bouquet de fleurs contient t-il une rose? : "
                + bouquetFleurs.contains(new Fleur("rose")));
        // Affiche:
        // Le bouquet de fleurs contient t-il une rose? : true
        // Coût de la méthode contains() : O(1)

        // On pourrait aussi utiliser un TreeSet<String> à la place du HashSet
        //  => il faudrait munir la classe Fleur d'un comparateur
        //  => le coût de l'ajout de toutes les fleurs passerait en O(n * log(n));
        //  => l'ordre d'affichage de mots respecterait l'ordre défini par le comparateur.
        //  => le coût de la méthode contains() passerait en O(log(n))

    }
}

Voici comment se passe l'ajout de l'objet Fleur avec comme nom « lantana ».

Ensemble ordonné

La classe TreeSet<E> définit un ensemble dont les valeurs sont ordonnées. Il est donc nécessaire de munir les éléments d'une relation d'ordre pour pouvoir les comparer. Comme précédemment, deux solutions sont possibles :

• La classe E des éléments peut réaliser l'interface Comparable<E>. C'est donc la méthode compareTo qui est utilisée pour ordonner les éléments dans la collection.
• Un objet de type Comparator<E> peut être donné au TreeSet. C'est alors lui qui réalise la comparaison des éléments même si la classe E réalise Comparable<E>.

Quelle que soit la méthode utilisée, la comparaison doit être compatible avec l'égalité : si e1.equals(e2) (respectivement !equals) alors e1.compareTo(e2) et/ou compare(e1, e2) doivent retourner 0 (respectivement une valeur non nulle).

L'implantation de cette classe repose sur un arbre équilibré (de type rouge-noir), avec des coûts en O(log(n)) pour les opérations principales.

Exemple d'ensemble ordonné

Un exemple (long mais complet) d'ordonnancement avec les célèbres frères Dalton, à retrouver dans le fichier ExempleOrdonnancement.java. Enjoy!

  // un exemple d'énumération. Observez comment on l'utilise...
  enum Taille {
      PETIT,
      MOYEN,
      BETE
  }

  /**
   * Class Dalton, munie d'un ordre naturel.
   */
  class Dalton implements Comparable<Dalton> {
      private String nom;
      private Taille taille;

      public Dalton(String nom, Taille taille) {
          this.nom = nom;
          this.taille = taille;
      }

      public String getNom() {
          return nom;
      }

      public Taille getTaille() {
          return taille;
      }

      @Override
      public String toString() {
          return nom + (" (") + taille.toString() + ")";
      }

      [...]  // to be continued...

      /**
       * Ordre naturel: comparaison sur la taille d'abord, puis sur le nom.
       * @return une valeur négative / nulle / positive si this est
       *         plus petit / égal / plus grand que d.
       */
      @Override
      public int compareTo(Dalton d) {
          if (d == null)
              throw new NullPointerException();

          int dt = this.taille.ordinal() - d.taille.ordinal(); // ordre ds l'enum
          if (dt < 0) {           // this < d
              return -1;
          } else if (dt > 0) {    // this > d
              return 1;
          } else {                // même taille, on compare donc sur le nom
                                  // (String realise Comparable<String>)
              return this.nom.compareTo(d.nom);
          }
      }

  @Override
  public boolean equals(Object o) {
      if (o instanceof Dalton == false) // verifie aussi o != null
          return false;
      // downcast, maintenant qu'on est sur que cet Objet est un Dalton
      Dalton d = (Dalton) o;
      return this.nom.equals(d.nom) && this.taille == d.taille;
  }

  @Override
  public int hashCode() {
      // ici on délègue au nom (hashCode de String est déjà redéfinie)
      return nom.hashCode();
  }

  /**
   * Classe servant à comparer deux objets Dalton sur leur nom uniquement.
   */
  class ComparateurNom implements Comparator<Dalton> {

      @Override
      public int compare(Dalton d0, Dalton d1) {
          return d0.getNom().compareTo(d1.getNom());
      }
  }

  /**
   * Classe servant à comparer deux objets Dalton sur leur taille uniquement.
   */
  class ComparateurTaille implements Comparator<Dalton> {

      @Override
      public int compare(Dalton d0, Dalton d1) {
          // ordre suivant la position dans l'énumération Taille
          return d0.getTaille().ordinal() - d1.getTaille().ordinal();
      }
  }

  // Trois ensembles ordonnés suivant un ordre différent:
  // - dans les deux premiers cas, on délègue la comparaison à un objet
  //   externe de type Comparator
  // - dans le dernier, on utilise l'ordre naturel de la classe Dalton
  SortedSet<Dalton> daltonsParNom    = new TreeSet<Dalton> (new ComparateurNom());
  SortedSet<Dalton> daltonsParTaille = new TreeSet<Dalton> (new ComparateurTaille());
  SortedSet<Dalton> daltons          = new TreeSet<Dalton> ();    // ordre naturel

  Dalton joe = new Dalton("Joe", Taille.PETIT);
  Dalton jack = new Dalton("Jack", Taille.MOYEN);
  Dalton william = new Dalton("William", Taille.MOYEN);
  Dalton averell = new Dalton("Averell", Taille.BETE);

  // insertion ds un ordre quelconque, de toutes façons c'est trié
  daltonsParNom.add(william);
  daltonsParNom.add(joe);
  daltonsParNom.add(averell);
  daltonsParNom.add(jack);

  daltonsParTaille.add(william);
  daltonsParTaille.add(joe);
  daltonsParTaille.add(averell);
  daltonsParTaille.add(jack);

  daltons.add(william);
  daltons.add(joe);
  daltons.add(averell);
  daltons.add(jack);

  System.out.println("Les Dalton, ordonnés par nom: ");
  System.out.println(daltonsParNom);
  System.out.println("  -> Bof...\n");

  System.out.println("Les Dalton, ordonnés par taille: " + daltonsParTaille);
  System.out.println("  -> Argh, il en manque un! (ben oui, c'est un Set!)\n");

  System.out.println("Les Dalton, tout court: " + daltons);
  System.out.println("  -> Là c'est mieux!\n");

  System.out.println("\n(I'm a poor lonesome teacher...)");

Les Dalton, ordonnés par nom:
[Averell (BETE), Jack (MOYEN), Joe (PETIT), William (MOYEN)]
  -> Bof...

Les Dalton, ordonnés par taille: [Joe (PETIT), William (MOYEN), Averell (BETE)]
  -> Argh, il en manque un! (ben oui, c'est un Set!)

Les Dalton, tout court: [Joe (PETIT), Jack (MOYEN), William (MOYEN), Averell (BETE)]
  -> Là c'est mieux!


(I'm a poor lonesome teacher...)

Dictionnaires: Map

L'interface Map<K,V> spécifie des associations entre une clé de type K et une valeur de type de V. Un Map ne peut pas contenir des clés identiques, et chaque clé n'est associée qu'à une et une seule valeur. Les opérations principales sont l'ajout d'un couple (put(K key, V value)), l'accès à une valeur via sa clé (V get(K key)), la recherche de clé ou de valeur, la suppression d'une valeur, etc.

L'interface SortedMap<K,V> étend Map<K,V>, en rajoutant une relation d'ordre sur les clés du dictionnaire.

Deux classes principales existent:

1. HashMap<K,V> : une table avec hachage sur les clés ;
2. TreeMap<K,V> : un ensemble ordonné sur les clés (implanté là encore avec un arbre rouge-noir équilibré).

Comme pour les Set, les méthodes equals, hashCode ainsi qu'une relation d'ordre doivent être correctement définies, en particulier sur le type K des clés.

Parcours

Un Map peut être parcouru de différentes manières. En fait trois méthodes renvoient les clés et/ou les valeurs dans des collections, qui peuvent à leur tour être itérées.

• la méthode Collection values() retourne une collection (dont on ne connaît pas le type dynamique, mais ce n'est pas nécessaire) contenant toutes les valeurs.
• Set<K> keySet() retourne un ensemble contenant toutes les clés.
• Set<Map.Entry<K,V>> entrySet() retourne un ensemble de tous les couples (clé, valeur). Ces couples sont de type Map.Entry<K,V>, où Entry<K,V> est une classe interne à Map fournissant principalement deux méthodes K getKey() et V getValue().

Pour un SortedMap, les collections ci-dessus sont ordonnées suivant l'ordre défini sur les clés.

Ci-dessous, un exemple (ExempleMap.java).

  // ex: dictionnaire associant des étudiants (clé, une chaîne)
  // à des notes (valeurs entières)
  Map<String, Integer> annuaire = new HashMap<String, Integer> ();

  String mc = new String("Matthieu");
  String sb = new String("Sylvain");
  String nc = new String("Nicolas");
  annuaire.put(mc, 4);
  annuaire.put(sb, 18);
  annuaire.put(nc, 12);
  annuaire.put(mc, 14); // pas de doublons,
                        // mais remplace l'ancienne valeur associée a mc

  // affichage avec toString() : {Nicolas=12, Sylvain=18, Matthieu=14}
  // (ordre indéterminé, c'est du hachage)
  System.out.println("L'annuaire contient: " + annuaire);

  // et quelle est la note de Catherine?
  Integer note = annuaire.get("Catherine");
  System.out.println("La note de Catherine est: " + note);  // null!

  // ensemble des clés : [Nicolas, Sylvain, Matthieu]
  Set<String> cles = annuaire.keySet();
  System.out.println("Les clés sont: " + cles);

  // collection des valeurs : [12, 18, 14]
  Collection<Integer> notes = annuaire.values();
  System.out.println("Les valeurs sont: " + notes);

  // parcours avec un itérateur sur les couples
  // (prévoir une aspirine pour la syntaxe...)
  System.out.println("Les couples sont:");
  Set<Map.Entry<String, Integer>> couples = annuaire.entrySet();
  Iterator<Map.Entry<String, Integer>> itCouples = couples.iterator();
  while (itCouples.hasNext()) {
      Map.Entry<String, Integer> couple = itCouples.next();
      System.out.println("\t" + couple.getKey()
                         + " a la note " + couple.getValue());
  }

Exemple d'ajout de l'objet mc. L'objet est déjà présent(comparaison de nom), par conséquent, il y a remplacement de l'objet déjà existant.

Cheat-sheet des coûts associés aux principales collections

Voici un tableau récapitulatif des coûts associés aux opérations sur les collections présentées dans cette fiche :