L'API Java propose une interface java.util.Collection qui est l'ancêtre de toutes les structures maintenant une collection d'éléments. Il existe principalement deux interfaces descendant de Collection :
- java.util.List qui représente une liste
- java.util.Set qui représente un ensemble ne comportant pas de doublon
Generics
Depuis Java 5, toutes les collections supportent le mécanisme de generics : on fait suivre le type de collection par le type d'élément contenu dans celle-ci ; par exemple Set<String> représente un ensemble de chaînes de caractères. Ceci permet d'éviter la coercition (cast) d'élément lors de leur récupération. Ainsi avant Java 1.5, si nous souhaitions afficher toutes les chaînes d'un ensemble de String, nous aurions utilisé le code suivant :
Set set = new HashSet();
set.add("toto");
set.add("foo");
for (Iterator it = set.iterator(); it.hasNext(); )
{
String element = (String)it.next();
System.out.println(element);
}
Depuis Java 5, on peut utiliser désormais ce code équivalent :
Set<String> set = new HashSet<>(); // La non-spécification du type paramétré lors de l'instanciation est autorisé depuis Java 1.7
set.add("toto");
set.add("foo");
for (String element: set)
System.out.println(element);
On note deux évolutions :
- La possibilité d'utiliser une boucle for (T element: iterable) (dite boucle for-each) à la place d'un itérateur ; une boucle for-each peut être utilisée pour tout objet implantant l'interface Iterable<T> (et également pour les tableaux)
- La non-nécessité de caster l'élément retourné par itération grâce au mécanisme de generics (sinon l'élément aurait été un Object que l'on aurait dû obligatoirement caster)
Java ne permet pas d'utiliser des types paramétrés qui sont des types primitifs : il faut donc toujours utiliser les types réifiés correspondants (i.e. Integer pour int, Long pour long, Character pour char, Boolean pour boolean...). Un type réifié est toujours immutable : une fois instantié, il ne peut pas être modifié. Voici un exemple d'implantation d'un incrémenteur de compteur utilisant une Map :
public static void incrementValue(Map<?, Integer> map, String key)
{
Integer i = map.get(key); // retourne null si la clé n'est pas présente
if (i == null) i = 0;
map.put(key, i + 1);
}
On remarque que l'on peut manipuler un type réifié comme un type primitif grâce aux mécanismes de boxing et unboxing automatiques. Attention toutefois au fait qu'une variable de type réifié peut accueillir une référence nulle ce qui n'est pas le cas d'un type primitif ; il faut donc toujours tester cette possibilité. L'instruction int i = map.get(key) compile mais nous aurait exposé à une NullPointerException si la clé n'était pas présente.
L'introduction de generics peut également dans certains situations aboutir à des ambiguités quant à la méthode à appeler. L'exemple le plus typique est l'utilisation de List<Integer>. L'interface List<T> possède les deux méthodes suivantes qui peuvent poser problème :
- T remove(int index) qui enlève l'élément d'indice index de la liste et le retourne ;
- et boolean remove(Object obj) qui enlève la première occurrence de l'élément obj de la liste
Nous pouvons nous interroger sur l'action qui serait réalisée dans le cas suivant :
package fr.upem.jacosa.collections;
import java.util.ArrayList;
import java.util.List;
/** Test the 2 methods remove on List<Integer */
public class AmbiguousListRemoval
{
public static void main(String[] args)
{
List<Integer> l = new ArrayList<>();
for (int i = 10; i >= 1; i++)
l.add(i);
System.out.println(l); // should print [10,9,8,...,1]
l.remove(10); // remove the last element that is 1 (call List.remove(int))
l.remove(Integer.valueOf(10)); // remove the number 10 in the list (in fact the first element) (calling List.remove(Integer))
l.remove(Integer.valueOf(10)); // remove the number 10 in the list (in fact the first element) (calling List.remove(Integer))
System.out.println(l); // should print [9,8,7,...,2]
}
}
Vérifier l'appartenance d'un élément à une collection
La méthode boolean contains(T element) permet de savoir si element appartient à une collection. Attention toutefois, son coût dépend du type de structure. Pour une List, il est nécessaire de parcourir tous les éléments pour statuer dans le pire des cas (dans le meilleur des cas, le premier élément de la liste est l'élément recherché) : le coût est linéaire en éléments. Pour un Set le coût est plus intéressant : $O(1)$ pour un HashSet reposant sur une table de hachage, $O(log n)$ pour n éléments dans un TreeSet qui est implanté par un arbre binaire de recherche équilibré.
Si l'on utilise un HashSet, il est nécessaire que la méthode int hashCode() soit bien redéfinie sur la classe des objets que l'on insère dans l'ensemble et que cette méthode évite les collisions (si deux éléments ont le même hashCode alors leur probabilité d'être différents au sens de equals() doit être très faible). Si deux objets sont égaux, ils doivent toujours retourner la même valeur de hachage ; si ce n'est pas le cas, le HashSet peut contenir des doublons. Aussi bien les éléments d'un Set que les clés d'une Map doivent être dans la mesure du possible immutables : en effet, toute modification risquerait d'impacter leur valeur de hachage ainsi que l'égalité avec d'autres éléments ; la cohérence de l'ensemble ne serait donc plus respecté. Un moyen simple de garantir l'immutabilité d'un objet est de faire en sorte que tous les champs de la classe soient déclarés final.
Pour pouvoir vérifier en pratique les problématiques de complexité de vérification d'appartenance d'un élément, on peut essayer de compiler et exécuter cette classe :
package fr.upem.jacosa.collections;
import java.util.*;
import java.lang.management.*;
/** A benchmark about the Collection.contains() method
* @author chilowi at u-pem.fr
*/
public class ContainsBench
{
private final Random random;
private final Collection<WrappedInt> collection;
private final boolean badHash;
/** An object containing an int */
public static class WrappedInt implements Comparable<WrappedInt>
{
public final int value;
public WrappedInt(int value) { this.value = value; }
/** A method declared final can be overriden in child classes */
@Override
public final boolean equals(Object obj)
{
if (! (obj instanceof WrappedInt)) return false;
return value == ((WrappedInt)obj).value;
}
@Override
public final int compareTo(WrappedInt other)
{
if (this == other) return 0;
if (other == null) return 1;
if (this.value > other.value) return 1;
if (this.value < other.value) return -1;
return 0;
}
@Override
public int hashCode() { return value; }
}
/** A WrappedInt with a dumb hashCode method */
public static class BadWrappedInt extends WrappedInt
{
/** We declare again the constructor */
public BadWrappedInt(int value) { super(value); }
@Override
public int hashCode() { return 0; }
}
public ContainsBench(Collection<WrappedInt> collection, boolean badHash)
{
this.random = new Random();
this.collection = collection;
this.badHash = badHash;
}
public ContainsBench(Collection<WrappedInt> collection)
{
this(collection, false);
}
private WrappedInt createInt(int i)
{
return (badHash)?new BadWrappedInt(i):new WrappedInt(i);
}
/** We put n integers from 0 to n-1 in the collection */
private void populateCollection(int n)
{
for (int i = 0; i < n; i++)
collection.add(createInt(i));
}
/** We run the benchmark */
public void run(int n, int k)
{
long startTime = getUserTime();
populateCollection(n);
System.out.println(String.format("Time required to populate %s with %d values %s: %f s", collection.getClass(), n, (badHash)?"with bad hash":"", (double)(getUserTime() - startTime) / 10e9));
startTime = getUserTime();
for (int i = 0; i < k; i++)
{
WrappedInt searched = createInt(random.nextInt(n));
boolean c = collection.contains(searched);
assert(c); // The searched value is always in the collection
}
System.out.println(String.format("Time required to run %d random contains() on %s of size %d %s: %f s", k, collection.getClass(), collection.size(), (badHash)?"with bad hash":"", (double)(getUserTime() - startTime) / 10e9));
}
public long getUserTime( )
{
ThreadMXBean bean = ManagementFactory.getThreadMXBean( );
return bean.isCurrentThreadCpuTimeSupported( ) ? bean.getCurrentThreadUserTime( ) : 0L;
}
public static void main(String[] args)
{
int n = Integer.parseInt(args[0]);
int k = Integer.parseInt(args[1]);
// Test a LinkedList
new ContainsBench(new LinkedList<WrappedInt>()).run(n, k);
// Test an ArrayList
new ContainsBench(new ArrayList<WrappedInt>()).run(n, k);
// Test a HashSet with a good hash function
new ContainsBench(new HashSet<WrappedInt>(), false).run(n, k);
// Test a HashSet with a bad hash function
new ContainsBench(new HashSet<WrappedInt>(), true).run(n, k);
// Test a TreeSet
new ContainsBench(new TreeSet<WrappedInt>()).run(n, k);
}
}
Notons que pour les listes, il est presque toujours préférable d'utiliser la méthode int indexOf(Object e) qui permet non seulement de savoir si l'élément est présent mais aussi de connaître l'indice de la première occurrence de cet élément. Il existe également une variante int lastIndexOf(Object e) pour obtenir l'indice de la dernière occurrence. Si l'élément n'est pas présent, -1 est retourné.
Ajouter et supprimer des éléments dans une collection
L'interface Collection propose la méthode boolean add(T element) qui retourne vrai ssi l'élément a été effectivement ajouté et son alter-ego boolean remove(Object element) qui retourne vrai ssi l'élément dont on a demandé la suppression était effectivement présent dans la collection (et a donc bien été supprimé). On notera que la méthode remove() ne supprime qu'un seul élément à la fois et teste l'égalité avec la méthode equals() ; si l'on veut supprimer tous les exemplaires d'un élément il faut répéter l'appel jusqu'à obtenir une valeur de retour fausse. Bien sûr cette remarque n'a pas d'intérêt pour les Set.
Pour une List, si l'on ajoute N fois un élément avec la méthode add(), il s'y retrouvera en N exemplaires ; add() retournera toujours vrai (à part des cas exceptionnels... où l'on aura une exception). Par contre pour un Set, si l'élément est déjà présent, l'ajout ne sera pas effectif et on récupérera faux comme valeur de retour : add() est dite idempotente dans ce cas de figure (l'appeler une fois ou plus avec le même argument ne change rien).
Il existe des méthodes permettant d'ajouter toute une collection dans une autre collection ou au contraire de supprimer tous les éléments d'une collection qui seraient présents dans une autre collection. Ces méthodes sont boolean addAll(Collection<? extends T> elements). <? extends T> indique que la collection que l'on peut ajouter doit être paramétrée par le même type ou alors un type plus spécifique que le type de la collection que l'on va modifier. Ainsi par exemple, on peut ajouter une Collection<String> dans une Collection<Object> mais l'inverse n'est pas vrai. Si la collection a changé, la méthode retourne true : dans le cas d'un Set par exemple, cela signifie que la collection ajoutée n'est pas un sous-ensemble. boolean removeAll(Collection<?> elements) existe également pour une suppression collective ; ici la collection en argument peut être paramétrée par un type quelconque : on pourrait très bien supprimer une Collection<Integer> d'une Collection<String> bien que cela ne présente pas un grand intérêt (rien ne serait supprimé). Là encore le type de retour indique si la collection a été modifiée suite à l'appel (au moins un élément supprimé).
Concernant les listes, par défaut la méthode add() ajoute un élément en fin de liste. Cela est réalisé en temps constant qu'il s'agisse d'une ArrayList utilisant un tableau ou d'une LinkedList utilisant des maillons chaînés. Par contre la suppression est bien plus problématique. En effet, il est nécessaire de préalablement retrouver l'élément à supprimer (en faisant plus ou moins le travail de contains()) ce qui n'est pas immédiat. Il faut ensuite réaliser la suppression proprement dite : ceci est fait en temps constant pour une LinkedList puisqu'il suffit de modifier le chaînage des éléments immédiatement précédent et suivant. En revanche pour une ArrayList il faut décaler tous les éléments qui suivent d'une position en arrière avec donc un coût linéaire en éléments. Concernant les Set la suppression est plus efficace et se fait en temps constant pour un HashSet et $O(log n)$ pour un TreeSet.
Notons que List offre la possibilité d'insérer un élément à une position quelconque avec add(int index, T element) ou d'en supprimer avec T remove(int index) (en retournant l'élément supprimé). Leur utilisation doit être évitée avec une ArrayList.
Itérer sur une collection
Toutes les collections implantent l'interface Iterable<T> : cela signifie qu'elles disposent d'une méthode Iterator<T> iterator(). Un itérateur possède une méthode boolean hasNext() pour savoir s'il existe un élément suivant, T next() pour récupérer l'élément suivant et void remove() pour supprimer l'élément actuel. Avant de récupérer un élément suivant, il faut toujours vérifier sa présence avec hasNext() ; si on ne le fait pas, on risque la levée d'une NoSuchElementException si l'on arrive à la fin de l'itérateur.
Un itérateur peut être instantié et parcouru explicitement ou alors implicitement en utilisant une boucle for-each sur un objet Iterable<T>. Le seul inconvénient d'une boucle for-each est qu'il devient impossible d'utiliser la méthode remove() de l'itérateur ; sinon il est conseillé de l'utiliser car elle allège la syntaxe.
Lorsque l'on itère sur une collection, une très mauvaise idée est d'essayer simultanément de modifier cette collection en ajoutant ou supprimant des éléments. Les seules modifications autorisées sont celles qui font appel à lam éthode remove() de l'itérateur (dont le support n'est pas obligatoire et peut alors lever NoSuchOperationException). Il existe également une méthode set(T element) qui permet de remplacer l'élément courant mais celle-ci n'est proposée que par ListIterator. Si l'on modifie la collection sans passer par l'itérateur, on risque d'obtenir un comportement d'itération indéterminé. Toutefois les itérateurs implantés dans l'API mettent en place un garde-fou pour éviter toute modification concurrente lors d'une itération : ils lèvent alors ConcurrentModificationException.
Plutôt que d'itérer avec un itérateur explicitement ou avec une boucle for-each (qui utilise implicitement un itérateur), on pourrait être tenté d'utiliser une itération par indice :
List<Object> l = ...; for (int i = 0; i < l.size(); i++) System.out.println(l.get(i));
Cette façon d'itérer ne fonctionne que pour les listes (les Set n'ont pas de notion d'élément indicé). Ce n'est pas une mauvaise idée pour une ArrayList car cela peut éviter d'instantier un itérateur. Par contre pour une LinkedList, cela nécessite un coût quadratique en nombre d'éléments car pour obtenir l'élément d'indice i, il faut à chaque fois reparcourir i maillons de la liste chaînée. Une ArrayList permet donc un accès aléatoire par indice à un élément : elle implante l'interface marqueur RandomAccess contrairement à LinkedList. Faire un test avec l instanceof RandomAccess nous permet donc de savoir si la méthode get(int) est coûteuse (coût linéaire) ou pas (coût constant).
Les ensembles ordonnés : SortedSet
L'interface SortedSet admet une implantation dans l'API : TreeSet. Cette implantation utilise un arbre binaire rouge-noir afin de classer les différents éléments. Un ordre doit être défini pour le classement :
- Soit en utilisant l'ordre naturel ; une classe dispose d'un ordre naturel si elle implante Comparable<T> avec sa méthode int compareTo(T element) retournant 0, une valeur < 0 ou > 0 suivant que l'élément en argument soit égal, plus petit ou plus grand que l'objet courant.
- Soit en utilisant un ordre externe implanté avec une classe dérivant de Comparable<T> avec une méthode int compare(T a, T b). Etant donné qu'une seule méthode doit être implantée, une expression lambda peut être utilisée.
Comment faire par exemple pour créer un Set d'entiers trié par ordre inverse ? Voici une solution en indiquant un Comparator<Integer> sous forme d'expression lambda inversant l'ordre naturel en constructeur de TreeSet :
SortedSet<Integer> set = new TreeSet<Integer>((x, y) -> - x.compareTo(y));
À noter que SortedSet dispose aussi d'une méthode Iterator<T> descendingIterator() afin d'obtenir un itérateur en ordre inverse ainsi que Set<T> descendingSet() qui permet d'obtenir une vue du Set en ordre inverse : on aurait pu donc écrire de façon équivalente :
SortedSet<Integer> set = new TreeSet<Integer>().descendingSet();
Tri d'une liste
Une liste peut être triée en utilisant la méthode sort(Comparator<T> cmp) de List. Avant Java 1.8, la méthode statique Collections.sort(List<T> l, Comparator<? super T> cmp) devait être utilisée. Est-il préférable d'utiliser une liste puis de la trier ou alors d'employer un SortedSet ? L'intérêt d'une SortedList est que le tri est réalisé par la structure même d'arbre binaire de recherche et est effectué progressivement à chaque ajout ou suppression. D'autre part aucun doublon n'est toléré. Si la collection est amenée à être modifiée régulièrement et ne comporte pas de doublon, un SortedSet est plus adapté. Par contre, si une fois construite la collection doit rester figée, l'usage d'une ArrayList puis d'un tri sur celle-ci est préférable ; la structure de tableau étant plus économe en mémoire qu'une structure d'arbre où de nombreuses références doivent être gérées. Le tri d'une LinkedList est théoriquement possible mais est à déconseiller en pratique car nous ne pourrons pas ensuite rechercher de manière efficace.
Après le tri d'une ArrayList, il peut être judicieux de la protéger contre des modifications accidentelles (ajout, suppression d'élément...). La méthode statique List<T> Collections.unmodifiableList(List<T> l) permet d'encapsuler une liste dans un nouvel objet List avec des méthodes add(), remove... levant une UnsupportedOperationException. Les plus curieux pourront consulter la classe Collections pour constater qu'il existe également des méthodes pour mettre en lecture seule un Set, un SortedSet, une Map ou une SortedMap.
Trier une liste sert à accélérer les recherches d'éléments sur celle-ci ; la méthode indexOf() (ou contains()) n'est pas pour autant accélérée et va toujours itérer sur tous les éléments de la liste jusqu'à trouver l'élément recherché. En effet la liste n'a pas connaissance elle-même du fait qu'elle soit triée. Il faut donc soi-même utiliser une méthode de recherche par dichotomie : soit à la main, soit en utilisant la méthode statique int binarySearch(List<? extends T> list, T key, Comparator<? super T> c). L'indice retourné est positif si l'élément a été trouvé (il s'agit de la position dans la liste) ; l'entier retourné est négatif lorsque la clé n'a pas été trouvée. Dans ce cas il s'agit de -i-1 où i est la position où devrait être insérée la clé dans la liste pour respecter l'ordre. Ainsi une valeur retournée de -1 indiquerait que l'élément devrait être inséré en début de liste tandis que -l.size()-1 indiquerait que l'élément est plus grand que tous les éléments de la liste (et devrait être inséré en fin).
A titre d'exemple, considérons une liste contenant des notes d'étudiants et essayons de trouver le ratio de notes égales ou au-dessus de 10 :
List<Integer> notes = new ArrayList<>();
... // nous peuplons la liste de notes dans un ordre quelconque
notes.sort(null); // nous trions la liste dans l'ordre naturel des entiers
notes = Collections.unmodifiableList(notes); // on rend la liste non-modifiable
// maintenant, notes.add(10); devrait lever une exception
int pos = Collections.binarySearch(notes, 10);
// si la note 10 a été attribuée, nous obtenons son indice
if (pos >= 0)
while (pos > 0 && l.get(pos-1) == 10) pos--; // Nous essayons de trouver la première note en dessous de 10 (car des doublons peuvent exister)
// sinon il s'agit de -i-1 où i est le point d'insertion
else
pos = -pos-1;
System.out.println("Ratio de notes au-dessus de 10: " + (double)(notes.size() - pos) / (double)notes.size());
Indexer des éléments selon des critères
L'usage classique d'une Map est de pouvoir indexer des éléments en fonction d'un critère. Cela permet d'obtenir directement un élément satisfaisant le critère sans avoir à itérer exhaustivement sur une collection. Si plusieurs critères de recherche sont requis, il est possible de conserver plusieurs Map.
Par exemple si nous souhaitons indexer des livres selon leur titre, nous pouvons utiliser une HashMap<String, Livre>. Cela suppose qu'il n'existe qu'un seul livre possédant un titre donné. Nous pouvons également utiliser une TreeMap<String, Livre> qui dérive de SortedMap. Le coût d'utilisation est un peu plus élevé en pratique mais cela permet d'itérer dans l'ordre lexicographique des titres. Il est possible d'obtenir un itérateur sur les clés d'une Map avec keySet().iterator(), sur les valeurs avec values().iterator() ou alors un itérateur de couples clé-valeur avec entrySet().iterator() comme illustré ici :
SortedMap<String, Livre> m = ...; for (Map.Entry<String, Livre> e: m.entrySet()) System.out.println(e.getKey() + "=" + e.getValue());
Itérer sur des Map.Entry (couple de clé-valeur) induit une petite perte de performance car cela nécessite l'allocation des objets Map.Entry.
Essayons maintenant de créer un carnet de contacts téléphoniques que nous définissons ainsi (nous n'avons pas mis de getters afin de raccourcir le code) :
public class PhoneBook
{
public static class Contact
{
public final String name;
public final String number;
public PhoneBook(String name, String number)
{
this.name = name;
this.number = number;
}
@Override
public int hashCode() { return name.hashCode() + number.hashCode(); }
@Override
public boolean(Object obj)
{
if (!(obj instanceof Contact)) return false;
Contact con = (Contact)obj;
return name.equals(con.name) && number.equals(con.number);
}
}
private final SortedSet<Contact> contacts = new TreeSet<Contact>((x, y) -> x.number.compareTo(y.number));
private final Map<String, Contact> byName = new HashMap<String, Contact>();
...
}
byName est une Map permettant d'accéder aux contacts à partir de leur nom (là encore on suppose que le nom est unique). Ainsi on récupère un contact nommé "toto" avec byName.get("toto") ; la valeur de retour est nulle si aucun contact de ce nom est présent. Est-il utile auparavant de tester byName.containsKey("toto") pour savoir si la clé est présente dans la map ? Absolument pas, car cela duplique le travail de recherche de clé : un simple get suffit. La seule utilité de tester l'appartenance serait pour distinguer le cas de la présence d'une clé associée à une valeur nulle de son absence de la map. Mais en règle générale, on s'abstiendra de mettre des références nulles en tant que valeur dans une map (byName.put("toto", null)).
Nous avons également un ensemble contacts : lorsque nous ajoutons un contact, il est nécessaire de l'insérer à la fois dans byName et contacts (même remarque pour la suppression) : les deux structures doivent être cohérentes. Cela suppose l'unicité de nom et de numéro parmi les contacts. contacts est un ensemble trié avec un comparateur sous forme d'expression lambda comparant les numéros : deux contacts avec le même numéro sont égaux (la définition d'égalité est donc plus faible que celle d'equals() qui compare aussi le nom). L'avantage d'un SortedSet est qu'il est possible d'itérer dans l'ordre défini et même d'obtenir rapidement des sous-ensembles bornés par des objets donnés. Par exemple, affichons tous les contacts dont le numéro de téléphone est un numéro de mobile français (qui commencent par +336 ou +337) :
for (Contact c: contacts.subSet(new Contact("", "+336"), new Contact("", "+338")))
System.out.println(c)
Tous les contacts avec un mobile français sont affichés par ordre lexicographique du numéro. On a indiqué pour cela des contacts fictifs (le nom ne sert à rien pour la comparaison) servant de bornes pour le sous-ensemble ; la borne de fin est inclusive et la borne de fin est exclusive : ce sont donc bien les contacts de numéros supérieurs ou égaux à +336 et strictement inférieurs à +338 qui sont affichés.
SortedSet<T> dispose également de méthodes SortedSet<T> tailSet(T start) et SortedSet<T> headSet(T stop) permettant respectivement d'obtenir un sous-ensemble de fin ou de début du Set. Les méthodes T first() et T last() permettent d'obtenir le plus petit et le plus grand élément du Set.
Ajouter des informations à un objet
Imaginons que nous disposions d'une classe Livre contenant comme informations l'auteur et le titre du livre. Nous souhaitons ajouter comme donnée le prix d'un livre sans modifier la classe Livre. Il serait possible de dériver Livre pour créer un LivreAvecPrix en ajoutant un champ prix. Mais que faire lorsque le livre peut avoir différents prix selon le pays où il est vendu ? Une approche envisageable serait de créer une bibliothèque de livres pour chaque pays embarquant un Set<Livre> de livres ainsi qu'une Map<Livre, Integer> associant à chaque livre un prix. Pour ajouter un livre, on l'ajoute dans le Set. On est libre ensuite de lui associer un prix par un prixMap.put(livre, prix). Si l'on souhaite supprimer un livre, on l'enlève du Set avec la méthode remove(). Mais celui-ci reste en mémoire s'il est mentionné dans prixMap : le ramasse-miettes ne supprime un élément que si plus aucune référence accessible ne pointe vers lui. Il faut donc supprimer également manuellement le livre de la Map. Une autre solution est d'utiliser un WeakHashMap : cette classe implantant Map, son utilisation est exactement la même qu'une HashMap. En revanche son fonctionnement diffère : les clés sont considérées comme des références faibles. Or des références faibles pointant vers un objet ne s'opposent pas à la suppression de l'objet par le ramasse-miette. Pour s'en convaincre, on peut tester le code suivant :
Map<Livre, Integer> map = new HashMap<>();
Livre l1 = new Livre("Java, l'île mystérieuse", "Jules Javernes");
map.put(l1, 10);
l1 = null;
System.gc();
Thread.sleep(1000); // Attendons un peu que le ramasse-miettes fasse son travail
System.out.println(map.size());
La taille de la map affichée est 1 car elle contient le livre défini avec le prix associé. Si nous remplaçons new HashMap<>() par new WeakHashMap<>(), on constate que la taille affichée est de 0 car le livre n'étant plus référencé fortement, la clé sous forme de référence faible a été détruite dans la map. Ainsi WeakHashMap est particulièrement adapté pour étendre des objets en leur ajoutant des informations ou pour servir de cache sans faire obstacle au travail de nettoyage du ramasse-miettes.
Mélanger une liste
Il existe une méthode utilitaire statique de l'API dans la classe Collections pour mélanger une liste : Collections.shuffle(List<T> l). Voici un exemple d'utilisation pour obtenir une permutation aléatoire :
package fr.upem.jacosa.collections;
import java.util.*;
public class RandomPerm
{
public static void main(String[] args)
{
List<Integer> l = new ArrayList<Integer>();
final int n = Integer.parseInt(args[0]);
for (int i = 1; i <= n; i++)
l.add(i);
Collections.shuffle(l);
System.out.println(l);
}
}