Collections en Java : notions intermédiaires

Lorsqu'on accède à un élément d'une collection sous Java 1.4, il est nécessaire de caster l'objet. Si l'on veut accéder à un String par exemple, il faut faire :

String s=(String)maCollection.get(i);

Les Generics permettent d'éviter ce cast en précisant à la création de la collection son type. Par exemple :

List<String> monArrayList = new ArrayList <String> (); // création d'un ArrayList qui contient des Integer
HashMap <String,Float> monHashMap = new HashMap(); // création d'un HashMap dont les clés sont des String et les valeurs sont des Float

Le cast disparaît. La lisibilité en est améliorée, tout comme le temps de maintenance ou la sécurité du code : un ArrayList<Integer> n'acceptera pas de compiler si vous essayez de lui ajouter un String par exemple.

Nous avons vu plus haut l'intérêt de l'Auto(Un)Boxing avec les collections, notamment lors de l'ajout. Cela posait problème dans le cas de la récupération.
En effet, une collection renvoie un Object. Si j'essaie de stocker un Object (qui en fait est un Integer) dans un type primitif int comme dans cet exemple :

List monArrayList=new ArrayList();
monArrayList.add(1);
int n=monArrayList.get(0);

Une erreur est générée à la compilation : incompatible types, et c'est plutôt logique. L'autoUnboxing va nous permettre de passer du type Integer au type int. Dans le cas des collections, les Generics nous servent de « casteur » pour passer de Object vers Integer. Avant, il aurait fallu faire :

List monArrayList=new ArrayList();
monArrayList.add(new Integer(1));
int n=((Integer)monArrayList.get(0)).intValue();

Maintenant, grâce à ces concepts, il suffit de faire :

List<Integer> monArrayList=new <Integer>ArrayList();
monArrayList.add(1); // Auto-Boxing
int n=monArrayList.get(0); // Application des Générics (Object -> Integer) puis Auto-Unboxing (Integer -> int)

Là encore, la lisibilité du code est accrue et par conséquent sa compréhension. Les casts disparaissent, les fonctions superflues aussi.

IV-A-1. Le principe▲

Iterator it=maCollection.iterator();
while (it.hasNext()) // tant que j'ai un élément non parcouru
{
  Object o = it.next();
  //mes opérations
}

while (it.hasNext)
{
    Objet o= maMap.get(it.next());
}

IV-A-2. Les itérateurs et les Generics▲

Iterator<String> it = maCollectionString.iterator();
while (it.hasNext()) // tant que j'ai un élément String non parcouru
{
  String s = it.next();
  //mes opérations
}

Les énumérations sont similaires aux itérateurs, à cela près que les itérateurs possèdent la fonction remove() qui permet de retirer de la liste le dernier élément renvoyé par next(). De la même façon que l'on fait appel à collection.iterator() pour récupérer un itérateur, on fera appel à Collections.enumeration(collection), ainsi que les fonctions hasNext() et next() remplacées par hasMoreElements() et nextElement().
Pourquoi alors les énumérations existent-elles ? Il est possible avec ces énumérations de parcourir un HashTable ou plutôt ses éléments / clefs, ce qui ne l'était pas avec un Iterator sans passer par des fonctions comme keySet() et entrySet().
Voici un exemple d'énumération sur les clefs d'un HashTable :

Enumeration enu=monHashTable.keys();
while(enu.hasMoreElements())
{
  Object o=enu.nextElement();
}

Il est évidemment possible d'utiliser la notion de Generics avec les énumérations.

Java 1.5 intègre une petite nouveauté : une boucle type for each. À l'instar de PHP, java intègre donc lui aussi une boucle de parcours d'une collection.
Le principe est simple, on se rapproche du pseudo-langage : pour chaque élément « e » dans la Collection « c ».
On a donc une syntaxe qui se ressemble à ça :

List<String> a=new ArrayList <String> ();
//remplissage de mon ArrayList avec des String
for(String current : a) // pour chaque String current dans a
{
  System.out.println(current);
}

Cette nouvelle boucle nous évite le problème de cast rébarbatif (tout comme les Generics) et donc améliore aussi la lisibilité.

Après la sortie de mon premier tutoriel, beaucoup de personnes m'ont demandé pourquoi je n'avais pas développé la partie sur thread safe.
Comme expliqué dans ce dernier, la notion thread safe signifie que l'objet est pourvu de sécurité en cas d'accès simultanés par deux threads. Cela signifie que des tests sont effectués à chaque accès pour savoir si un thread n'est pas déjà en train d'utiliser l'objet.
Cela provoque bien évidemment une perte de performance, pas forcément significative, mais elle existe.
Dès lors que l'on utilise le multithread, il faut prendre impérativement en compte que certains éléments peuvent être modifiés depuis un autre Thread et que cela peut aboutir à un état incohérent.
Par exemple, la méthode add(Object) de ArrayList effectue les traitements suivants :

• vérification de la capacité du tableau représentant la liste ;
• redimensionnement du tableau si nécessaire ;
• ajout de l'élément à la dernière position et incrémentation de l'index de la dernière position.

Maintenant, supposons que le tableau n'accepte plus qu'un seul élément avant d'être redimensionné, et que l'on ajoute deux éléments à partir de deux Thread différents. Voici le scénario :

1. le Thread 1 vérifie la capacité de la liste et ne redimensionne pas la liste puisqu'il reste une place libre ;
2. le Thread 2 prend la main, vérifie la capacité de la liste et ne redimensionne pas non plus la liste puisqu'il reste une place libre ;
3. le Thread 2 ajoute l'élément à la dernière place et incrémente l'index de celle-ci ;
4. le Thread 1 reprend la main et ajoute l'élément à une position incorrecte…

Une jolie exception en perspective…
Le code ci-dessous vous montre bien ce type d'erreur : il crée 20 Threads qui ajoutent en parallèle 1000 éléments dans a même liste :

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

public class Main implements Runnable
{
  private final List list;
  Main(List list)
  {
    this.list=list;
  }
  public void run()
  {
    for(int i=0; i<1000; i++)
    {
      list.add("Element "+i);
    }
    System.out.println(Thread.currentThread().getName()+ " OK...");
  }
  public static void main(String [] args)
  {
      Main m=new Main(new ArrayList<String> ());
    Thread[] threads=new Thread[20];
    for(int i=0; i<threads.length; i++)
    {
      threads[i] = new Thread(m);
    }
    for(int i=0; i<threads.length; i++)
    {
      threads[i].start();
    }
  }
}

Vous devriez vous retrouver avec un certain nombre d'exceptions du type : Exception in thread « Thread-X » java.lang.ArrayIndexOutOfBoundsException, si ce n'est pas le cas, augmentez juste le nombre de Threads et/ou d'éléments ajoutés.
Ce type d'erreur dépend en effet de l'ordre dans lequel les Threads effectuent les opérations à tour de rôle, et c'est totalement aléatoire… ce qui rend ce type d'erreur très dur à déboguer.
On dit que la méthode add() n'est pas thread-safe, puisqu'elle ne gère pas le multithreading.

Pour corriger ce problème, il faut impérativement utiliser la synchronisation avec le mot clef synchronized (ou la nouvelle API de concurrence du JDK 5), comme ici :

sychronized(reference)
{
  // code sécurisé
}

On « verrouille » l'objet reference, ce qui a pour effet de garantir qu'un seul Thread à la fois puisse entrer dans le bloc « sécurisé ». Évidemment, tous les Threads doivent utiliser la synchronisation sur la même référence.
Ainsi, si on remplace le run() de l'exemple au-dessus par celui-ci, on n'obtient plus d'erreur :

public void run()
{
  for(int i=0;i<1000;i++)
  {
    synchronized(list) 
    {
      list.add("Element "+i);
    }
  }
}

Comme la collection utilisée est un ArrayList qui n'est pas thread-safe, c'est à nous de gérer la synchronisation. Maintenant, si l'on remplace notre ArrayList par un Vector dans notre premier code (ou en créant une List synchronized) :

Main m=new Main(Collections.synchronizedList(new ArrayList<String>()));

Les erreurs ont là aussi disparu.
Mais pourquoi certaines collections (Vector et HashTable) sont thread-safe et d'autres (ArrayList, LinkedList, HashMap…) pas ?
Vector et HashTable ont été hérités de Java 1.0, où la logique était de faire un maximum de choses pour assister le développeur, donc un maximum de classes thread-safe… Cela pose un gros problème de coût en temps d'exécution (moins significatif qu'avant).
Dans la majorité des cas, on utilisait ces classes dans un environnement monothread, et la synchronisation devenait inutilement coûteuse.
Java 1.2 a donc vu naître l'API de Collections et ses interfaces (Collection, List, Set, Map, SortedSet, SortedMap) et plusieurs implémentations (LinkedList, ArrayList, HashMap…). Sauf indication contraire, toutes ces implémentations ne sont pas thread-safe et les méthodes synchronizedXXXX() de Collections permettent d'en obtenir une version thread-safe.
Il est à noter que les Iterator, même après avoir synchronisé la collection, ne sont pas thread-safe de base, il faut gérer la synchronisation nous-mêmes.

Merci à adiGuba pour ses précisions sur ce concept.

Il est très fréquent de voir des développeurs réinventer la roue, à savoir refaire des fonctions de tri, de copie, de recherche (objet, minimum, maximum), etc. Il existe une classe Collections qui permet de faire tout ça. En voici les principales fonctions.

V-B-1. Le tri de listes▲

public class Personne implements Comparable
{
  public String nom,prenom;
  Personne(String nom, String prenom)
  {
    this.nom=nom;
    this.prenom=prenom;
  }
  public int compareTo(Object o) // on redéfinit compareTo(Object)
  {
    Personne p=(Personne)o;
    if(nom.equals(p.nom))
    {
      return prenom.compareTo(p.prenom);
    }
   return nom.compareTo(p.nom);
  }
}

import java.util.Comparator;
public class MonComparator implements Comparator
{
  MonComparator()
  {
  }
  public int compare(Object arg0, Object arg1) 
  {
    Personne p1 = (Personne) arg0;
    Personne p2 = (Personne) arg1;
    
    int result = p1.name.compareTo(p2.name);
    
    if(result==0)
      result = p1.prenom.compareTo(p2.prenom);
    
      return result;
  }

}

V-B-2. Minimum et maximum▲

V-B-3. Remplacements▲

V-B-4. Lecture-seule▲