
|
auteur :
Clément Cunin | Les collections font partie de Java (J2SE) depuis la version 1.2. Les collections proposent une série 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énients. 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.
List list = new ArrayList();
Set set = new HashSet();
Map map = new TreeMap();
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 java.util.Set (ensembles) sont un groupe d'éléments uniques. Les 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 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 : Quels sont les différents types de Map ?
|
|
auteur :
Clément Cunin | L'API propose trois implémentations concrètes pour les ensembles (java.util.Set). Un ensemble est un groupe d'élément uniques.
java.util.HashSet : Le 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 java.util.TreeSet contient un ensemble d'éléments ordonnés (il implémente également l'interface java.util.SortedSet). Les éléments sont ordonnés en fonction de leur ordre naturel (voir java.util.Comparable), ou en fonction d'un 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 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 ?
|
|
auteur :
Clément Cunin | L'API propose deux implémentations concrètes pour les listes (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 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. Complexité : Les opérations size, isEmpty, get, set, iterator sont exécutées en temps constant. Les opérations d'ajout/suppression sont exécutées en temps constant amorti (les ajouts/suppressions en fin de liste sont plus rapides).
java.util.LinkedList : Un java.util.LinkedList utilise une liste chainée pour ranger les données. L'ajout et la suppression d'éléments est aussi rapide quelle que 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érence à un indice sont exécutées en temps O(n).
java.util.Vector : La classe 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ée dans les nouveaux programmes. Dans tous les cas, il est préférable d'utiliser un ArrayList. Note : Cette classe est "thread-safe", c'est-à-dire 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 ?
|
|
auteur :
Clément Cunin | L'API propose cinq implémentations concrètes pour les 'Map' (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 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 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 java.util.Comparator sinon c'est l'ordre naturel des clés qui sera utilisé (elles doivent donc implémenter 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();
map.put(....);
map = new TreeMap(map);
java.util.LinkedHashMap : La classe 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 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 equals(java.lang.Object)).
java.util.WeakHashMap : La classe 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 java.lang.ref.WeakReference).
java.util.Hashtable : La classe 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 ?
|
|
auteur :
Clément Cunin | La classe Stack La classe java.util.Stack pourrait correspondre à nos besoins, mais elle hérite de 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 java.util.LinkedList contient toutes les méthodes nécessaires à la création d'un pile : addFirst(Object o), getFirst() et 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 Stack et une classe concrète LinkedStack.
|
lien : Comment bien utiliser les collections ?
téléchargement : Stack.java
téléchargement : LinkedStack.java
|
|
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 arraycopy(java.lang.Object, int, java.lang.Object, int, int) de la classe java.lang.System bien plus performante qu'une itération.
/** la méthode simple */
int[] nouveau = new int[longueur];
System.arraycopy(vieuxTableau,0,nouveau,0,vieuxTableau.length);
/** Note : On place ici les anciennes valeurs au début du nouveau tableau. */
|
lien : Quelles différences entre ArrayList, LinkedList et Vector ?
|
|
auteur :
Clément Cunin | Bien utiliser une structure de données implique d'en comprendre le fonctionnement. Les classes java.util.Vector et 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. Evidemment, à force d'ajouter des éléments, le tableau interne peut se trouver 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é minimale. 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 ?
|
|
auteurs :
braim, duj, Grégory Danelon | La classe java.util.Collections apporte la solution :
List ma_liste = new ArrayList();
Collections.sort(ma_liste);
ma_liste est ainsi triée par ordre croissant. Pour trier dans l'ordre décroissant, il suffit de faire ceci :
Collections.sort(ma_liste, Collections.reverseOrder());
Attention cependant, cet exemple fonctionne que si les éléments dans la liste sont de type Comparable, comme int, String, Date, ... (voir l'interface java.lang.Comparable). Si ce n'est pas le cas (les éléments sont des objets que vous avez défini), il faut que votre classe implémente l'interface java.lang.Comparable, donc en fait il faut définir la méthode int compareTo(Object o).
Prenons un exemple simple :
class Voiture {
String marque = "";
int nbCheveau = 0;
public Voiture(String s, int i) {
marque = s;
nbCheveau = i;
}
public int getNbCheveau() { return nbCheveau; }
public String toString() { return marque + "\t" + nbCheveau; }
}
On veut pouvoir trier une liste de Voiture suivant leur nombre de chevaux. Voilà alors les modifications à apporter à la classe :
class Voiture implements java.util.Comparable {
/**
* @param other other doit être de type Voiture !
*/
public int compareTo(Object other) {
int nombre1 = ((Voiture) other).getNbCheveau();
int nombre2 = this.getNbCheveau();
if (nombre1 > nombre2) return -1;
else if(nombre1 == nombre2) return 0;
else return 1;
}
}
Maintenant, vous pouvez trier facilement une liste de voitures :
Collections.sort(liste_voitures);
Le code est identique pour un tableau. Il faut seulement utiliser la classe Arrays.
Arrays.sort(unTableauDeVoitures);
Vous avez aussi la possibilité de facilement mélanger une liste grâce à la méthode shuffle de Collections.
|
lien : Comment bien utiliser les collections ?
lien : Quelles différences entre ArrayList, LinkedList et Vector ?
|
|
auteur :
Clément Cunin | Tout simplement en faisant :
boolean estUnTableau = monObjet.getClass().isArray();
|
|
auteur :
Clément Cunin | Cette propriété n'est pas directement accessible, mais une petite fonction permet de la calculer rapidement. On se base sur le fait qu'un tableau à plusieurs dimensions est en fait un tableau de tableaux.
public static int getNbDimension( Object monTableau ) {
int dim=0;
Class cls = monTableau.getClass();
while( cls.isArray() ) {
cls = cls.getComponentType();
dim++;
}
return( dim );
}
|
|
auteur :
Clément Cunin | En Java, les tableaux ne sont pas extensibles. On doit donc procéder en 2 étapes, créer un nouveau tableau plus grand, puis copier toutes les valeurs de l'ancien tableau dans le nouveau.
Object nouveauTableau = Array.newInstance( ancienTableau.getClass().getComponentType(),
nouvelleTaille );
System.arraycopy( ancienTableau, 0, nouveauTableau, Array.getLength(ancienTableau);
Note : Avant de vous embarquer dans cette solution, réfléchissez bien si un .ArrayList ou un Vector ne seraient pas plus appropriés à votre problème.
|
|
auteur :
Nourdine Falola | Boucle "for"
A l'ancienne, avec une boucle for traditionnelle
int tab[50];
...
for (int index = 0; i < tab.length; index++)
System.out.println(tab[index]);
Boucle "for each"
Le JDK 5.0 apporte une construction de boucle performante qui permet de parcourir tous les éléments d'un tableau, ou d'un objet implémentant l'interface Iterable (ArrayList, ...), sans se préoccuper de l'indice.
int tab[50];
...
for (int n : tab)
System.out.println(n);
|
Consultez les autres F.A.Q's
Les codes sources présentés sur cette page sont libres de droits, et vous pouvez les utiliser à votre convenance. Pour le reste, ce document constitue une oeuvre intellectuelle protégée par les droits d'auteurs.
Ce document issu de http://www.developpez.com est soumis à deux licences, en fonction des contributeurs :
- Les contributions de Clément Cunin et Johann Heymes sont soumises aux termes de la la licence GNU FDL traduite en français ici. Permission vous est donnée de distribuer, modifier des copies des contributions de Clément Cunin et Johann Heymes tant que cette note apparaît clairement :
"Ce document issu de http://www.developpez.com est soumis à la licence GNU FDL traduite en français ici. Permission vous est donnée de distribuer, modifier des copies de cette page tant que cette note apparaît clairement".
- Pour ce qui est des autres contributions : Copyright © 2004 Developpez LLC : Tous droits réservés Developpez LLC. Aucune reproduction, ne peux en être faite sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts. Cette page est déposée à la SACD.
|
|
|