IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Penser en Java 2nde édition - Sommaire |  Préface |  Avant-propos | Chapitre : 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 |  Annexe : A B C D  | Tables des matières - Thinking in Java

  Chapitre 9 - Stockage des objets

pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 

Réaliser une pile à partir d'une LinkedList

Une pile est un conteneur « dernier arrivé, premier sorti » (LIFO - « Last In, First Out »). C'est à dire que l'objet qu'on « pousse » (« push »)sur la pile en dernier sera le premier accessible lors d'une extraction (« pop »). Comme tous les autres conteneurs de Java, on stocke et récupère des Objects, qu'il faudra donc retranstyper après leur extraction, à moins qu'on ne se contente des fonctionnalités de la classe Object.

La classe LinkedList possède des méthodes qui implémentent directement les fonctionnalités d'une pile, on peut donc utiliser directement une LinkedList plutôt que de créer une classe implémentant une pile. Cependant une classe est souvent plus explicite :

//: c09:StackL.java
// Réaliser une pile à partir d'une LinkedList.
import java.util.*;
import com.bruceeckel.util.*;

public class StackL {
  private LinkedList list = new LinkedList();
  public void push(Object v) {
    list.addFirst(v);
  }
  public Object top() { return list.getFirst(); }
  public Object pop() {
    return list.removeFirst();
  }
  public static void main(String[] args) {
    StackL stack = new StackL();
    for(int i = 0; i < 10; i++)
      stack.push(Collections2.countries.next());
    System.out.println(stack.top());
    System.out.println(stack.top());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
    System.out.println(stack.pop());
  }
} ///:~

L'héritage n'est pas approprié ici puisqu'il produirait une classe contenant toutes les méthodes d'une LinkedList (on verra que cette erreur a déjà été faite par les concepteurs de la bibliothèque Java 1.0 avec la classe Stack).

Réaliser une file à partir d'une LinkedList

Une file (ou queue) est un conteneur « premier arrivé, premier sorti » (FIFO - « First In, First Out »). C'est à dire qu'on « pousse » des objets à une extrémité et qu'on les en retire à l'autre extrémité. L'ordre dans lequel on pousse les objets sera donc le même que l'ordre dans lequel on les récupérera. La classe LinkedList possède des méthodes qui implémentent directement les fonctionnalités d'une file, on peut donc les utiliser directement dans une classe Queue :

//: c09:Queue.java
// Réaliser une file à partir d'une LinkedList.
import java.util.*;

public class Queue {
  private LinkedList list = new LinkedList();
  public void put(Object v) { list.addFirst(v); }
  public Object get() {
    return list.removeLast();
  }
  public boolean isEmpty() {
    return list.isEmpty();
  }
  public static void main(String[] args) {
    Queue queue = new Queue();
    for(int i = 0; i < 10; i++)
      queue.put(Integer.toString(i));
    while(!queue.isEmpty())
      System.out.println(queue.get());
  }
} ///:~

Il est aussi facile de créer une file double (queue à double entrée) à partir d'une LinkedList. Une file double est une file à laquelle on peut ajouter et supprimer des éléments à chacune de ses extrémités.

Fonctionnalités des Sets

Les Sets ont exactement la même interface que les Collections, et à l'inverse des deux différentes Lists, ils ne proposent aucune fonctionnalité supplémentaire. Les Sets sont donc juste une Collection ayant un comportement particulier (implémenter un comportement différent constitue l'exemple type où il faut utiliser l'héritage et le polymorphisme). Un Set refuse de contenir plus d'une instance de chaque valeur d'un objet (savoir ce qu'est la « valeur » d'un objet est plus compliqué, comme nous allons le voir).

Set (interface) Chaque élément ajouté au Set doit être unique ; sinon le Set n'ajoutera pas le doublon. Les Objects ajoutés à un Set doivent définir la méthode equals() pour pouvoir établir l'unicité de l'objet. Un Set possède la même interface qu'une Collection. L'interface Set ne garantit pas qu'il maintiendra les éléments dans un ordre particulier.
HashSet* Pour les Sets où le temps d'accès aux éléments est primordial. Les Objects doivent définir la méthode hashCode().
TreeSet Un Set trié stocké dans un arbre. De cette manière, on peut extraire une séquence triée à partir du Set.

L'exemple suivant ne montre pas tout ce qu'il est possible de faire avec un Set, puisque l'interface est la même que pour les Collections, et comme telle a déjà été testée dans l'exemple précédent. Par contre, il illustre les comportements qui rendent un Set particulier :

//: c09:Set1.java
// Opérations disponibles pour les Sets.
import java.util.*;
import com.bruceeckel.util.*;

public class Set1 {
  static Collections2.StringGenerator gen =
    Collections2.countries;
  public static void testVisual(Set a) {
    Collections2.fill(a, gen.reset(), 10);    
    Collections2.fill(a, gen.reset(), 10);    
    Collections2.fill(a, gen.reset(), 10);    
    System.out.println(a); // Pas de doublons !
    // Ajoute un autre ensemble à celui-ci :
    a.addAll(a);
    a.add("one");
    a.add("one");
    a.add("one");
    System.out.println(a);
    // Extraction d'item :
    System.out.println("a.contains(\"one\"): " +
      a.contains("one"));
  }
  public static void main(String[] args) {
    System.out.println("HashSet");
    testVisual(new HashSet());
    System.out.println("TreeSet");
    testVisual(new TreeSet());
  }
} ///:~

Cet exemple tente d'ajouter des valeurs dupliquées au Set, mais lorsqu'on l'imprime on voit que le Set n'accepte qu'une instance de chaque valeur.

Lorsqu'on lance ce programme, on voit que l'ordre interne maintenu par le HashSet est différent de celui de TreeSet, puisque chacune de ces implémentations stocke les éléments d'une manière différente (TreeSet garde les éléments triés, tandis que HashSet utilise une fonction de hachage, conçue spécialement pour des accès optimisés). Quand on crée un nouveau type, il faut bien se rappeler qu'un Set a besoin de maintenir un ordre de stockage, ce qui veut dire qu'il faut implémenter l'interface Comparable et définir la méthode compareTo(). Voici un exemple :

//: c09:Set2.java
// Ajout d'un type particulier dans un Set.
import java.util.*;

class MyType implements Comparable {
  private int i;
  public MyType(int n) { i = n; }
  public boolean equals(Object o) {
    return
      (o instanceof MyType)
      && (i == ((MyType)o).i);
  }
  public int hashCode() { return i; }
  public String toString() { return i + " "; }
  public int compareTo(Object o) {
    int i2 = ((MyType)o).i;
    return (i2 < i ? -1 : (i2 == i ? 0 : 1));
  }
}

public class Set2 {
  public static Set fill(Set a, int size) {
    for(int i = 0; i < size; i++)
      a.add(new MyType(i));
    return a;
  }
  public static void test(Set a) {
    fill(a, 10);
    fill(a, 10); // Tente de créer des doublons
    fill(a, 10);
    a.addAll(fill(new TreeSet(), 10));
    System.out.println(a);
  }
  public static void main(String[] args) {
    test(new HashSet());
    test(new TreeSet());
  }
} ///:~

La forme que doivent avoir les définitions des méthodes equals() et hashCode() sera décrite plus tard dans ce chapitre. Il faut définir une méthode equals() pour les deux implémentations de Set, mais hashCode() n'est nécessaire que si la classe est placée dans un hashSet (ce qui est probable, puisqu'il s'agit de l'implémentation recommandée pour un Set). Cependant, c'est une bonne pratique de programmation de redéfinir hashCode() lorsqu'on redéfinit equals(). Ce processus sera examiné en détails plus loin dans ce chapitre.

Notez que je n'ai pas utilisé la forme « simple et évidente » return i-i2 dans la méthode compareTo(). Bien que ce soit une erreur de programmation classique, elle ne fonctionne que si i et i2 sont des ints « non signés » (si Java disposait d'un mot-clef « unsigned », ce qu'il n'a pas). Elle ne marche pas pour les ints signés de Java, qui ne sont pas assez grands pour représenter la différence de deux ints signés. Si i est un grand entier positif et j un grand entier négatif, i-j débordera et renverra une valeur négative, ce qui n'est pas le résultat attendu.

Sets triés : les SortedSets

Un SortedSet (dont TreeSet est l'unique représentant) garantit que ses éléments seront stockés triés, ce qui permet de proposer de nouvelles fonctionnalités grâce aux méthodes supplémentaires de l'interface SortedSet suivantes :

Comparator comparator() : Renvoie le Comparator utilisé pour ce Set, ou null dans le cas d'un tri naturel.

Object first() : Renvoie le plus petit élément.

Object last() : Renvoie le plus grand élément.

SortedSet subSet(fromElement, toElement) : Renvoie une vue du Set contenant les éléments allant de fromElement inclus à toElement exclu.

SortedSet headSet(toElement) : Renvoie une vue du Set contenant les éléments inférieurs à toElement.

SortedSet tailSet(fromElement): Renvoie une vue du Set contenant les éléments supérieurs ou égaux à fromElement.

Fonctionnalités des Maps

Une ArrayList permet de sélectionner des éléments dans une séquence d'objets en utilisant un nombre, elle associe donc des nombres à des objets. Mais qu'en est-il si on souhaite sélectionner des éléments d'une séquence en utilisant un autre critère ? Dans l'exemple d'une pile, son critère de sélection est « le dernier objet poussé sur la pile ». Un tableau associatif, ou map, ou dictionnaire est une alternative particulièrement puissante de cette idée de « sélection dans une séquence ». Conceptuellement, cela ressemble à une ArrayList, mais au lieu de sélectionner un objet par un nombre, on le sélectionne en utilisant un autre objet ! Ce fonctionnement est d'une valeur inestimable dans un programme.

Le concept est illustré dans Java via l'interface Map. La méthode put(Object key, Object value) ajoute une valeur (la chose qu'on veut stocker), et l'associe à une clef (la chose grâce à laquelle on va retrouver la valeur). La méthode get(Object key) renvoie la valeur associée à la clef correspondante. Il est aussi possible de tester une Map pour voir si elle contient une certaine clef ou une certaine valeur avec les méthodes containsKey() et containsValue().

La bibliothèque Java standard propose deux types de Maps : HashMap et TreeMap. Les deux implémentations ont la même interface (puisqu'elles implémentent toutes les deux Map), mais diffèrent sur un point particulier : les performances. Dans le cas d'un appel à  get(), il est peu efficace de chercher dans une ArrayList (par exemple) pour trouver une clef. C'est là que le HashMap intervient. Au lieu d'effectuer une recherche lente sur la clef, il utilise une valeur spéciale appelée code de hachage (hash code). Le code de hachage est une façon d'extraire une partie de l'information de l'objet en question et de la convertir en un int « relativement unique ». Tous les objets Java peuvent produire un code de hachage, et hashCode() est une méthode de la classe racine Object. Un HashMap récupère le hashCode() de l'objet et l'utilise pour retrouver rapidement la clef. Le résultat en est une augmentation drastique des performances  [50].  

Map (interface) Maintient des associations clef - valeur (des paires), afin de pouvoir accéder à une valeur en utilisant une clef.
HashMap* Implémentation basée sur une table de hachage (utilisez ceci à la place d'une Hashtable). Fournit des performances constantes pour l'insertion et l'extraction de paires. Les performances peuvent être ajustées via des constructeurs qui permettent de positionner la capacité et le facteur de charge de la table de hachage.
TreeMap Implémentation basée sur un arbre rouge-noir. L'extraction des clefs ou des paires fournit une séquence triée (selon l'ordre spécifié par Comparable ou Comparator, comme nous le verrons plus loin). Le point important dans un TreeMap est qu'on récupère les résultats dans l'ordre. TreeMap est la seule Map disposant de la méthode subMap(), qui permet de renvoyer une portion de  l'arbre.

Nous nous pencherons sur les mécanismes de hachage un peu plus loin. L'exemple suivant utilise la méthode Collections2.fill() et les ensembles de données définis précédemment :

//: c09:Map1.java
// Opérations disponibles pour les Maps.
import java.util.*;
import com.bruceeckel.util.*;

public class Map1 {
  static Collections2.StringPairGenerator geo =
    Collections2.geography;
  static Collections2.RandStringPairGenerator
    rsp = Collections2.rsp;
  // Produire un Set de clefs :
  public static void printKeys(Map m) {
    System.out.print("Size = " + m.size() +", ");
    System.out.print("Keys: ");
    System.out.println(m.keySet());
  }
  // Produire une Collection de valeurs :
  public static void printValues(Map m) {
    System.out.print("Values: ");
    System.out.println(m.values());
  }
  public static void test(Map m) {
    Collections2.fill(m, geo, 25);
    // Une Map a un comportement de « Set » pour les clefs :
    Collections2.fill(m, geo.reset(), 25);
    printKeys(m);
    printValues(m);
    System.out.println(m);
    String key = CountryCapitals.pairs[4][0];
    String value = CountryCapitals.pairs[4][1];
    System.out.println("m.containsKey(\"" + key +
      "\"): " + m.containsKey(key));
    System.out.println("m.get(\"" + key + "\"): "
      + m.get(key));
    System.out.println("m.containsValue(\""
      + value + "\"): " +
      m.containsValue(value));
    Map m2 = new TreeMap();
    Collections2.fill(m2, rsp, 25);
    m.putAll(m2);
    printKeys(m);
    key = m.keySet().iterator().next().toString();
    System.out.println("First key in map: "+key);
    m.remove(key);
    printKeys(m);
    m.clear();
    System.out.println("m.isEmpty(): "
      + m.isEmpty());
    Collections2.fill(m, geo.reset(), 25);
    // Les opérations sur le Set changent la Map :
    m.keySet().removeAll(m.keySet());
    System.out.println("m.isEmpty(): "
      + m.isEmpty());
  }
  public static void main(String[] args) {
    System.out.println("Testing HashMap");
    test(new HashMap());
    System.out.println("Testing TreeMap");
    test(new TreeMap());
  }
} ///:~

Les méthodes printKeys() et printValues() ne sont pas seulement des utilitaires pratiques, elles illustrent aussi comment produire une vue (sous la forme d'une Collection) d'une Map. La méthode keySet() renvoie un Set rempli par les clefs de la Map. La méthode values() renvoie quant à elle une Collection contenant toutes les valeurs de la Map (notez bien que les clefs doivent être uniques, alors que les valeurs peuvent contenir des doublons). Ces Collections sont liées à la Map, tout changement effectué dans une Collection sera donc répercuté dans la Map associée.

Le reste du programme fournit des exemples simples pour chacune des opérations disponibles pour une Map, et teste les deux types de Maps.

Comme exemple d'utilisation d'un HashMap, considérons un programme vérifiant la nature aléatoire de la méthode Math.random() de Java. Idéalement, elle devrait produire une distribution parfaite de nombres aléatoires, mais pour tester cela il faut générer un ensemble de nombres aléatoires et compter ceux qui tombent dans les différentes plages. Un HashMap est parfait pour ce genre d'opérations, puisqu'il associe des objets à d'autres objets (dans ce cas, les objets valeurs contiennent le nombre produit par Math.random() ainsi que le nombre de fois où ce nombre apparaît) :

//: c09:Statistics.java
// Simple démonstration de l'utilisation d'un HashMap.
import java.util.*;

class Counter {
  int i = 1;
  public String toString() {
    return Integer.toString(i);
  }
}

class Statistics {
  public static void main(String[] args) {
    HashMap hm = new HashMap();
    for(int i = 0; i < 10000; i++) {
      // Produit un nombre entre 0 et 20 :
      Integer r =
        new Integer((int)(Math.random() * 20));
      if(hm.containsKey(r))
        ((Counter)hm.get(r)).i++;
      else
        hm.put(r, new Counter());
    }
    System.out.println(hm);
  }
} ///:~

Ce livre a été écrit par Bruce Eckel ( télécharger la version anglaise : Thinking in java )
Ce chapitre a été traduit par Jérome Quelin ( groupe de traduction )
télécharger la version francaise (PDF) | Commandez le livre en version anglaise (amazon) | télécharger la version anglaise
pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
Penser en Java 2nde édition - Sommaire |  Préface |  Avant-propos | Chapitre : 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 |  Annexe : A B C D  | Tables des matières - Thinking in Java