#ProgX

~ FUCK THE FUCKING FUCKERS !

Articles | Connexion

Peuw.net c'est mieux que la trotinette !

~Les collections en Java

Java

Présentation

La méthode la plus répandu en programmation pour stocker une grande quantitée de données d'une même nature passe par l'utilisation, somme toute naturelle, des tableaux. Cependant, dans de nombreuses situations le programmeur peut être amené à gérer des listes de données dont il ne connait pas par avance la taille. Ou encore des listes de données mixtes. C'est dans ce genre de situations qu'interviennent les collections d'objets.

Sommaire

1. Introduction aux collections

2. Vector et ArrayList

3. Hashtable et HashMap

4. Conclusion

Introduction aux collections

Bien sûr, il est souvent possible de déclarer un tableau dont la taille est suffisament importante pour les besoins du programmes. Prenons le cas d'un algorithme qui stockera des données dans un tableau. Si l'on sait juste que ces données n'excéderont pas 500 élements, nous pouvons nous contenter de la déclaration suivante:

// déclaration d'un tableau de 500 objets
protected Object[] datas = new Object[500];
       
      Copier dans Jext | Jext | Plugin Codegeek

Malheureusement, une telle solution n'a que peu d'avantages. Certes, l'accès aux éléments du tableau sera relativement rapide et facile à programmer. Pourtant, une telle méthode peut entraîner un grave gaspillage des ressources. Si d'aventure votre tableau ne venait à contenir que 3 éléments, 497 allocations mémoires inutiles auront été effectuées. En outre, votre programme peut tout à fait par la suite avoir besoin de plus de 500 éléments, vous obligeant à modifier votre code source.

Mais louée soit la POO, les collections sont là ! Un collection est une sorte de tableau possédant deux limites: une de taille (dite "size") et une de capacité (dite "capacity"). Par exemple, une collection de String peut avoir une capacité de 10 éléments et une taille de 3 éléments. Vous l'aurez compris, la taille indique le nombre d'objets que contient effectivement la collection et la capacité le nombre d'objets que la collection est susceptible d'accueillir.

L'intérêt des collections n'est pas encore flagrant... nous y venons. Les collections ont pour particularité très intéressante de se redimenssionner automatiquement lorsque cela est nécessaire. Imaginons un instant que vous ayiez une collection possédant une capacité de 10 éléments et une taille de 10 éléments. Si vous ajoutez un élément, alors la capacité de la collection sera automatiquement augmentée (en Java, les tailles doublent ou se multiplient par 0.75). Cependant, le redimenssionement automatique ne se fait que lors de l'addition d'un élément. Pour diminuer la capacité d'une collection après un retrait, vous devez le faire manuellement, en appelant une fonction prévue à cet effet (généralement nommée trimToSize).

La plate-forme Java propose de nombreuses collections toutes plus utiles les unes que les autres (citons Stack, LinkedList, ...). Du lot, deux se dégagent réellement: Vector et Hashtable. Nous allons les étudier ainsi que leurs deux dérivés: ArrayList et HashMap.

Vector et ArrayList

Ces deux classes font parties du package java.util de Java. Ces deux objets sont la forme la plus classique de collection. Tout d'abord sachez que ArrayList propose exactement les mêmes fonctions que Vector. Les seules différences résident dans le nom des fonctions des deux objets. ArrayList colle en effet aux conventions de nomination de Sun, au contraire de Vector. De plus ArrayList n'est pas thread-safe. C'est à dire que le mot clé synchronized n'est pas appliqué à ses méthodes. Il en résulte une collection plus rapide à manipuler que Vector mais dangereuse dans le cadre de l'utilisation de threads.

Constructeurs

Dans la suite de ce cours, nous n'emploierons que l'objet Vector, plus répandu car existant dans le JDK 1.1. Pour construire une collection de type Vector, il existe deux constructeurs principaux:

// on utilise Vector
import java.util.Vector;

public class CollectionTest
{
  // constructeur vide
  protected Vector v = new Vector();
  // constructeur avec capacité initiale
  protected Vector v2 = new Vector(200);
}
       
      Copier dans Jext | Jext | Plugin Codegeek

Le premier constructeur crée une nouvelle collection possédant une capacité de 10 éléments. C'est peu. C'est pour cela que vous pourrez, et devrez, faire souvent appel au second constructeur. Celui-ci permet de déclarer la capacité initiale. Ici, contrairement aux tableaux, il ne s'agit plus de deviner la capacité maximale de votre ensemble de données, mais minimale. Ainsi, si vous savez que vous ajouterez au moins 175 éléments à la collection, donnez lui une capacité de 200. Pourquoi donc ? Tout simplement parce que lorsque vous atteignez la capacité limite, l'allocation mémoire est doublée mais surtout la collection effectue une recopie des éléments existants ! Ainsi, si vous avez 175 éléments dans une collection de capacité 175, l'ajout d'un élément provoquera la création d'un tableau temporaire de 175 éléments, d'un nouveau de 350 et d'une recopie des 175 anciens éléments dans le nouveau tableau. Un coup dur pour les performances.

Ajouter un élément

L'ajout d'un élément à un Vector se fait de la manière suivante:

Object o = new Object();
vector.addElement(o);
       
      Copier dans Jext

La méthode addElement existe aussi sous le nom de add. Cependant, cette deuxième forme n'existe qu'à partir du JDK 1.2. Vous noterez que ces méthodes n'accepte en paramètre que le type Object. Autrement dit, il est hors de question d'utiliser des types primitifs (int, double, ...) avec une collection. Si vous y tenez, vous pourrez faire appel aux objets "wrappers" tels que Integer ou Double pour pouvoir ajouter des types primitifs de manières indirecte à une collection.

Parcourir la collection

La classe Vector propose deux manières de parcourir l'ensemble des éléments. La première s'inspire des tableaux:

Vector v = new Vector();

// ... ajout d'éléments

// on affiche chaque élément dans la console
for (int i = 0; i < v.getSize(); i++)
  System.out.println(v.getElementAt(i));
       
      Copier dans Jext

Le parcours du Vector ressemble donc vraiment à celui d'un tableau. La syntaxe présentée ci-dessus correspond à celle du JDK 1.1. Avec le JDK 1.2 (ou l'objet ArrayList), il convient d'écrire ceci:

for (int i = 0; i < v.size(); i++)
  System.out.println(v.get(i));
       
      Copier dans Jext

La seconde méthode de parcours invoque les énumérations. Une énumération, en Java, est classe implémentant l'interface Enumeration. La classe StringTokenizer par exemple fait appel aux énumérations.

Vector v = new Vector();
Enumeration e;
// ... ajout d'éléments
e = v.elements();

// on affiche chaque élément dans la console
while (e.hasMoreElements())
  System.out.println(e.nextElement());
       
      Copier dans Jext

Le parcours est ici unidirectionnel. La méthode a son avantage dans certaines situations mais ne permet pas un accès direct à tel ou tel élément. La collection ArrayList quant à elle fait appel à l'énumération Iterator:

ArrayList a = new ArrayList();
Iterator i;
// ... ajout d'éléments
i = a.iterator();

// on affiche chaque élément dans la console
while (i.hasNext())
  System.out.println(i.next());
       
      Copier dans Jext

ArrayList possède également la méthode listIterator retournant un objet ListIterator. Ce dernier possède les mêmes fonctions que Iterator mais permet en outre des additions, retraits d'éléments et de parcourir les données vers l'arrière également.

Diverses fonctions

Ces deux collections proposent plusieurs fonctions très pratiques permettant d'extraire des éléments, d'en insérer, de trouver la place d'un élément, etc... Voici un petit listing répertoriant les fonctions les plus pratiques:

Vector v = new Vector();
// ... ajout d'éléments

// insérer un élément
v.insertElementAt(obj, position);
// JDK 1.2
v.add(position, obj);

// effacer tous les éléments
v.removeAllElements();
//JDK 1.2
v.clear();

// positions d'un élément
position = v.indexOf(obj);

// enlever un élément donné
v.removeElement(obj);
// JDK 1.2
v.remove(obj);

// enlever un élément à une position
v.removeElementAt(position);
// JDK 1.2
v.remove(position);

// changer un élément
v.setElementAt(obj, position);
// JDK 1.2
v.set(position, obj);

// obtenir un tableau contenant les éléments
Object[] oo = new Object[v.getSize()];
v.copyInto(oo);
// JDK 1.2
oo = v.toArray();
       
      Copier dans Jext

Hashtable et HashMap

Ces deux classes font également parties du package java.util de Java. Ces deux objets permettent de créer des tableaux d'éléments indexés par clés. Ainsi, si l'on associe la clé "Claire" à l'objet "Romain", on pourra obtenir le second objet en connaissant sa clé. De la même manière que précédemment, Hashtable appartient au JDK 1.1 et HashMap au JDK 1.2. Et de la même manière encore, HashMap est plus rapide car non thread-safe.

Constructeurs

// on utilise Hashtable
import java.util.Hashtable;

public class CollectionTest
{
  // constructeur vide
  protected Hashtable h = new Hashtable();
  // constructeur avec capacité initiale
  protected Hashtable h2 = new Hashtable(200);
}
       
      Copier dans Jext | Jext | Plugin Codegeek

Aucune explication ne sera ici nécessaire. Le principe de taille et de capacité de Vector s'applique également à nos deux nouveaux objets.

Ajouter un élément

Pour ajouter un nouvel élément au Hashtable:

// élément
Object o = new Object();
// clé
Object key = new Object;
// l'objet o est associé à la clé key
hashtable.put(key, o);
       
      Copier dans Jext

Ici aucune différence notable entre Hashtable et HashMap n'est à souligner. L'un comme l'autre possèdent les mêmes fonctions. Seul Hashtable propose des duplicatas de certaines fonctions, du à son antériorité.

Parcourir les collections

A l'instar de Vector, Hashtable possède deux méthodes pour parcourir la collection. HashMap n'en propose qu'une. Mais commençons par voir commen récupérer un objet à l'aide de sa clé:

// récupére l'objet associé à la clé key
Object o = hashtable.get(key);
       
      Copier dans Jext

Les méthodes elements() et keys() de l'objet Hashtable permettent de parcourir respectivement les objets et leurs clés à l'aide d'un objet Enumeration. Rien de nouveau ici, donc nous ne nous y attarderons pas. Cependant, HashMap (et Hashtable) offrent une autre méthode proche de l'utilisation des énumérations:

HashMap h = new HashMap();
// ... ajout d'éléments

// contient les objets...
Set entries = h.entrySet();
// ... et leurs clés
Set keys = h.keySet();

// itérateurs
Iterator ie = entries.iterator();
Iterator ik = keys.iterator();

// on affiche chaque élément dans la console
while (ie.hasNext())
  System.out.println("Clé: " + ik.next() + " associé à l'objet " + ie.next());
       
      Copier dans Jext

Eh oui, finalement on retrouve nos Iterator vu dans l'objet ArrayList. Seulement ici leur accès est indirect. Les objets Set intermédiaires sont également des collections proposant quelques méthodes intéressantes telles toArray déjà évoquée plus haut. Attention, ne vous avisez pas de modifier l'un des objets Set sans faire de même avec l'autre. Vous risqueriez de vous retrouver confronté à des bugs difficiles à dénicher.

Diverses fonctions

Pour finir, voici une liste de quelques fonctions utiles, applicables aux deux collections que nous étudions:

HashMap h = new HashMap();
// ... ajout d'éléments

// effacer tous les éléments
h.clear();

// vérifie si la clé existe
boolean exist = h.containsKey(key);
// si l'objet existe
exist = h.containsValue(obj);

// vérifier si la collection est vide
exist = h.isEmpty();

// retirer un élément
h.remove(key);

// obtenir le nombre de clés
int keysNumber = h.size();
       
      Copier dans Jext

Conclusion

Avec la pratique, vous découvrirez vite la puissance et l'importance de ces collections. Comme nous l'avons dit dans l'introduction, de nombreuses autres collections existents. Les piles, les files, les listes liées, doublement liées, etc... autant d'objets qui trouvent leur importance dans de nombreux programmes. Cependant, les deux types de collections traités dans ce cours restent les plus fréquemment employés.

par Romain Guy
romain.guy@jext.org
http://www.jext.org
Dernière mise à jour : 14/10/2006

Java

Alias :
Message :