IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)



Comment bien utiliser les collections ?
auteur : Clément Cunin
Les collections font partie de Java (J2SE) depuis la version 1.2. Les collections proposent une serie de classes, d'interfaces et d'implémentations pour gérer efficacement les données.

Pour chaque type de structure de données (liste, ensemble, association) existe une interface et plusieurs implémentations. Chaque implémentation utilise une stratégie avec des avantages et des inconvéniants. Il est important de bien comprendre les différentes stratégies pour choisir l'implémentation la plus performante en fonction de ses besoins.

Conseil :
Tout d'abord, afin de minimiser la quantité de code à modifier pour changer d'implémentation, il convient de toujours faire référence aux collections en utilisant les interfaces, seule l'étape de construction faisant référence à l'implémentation.

<comment>La bonne solution :</comment>List list = new ArrayList();Set set = new HashSet();Map map = new TreeMap();<comment>La mauvaise solution :</comment>ArrayList list = new ArrayList();HashSet set = new HashSet();TreeMap map = new TreeMap();
Il peut néanmoins arriver qu'on soit contraint d'utiliser la 2ème solution pour avoir accès aux méthodes spécifiques à l'implémentation. En effet les classes concrètes sont souvent plus riches que les interfaces, ce qui peut se révéler nécessaire pour tirer le meilleur parti possible d'une implémentation.

Détails :
Les <javaInterface class="java.util.Set"/> (ensembles) sont un groupe d'éléments uniques.
Les <javaInterface class="java.util.List"/> (listes) sont une suite d'éléments ordonnés accessibles par leur indice (leur place dans la liste). Les listes ne garantissent pas l'unicité des éléments.
Les <javaInterface class="java.util.Map"/> (associations) mémorisent une collection de couples clé-valeur. Si vous avez une clé, l'association retrouvera la valeur associée à cette clé. Les clés sont uniques, mais la même valeur peut-être associée à plusieurs clés.

lien : Quel différence entre HashSet, TreeSet et LinkedHashSet ?
lien : Quelles différences entre ArrayList, LinkedList et Vector ?
lien : Quelles différences entre HashMap, TreeMap, LinkedHashMap, IdentityHashMap, WeakHashMap et Hashtable ?

Quel différence entre HashSet, TreeSet et LinkedHashSet ?
auteur : Clément Cunin
L'API propose trois implémentations concrètes pour les ensembles (<javaInterface class="java.util.Set"/>). Un ensemble est un groupe d'élément uniques.

java.util.HashSet :
Le <javaClass class="java.util.HashSet"/> est la plus utile des implémentations.
Note : L'ordre d'itération des éléments est aléatoire.
Complexité : Les opérations add, remove, contains and size sont exécutées en un temps constant.

java.util.TreeSet :
Le <javaClass class="java.util.TreeSet"/> contient un ensemble d'éléments ordonnés (il implémente également l'interface <javaInterface class="java.util.SortedSet"/>). Les éléments sont ordonnés en fonction de leur ordre naturel (voir <javaInterface class="java.util.Comparable"/>), ou en fonction d'un <javaClass class="java.util.Comparator"/> précisé à la construction du TreeSet.
Complexité : Les opérations add, remove, contains and size sont exécutées en un temps log(n).

java.util.LinkedHashSet :
Un <javaClass class="java.util.LinkedHashSet"/> est identique au HashSet sauf qu'il conserve l'ordre d'insertion des éléments dans une liste doublement chainée.
Note : L'ordre d'itération des éléments correspond à l'ordre d'insertion, l'ordre reste inchangé si l'on ajoute un élément déjà présent.
Complexité : Les opérations add, remove, contains and size sont exécutées en un temps constant (mais supérieur au temps du HashSet car il faut également gérer la liste chainée).

lien : Comment bien utiliser les collections ?

Quelles différences entre ArrayList, LinkedList et Vector ?
auteur : Clément Cunin
L'API propose deux implémentations concrètes pour les listes (<javaInterface class="java.util.List"/>). Une liste est une suite ordonnée d'éléments (les éléments peuvent être ajoutés à plusieurs endroits de la liste).

java.util.ArrayList :
Un <javaClass class="java.util.ArrayList"/> utilise un tableau en interne pour ranger les données. Un ArrayList fournit un accès aux éléments par leur indice très performant et est optimisé pour des opérations d'ajout/suppression d'éléments en fin de liste ( voir Comment fonctionne un ArrayList ? ).
Complexité : Les opération size, isEmpty, get, set, iterator sont exécutées en temps constant.
Les opérations d'ajouts/supprétions sont exécutées en temps constant amorti (les ajouts/suppréssion en fin de liste sont plus rapides).

java.util.LinkedList :
Un <javaClass class="java.util.LinkedList"/> utilise une liste chainée pour ranger les données. L'ajout et la suppression d'éléments est aussi rapide quelque soit la position, mais l'accès aux valeurs par leur indice est très lente.
Complexité : Les opérations size, isEmpty, add, remove, set, get sont exécutées en temps constant. Toutes les méthodes qui font référance à un indice sont exécutées en temps O(n).

java.util.Vector :
La classe <javaClass class="java.util.Vector"/> est une classe héritée de Java 1. Elle n'est conservée dans l'API actuelle que pour des raisons de compatiblité ascendante et elle ne devrait pas être utilisé dans les nouveaux programmes. Dans tous les cas, il est préférable d'utiliser un ArrayList.
Note : Cette classe est "thread-safe", càd que plusieurs processus peuvent l'utiliser en même temps sans risque.
Complexité : idem que pour ArrayList, plus le temps de synchronisation des méthodes.

lien : Comment bien utiliser les collections ?

Quelles différences entre HashMap, TreeMap, LinkedHashMap, IdentityHashMap, WeakHashMap et Hashtable ?
auteur : Clément Cunin
L'API propose cinq implémentations concrètes pour les 'Map' (<javaInterface class="java.util.Map"/>). Une map permet de créer un ensemble de couples clé/valeur (On parle aussi de tableaux associatifs), la clé permettant de retrouver rapidement la valeur qui lui a été associée. Les clés sont des objets uniques, non NULL ; Les valeurs peuvent être multiples et NULL.

java.util.HashMap :
La classe <javaClass class="java.util.HashMap"/> est l'implémentation concrète la plus standard, elle est adaptée à la plupart des situations.

java.util.TreeMap :
La classe <javaClass class="java.util.TreeMap"/> ajoute une fonction de tri des clés de la Map. L'ordre des clés peut être choisi en donnant une instance de <javaClass class="java.util.Comparator"/> sinon c'est l'ordre naturel des clés qui sera utilisé (elles doivent donc implémenter <javaInterface class="java.lang.Comparable"/>). Si vous avez une grande quantité de données à ajouter dans la collection et que l'ordre clés n'est utile qu'après l'ajout, il est plus efficace de créer un HashMap pour ajouter les éléments et de construire la TreeMap à partir de la HasMap :

Map map = new HashMap();<comment>Toutes les operations pour ajouter les éléments...</comment>map.put(....);<comment>... puis on construit la TreeMap.</comment>map = new TreeMap(map);
java.util.LinkedHashMap :
La classe <javaClass class="java.util.LinkedHashMap"/> conserve l'ordre d'ajout des clés (même principe que java.util.LinkedHashSet avec un set). Si la clé ajoutée est déjà présente, l'ordre ne change pas.

java.util.IdentityHashMap :
La classe <javaClass class="java.util.IdentityHashMap"/>, contrairement aux autres implémentations concrètes, utilise l'opérateur '==' pour savoir si deux clés sont identiques (les autres utilisent le résultat de la méthode <javaMethode class="java.lang.Object" methode="equals(java.lang.Object)"/>).

java.util.WeakHashMap :
La classe <javaClass class="java.util.WeakHashMap"/> conserve les couples en utilisant des références faibles, donc si la clé n'est plus référencée ailleurs dans le programme, le couple est automatiquement supprimé de la collection (voir <javaClass class="java.lang.ref.WeakReference"/>).

java.util.Hashtable :
La classe <javaClass class="java.util.Hashtable"/> est une classe héritée de Java 1. Elle n'est conservée dans l'API actuelle que pour des raisons de compatiblité ascendante et elle ne devrait pas être utilisée dans les nouveaux programmes. Dans tous les cas, il est préférable d'utiliser un HashMap.

lien : Comment bien utiliser les collections ?

Comment créer une pile (LIFO) ?
auteur : Clément Cunin
La classe Stack
La classe <javaClass class="java.util.Stack"/> pourrait correspondre à nos besoins, mais elle hérite de <javaClass class="Vector"/>, ces méthodes sont synchronisées et donc plus lentes que si l'on créait une pile en se basant sur une collection de l'API java 2 ( voir : Comment bien utiliser les collections ?).

La classe LinkedList
La classe <javaClass class="java.util.LinkedList"/> contient toutes les méthodes nécessaires à la création d'un pile : <javaMethode class="java.util.LinkedList" methode="addFirst(Object o)"/>, <javaMethode class="java.util.LinkedList" methode="getFirst()"/> et <javaMethode class="java.util.LinkedList" methode="removeFirst()"/>. On peut donc très bien utiliser cette classe comme une pile.

Créer sa propre classe
Le but n'est pas de réinventer la roue, mais juste d'utiliser une classe qui porte le nom 'Stack' ou 'Pile' pour plus de clarté dans le code source sans plomber les performances avec la classe Stack de Java 1. L'implémentation proposée ici est basée sur le modèle des collections de Java2, elle utilise une interface <file href="Stack.java"/> et une classe concrète <file href="LinkedStack.java"/>.

lien : Comment bien utiliser les collections ?

Comment augmenter la taille d'un tableau ?
auteur : Clément Cunin
La taille d'un tableau est fixée lors de sa construction et ne peut plus être modifiée. La seule solution consiste à créer un nouveau tableau plus grand et à copier les anciennes valeurs dans le nouveau tableau. Pour effectuer la copie de tableau, on utilise la méthode <javaMethode class="java.lang.System" name="arraycopy(java.lang.Object, int, java.lang.Object, int, int)" /> de la classe <javaClass class="java.lang.System"/> bien plus performante qu'une itération.

<comment>la méthode simple</comment>int[] nouveau = new int[longueur];System.arraycopy(vieuxTableau,0,nouveau,0,vieuxTableau.length);<comment>Note : On place ici les anciennes valeurs au début du nouveau tableau.</comment>
Note :
La création d'un nouveau tableau est une opération coûteuse en terme de performances, si vous devez utiliser une structure de données dont la taille change souvent, il est fortement conseillé d'utiliser une liste (Quelles différences entre ArrayList, LinkedList et Vector ?).

lien : Quelles différences entre ArrayList, LinkedList et Vector ?

Comment fonctionne un ArrayList ?
auteur : Clément Cunin
Bien utiliser une structure de données implique d'en comprendre le fonctionnement. Les classes <javaClass class="java.util.Vector"/> et <javaClass class="java.util.ArrayList"/> fonctionnent de la même manière (Quel différance ?).

Structure interne :
Les données de la liste sont rangées dans un tableau d'objets. Le principal intérêt d'un ArrayList ou d'un Vector étant de pouvoir facilement ajouter un élément à la liste, le tableau utilisé en interne est surdimensionné par rapport au besoin. Exemple : Un ArrayList de 5 éléments pourrait utiliser un tableau de 10 éléments, lorsque qu'on ajoute un nouvel élément, on le place dans la 1ère case libre du tableau interne, on n'est pas obligé d'instancier un nouveau tableau. Evidement, à force d'ajouter des éléments, le tableau interne peut se touver saturé, dans ce cas un nouveau tableau est créé et les anciennes valeurs sont recopiées dedans.

Optimisation :
La gestion automatique de la taille du tableau interne ne nous empêche pas de donner un coup de main pour améliorer les performances. Lors de la création d'une liste, il est important d'utiliser un constructeur précisant la capacité (taille du tableau interne), il est en général facile d'estimer la taille moyenne de sa structure de données, on évite ainsi de passer par plusieurs dizaines de réallocation du tableau interne. De même, avant d'insérer une grande quantité d'information, il est possible de demander de garantir une capacité minimumale. Ces précautions sont d'autant plus importantes si la liste contient beaucoup d'éléments.

lien : Comment bien utiliser les collections ?
lien : Quelles différences entre ArrayList, LinkedList et Vector ?


Ce document issu de http://www.developpez.com est soumis à la licence GNU FDL traduit en français ici.
Permission vous est donnée de distribuer, modifier des copies de cette page tant que cette note apparaît clairement.