Penser en Java

Indépendamment du type de tableau qu'on utilise, un identifiant de tableau est en fait une référence sur un vrai objet créé dans le segment. C'est l'objet qui stocke les références sur les autres objets, et il peut être créé soit implicitement grâce à la syntaxe d'initialisation de tableau, soit explicitement avec une expression new. Une partie de l'objet tableau (en fait, la seule méthode ou champ auquel on peut accéder) est le membre en lecture seule length qui indique combien d'éléments peuvent être stockés dans l'objet. La syntaxe « [] » est le seul autre accès disponible pour les objets tableaux.

L'exemple suivant montre les différentes façons d'initialiser un tableau, et comment les références sur un tableau peuvent être assignées à différents objets tableau. Il montre aussi que les tableaux d'objets et les tableaux de scalaires sont quasi identiques dans leur utilisation. La seule différence est qu'un tableau d'objets stocke des références, alors qu'un tableau de scalaires stocke les valeurs directement.

//: c09:ArraySize.java
// Initialisation & réassignation des tableaux.

class Weeble {} // Une petite créature mythique

public class ArraySize {
  public static void main(String[] args) {
    // Tableaux d'objets :
    Weeble[] a; // Référence Null.
    Weeble[] b = new Weeble[5]; // Références Null
    Weeble[] c = new Weeble[4];
    for(int i = 0; i < c.length; i++)
      c[i] = new Weeble();
    // Initialisation par agrégat :
    Weeble[] d = { 
      new Weeble(), new Weeble(), new Weeble()
    };
    // Initialisation dynamique par agrégat :
    a = new Weeble[] {
      new Weeble(), new Weeble()
    };
    System.out.println("a.length=" + a.length);
    System.out.println("b.length = " + b.length);
    // Les références à l'intérieur du tableau sont
    // automatiquement initialisées à null :
    for(int i = 0; i < b.length; i++)
      System.out.println("b[" + i + "]=" + b[i]);
    System.out.println("c.length = " + c.length);
    System.out.println("d.length = " + d.length);
    a = d;
    System.out.println("a.length = " + a.length);

    // Tableaux de scalaires :
    int[] e; // Référence Null
    int[] f = new int[5];
    int[] g = new int[4];
    for(int i = 0; i < g.length; i++)
      g[i] = i*i;
    int[] h = { 11, 47, 93 };
    // Erreur de compilation : variable e non initialisée :
    //!System.out.println("e.length=" + e.length);
    System.out.println("f.length = " + f.length);
    // Les scalaires dans le tableau sont
    // automatiquement initialisées à zéro :
    for(int i = 0; i < f.length; i++)
      System.out.println("f[" + i + "]=" + f[i]);
    System.out.println("g.length = " + g.length);
    System.out.println("h.length = " + h.length);
    e = h;
    System.out.println("e.length = " + e.length);
    e = new int[] { 1, 2 };
    System.out.println("e.length = " + e.length);
  }
} ///:~

Voici la sortie du programme :

a.length = 2
b.length = 5
b[0]=null
b[1]=null
b[2]=null
b[3]=null
b[4]=null
c.length = 4
d.length = 3
a.length = 3
f.length = 5
f[0]=0
f[1]=0
f[2]=0
f[3]=0
f[4]=0
g.length = 4
h.length = 3
e.length = 3
e.length = 2

Le tableau a n'est initialement qu'une référence null, et le compilateur interdit d'utiliser cette référence tant qu'elle n'est pas correctement initialisée. Le tableau b est initialisé afin de pointer sur un tableau de références Weeble, même si aucun objet Weeble n'est réellement stocké dans le tableau. Cependant, on peut toujours s'enquérir de la taille du tableau, puisque b pointe sur un objet valide. Ceci montre un inconvénient des tableaux : on ne peut savoir combien d'éléments sont actuellement stockés dans le tableau, puisque length renvoie seulement le nombre d'éléments qu'on peut stocker dans le tableau, autrement dit la taille de l'objet tableau, et non le nombre d'éléments qu'il contient réellement. Cependant, quand un objet tableau est créé, ses références sont automatiquement initialisées à null, on peut donc facilement savoir si une cellule du tableau contient un objet ou pas en testant si son contenu est null. De même, un tableau de scalaires est automatiquement initialisé à zéro pour les types numériques, (char)0 pour les caractères et false pour les booleans.

Le tableau c montre la création d'un objet tableau suivi par l'assignation d'un objet Weeble à chacune des cellules du tableau. Le tableau d illustre la syntaxe d'« initialisation par agrégat » qui permet de créer un objet tableau (implicitement sur le segment avec new, comme le tableau c) et de l'initialiser avec des objets Weeble, le tout dans une seule instruction.

L'initialisation de tableau suivante peut être qualifiée d'« initialisation dynamique par agrégat ». L'initialisation par agrégat utilisée par d doit être utilisée lors de la définition de d, mais avec la seconde syntaxe il est possible de créer et d'initialiser un objet tableau n'importe où. Par exemple, supposons que hide() soit une méthode qui accepte un tableau d'objets Weeble comme argument. On peut l'appeler via :

hide(d);

mais on peut aussi créer dynamiquement le tableau qu'on veut passer comme argument :

hide(new Weeble[] { new Weeble(), new Weeble() });

Cette nouvelle syntaxe est bien plus pratique pour certaines parties de code.

L'expression :

a = d;

montre comment prendre une référence attachée à un tableau d'objets et l'assigner à un autre objet tableau, de la même manière qu'avec n'importe quel type de référence. Maintenant a et d pointent sur le même tableau d'objets dans le segment.

La seconde partie de ArraySize.java montre que les tableaux de scalaires fonctionnent de la même manière que les tableaux d'objets sauf que les tableaux de scalaires stockent directement les valeurs des scalaires.

XI-A-1-a. Conteneurs de scalaires▲

Supposons qu'on veuille écrire une méthode qui ne renvoie pas une seule chose, mais tout un ensemble de choses. Ce n'est pas facile à réaliser dans des langages tels que C ou C++ puisqu'ils ne permettent pas de renvoyer un tableau, mais seulement un pointeur sur un tableau. Cela ouvre la porte à de nombreux problèmes du fait qu'il devient ardu de contrôler la durée de vie du tableau, ce qui mène très rapidement à des fuites de mémoire.

Java utilise une approche similaire, mais permet de « renvoyer un tableau ». Bien sûr, il s'agit en fait d'une référence sur un tableau, mais Java assume de manière transparente la responsabilité de ce tableau - il sera disponible tant qu'on en aura besoin, et le ramasse-miettes le nettoiera lorsqu'on en aura fini avec lui.

Voici un exemple retournant un tableau de String :

//: c09:IceCream.java
// Renvoyer un tableau depuis des méthodes.

public class IceCream {
  static String[] flav = {
    "Chocolate", "Strawberry",
    "Vanilla Fudge Swirl", "Mint Chip",
    "Mocha Almond Fudge", "Rum Raisin",
    "Praline Cream", "Mud Pie" 
  };
  static String[] flavorSet(int n) {
    // Force l'argument à être positif & à l'intérieur des indices :
    n = Math.abs(n) % (flav.length + 1);
    String[] results = new String[n];
    boolean[] picked = 
      new boolean[flav.length];
    for (int i = 0; i < n; i++) {
      int t;
      do 
        t = (int)(Math.random() * flav.length);
      while (picked[t]);
      results[i] = flav[t];
      picked[t] = true;
    }
    return results;
  }
  public static
   void main(String[] args) {
    for(int i = 0; i < 20; i++) {
      System.out.println(
        "flavorSet(" + i + ") = ");
      String[] fl = flavorSet(flav.length);
      for(int j = 0; j < fl.length; j++)
        System.out.println("\t" + fl[j]);
    }
  }
} ///:~

La méthode flavorSet() crée un tableau de Strings de taille n (déterminé par l'argument de la méthode) appelé results. Elle choisit alors au hasard des parfums dans le tableau flav et les place dans results, qu'elle renvoie quand elle en a terminé. Renvoyer un tableau s'apparente à renvoyer n'importe quel autre objet - ce n'est qu'une référence. Le fait que le tableau ait été créé dans flavorSet() n'est pas important, il aurait pu être créé n'importe où. Le ramasse-miettes s'occupe de nettoyer le tableau quand on en a fini avec lui, mais le tableau existera tant qu'on en aura besoin.

Notez en passant que quand flavorSet() choisit des parfums au hasard, elle s'assure que le parfum n'a pas déjà été choisi auparavant. Ceci est réalisé par une boucle do qui continue de tirer un parfum au sort jusqu'à ce qu'elle en trouve un qui ne soit pas dans le tableau picked (bien sûr, on aurait pu utiliser une comparaison sur String avec les éléments du tableau results, mais les comparaisons sur String ne sont pas efficaces). Une fois le parfum sélectionné, elle l'ajoute dans le tableau et trouve le parfum suivant (i est alors incrémenté).

main() affiche 20 ensembles de parfums, et on peut voir que flavorSet() choisit les parfums dans un ordre aléatoire à chaque fois. Il est plus facile de s'en rendre compte si on redirige la sortie dans un fichier. Et lorsque vous examinerez ce fichier, rappelez-vous que vous voulez juste la glace, vous n'en avez pas besoin.

java.util contient la classe Arrays, qui propose un ensemble de méthodes static réalisant des opérations utiles sur les tableaux. Elle dispose de quatre fonctions de base : equals(), qui compare deux tableaux ; fill(), pour remplir un tableau avec une valeur ; sort(), pour trier un tableau ; et binarySearch(), pour trouver un élément dans un tableau trié. Toutes ces méthodes sont surchargées pour tous les types scalaires et les Objects. De plus, il existe une méthode asList() qui transforme un tableau en un conteneur List - que nous rencontrerons plus tard dans ce chapitre.

Bien que pratique, la classe Arrays montre vite ses limites. Par exemple, il serait agréable de pouvoir facilement afficher les éléments d'un tableau sans avoir à coder une boucle for à chaque fois. Et comme nous allons le voir, la méthode fill() n'accepte qu'une seule valeur pour remplir le tableau, ce qui la rend inutile si on voulait - par exemple - remplir le tableau avec des nombres aléatoires.

Nous allons donc compléter la classe Arrays avec d'autres utilitaires, qui seront placés dans le package com.bruceeckel.util. Ces utilitaires permettront d'afficher un tableau de n'importe quel type, et de remplir un tableau avec des valeurs ou des objets créés par un objet appelé générateur qu'il est possible de définir.

Du fait qu'il faille écrire du code pour chaque type scalaire de base aussi bien que pour la classe Object, une grande majorité de ce code est dupliqué (39). Ainsi une interface « générateur » est requise pour chaque type parce que le type renvoyé par next() doit être différent dans chaque cas :

//: com:bruceeckel:util:Generator.java
package com.bruceeckel.util;
public interface Generator { 
  Object next(); 
} ///:~

//: com:bruceeckel:util:BooleanGenerator.java
package com.bruceeckel.util;
public interface BooleanGenerator {
  boolean next();
} ///:~

//: com:bruceeckel:util:ByteGenerator.java
package com.bruceeckel.util;
public interface ByteGenerator {
  byte next();
} ///:~

//: com:bruceeckel:util:CharGenerator.java
package com.bruceeckel.util;
public interface CharGenerator {
  char next();
} ///:~

//: com:bruceeckel:util:ShortGenerator.java
package com.bruceeckel.util;
public interface ShortGenerator {
  short next();
} ///:~

//: com:bruceeckel:util:IntGenerator.java
package com.bruceeckel.util;
public interface IntGenerator {
  int next();
} ///:~

//: com:bruceeckel:util:LongGenerator.java
package com.bruceeckel.util;
public interface LongGenerator {
  long next();
} ///:~

//: com:bruceeckel:util:FloatGenerator.java
package com.bruceeckel.util;
public interface FloatGenerator {
  float next();
} ///:~

//: com:bruceeckel:util:DoubleGenerator.java
package com.bruceeckel.util;
public interface DoubleGenerator {
  double next();
} ///:~

//: com:bruceeckel:util:Arrays2.java
// Un complément à java.util.Arrays, pour fournir
// de nouvelles fonctionnalités utiles lorsqu'on
// travaille avec des tableaux. Permet d'afficher
// n'importe quel tableau, et de le remplir via un
// objet « générateur » personnalisable.
package com.bruceeckel.util;
import java.util.*;

public class Arrays2 {
  private static void
  start(int from, int to, int length) {
    if(from != 0 || to != length)
      System.out.print("["+ from +":"+ to +"] ");
    System.out.print("(");
  }
  private static void end() {
    System.out.println(")");
  }
  public static void print(Object[] a) {
    print(a, 0, a.length);
  }
  public static void 
  print(String msg, Object[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(Object[] a, int from, int to){
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to -1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(boolean[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, boolean[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(boolean[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to -1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(byte[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, byte[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(byte[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to -1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(char[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, char[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(char[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to -1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(short[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, short[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(short[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to &#150; 1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(int[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, int[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(int[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to &#150; 1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(long[] a) {
    print(a, 0, a.length);
  }
  public static void 
  print(String msg, long[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(long[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to &#150; 1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(float[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, float[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(float[] a, int from, int to) {
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to &#150; 1)
        System.out.print(", ");
    }
    end();
  }
  public static void print(double[] a) {
      print(a, 0, a.length);
  }
  public static void 
  print(String msg, double[] a) {
    System.out.print(msg + " ");
    print(a, 0, a.length);
  }
  public static void 
  print(double[] a, int from, int to){
    start(from, to, a.length);
    for(int i = from; i < to; i++) {
      System.out.print(a[i]);
      if(i < to &#150; 1)
        System.out.print(", ");
    }
    end();
  }
  // Remplit un tableau en utilisant un générateur :
  public static void 
  fill(Object[] a, Generator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(Object[] a, int from, int to, 
       Generator gen){
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(boolean[] a, BooleanGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(boolean[] a, int from, int to,
       BooleanGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(byte[] a, ByteGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(byte[] a, int from, int to, 
       ByteGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(char[] a, CharGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(char[] a, int from, int to, 
       CharGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(short[] a, ShortGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(short[] a, int from, int to, 
       ShortGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(int[] a, IntGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(int[] a, int from, int to, 
       IntGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(long[] a, LongGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(long[] a, int from, int to, 
       LongGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(float[] a, FloatGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(float[] a, int from, int to, 
       FloatGenerator gen) {
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  public static void 
  fill(double[] a, DoubleGenerator gen) {
      fill(a, 0, a.length, gen);
  }
  public static void 
  fill(double[] a, int from, int to,
       DoubleGenerator gen){
    for(int i = from; i < to; i++)
      a[i] = gen.next();
  }
  private static Random r = new Random();
  public static class RandBooleanGenerator 
  implements BooleanGenerator {
    public boolean next() { 
      return r.nextBoolean();
    }
  }
  public static class RandByteGenerator 
  implements ByteGenerator {
    public byte next() { 
      return (byte)r.nextInt();
    }
  }
  static String ssource = 
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ" +
    "abcdefghijklmnopqrstuvwxyz";
  static char[] src = ssource.toCharArray();
  public static class RandCharGenerator 
  implements CharGenerator {
    public char next() {
      int pos = Math.abs(r.nextInt());
      return src[pos % src.length];
    }
  }
  public static class RandStringGenerator
  implements Generator {
    private int len;
    private RandCharGenerator cg = 
      new RandCharGenerator();
    public RandStringGenerator(int length) {
      len = length;
    }
    public Object next() {
      char[] buf = new char[len];
      for(int i = 0; i < len; i++)
        buf[i] = cg.next();
      return new String(buf);
    }
  }
  public static class RandShortGenerator 
  implements ShortGenerator {
    public short next() { 
      return (short)r.nextInt();
    }
  }
  public static class RandIntGenerator 
  implements IntGenerator {
    private int mod = 10000;
    public RandIntGenerator() {}
    public RandIntGenerator(int modulo) {
      mod = modulo;
    }
    public int next() { 
      return r.nextInt() % mod; 
    }
  }
  public static class RandLongGenerator 
  implements LongGenerator {
    public long next() { return r.nextLong(); }
  }
  public static class RandFloatGenerator 
  implements FloatGenerator {
    public float next() { return r.nextFloat(); }
  }
  public static class RandDoubleGenerator 
  implements DoubleGenerator {
    public double next() {return r.nextDouble();}
  }
} ///:~

Pour remplir un tableau en utilisant un générateur, la méthode fill() accepte une référence sur une interface génératrice, qui dispose d'une méthode next() produisant d'une façon ou d'une autre (selon l'implémentation de l'interface) un objet du bon type. La méthode fill() se contente d'appeler next() jusqu'à ce que la plage désirée du tableau soit remplie. Il est donc maintenant possible de créer un générateur en implémentant l'interface appropriée, et d'utiliser ce générateur avec fill().

Les générateurs de données aléatoires sont utiles lors des tests, un ensemble de classes internes a donc été créé pour implémenter toutes les interfaces pour les types scalaires de base, de même qu'un générateur de String pour représenter des Objects. On peut noter au passage que RandStringGenerator utilise RandCharGenerator pour remplir un tableau de caractères, qui est ensuite transformé en String. La taille du tableau est déterminée par l'argument du constructeur.

Afin de générer des nombres qui ne soient pas trop grands, RandIntGenerator utilise un modulus par défaut de 10 000, mais un constructeur surchargé permet de choisir une valeur plus petite.

Voici un programme qui teste la bibliothèque et illustre la manière de l'utiliser :

//: c09:TestArrays2.java
// Teste et illustre les utilitaires d'Arrays2
import com.bruceeckel.util.*;

public class TestArrays2 {
  public static void main(String[] args) {
    int size = 6;
    // Ou récupère la taille depuis la ligne de commande :
    if(args.length != 0)
      size = Integer.parseInt(args[0]);
    boolean[] a1 = new boolean[size];
    byte[] a2 = new byte[size];
    char[] a3 = new char[size];
    short[] a4 = new short[size];
    int[] a5 = new int[size];
    long[] a6 = new long[size];
    float[] a7 = new float[size];
    double[] a8 = new double[size];
    String[] a9 = new String[size];
    Arrays2.fill(a1, 
      new Arrays2.RandBooleanGenerator());
    Arrays2.print(a1);
    Arrays2.print("a1 = ", a1);
    Arrays2.print(a1, size/3, size/3 + size/3);
    Arrays2.fill(a2,
      new Arrays2.RandByteGenerator());
    Arrays2.print(a2);
    Arrays2.print("a2 = ", a2);
    Arrays2.print(a2, size/3, size/3 + size/3);
    Arrays2.fill(a3,
      new Arrays2.RandCharGenerator());
    Arrays2.print(a3);
    Arrays2.print("a3 = ", a3);
    Arrays2.print(a3, size/3, size/3 + size/3);
    Arrays2.fill(a4,
      new Arrays2.RandShortGenerator());
    Arrays2.print(a4);
    Arrays2.print("a4 = ", a4);
    Arrays2.print(a4, size/3, size/3 + size/3);
    Arrays2.fill(a5,
      new Arrays2.RandIntGenerator());
    Arrays2.print(a5);
    Arrays2.print("a5 = ", a5);
    Arrays2.print(a5, size/3, size/3 + size/3);
    Arrays2.fill(a6,
      new Arrays2.RandLongGenerator());
    Arrays2.print(a6);
    Arrays2.print("a6 = ", a6);
    Arrays2.print(a6, size/3, size/3 + size/3);
    Arrays2.fill(a7,
      new Arrays2.RandFloatGenerator());
    Arrays2.print(a7);
    Arrays2.print("a7 = ", a7);
    Arrays2.print(a7, size/3, size/3 + size/3);
    Arrays2.fill(a8,
      new Arrays2.RandDoubleGenerator());
    Arrays2.print(a8);
    Arrays2.print("a8 = ", a8);
    Arrays2.print(a8, size/3, size/3 + size/3);
    Arrays2.fill(a9,
      new Arrays2.RandStringGenerator(7));
    Arrays2.print(a9);
    Arrays2.print("a9 = ", a9);
    Arrays2.print(a9, size/3, size/3 + size/3);
  }
} ///:~

La bibliothèque standard Java Arrays propose aussi une méthode fill(), mais celle-ci est relativement triviale : elle ne fait que dupliquer une certaine valeur dans chaque cellule, ou dans le cas d'objets, copier la même référence dans chaque cellule. En utilisant Arrays2.print(), les méthodes Arrays.fill() peuvent être facilement illustrées :

//: c09:FillingArrays.java
// Utilisation de Arrays.fill()
import com.bruceeckel.util.*;
import java.util.*;

public class FillingArrays {
  public static void main(String[] args) {
    int size = 6;
    // Ou récupère la taille depuis la ligne de commande :
    if(args.length != 0)
      size = Integer.parseInt(args[0]);
    boolean[] a1 = new boolean[size];
    byte[] a2 = new byte[size];
    char[] a3 = new char[size];
    short[] a4 = new short[size];
    int[] a5 = new int[size];
    long[] a6 = new long[size];
    float[] a7 = new float[size];
    double[] a8 = new double[size];
    String[] a9 = new String[size];
    Arrays.fill(a1, true);
    Arrays2.print("a1 = ", a1);
    Arrays.fill(a2, (byte)11);
    Arrays2.print("a2 = ", a2);
    Arrays.fill(a3, 'x');
    Arrays2.print("a3 = ", a3);
    Arrays.fill(a4, (short)17);
    Arrays2.print("a4 = ", a4);
    Arrays.fill(a5, 19);
    Arrays2.print("a5 = ", a5);
    Arrays.fill(a6, 23);
    Arrays2.print("a6 = ", a6);
    Arrays.fill(a7, 29);
    Arrays2.print("a7 = ", a7);
    Arrays.fill(a8, 47);
    Arrays2.print("a8 = ", a8);
    Arrays.fill(a9, "Hello");
    Arrays2.print("a9 = ", a9);
    // Manipulation de plages d'index :
    Arrays.fill(a9, 3, 5, "World");
    Arrays2.print("a9 = ", a9);
  }
} ///:~

On peut soit remplir un tableau complètement, soit - comme le montrent les deux dernières instructions - une certaine plage d'indices. Mais comme il n'est possible de ne fournir qu'une seule valeur pour le remplissage dans Arrays.fill(), les méthodes Arrays2.fill() sont bien plus intéressantes.

La bibliothèque standard Java propose une méthode static, System.arraycopy(), qui réalise des copies de tableau bien plus rapidement qu'une boucle for. System.arraycopy() est surchargée afin de gérer tous les types. Voici un exemple qui manipule des tableaux d'int :

//: c09:CopyingArrays.java
// Utilisation de System.arraycopy()
import com.bruceeckel.util.*;
import java.util.*;

public class CopyingArrays {
  public static void main(String[] args) {
    int[] i = new int[25];
    int[] j = new int[25];
    Arrays.fill(i, 47);
    Arrays.fill(j, 99);
    Arrays2.print("i = ", i);
    Arrays2.print("j = ", j);
    System.arraycopy(i, 0, j, 0, i.length);
    Arrays2.print("j = ", j);
    int[] k = new int[10];
    Arrays.fill(k, 103);
    System.arraycopy(i, 0, k, 0, k.length);
    Arrays2.print("k = ", k);
    Arrays.fill(k, 103);
    System.arraycopy(k, 0, i, 0, k.length);
    Arrays2.print("i = ", i);
    // Objects :
    Integer[] u = new Integer[10];
    Integer[] v = new Integer[5];
    Arrays.fill(u, new Integer(47));
    Arrays.fill(v, new Integer(99));
    Arrays2.print("u = ", u);
    Arrays2.print("v = ", v);
    System.arraycopy(v, 0, 
      u, u.length/2, v.length);
    Arrays2.print("u = ", u);
  }
} ///:~

arraycopy() accepte comme arguments le tableau source, le déplacement dans le tableau source à partir duquel démarrer la copie, le tableau destination, le déplacement dans le tableau destination à partir duquel démarrer la copie, et le nombre d'éléments à copier. Bien entendu, toute violation des frontières du tableau générera une exception.

L'exemple montre bien qu'on peut copier des tableaux de scalaires comme des tableaux d'objets. Cependant, dans le cas de la copie de tableaux d'objets, seules les références sont copiées - il n'y a pas duplication des objets eux-mêmes. C'est ce qu'on appelle une copie superficielle (voir l'Annexe A).

Arrays fournit la méthode surchargée equals() pour comparer des tableaux entiers. Encore une fois, ces méthodes sont surchargées pour chacun des types de base, ainsi que pour les Objects. Pour être égaux, les tableaux doivent avoir la même taille et chaque élément doit être équivalent (au sens de la méthode equals()) à l'élément correspondant dans l'autre tableau (pour les types scalaires, la méthode equals() de la classe d'encapsulation du type concerné est utilisé ; par exemple, Integer.equals() est utilisé pour les int). Voici un exemple :

//: c09:ComparingArrays.java
// Utilisation de Arrays.equals()
import java.util.*;

public class ComparingArrays {
  public static void main(String[] args) {
    int[] a1 = new int[10];
    int[] a2 = new int[10];
    Arrays.fill(a1, 47);
    Arrays.fill(a2, 47);
    System.out.println(Arrays.equals(a1, a2));
    a2[3] = 11;
    System.out.println(Arrays.equals(a1, a2));
    String[] s1 = new String[5];
    Arrays.fill(s1, "Hi");
    String[] s2 = {"Hi", "Hi", "Hi", "Hi", "Hi"};
    System.out.println(Arrays.equals(s1, s2));
  }
} ///:~

Au début du programme, a1 et a2 sont identiques, donc le résultat est « true » ; puis l'un des éléments est changé donc la deuxième ligne affichée est « false ». Dans le dernier cas, tous les éléments de s1 pointent sur le même objet, alors que s2 contient cinq objets différents. Cependant, l'égalité de tableaux est basée sur le contenu (via Object.equals()) et donc le résultat est « true ».

Quelques-unes des fonctionnalités manquantes dans les bibliothèques Java 1.0 et 1.1 sont les opérations algorithmiques - y compris les simples tris. Ceci était relativement frustrant pour quiconque s'attendait à une bibliothèque standard conséquente. Heureusement, Java 2 a corrigé cette situation, au moins pour le problème du tri.

Le problème posé par l'écriture d'une méthode de tri générique est que le tri doit réaliser des comparaisons basées sur le type réel de l'objet. Bien sûr, l'une des approches consiste à écrire une méthode de tri différente pour chaque type, mais cela va à l'encontre du principe de réutilisabilité du code pour les nouveaux types.

L'un des buts principaux de la conception est de « séparer les choses qui changent de celles qui ne bougent pas » ; ici, le code qui reste le même est l'algorithme général de tri, alors que la manière de comparer les objets entre eux est ce qui change d'un cas d'utilisation à l'autre. Donc au lieu de coder en dur le code de comparaison dans différentes procédures de tri, on utilise ici la technique des callbacks. Avec un callback, la partie du code qui varie d'un cas à l'autre est encapsulée dans sa propre classe, et la partie du code qui ne change pas appellera ce code pour réaliser les comparaisons. De cette manière, il est possible de créer différents objets pour  exprimer différentes sortes de comparaisons et de les passer au même code de tri.

Dans Java 2, il existe deux manières de fournir des fonctionnalités de comparaison. La méthode naturelle de comparaison constitue la première, elle est annoncée dans une classe en implémentant l'interface java.lang.Comparable. C'est une interface très simple ne disposant que d'une seule méthode, compareTo(). Cette méthode accepte un autre Object comme argument, et renvoie une valeur négative si l'argument est plus grand que l'objet courant, zéro s'ils sont égaux, ou une valeur positive si l'argument est plus petit que l'objet courant.

Voici une classe qui implémente Comparable et illustre la comparaison en utilisant la méthode Arrays.sort() de la bibliothèque standard Java :

//: c09:CompType.java
// Implémenter Comparable dans une classe.
import com.bruceeckel.util.*;
import java.util.*;

public class CompType implements Comparable {
  int i;
  int j;
  public CompType(int n1, int n2) { 
    i = n1;
    j = n2;
  }
  public String toString() { 
    return "[i = " + i + ", j = " + j + "]";
  }
  public int compareTo(Object rv) {
    int rvi = ((CompType)rv).i;
    return (i < rvi ? -1 : (i == rvi ? 0 : 1));
  }
  private static Random r = new Random();
  private static int randInt() {
    return Math.abs(r.nextInt()) % 100;
  }
  public static Generator generator() {
    return new Generator() {
      public Object next() {
        return new CompType(randInt(),randInt());
      }
    };
  }
  public static void main(String[] args) {
    CompType[] a = new CompType[10];
    Arrays2.fill(a, generator());
    Arrays2.print("before sorting, a = ", a);
    Arrays.sort(a);
    Arrays2.print("after sorting, a = ", a);
  }
} ///:~

Lorsque la fonction de comparaison est définie, il vous incombe de décider du sens à donner à la comparaison entre deux objets. Ici, seules les valeurs i sont utilisées dans la comparaison, les valeurs j sont ignorées.

La méthode static randInt() produit des valeurs positives entre zéro et 100, et la méthode generator() produit un objet implémentant l'interface Generator, en créant une classe interne anonyme (cf. titre X). Celui-ci génère des objets CompType en les initialisant avec des valeurs aléatoires. Dans main(), le générateur est utilisé pour remplir un tableau de CompType, qui est alors trié. Si Comparable n'avait pas été implémentée, une erreur de compilation aurait été générée lors d'un appel à sort().

Dans le cas où une classe n'implémente pas Comparable, ou qu'elle l'implémente d'une manière qui ne vous satisfait pas (c'est-à-dire que vous souhaitez une autre fonction de comparaison pour ce type), il faut utiliser une autre approche pour comparer des objets. Cette approche nécessite de créer une classe séparée qui implémente l'interface Comparator, comportant les deux méthodes compare() et equals(). Cependant, sauf cas particulier (pour des raisons de performance notamment), il n'est pas nécessaire d'implémenter equals(), car chaque classe dérive implicitement de Object, qui fournit déjà cette méthode. On peut donc se contenter de la méthode Object.equals() pour satisfaire au contrat imposé par l'interface.

La classe Collections (que nous étudierons plus en détail par la suite) dispose d'un Comparator qui inverse l'ordre de tri. Ceci peut facilement être appliqué à CompType :

//: c09:Reverse.java
// Le Comparator Collecions.reverseOrder().
import com.bruceeckel.util.*;
import java.util.*;

public class Reverse {
  public static void main(String[] args) {
    CompType[] a = new CompType[10];
    Arrays2.fill(a, CompType.generator());
    Arrays2.print("before sorting, a = ", a);
    Arrays.sort(a, Collections.reverseOrder());
    Arrays2.print("after sorting, a = ", a);
  }
} ///:~

L'appel à Collections.reverseOrder() produit une référence sur le Comparator.

Voici un deuxième exemple dans lequel un Comparator compare des objets CompType en se basant cette fois sur la valeur de leur j plutôt que sur celle de i :

//: c09:ComparatorTest.java
// Implémenter un Comparator pour une classe.
import com.bruceeckel.util.*;
import java.util.*;

class CompTypeComparator implements Comparator {
  public int compare(Object o1, Object o2) {
    int j1 = ((CompType)o1).j;
    int j2 = ((CompType)o2).j;
    return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1));
  }
}
           
public class ComparatorTest {
  public static void main(String[] args) {
    CompType[] a = new CompType[10];
    Arrays2.fill(a, CompType.generator());
    Arrays2.print("before sorting, a = ", a);
    Arrays.sort(a, new CompTypeComparator());
    Arrays2.print("after sorting, a = ", a);
  }
} ///:~

La méthode compare() doit renvoyer un entier négatif, zéro ou un entier positif selon que le premier argument est respectivement plus petit, égal ou plus grand que le second.

Avec les méthodes de tri intégrées, il est maintenant possible de trier n'importe quel tableau de scalaires ou d'objets implémentant Comparable ou disposant d'une classe Comparator associée. Ceci comble un énorme trou dans les bibliothèques de Java - croyez-le ou non, Java 1.0 et 1.1 ne fournissaient aucun moyen de trier des Strings ! Voici un exemple qui génère des objets String aléatoirement et les trie :

//: c09:StringSorting.java
// Trier un tableau de Strings.
import com.bruceeckel.util.*;
import java.util.*;

public class StringSorting {
  public static void main(String[] args) {
    String[] sa = new String[30];
    Arrays2.fill(sa,
      new Arrays2.RandStringGenerator(5));
    Arrays2.print("Before sorting: ", sa);
    Arrays.sort(sa);
    Arrays2.print("After sorting: ", sa);
  }
} ///:~

Il est bon de noter que le tri effectué sur les Strings est lexicographique, c'est-à-dire que les mots commençant par des majuscules apparaissent avant ceux débutant par une minuscule (typiquement les annuaires sont triés de cette façon). Il est toutefois possible de redéfinir ce comportement et d'ignorer la casse en définissant une classe Comparator. Cette classe sera placée dans le package « util » à des fins de réutilisation :

//: com:bruceeckel:util:AlphabeticComparator.java
// Garder les lettres majuscules et minuscules ensemble.
package com.bruceeckel.util;
import java.util.*;

public class AlphabeticComparator 
implements Comparator{
  public int compare(Object o1, Object o2) {
    String s1 = (String)o1;
    String s2 = (String)o2;
    return s1.toLowerCase().compareTo(
      s2.toLowerCase());
  }
} ///:~

Chaque String est convertie en minuscules avant la comparaison. La méthode compareTo() de String fournit ensuite le comparateur désiré.

Voici un exemple d'utilisation d'AlphabeticComparator :

//: c09:AlphabeticSorting.java
// Garder les lettres majuscules et minuscules ensemble.
import com.bruceeckel.util.*;
import java.util.*;

public class AlphabeticSorting {
  public static void main(String[] args) {
    String[] sa = new String[30];
    Arrays2.fill(sa,
      new Arrays2.RandStringGenerator(5));
    Arrays2.print("Before sorting: ", sa);
    Arrays.sort(sa, new AlphabeticComparator());
    Arrays2.print("After sorting: ", sa);
  }
} ///:~

L'algorithme de tri utilisé dans la bibliothèque standard de Java est conçu pour être optimal suivant le type d'objets triés : un Quicksort pour les scalaires, et un tri-fusion stable pour les objets. Vous ne devriez donc pas avoir à vous soucier des performances à moins qu'un outil de profilage ne vous démontre explicitement que le goulot d'étranglement de votre programme soit le processus de tri.

Une fois un tableau trié, il est possible d'effectuer une recherche rapide sur un item en utilisant Arrays.binarySearch(). Il est toutefois très important de ne pas utiliser binarySearch() sur un tableau non trié ; le résultat en serait imprévisible. L'exemple suivant utilise un RandIntGenerator pour remplir un tableau et produire des valeurs à chercher dans ce tableau :

//: c09:ArraySearching.java
// Utilisation de Arrays.binarySearch().
import com.bruceeckel.util.*;
import java.util.*;

public class ArraySearching {
  public static void main(String[] args) {
    int[] a = new int[100];
    Arrays2.RandIntGenerator gen = 
      new Arrays2.RandIntGenerator(1000);
    Arrays2.fill(a, gen);
    Arrays.sort(a);
    Arrays2.print("Sorted array: ", a);
    while(true) {
      int r = gen.next();
      int location = Arrays.binarySearch(a, r);
      if(location >= 0) {
        System.out.println("Location of " + r + 
          " is " + location + ", a[" + 
          location + "] = " + a[location]);
        break; // Sortie de la boucle while
      }
    }
  }
} ///:~

Arrays.binarySearch() renvoie une valeur supérieure ou égale à zéro si l'item recherché est trouvé. Dans le cas contraire, elle renvoie une valeur négative représentant l'endroit où insérer l'élément si on désirait maintenir le tableau trié à la main. La valeur retournée est :

-(point d'insertion) – 1

Le point d'insertion est l'index du premier élément plus grand que la clef, ou a.size() si tous les éléments du tableau sont plus petits que la clef spécifiée.

Si le tableau contient des éléments dupliqués, aucune garantie n'est apportée quant à celui qui sera trouvé. L'algorithme n'est donc pas conçu pour les tableaux comportant des doublons, bien qu'il les tolère. Dans le cas où on a besoin d'une liste triée d'éléments sans doublons, mieux vaut se tourner vers un TreeSet (qui sera introduit plus loin dans ce chapitre) qui gère tous ces détails automatiquement, plutôt que de maintenir un tableau à la main (à moins que des questions de performance ne se greffent là-dessus).

Il faut fournir à binarySearch() le même objet Comparator que celui utilisé pour trier le tableau d'objets (les tableaux de scalaires n'autorisent pas les tris avec des Comparator), afin qu'elle utilise la version redéfinie de la fonction de comparaison. Ainsi, le programme AlphabeticSorting.java peut être modifié pour effectuer une recherche :

//: c09:AlphabeticSearch.java
// Rechercher avec un Comparator.
import com.bruceeckel.util.*;
import java.util.*;

public class AlphabeticSearch {
  public static void main(String[] args) {
    String[] sa = new String[30];
    Arrays2.fill(sa,
      new Arrays2.RandStringGenerator(5));
    AlphabeticComparator comp =      new AlphabeticComparator();
    Arrays.sort(sa, comp);
    int index =      Arrays.binarySearch(sa, sa[10], comp);
    System.out.println("Index = " + index);
  }
} ///:~

binarySearch() accepte le Comparator en troisième argument. Dans l'exemple précédent, le succès de la recherche est garanti puisque l'item recherché est tiré du tableau lui-même.

Pour résumer ce qu'on a vu jusqu'à présent, un tableau se révèle la manière la plus simple et la plus efficace pour stocker un groupe d'objets, et le seul choix possible dans le cas où on veut stocker un ensemble de scalaires. Dans le reste de ce chapitre, nous allons étudier le cas plus général dans lequel on ne sait pas au moment de l'écriture du programme combien d'objets seront requis, ainsi que des moyens plus sophistiqués de stocker les objets. Java propose en effet des classes conteneurs qui adressent différents problèmes. Les types de base en sont les Lists, les Sets et les Maps. Un nombre surprenant de problèmes peuvent être facilement résolus grâce à ces outils.

Entre autres caractéristiques - les Sets, par exemple, ne stockent qu'un objet de chaque valeur, les Maps sont des tableaux associatifs qui permettent d'associer n'importe quel objet avec n'importe quel autre objet - les classes conteneurs de Java se redimensionnent automatiquement. À l'inverse des tableaux, ils peuvent donc stocker un nombre quelconque d'objets et on n'a pas besoin de se soucier de leur taille lors de l'écriture du programme.

À l'inverse des tableaux, les conteneurs s'affichent correctement sans aide. Voici un exemple qui introduit en même temps les conteneurs de base :

//: c09:PrintingContainers.java
// Les conteneurs savent comment s'afficher.
import java.util.*;

public class PrintingContainers {
  static Collection fill(Collection c) {
    c.add("dog");
    c.add("dog");
    c.add("cat");
    return c;
  }
  static Map fill(Map m) {
    m.put("dog", "Bosco");
    m.put("dog", "Spot");
    m.put("cat", "Rags");
    return m;
  }
  public static void main(String[] args) {
    System.out.println(fill(new ArrayList()));
    System.out.println(fill(new HashSet()));
    System.out.println(fill(new HashMap()));
  }
} ///:~

Comme mentionné précédemment, il existe deux catégories de base dans la bibliothèque de conteneurs Java. La distinction est basée sur le nombre d'items stockés dans chaque cellule du conteneur. La catégorie Collection ne stocke qu'un item dans chaque emplacement (le nom est un peu trompeur puisque les bibliothèques des conteneurs sont souvent appelées des « collections »). Elle inclut la List, qui stocke un groupe d'items dans un ordre spécifique, et le Set, qui autorise l'addition d'une seule instance pour chaque item. Une ArrayList est un type de List, et HashSet est un type de Set. La méthode add() permet d'ajouter des éléments dans une Collection.

Une Map contient des paires clef - valeur, un peu à la manière d'une mini base de données. Le programme précédent utilise un type de Map, le HashMap. Si on dispose d'une Map qui associe les états des USA avec leur capitale et qu'on souhaite connaître la capitale de l'Ohio, il suffit de la rechercher - comme si on indexait un tableau (les Maps sont aussi appelés des tableaux associatifs). La méthode put(), qui accepte deux arguments - la clef et la valeur -, permet de stocker des éléments dans une Map. L'exemple précédent se contente d'ajouter des éléments, mais ne les récupère pas une fois stockés. Ceci sera illustré plus tard.

Les méthodes surchargées fill() remplissent respectivement des Collections et des Maps. En examinant la sortie produite par le programme, on peut voir que le comportement par défaut pour l'affichage (fourni par les méthodes toString() des différents conteneurs) produit un résultat relativement clair, il n'est donc pas nécessaire d'ajouter du code pour imprimer les conteneurs comme nous avons dû le faire avec les tableaux :

[dog, dog, cat]
[cat, dog]
{cat=Rags, dog=Spot}

Une Collection est imprimée entre crochets, chaque élément étant séparé par une virgule. Une Map est entourée par des accolades, chaque clef étant associée à sa valeur avec un signe égal (les clefs à gauche, les valeurs à droite).

Le comportement de base des différents conteneurs est évident dans cet exemple. La List stocke les objets dans l'ordre exact où ils ont été ajoutés, sans aucun réarrangement ni édition. Le Set, lui, n'accepte qu'une seule instance d'un objet et utilise une méthode interne de tri (en général, un Set sert à savoir si un élément est un membre d'un Set ou non, et non l'ordre dans lequel il apparaît dans ce Set - pour cela il faut utiliser une List). La Map elle aussi n'accepte qu'une seule instance d'un objet pour la clef, possède elle aussi sa propre organisation interne et ne tient pas compte de l'ordre dans lequel les éléments ont été insérés.

Bien que le problème d'impression des conteneurs soit géré pour nous, le remplissage des conteneurs souffre des mêmes limitations que java.util.Arrays. De même que pour les Arrays, il existe une classe compagnon appelée Collections contenant des méthodes static dont l'une s'appelle fill(). Cette méthode fill() ne fait que dupliquer une unique référence sur un objet dans le conteneur, et ne fonctionne que sur les objets List, pas sur les Sets ni les Maps :

//: c09:FillingLists.java
// La méthode Collections.fill().
import java.util.*;

public class FillingLists {
  public static void main(String[] args) {
    List list = new ArrayList();
    for(int i = 0; i < 10; i++)
      list.add("");
    Collections.fill(list, "Hello");
    System.out.println(list);
  }
} ///:~

Cette méthode est encore moins intéressante parce qu'elle ne fait que remplacer les éléments déjà présents dans la List, sans ajouter aucun élément.

Pour être capable de créer des exemples intéressants, voici une bibliothèque complémentaire Collections2 (appartenant par commodité à com.bruceeckel.util) disposant d'une méthode fill() utilisant un générateur pour ajouter des éléments, et permettant de spécifier le nombre d'éléments qu'on souhaite ajouter. L'interface Generator définie précédemment fonctionne pour les Collections, mais les Maps requièrent leur propre interface génératrice puisqu'un appel à next() doit produire une paire d'objets (une clef et une valeur). Voici tout d'abord la classe Pair :

//: com:bruceeckel:util:Pair.java
package com.bruceeckel.util;
public class Pair {
  public Object key, value;
  Pair(Object k, Object v) {
    key = k;
    value = v;
  }
} ///:~

Ensuite, l'interface génératrice qui produit un objet Pair :

//: com:bruceeckel:util:MapGenerator.java
package com.bruceeckel.util;
public interface MapGenerator {
  Pair next();
} ///:~

Avec ces deux objets, un ensemble d'utilitaires pour travailler avec les classes conteneurs peuvent être développés :

//: com:bruceeckel:util:Collections2.java
// Remplir n'importe quel type de conteneur en
// utilisant un objet générateur.
package com.bruceeckel.util;
import java.util.*;

public class Collections2 {
  // Remplit une Collection en utilisant un générateur :
  public static void 
  fill(Collection c, Generator gen, int count) {
    for(int i = 0; i < count; i++)
      c.add(gen.next());
  }
  public static void 
  fill(Map m, MapGenerator gen, int count) {
    for(int i = 0; i < count; i++) {
      Pair p = gen.next();
      m.put(p.key, p.value);
    }
  }
  public static class RandStringPairGenerator
  implements MapGenerator {
    private Arrays2.RandStringGenerator gen;
    public RandStringPairGenerator(int len) {
      gen = new Arrays2.RandStringGenerator(len);
    }
    public Pair next() {
      return new Pair(gen.next(), gen.next());
    }
  }
  // Objet par défaut afin de ne pas avoir
  // à en créer un de notre cru :
  public static RandStringPairGenerator rsp =    new RandStringPairGenerator(10);
  public static class StringPairGenerator
  implements MapGenerator {
    private int index = -1;
    private String[][] d;
    public StringPairGenerator(String[][] data) {
      d = data;
    }
    public Pair next() {
      // Force l'index dans la plage de valeurs :
      index = (index + 1) % d.length;
      return new Pair(d[index][0], d[index][1]);
    }
    public StringPairGenerator reset() { 
      index = -1; 
      return this;
    }
  }
  // Utilisation d'un ensemble de données prédéfinies :
  public static StringPairGenerator geography =    new StringPairGenerator(
      CountryCapitals.pairs);
  // Produit une séquence à partir d'un tableau 2D :
  public static class StringGenerator
  implements Generator {
    private String[][] d;
    private int position;
    private int index = -1;
    public 
    StringGenerator(String[][] data, int pos) {
      d = data;
      position = pos;
    }
    public Object next() {
      // Force l'index dans la plage de valeurs :
      index = (index + 1) % d.length;
      return d[index][position];
    }
    public StringGenerator reset() { 
      index = -1;
      return this;
    }
  }
  // Utilisation d'un ensemble de données prédéfinies :
  public static StringGenerator countries =    new StringGenerator(CountryCapitals.pairs,0);
  public static StringGenerator capitals =    new StringGenerator(CountryCapitals.pairs,1);
} ///:~

Voici l'ensemble de données prédéfinies, qui consiste en noms de pays avec leur capitale. Il est affiché avec une petite fonte afin de réduire l'espace occupé :

//: com:bruceeckel:util:CountryCapitals.java
package com.bruceeckel.util;
public class CountryCapitals {
  public static final String[][] pairs = {
    // Afrique
    {"ALGERIA","Algiers"}, {"ANGOLA","Luanda"},
    {"BENIN","Porto-Novo"}, {"BOTSWANA","Gaberone"},
    {"BURKINA FASO","Ouagadougou"}, {"BURUNDI","Bujumbura"},
    {"CAMEROON","Yaounde"}, {"CAPE VERDE","Praia"},
    {"CENTRAL AFRICAN REPUBLIC","Bangui"},
    {"CHAD","N'djamena"},  {"COMOROS","Moroni"},
    {"CONGO","Brazzaville"}, {"DJIBOUTI","Dijibouti"},
    {"EGYPT","Cairo"}, {"EQUATORIAL GUINEA","Malabo"},
    {"ERITREA","Asmara"}, {"ETHIOPIA","Addis Ababa"},
    {"GABON","Libreville"}, {"THE GAMBIA","Banjul"},
    {"GHANA","Accra"}, {"GUINEA","Conakry"},
    {"GUINEA","-"}, {"BISSAU","Bissau"},
    {"CETE D'IVOIR (IVORY COAST)","Yamoussoukro"},
    {"KENYA","Nairobi"}, {"LESOTHO","Maseru"},
    {"LIBERIA","Monrovia"}, {"LIBYA","Tripoli"},
    {"MADAGASCAR","Antananarivo"}, {"MALAWI","Lilongwe"},
    {"MALI","Bamako"}, {"MAURITANIA","Nouakchott"},
    {"MAURITIUS","Port Louis"}, {"MOROCCO","Rabat"},
    {"MOZAMBIQUE","Maputo"}, {"NAMIBIA","Windhoek"},
    {"NIGER","Niamey"}, {"NIGERIA","Abuja"},
    {"RWANDA","Kigali"}, {"SAO TOME E PRINCIPE","Sao Tome"},
    {"SENEGAL","Dakar"}, {"SEYCHELLES","Victoria"},
    {"SIERRA LEONE","Freetown"}, {"SOMALIA","Mogadishu"},
    {"SOUTH AFRICA","Pretoria/Cape Town"}, {"SUDAN","Khartoum"},
    {"SWAZILAND","Mbabane"}, {"TANZANIA","Dodoma"},
    {"TOGO","Lome"}, {"TUNISIA","Tunis"},
    {"UGANDA","Kampala"},
    {"DEMOCRATIC REPUBLIC OF THE CONGO (ZAIRE)","Kinshasa"},
    {"ZAMBIA","Lusaka"}, {"ZIMBABWE","Harare"},
    // Asie
    {"AFGHANISTAN","Kabul"}, {"BAHRAIN","Manama"},
    {"BANGLADESH","Dhaka"}, {"BHUTAN","Thimphu"},
    {"BRUNEI","Bandar Seri Begawan"}, {"CAMBODIA","Phnom Penh"},
    {"CHINA","Beijing"}, {"CYPRUS","Nicosia"},
    {"INDIA","New Delhi"}, {"INDONESIA","Jakarta"},
    {"IRAN","Tehran"}, {"IRAQ","Baghdad"},
    {"ISRAEL","Jerusalem"}, {"JAPAN","Tokyo"},
    {"JORDAN","Amman"}, {"KUWAIT","Kuwait City"},
    {"LAOS","Vientiane"}, {"LEBANON","Beirut"},
    {"MALAYSIA","Kuala Lumpur"}, {"THE MALDIVES","Male"},
    {"MONGOLIA","Ulan Bator"}, {"MYANMAR (BURMA)","Rangoon"},
    {"NEPAL","Katmandu"}, {"NORTH KOREA","P'yongyang"},
    {"OMAN","Muscat"}, {"PAKISTAN","Islamabad"},
    {"PHILIPPINES","Manila"}, {"QATAR","Doha"},
    {"SAUDI ARABIA","Riyadh"}, {"SINGAPORE","Singapore"},
    {"SOUTH KOREA","Seoul"}, {"SRI LANKA","Colombo"},
    {"SYRIA","Damascus"}, {"TAIWAN (REPUBLIC OF CHINA)","Taipei"},
    {"THAILAND","Bangkok"}, {"TURKEY","Ankara"},
    {"UNITED ARAB EMIRATES","Abu Dhabi"}, {"VIETNAM","Hanoi"},
    {"YEMEN","Sana'a"},
    // Australie et Océanie
    {"AUSTRALIA","Canberra"}, {"FIJI","Suva"},
    {"KIRIBATI","Bairiki"},
    {"MARSHALL ISLANDS","Dalap-Uliga-Darrit"},
    {"MICRONESIA","Palikir"}, {"NAURU","Yaren"},
    {"NEW ZEALAND","Wellington"}, {"PALAU","Koror"},
    {"PAPUA NEW GUINEA","Port Moresby"},
    {"SOLOMON ISLANDS","Honaira"}, {"TONGA","Nuku'alofa"},
    {"TUVALU","Fongafale"}, {"VANUATU","< Port-Vila"},
    {"WESTERN SAMOA","Apia"},
    // Europe de l'Est et ancienne URSS
    {"ARMENIA","Yerevan"}, {"AZERBAIJAN","Baku"},
    {"BELARUS (BYELORUSSIA)","Minsk"}, {"GEORGIA","Tbilisi"},
    {"KAZAKSTAN","Almaty"}, {"KYRGYZSTAN","Alma-Ata"},
    {"MOLDOVA","Chisinau"}, {"RUSSIA","Moscow"},
    {"TAJIKISTAN","Dushanbe"}, {"TURKMENISTAN","Ashkabad"},
    {"UKRAINE","Kyiv"}, {"UZBEKISTAN","Tashkent"},
    // Europe 
    {"ALBANIA","Tirana"}, {"ANDORRA","Andorra la Vella"},
    {"AUSTRIA","Vienna"}, {"BELGIUM","Brussels"},
    {"BOSNIA","-"}, {"HERZEGOVINA","Sarajevo"},
    {"CROATIA","Zagreb"}, {"CZECH REPUBLIC","Prague"},
    {"DENMARK","Copenhagen"}, {"ESTONIA","Tallinn"},
    {"FINLAND","Helsinki"}, {"FRANCE","Paris"},
    {"GERMANY","Berlin"}, {"GREECE","Athens"},
    {"HUNGARY","Budapest"}, {"ICELAND","Reykjavik"},
    {"IRELAND","Dublin"}, {"ITALY","Rome"},
    {"LATVIA","Riga"}, {"LIECHTENSTEIN","Vaduz"},
    {"LITHUANIA","Vilnius"}, {"LUXEMBOURG","Luxembourg"},
    {"MACEDONIA","Skopje"}, {"MALTA","Valletta"},
    {"MONACO","Monaco"}, {"MONTENEGRO","Podgorica"},
    {"THE NETHERLANDS","Amsterdam"}, {"NORWAY","Oslo"},
    {"POLAND","Warsaw"}, {"PORTUGAL","Lisbon"},
    {"ROMANIA","Bucharest"}, {"SAN MARINO","San Marino"},
    {"SERBIA","Belgrade"}, {"SLOVAKIA","Bratislava"},
    {"SLOVENIA","Ljujiana"}, {"SPAIN","Madrid"},
    {"SWEDEN","Stockholm"}, {"SWITZERLAND","Berne"},
    {"UNITED KINGDOM","London"}, {"VATICAN CITY","---"},
    // Amérique du Nord et Amérique Centrale
    {"ANTIGUA AND BARBUDA","Saint John's"}, {"BAHAMAS","Nassau"},
    {"BARBADOS","Bridgetown"}, {"BELIZE","Belmopan"},
    {"CANADA","Ottawa"}, {"COSTA RICA","San Jose"},
    {"CUBA","Havana"}, {"DOMINICA","Roseau"},
    {"DOMINICAN REPUBLIC","Santo Domingo"},
    {"EL SALVADOR","San Salvador"}, {"GRENADA","Saint George's"},
    {"GUATEMALA","Guatemala City"}, {"HAITI","Port-au-Prince"},
    {"HONDURAS","Tegucigalpa"}, {"JAMAICA","Kingston"},
    {"MEXICO","Mexico City"}, {"NICARAGUA","Managua"},
    {"PANAMA","Panama City"}, {"ST. KITTS","-"},
    {"NEVIS","Basseterre"}, {"ST. LUCIA","Castries"},
    {"ST. VINCENT AND THE GRENADINES","Kingstown"},
    {"UNITED STATES OF AMERICA","Washington, D.C."},
    // Amérique du Sud
    {"ARGENTINA","Buenos Aires"},
    {"BOLIVIA","Sucre (legal)/La Paz(administrative)"},
    {"BRAZIL","Brasilia"}, {"CHILE","Santiago"},
    {"COLOMBIA","Bogota"}, {"ECUADOR","Quito"},
    {"GUYANA","Georgetown"}, {"PARAGUAY","Asuncion"},
    {"PERU","Lima"}, {"SURINAME","Paramaribo"},
    {"TRINIDAD AND TOBAGO","Port of Spain"},
    {"URUGUAY","Montevideo"}, {"VENEZUELA","Caracas"},
  };
} ///:~

Il s'agit juste d'un tableau bidimensionnel de String (41). Voici un simple test illustrant les méthodes fill() et les générateurs :

//: c09:FillTest.java
import com.bruceeckel.util.*;
import java.util.*;

public class FillTest {
  static Generator sg = 
    new Arrays2.RandStringGenerator(7);
  public static void main(String[] args) {
    List list = new ArrayList();
    Collections2.fill(list, sg, 25);
    System.out.println(list + "\n");
    List list2 = new ArrayList();
    Collections2.fill(list2, 
      Collections2.capitals, 25);
    System.out.println(list2 + "\n");
    Set set = new HashSet();
    Collections2.fill(set, sg, 25);
    System.out.println(set + "\n");
    Map m = new HashMap();
    Collections2.fill(m, Collections2.rsp, 25);
    System.out.println(m + "\n");
    Map m2 = new HashMap();
    Collections2.fill(m2, 
      Collections2.geography, 25);
    System.out.println(m2);
  }
} ///:~

Avec ces outils vous pourrez facilement tester les différents conteneurs en les remplissant avec des données intéressantes.

Dans certains cas les choses semblent fonctionner correctement sans avoir à transtyper vers le type originel. Un cas particulier est constitué par la classe String que le compilateur traite de manière particulière pour la faire fonctionner de manière idoine. Quand le compilateur attend un objet String et qu'il obtient autre chose, il appellera automatiquement la méthode toString() définie dans Object et qui peut être redéfinie par chaque classe Java. Cette méthode produit l'objet String désiré, qui est ensuite utilisé là où il était attendu.

Il suffit donc de redéfinir la méthode toString() pour afficher un objet d'une classe donnée, comme on peut le voir dans l'exemple suivant :

//: c09:Mouse.java
// Redéfinition de toString().
public class Mouse {
  private int mouseNumber;
  Mouse(int i) { mouseNumber = i; }
  // Redféinition de Object.toString():
  public String toString() {
    return "This is Mouse #" + mouseNumber;
  }
  public int getNumber() {
    return mouseNumber;
  }
} ///:~

//: c09:WorksAnyway.java
// Dans certains cas spéciaux, les choses
// semblent fonctionner correctement.
import java.util.*;

class MouseTrap {
  static void caughtYa(Object m) {
    Mouse mouse = (Mouse)m; // Transtypage depuis un Object
    System.out.println("Mouse: " + 
      mouse.getNumber());
  }
}

public class WorksAnyway {
  public static void main(String[] args) {
    ArrayList mice = new ArrayList();
    for(int i = 0; i < 3; i++)
      mice.add(new Mouse(i));
    for(int i = 0; i < mice.size(); i++) {
      // Aucun transtypage nécessaire, appel
      // automatique à Object.toString() :
      System.out.println(
        "Free mouse: " + mice.get(i));
      MouseTrap.caughtYa(mice.get(i));
    }
  }
} ///:~

La méthode toString() est redéfinie dans Mouse. Dans la deuxième boucle for de main() on peut voir l'instruction :

System.out.println("Free mouse: " + mice.get(i));

Après le signe « + » le compilateur s'attend à trouver un objet String. get() renvoie un Object, le compilateur appelle donc implicitement la méthode toString() pour obtenir l'objet String désiré. Cependant, ce comportement magique n'est possible qu'avec les String, il n'est pas disponible pour les autres types.

Une seconde approche pour cacher le transtypage est de le placer dans la classe MouseTrap. La méthode caughtYa() n'accepte pas une Mouse, mais un Object, qu'elle transtype alors en Mouse. Ceci ne fait que repousser le problème puisqu'en acceptant un Object on peut passer un objet de n'importe quel type à la méthode. Cependant, si le transtypage n'est pas valide - si un objet du mauvais type est passé en argument - une exception est générée lors de l'exécution. Ce n'est pas aussi bien qu'un contrôle lors de la compilation, mais l'approche reste robuste. Notez qu'aucun transtypage n'est nécessaire lors de l'utilisation de cette méthode :

MouseTrap.caughtYa(mice.get(i));

Pas question toutefois de s'arrêter en si bon chemin. Une solution encore plus robuste consiste à créer une nouvelle classe utilisant une ArrayList, n'acceptant et ne produisant que des objets du type voulu :

//: c09:MouseList.java
// Une ArrayList consciente du type.
import java.util.*;

public class MouseList {
  private ArrayList list = new ArrayList();
  public void add(Mouse m) {
    list.add(m);
  }
  public Mouse get(int index) {
    return (Mouse)list.get(index);
  }
  public int size() { return list.size(); }
} ///:~

Voici un test pour le nouveau conteneur :

//: c09:MouseListTest.java
public class MouseListTest {
  public static void main(String[] args) {
    MouseList mice = new MouseList();
    for(int i = 0; i < 3; i++)
      mice.add(new Mouse(i));
    for(int i = 0; i < mice.size(); i++)
      MouseTrap.caughtYa(mice.get(i));
  }
} ///:~

Cet exemple est similaire au précédent, sauf que la nouvelle classe MouseList dispose d'un membre private de type ArrayList, et de méthodes identiques à celles fournies par ArrayList. Cependant, ces méthodes n'acceptent et ne produisent pas des Objects génériques, mais seulement des objets Mouse.

Notez que si MouseList avait été dérivée de ArrayList, la méthode add(Mouse) aurait simplement surchargé la méthode existante add(Object) et aucune restriction sur le type d'objets acceptés n'aurait donc été ajoutée. La MouseList est donc un substitut à l'ArrayList, réalisant certaines opérations avant de déléguer la responsabilité (cf. Thinking in Patterns with Java, téléchargeable sur www.BruceEckel.com).

Du fait qu'une MouseList n'accepte qu'une Mouse, l'instruction suivante :

mice.add(new Pigeon());

provoque un message d'erreur durant la phase de compilation. Cette approche, bien que plus fastidieuse du point de vue du code, signalera immédiatement si on utilise un type de façon incorrecte.

Notez aussi qu'aucun transtypage n'est nécessaire lors d'un appel à get() - elle renvoie toujours une Mouse.

XI-C-2-a. Types paramétrés▲

XI-C-2-b. Récursion indésirable▲

//: c09:InfiniteRecursion.java
// Récursion accidentelle.
import java.util.*;

public class InfiniteRecursion {
  public String toString() {
    return " InfiniteRecursion address: " 
      + this + "\n";
  }
  public static void main(String[] args) {
    ArrayList v = new ArrayList();
    for(int i = 0; i < 10; i++)
      v.add(new InfiniteRecursion());
    System.out.println(v);
  }
} ///:~

"InfiniteRecursion address: " + this

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).

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.

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.

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

Comparator comparator() : renvoie le Comparator utilisé pour cette Map, ou null dans le cas d'un tri naturel ;

Object firstKey() : renvoie la plus petite clef ;

Object lastKey() : renvoie la plus grande clef ;

SortedMap subMap(fromKey, toKey) : renvoie une vue de la Map contenant les paires dont les clefs vont de fromKey inclus à toKey exclu ;

SortedMap headMap(toKey) : renvoie une vue de la Map contenant les paires dont la clef est inférieure à toKey ;

SortedMap tailMap(fromKey) : renvoie une vue de la Map contenant les paires dont la clef est supérieure ou égale à fromKey.

Dans l'exemple précédent, une classe de la bibliothèque standard (Integer) était utilisée comme clef pour le HashMap. Cela ne pose pas de problèmes, car elle dispose de tout ce qu'il faut pour fonctionner correctement comme une clef. Mais il existe un point d'achoppement classique avec les HashMaps lorsqu'on crée une classe destinée à être utilisée comme clef. Considérons par exemple un système de prévision météorologique qui associe des objets Groundhog à des objets Prediction. Cela semble relativement simple : il suffit de créer deux classes, et d'utiliser Groundhog comme clef et Prediction comme valeur :

//: c09:SpringDetector.java
// Semble plausible, mais ne fonctionne pas.
import java.util.*;

class Groundhog {
  int ghNumber;
  Groundhog(int n) { ghNumber = n; }
}

class Prediction {
  boolean shadow = Math.random() > 0.5;
  public String toString() {
    if(shadow)
      return "Six more weeks of Winter!";
    else
      return "Early Spring!";
  }
}

public class SpringDetector {
  public static void main(String[] args) {
    HashMap hm = new HashMap();
    for(int i = 0; i < 10; i++)
      hm.put(new Groundhog(i), new Prediction());
    System.out.println("hm = " + hm + "\n");
    System.out.println(
      "Looking up prediction for Groundhog #3:");
    Groundhog gh = new Groundhog(3);
    if(hm.containsKey(gh))
      System.out.println((Prediction)hm.get(gh));
    else
      System.out.println("Key not found: " + gh);
  }
} ///:~

Chaque Groundhog se voit attribuer un numéro d'identité, afin de pouvoir récupérer une Prediction dans le HashMap en disant « Donne-moi la Prediction associée au Groundhog numéro 3 ». La classe Prediction contient un boolean initialisé en utilisant Math.random(), et une méthode toString() pour en interpréter la valeur. Dans main(), un HashMap est rempli avec des Groundhogs et leurs Predictions associées. Le HashMap est affiché afin de voir qu'il a été correctement rempli. Un Groundhog avec une identité de 3 est alors utilisé comme clef pour extraire la prédiction du Groundhog numéro 3 (qui doit être dans le HashMap).

Tout ceci semble très simple, mais ne marche pas. Le problème vient du fait que Groundhog hérite de la classe de base Object (ce qui est le comportement par défaut si aucune superclasse n'est précisée ; toutes les classes dérivent donc en fin de compte de la classe Object). C'est donc la méthode hashCode() de Object qui est utilisée pour générer le code de hachage pour chaque objet, et par défaut, celle-ci renvoie juste l'adresse de cet objet. La première instance de Groundhog(3) ne renvoie donc pas le même code de hachage que celui de la seconde instance de Groundhog(3) que nous avons tenté d'utiliser comme clef d'extraction.

On pourrait penser qu'il suffit de redéfinir hashCode(). Mais ceci ne fonctionnera toujours pas tant qu'on n'aura pas aussi redéfini la méthode equals() qui fait aussi partie de la classe Object. Cette méthode est utilisée par le HashMap lorsqu'il essaie de déterminer si la clef est égale à l'une des autres clefs de la table. Et la méthode par défaut Object.equals() compare simplement les adresses des objets, ce qui fait qu'un objet Groundhog(3) est différent d'un autre Groundhog(3).

Pour utiliser un nouveau type comme clef dans un HashMap, il faut donc redéfinir les deux méthodes hashCode() et equals(), comme le montre la solution suivante :

//: c09:SpringDetector2.java
// Une classe utilisée comme clef dans un HashMap 
// doit redéfinir hashCode() et equals().
import java.util.*;

class Groundhog2 {
  int ghNumber;
  Groundhog2(int n) { ghNumber = n; }
  public int hashCode() { return ghNumber; }
  public boolean equals(Object o) {
    return (o instanceof Groundhog2)
      && (ghNumber == ((Groundhog2)o).ghNumber);
  }
}

public class SpringDetector2 {
  public static void main(String[] args) {
    HashMap hm = new HashMap();
    for(int i = 0; i < 10; i++)
      hm.put(new Groundhog2(i),new Prediction());
    System.out.println("hm = " + hm + "\n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog2 gh = new Groundhog2(3);
    if(hm.containsKey(gh))
      System.out.println((Prediction)hm.get(gh));
  }
} ///:~

Notez que cet exemple utilise la classe Prediction de l'exemple précédent, donc SpringDetector.java doit déjà avoir été compilé ou vous aurez une erreur lorsque vous tenterez de compiler SpringDetector2.java.

Groundhog2.hashCode() renvoie le numéro de marmotte comme identifiant. Dans cet exemple, le programmeur doit s'assurer que deux marmottes ne portent pas le même identifiant. La méthode hashCode() n'est pas obligée de renvoyer un identifiant unique (vous comprendrez mieux ceci plus tard dans ce chapitre), mais la méthode equals() doit être capable de déterminer si deux objets sont strictement équivalents.

Bien que la méthode equals() semble ne vérifier que si l'argument est bien une instance de Groundhog2 (en utilisant le mot-clef instanceof, expliqué plus en détail dans le titre XIV), instanceof effectue en fait implicitement un deuxième contrôle puisqu'il renvoie false si l'argument de gauche est null. En supposant que le contrôle de type s'est bien passé, la comparaison est basée sur les ghNumbers des instances. Et cette fois, lorsqu'on lance le programme, on peut voir qu'il produit le résultat attendu.

On rencontre les mêmes problèmes quand on crée un nouveau type destiné à être stocké dans un HashSet ou utilisé comme clef dans un HashMap.

XI-I-2-a. Comprendre hashCode()▲

//: c09:MPair.java
// Une Map implémentée avec des ArrayLists.
import java.util.*;

public class MPair 
implements Map.Entry, Comparable {
  Object key, value;
  MPair(Object k, Object v) {
    key = k;
    value = v;
  }
  public Object getKey() { return key; }
  public Object getValue() { return value; }
  public Object setValue(Object v){
    Object result = value;
    value = v;
    return result;
  }
  public boolean equals(Object o) {
    return key.equals(((MPair)o).key);
  }
  public int compareTo(Object rv) {
    return ((Comparable)key).compareTo(
      ((MPair)rv).key);
  }
} ///:~

//: c09:SlowMap.java
// Une Map implémentée avec des ArrayLists.
import java.util.*;
import com.bruceeckel.util.*;

public class SlowMap extends AbstractMap {
  private ArrayList 
    keys = new ArrayList(),
    values = new ArrayList();
  public Object put(Object key, Object value) {
    Object result = get(key);
    if(!keys.contains(key)) {
      keys.add(key);
      values.add(value);
    } else
      values.set(keys.indexOf(key), value);
    return result;
  }
  public Object get(Object key) {
    if(!keys.contains(key))
      return null;
    return values.get(keys.indexOf(key));
  }
  public Set entrySet() {
    Set entries = new HashSet();
    Iterator
      ki = keys.iterator(),
      vi = values.iterator();
    while(ki.hasNext())
      entries.add(new MPair(ki.next(), vi.next()));
    return entries;
  }
  public static void main(String[] args) {
    SlowMap m = new SlowMap();
    Collections2.fill(m, 
      Collections2.geography, 25);
    System.out.println(m);    
  }
} ///:~

//: c09:SimpleHashMap.java
// Démonstration d'une Map hachée.
import java.util.*;
import com.bruceeckel.util.*;

public class SimpleHashMap extends AbstractMap {
  // Choisir un nombre premier pour la taille de la table
  // de hachage, afin d'obtenir une distribution uniforme :
  private final static int SZ = 997;
  private LinkedList[] bucket= new LinkedList[SZ];
  public Object put(Object key, Object value) {
    Object result = null;
    int index = key.hashCode() % SZ;
    if(index < 0) index = -index;
    if(bucket[index] == null)
      bucket[index] = new LinkedList();
    LinkedList pairs = bucket[index];
    MPair pair = new MPair(key, value);
    ListIterator it = pairs.listIterator();
    boolean found = false;
    while(it.hasNext()) {
      Object iPair = it.next();
      if(iPair.equals(pair)) {
        result = ((MPair)iPair).getValue();
        it.set(pair); // Remplace l'ancien par le nouveau
        found = true;
        break;
      }
    }
    if(!found)
      bucket[index].add(pair);
    return result;
  }
  public Object get(Object key) {
    int index = key.hashCode() % SZ;
    if(index < 0) index = -index;
    if(bucket[index] == null) return null;
    LinkedList pairs = bucket[index];
    MPair match = new MPair(key, null);
    ListIterator it = pairs.listIterator();
    while(it.hasNext()) {
      Object iPair = it.next();
      if(iPair.equals(match))
        return ((MPair)iPair).getValue();
    }
    return null;
  }
  public Set entrySet() {
    Set entries = new HashSet();
    for(int i = 0; i < bucket.length; i++) {
      if(bucket[i] == null) continue;
      Iterator it = bucket[i].iterator();
      while(it.hasNext())
        entries.add(it.next());
    }
    return entries;
  }
  public static void main(String[] args) {
    SimpleHashMap m = new SimpleHashMap();
    Collections2.fill(m, 
      Collections2.geography, 25);
    System.out.println(m);    
  }
} ///:~

Maintenant que nous avons vu les processus impliqués dans le fonctionnement d'un HashMap, les problèmes rencontrés dans l'écriture d'une méthode hashCode() prennent tout leur sens.

Tout d'abord, on ne contrôle pas la valeur réellement utilisée pour indexer le seau dans le tableau. Celle-ci est dépendante de la capacité de l'objet HashMap, et cette capacité change suivant la taille et la charge du conteneur. La valeur renvoyée par la méthode hashCode() est simplement utilisée pour calculer l'index du seau (dans SimpleHashMap le calcul se résume à un modulo de la taille du tableau de seaux).

Le facteur le plus important lors de la création d'une méthode hashCode() est qu'elle doit toujours renvoyer la même valeur pour un objet particulier, quel que soit le moment où hashCode() est appelée. Si on a un objet dont la méthode hashCode() renvoie une valeur lors d'un put() dans un HashMap, et une autre durant un appel à get(), on sera incapable de retrouver cet objet. Si la méthode hashCode() s'appuie sur des données modifiables dans l'objet, l'utilisateur doit alors être prévenu que changer ces données produira une clef différente en générant un code de hachage différent.

De plus, on ne veut pas non plus générer un code de hachage qui soit basé uniquement sur des informations uniques spécifiques à l'instance de l'objet - en particulier, la valeur de this est une mauvaise idée pour un code de hachage, puisqu'on ne peut générer une nouvelle clef identique à celle utilisée pour stocker la paire originale clef-valeur. C'est le problème que nous avons rencontré dans SpringDetector.java parce que l'implémentation par défaut de hashCode() utilise l'adresse de l'objet. Il faut donc utiliser des informations de l'objet qui identifient l'objet d'une façon sensée.

Un exemple en est trouvé dans la classe String. Les Strings ont cette caractéristique spéciale : si un programme utilise plusieurs objets String contenant la même séquence de caractères, alors ces objets String pointent tous vers la même zone de mémoire (ce mécanisme est décrit dans l'annexe A). Il semble donc sensé que le code de hachage produit par deux instances distinctes de new String("hello") soit identique. On peut le vérifier avec ce petit programme :

//: c09:StringHashCode.java
public class StringHashCode {
  public static void main(String[] args) {
    System.out.println("Hello".hashCode());
    System.out.println("Hello".hashCode());
  }
} ///:~

Pour que ceci fonctionne, le code de hachage de String doit être basé sur le contenu de la String.

Pour qu'un code de hachage soit efficace, il faut donc qu'il soit rapide et chargé de sens : c'est donc une valeur basée sur le contenu de l'objet. Rappelons que cette valeur n'a pas à être unique - mieux vaut se pencher sur la vitesse que sur l'unicité -, mais l'identité d'un objet doit être complètement résolue entre hashCode() et equals().

Parce qu'un code de hachage est traité avant de produire un index de seau, la plage de valeurs n'est pas importante ; il suffit de générer un int.

Enfin, il existe un autre facteur : une méthode hashCode() bien conçue doit renvoyer des valeurs bien distribuées. Si les valeurs tendent à se regrouper, alors les HashMaps et les HashSets seront plus chargés dans certaines parties et donc moins rapides que ce qu'ils pourraient être avec une fonction de hachage mieux répartie.

Voici un exemple qui respecte ces règles de base :

//: c09:CountedString.java
// Créer une bonne méthode hashCode().
import java.util.*;

public class CountedString {
  private String s;
  private int id = 0;
  private static ArrayList created = 
    new ArrayList();
  public CountedString(String str) {
    s = str;
    created.add(s);
    Iterator it = created.iterator();
    // id est le nombre total d'instances de cette
    // chaîne utilisées par CountedString :
    while(it.hasNext())
      if(it.next().equals(s))
        id++;
  }
  public String toString() {
    return "String: " + s + " id: " + id +
      " hashCode(): " + hashCode() + "\n";
  }
  public int hashCode() { 
    return s.hashCode() * id;
  }
  public boolean equals(Object o) {
    return (o instanceof CountedString)
      && s.equals(((CountedString)o).s)
      && id == ((CountedString)o).id;
  }
  public static void main(String[] args) {
    HashMap m = new HashMap();
    CountedString[] cs = new CountedString[10];
    for(int i = 0; i < cs.length; i++) {
      cs[i] = new CountedString("hi");
      m.put(cs[i], new Integer(i));
    }
    System.out.println(m);
    for(int i = 0; i < cs.length; i++) {
      System.out.print("Looking up " + cs[i]);
      System.out.println(m.get(cs[i]));
    }
  }
} ///:~

CountedString inclut une String et un id représentant le nombre d'objets CountedString contenant une String identique. Le compte est réalisé dans le constructeur en parcourant la static ArrayList où toutes les Strings sont stockées.

Les méthodes hashCode() et equals() renvoient des résultats basés sur les deux champs ; si elles étaient basées juste sur la String ou sur l'id, il y aurait eu des doublons pour des valeurs distinctes.

Notez comme la fonction de hachage est simple : le code de hachage de la String multiplié par l'id. Généralement, la qualité et la rapidité d'une fonction de hachage est inversement proportionnelle à sa taille.

Dans main(), un ensemble d'objets CountedString est créé, en utilisant la même String pour montrer que les  doublons créent des valeurs uniques grâce au compteur id. Le HashMap est affiché afin de voir son organisation interne (aucun ordre n'est discernable) ; chaque clef est alors recherchée individuellement pour démontrer que le mécanisme de recherche fonctionne correctement.

La bibliothèque de conteneurs propose une Map spéciale pour stocker les références faibles : le WeakHashMap. Cette classe est conçue pour faciliter la création de mappages canoniques. Dans de tels mappages, on économise sur le stockage en ne créant qu'une instance d'une valeur particulière. Quand le programme a besoin de cette valeur, il recherche l'objet existant dans le mappage et l'utilise (plutôt que d'en créer un complètement nouveau). Le mappage peut créer les valeurs comme partie de son initialisation, mais il est plus courant que les valeurs soient créées à la demande.

Puisqu'il s'agit d'une technique permettant d'économiser sur le stockage, il est très pratique que le WeakHashMap autorise le ramasse-miettes à nettoyer automatiquement les clefs et les valeurs. Aucune opération particulière n'est nécessitée sur les clefs et les valeurs qu'on veut placer dans le WeakHashMap ; ils sont automatiquement encapsulés dans des WeakReferences par le WeakHashMap. Le déclenchement qui autorise le nettoyage survient lorsque la clef n'est plus utilisée, ainsi que démontré dans cet exemple :

//: c09:CanonicalMapping.java
// Illustre les WeakHashMaps.
import java.util.*;
import java.lang.ref.*;

class Key {
  String ident;
  public Key(String id) { ident = id; }
  public String toString() { return ident; }
  public int hashCode() { 
    return ident.hashCode();
  }
  public boolean equals(Object r) {
    return (r instanceof Key)
      && ident.equals(((Key)r).ident);
  }
  public void finalize() {
    System.out.println("Finalizing Key "+ ident);
  }
}

class Value {
  String ident;
  public Value(String id) { ident = id; }
  public String toString() { return ident; }
  public void finalize() {
    System.out.println("Finalizing Value "+ident);
  }
}

public class CanonicalMapping {
  public static void main(String[] args) {
    int size = 1000;
    // La taille peut être choisie via la ligne de commande :
    if(args.length > 0)
      size = Integer.parseInt(args[0]);    
    Key[] keys = new Key[size];
    WeakHashMap whm = new WeakHashMap();
    for(int i = 0; i < size; i++) {
      Key k = new Key(Integer.toString(i));
      Value v = new Value(Integer.toString(i));
      if(i % 3 == 0)
        keys[i] = k; // Save as "real" references
      whm.put(k, v);
    }
    System.gc();
  }
} ///:~