 |
|
9) Stockage des objets |
|
|
|
|
| Texte original |
|
Traducteur :
Jérome Quelin |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
HashMap performance factors
|
|
Facteurs de performance d'un HashMap
|
|
|
|
To understand the issues, some
terminology is necessary:
|
|
Voici tout d'abord une terminologie nécessaire pour comprendre les mécanismes
mis en jeu :
|
|
|
|
Capacity:
The number of buckets in the table.
|
|
Capacité : Le nombre de seaux dans la
table.
|
|
|
|
Initial
capacity: The number of buckets when the table is created.
HashMap and HashSet: have constructors that allow you to specify
the initial capacity.
|
|
Capacité initiale : Le nombre de seaux dans la
table quand celle-ci est créée. Les HashMap et les HashSet
proposent des constructeurs qui permettent de spécifier la capacité initiale.
|
|
|
|
Size:
The number of entries currently in the table.
|
|
Taille : Le nombre courant d'entrées dans la
table.
|
|
|
|
Load
factor: size/capacity. A load factor of 0 is an empty table, 0.5
is a half-full table, etc. A lightly-loaded table will have few collisions and
so is optimal for insertions and lookups (but will slow down the process of
traversing with an iterator). HashMap and HashSet have
constructors that allow you to specify the load factor, which means that when
this load factor is reached the container will automatically increase the
capacity (the number of buckets) by roughly doubling it, and will redistribute
the existing objects into the new set of buckets (this is called
rehashing).
|
|
Facteur de charge : taille/capacité. Un facteur
de charge de 0 correspond à une table vide, 0.5 correspond à une table à moitié pleine, etc. Une
table faiblement chargée aura peu de collisions et sera donc optimale pour les insertions et les
recherches (mais ralentira le processus de parcours avec un itérateur). HashMap et
HashSet proposent des constructeurs qui permettent de spécifier un facteur de
charge, ce qui veut dire que lorsque ce facteur de charge est atteint le conteneur augmentera
automatiquement sa capacité (le nombre de seaux) en la doublant d'un coup, et redistribuera les
objets existants dans le nouvel ensemble de seaux (c'est ce qu'on appelle le
rehachage).
|
|
|
|
The default load factor used by
HashMap is 0.75 (it doesn’t rehash until the table is ¾ full).
This seems to be a good trade-off between time and space costs. A higher load
factor decreases the space required by the table but increases the lookup cost,
which is important because lookup is what you do most of the time (including
both get( ) and put( )).
|
|
Le facteur de charge par défaut utilisé par HashMap est
0.75 (il ne se rehache pas avant que la table ne soit aux ¾ pleine). Cette valeur est un bon
compromis entre les performances et le coût en espace. Un facteur de charge plus élevé réduit
l'espace requis par une table mais augmente le coût d'une recherche, ce qui est important parce que
les recherches sont les opérations les plus courantes (incluant les appels get()
et put()).
|
|
|
|
If you know that you’ll be storing
many entries in a HashMap, creating it with an appropriately large
initial capacity will prevent the overhead of automatic
rehashing.
|
|
Si un HashMap est destiné à recevoir beaucoup d'entrées,
le créer avec une grosse capacité initiale permettra d'éviter le surcoût du rehachage
automatique.
|
|
|
|
Overriding hashCode( )
|
|
Redéfinir hashCode()
|
|
|
|
Now that you understand what’s
involved in the function of the HashMap, the issues involved in writing a
hashCode( ) will make more
sense.
|
|
Maintenant que nous avons vu les processus impliqués dans le fonctionnement
d'un HashMap, les problèmes rencontrés dans l'écriture d'une
méthode hashCode() prennent tout leur sens.
|
|
|
|
First of all, you don’t have
control of the creation of the actual value that’s used to index into the
array of buckets. That is dependent on the capacity of the particular
HashMap object, and that capacity changes depending on how full the
container is, and what the load factor is. The value produced by your
hashCode( ) will be further processed in order to create the bucket
index (in SimpleHashMap the calculation is just a modulo by the size of
the bucket array).
|
|
Tout d'abord, on ne contrôle pas la valeur réellement utilisée pour indexer
le seau dans le tableau. Celle-ci est dépendante de la capacité de l'objet
HashMap, et cette capacité change suivant la taille et la charge du conteneur. La
valeur renvoyée par la méthode hashCode() est simplement utilisée pour calculer
l'index du seau (dans SimpleHashMap le calcul se résume à un modulo de la taille
du tableau de seaux).
|
|
|
|
The most important factor in creating a
hashCode( ) is that, regardless of when hashCode( ) is
called, it produces the same value for a particular object every time it is
called. If you end up with an object that produces one hashCode( )
value when it is put( ) into a HashMap, and another
during a get( ), you won’t be able to retrieve the objects. So
if your hashCode( ) depends on mutable data in the object the user
must be made aware that changing the data will effectively produce a different
key by generating a different hashCode( ).
|
|
Le facteur le plus important lors de la création d'une méthode
hashCode() est qu'elle doit toujours renvoyer la même valeur pour un objet
particulier, quel que soit le moment où hashCode() est appelée. Si on a un objet
dont la méthode hashCode() renvoie une valeur lors d'un put()
dans un HashMap, et une autre durant un appel à get(), on sera
incapable de retrouver cet objet. Si la méthode hashCode() s'appuie sur des
données modifiables dans l'objet, l'utilisateur doit alors être prévenu que changer ces données
produira une clef différente en générant un code de hachage différent.
|
|
|
|
In addition, you will probably not
want to generate a hashCode( ) that is based on unique object
information—in particular, the value of this makes a bad
hashCode( ) because then you can’t generate a new identical
key to the one used to put( ) the original key-value pair. This was
the problem that occurred in SpringDetector.java because the default
implementation of hashCode( ) does use the object address. So
you’ll want to use information in the object that identifies the object in
a meaningful way.
|
|
De plus, on ne veut pas non plus générer un code de hachage qui
soit basé uniquement sur des informations uniques spécifiques à l'instance de l'objet - en
particulier, la valeur de this est une mauvaise idée pour un code de hachage,
puisqu'on ne peut générer une nouvelle clef identique à celle utilisée pour stocker la paire
originale clef-valeur. C'est le problème que nous avons rencontré dans
SpringDetector.java parce que l'implémentation par défaut de
hashCode()utilise l'adresse de l'objet. Il faut donc utiliser des
informations de l'objet qui identifient l'objet d'une façon sensée.
|
|
|
|
One example is found in the String
class. Strings have the special characteristic that if a program has
several String objects that contain identical character sequences, then
those String objects all map to the same memory (the mechanism for this
is described in Appendix A). So it makes sense that the hashCode( )
produced by two separate instances of new String(“hello”)
should be identical. You can see it by running this program:
|
|
Un exemple en est trouvé dans la classe String. Les
Strings ont cette caractéristique spéciale : si un programme utilise
plusieurs objets String contenant la même séquence de caractères, alors ces objets
String pointent tous vers la même zone de mémoire (ce mécanisme est décrit dans
l'annexe A). Il semble donc sensé que le code de hachage produit par deux instances distinctes de
new String("hello") soit identique. On peut le vérifier avec ce petit
programme :
|
|
|
|
|
//: c09:StringHashCode.java
public class StringHashCode {
public static void main(String[] args) {
System.out.println("Hello".hashCode());
System.out.println("Hello".hashCode());
}
} ///:~
|
|
//: c09:StringHashCode.java
public class StringHashCode {
public static void main(String[] args) {
System.out.println("Hello".hashCode());
System.out.println("Hello".hashCode());
}
} ///:~
|
|
|
|
For this to work, the
hashCode( ) for String must be based on the contents of the
String.
|
|
Pour que ceci fonctionne, le code de hachage de String
doit être basé sur le contenu de la String.
|
|
|
|
So for a hashCode( ) to be
effective, it must be fast and it must be meaningful: that is, it must generate
a value based on the contents of the object. Remember that this value
doesn’t have to be unique—you should lean toward speed rather than
uniqueness—but between hashCode( ) and equals( )
the identity of the object must be completely resolved.
|
|
Pour qu'un code de hachage soit efficace, il faut donc qu'il soit rapide et
chargé de sens : c'est donc une valeur basée sur le contenu de l'objet. Rappelons que cette
valeur n'a pas à être unique - mieux vaut se pencher sur la vitesse que sur l'unicité - mais
l'identité d'un objet doit être complètement résolue entre hashCode() et
equals().
|
|
|
|
Because the hashCode( ) is
further processed before the bucket index is produced, the range of values is
not important; it just needs to generate an int.
|
|
Parce qu'un code de hachage est traité avant de produire un index de seau,
la plage de valeurs n'est pas importante ; il suffit de générer un int.
|
|
|
|
There’s one other factor: a good
hashCode( ) should result in an even distribution of values. If the
values tend to cluster, then the HashMap or HashSet will be more
heavily loaded in some areas and will not be as fast as it could be with an
evenly distributed hashing function.
|
|
Enfin, il existe un autre facteur : une méthode
hashCode() bien conçue doit renvoyer des valeurs bien distribuées. Si les valeurs
tendent à se regrouper, alors les HashMaps et les HashSets seront
plus chargés dans certaines parties et donc moins rapides que ce qu'ils pourraient être avec une
fonction de hachage mieux répartie.
|
|
|
|
Here’s an example that follows
these guidelines:
|
|
Voici un exemple qui respecte ces règles de base :
|
|
|
|
|
//: c09:CountedString.java
// Creating a good hashCode().
import java.util.*;
public class CountedString {
private String s;
private int id = 0;
private static ArrayList created =
new ArrayList();
public CountedString(String str) {
s = str;
created.add(s);
Iterator it = created.iterator();
// Id is the total number of instances
// of this string in use by CountedString:
while(it.hasNext())
if(it.next().equals(s))
id++;
}
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode() + "\n";
}
public int hashCode() {
return s.hashCode() * id;
}
public boolean equals(Object o) {
return (o instanceof CountedString)
&& s.equals(((CountedString)o).s)
&& id == ((CountedString)o).id;
}
public static void main(String[] args) {
HashMap m = new HashMap();
CountedString[] cs = new CountedString[10];
for(int i = 0; i < cs.length; i++) {
cs[i] = new CountedString("hi");
m.put(cs[i], new Integer(i));
}
System.out.println(m);
for(int i = 0; i < cs.length; i++) {
System.out.print("Looking up " + cs[i]);
System.out.println(m.get(cs[i]));
}
}
} ///:~
|
|
//: c09:CountedString.java
// Créer une bonne méthode hashCode().
import java.util.*;
public class CountedString {
private String s;
private int id = 0;
private static ArrayList created =
new ArrayList();
public CountedString(String str) {
s = str;
created.add(s);
Iterator it = created.iterator();
// id est le nombre total d'instances de cette
// chaîne utilisées par CountedString :
while(it.hasNext())
if(it.next().equals(s))
id++;
}
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode() + "\n";
}
public int hashCode() {
return s.hashCode() * id;
}
public boolean equals(Object o) {
return (o instanceof CountedString)
&& s.equals(((CountedString)o).s)
&& id == ((CountedString)o).id;
}
public static void main(String[] args) {
HashMap m = new HashMap();
CountedString[] cs = new CountedString[10];
for(int i = 0; i < cs.length; i++) {
cs[i] = new CountedString("hi");
m.put(cs[i], new Integer(i));
}
System.out.println(m);
for(int i = 0; i < cs.length; i++) {
System.out.print("Looking up " + cs[i]);
System.out.println(m.get(cs[i]));
}
}
} ///:~
|
|
|
|
CountedString includes a
String and an id that represents the number of
CountedString objects that contain an identical String. The
counting is accomplished in the constructor by iterating through the static
ArrayList where all the Strings are stored.
|
|
CountedString inclut une String et un
id représentant le nombre d'objets CountedString contenant une
String identique. Le compte est réalisé dans le constructeur en parcourant la
static ArrayList où toutes les Strings sont stockées.
|
|
|
|
Both hashCode( ) and
equals( ) produce results based on both fields; if they were just
based on the String alone or the id alone there would be duplicate
matches for distinct values.
|
|
Les méthodes hashCode() et equals()
renvoient des résultats basés sur les deux champs ; si elles étaient basées juste sur la
String ou sur l'id, il y aurait eu des doublons pour des valeurs
distinctes.
|
|
|
|
Note how simple the
hashCode( ) is: String’s hashCode( ) is
multiplied by the id. Smaller is generally better (and faster) for
hashCode( ).
|
|
Notez comme la fonction de hachage est simple : le code de hachage de
la String multiplié par l'id. Généralement, la qualité et la
rapidité d'une fonction de hachage est inversement proportionnelle à sa taille.
|
|
|
|
In main( ), a bunch of
CountedString objects are created, using the same String to show
that the duplicates create unique values because of the count id. The
HashMap is displayed so that you can see how it is stored internally (no
discernible orders) and then each key is looked up individually to demonstrate
that the lookup mechanism is working
properly.
|
|
Dans main(), un ensemble d'objets
CountedString est créé, en utilisant la même String pour montrer
que les doublons créent des valeurs uniques grâce au compteur id. Le
HashMap est affiché afin de voir son organisation interne (aucun ordre n'est
discernable) ; chaque clef est alors recherchée individuellement pour démontrer que le
mécanisme de recherche fonctionne correctement.
|
|
|
|
Holding references
|
|
Stocker des références
|
|
|
|
The java.lang.ref library contains
a set of classes that allow greater flexibility in garbage collection, which are
especially useful when you have large objects that may cause memory exhaustion.
There are three classes inherited from the abstract class
Reference:
SoftReference,
WeakReference, and
PhantomReference. Each of these provides a different
level of indirection for the garbage collector, if the object in question is
only reachable through one of these Reference objects.
|
|
La bibliothèque java.lang.ref contient un ensemble de
classes qui permettent une plus grande flexibilité dans le nettoyage des objets, et qui se révèlent
particulièrement pratiques lorsqu'on a de gros objets qui peuvent saturer la mémoire. Il y a trois
classes dérivées de la classe abstraite Reference
: SoftReference, WeakReference
et PhantomReference. Chacune d'entre elles fournit un niveau différent
d'abstraction au ramasse miettes, si l'objet en question n'est accessible qu'à travers un
de ces objets Reference.
|
|
|
|
If an object is
reachable it means that
somewhere in your program the object can be found. This could mean that you have
an ordinary reference on the stack that goes right to the object, but you might
also have a reference to an object that has a reference to the object in
question; there could be many intermediate links. If an object is reachable, the
garbage collector cannot release it because it’s still in use by your
program. If an object isn’t reachable, there’s no way for your
program to use it so it’s safe to garbage-collect that
object.
|
|
Si un objet est accessible cela veut dire que l'objet peut
être trouvé quelque part dans le programme. Ceci peut vouloir dire qu'on a une référence ordinaire
sur la pile qui pointe directement sur l'objet, mais on peut aussi avoir une référence sur un objet
qui possède une référence sur l'objet en question ; il peut y avoir de nombreux liens
intermédiaires. Si un objet est accessible, le ramasse miettes ne peut pas le nettoyer parce qu'il
est toujours utilisé par le programme. Si un objet n'est pas accessible, le programme ne dispose
d'aucun moyen pour y accéder et on peut donc nettoyer cet objet tranquillement.
|
|
|
|
You use Reference objects when you
want to continue to hold onto a reference to that object—you want to be
able to reach that object—but you also want to allow the garbage collector
to release that object. Thus, you have a way to go on using the object, but if
memory exhaustion is imminent you allow that object to
be released.
|
|
On utilise des objets Reference quand on veut continuer à
stocker une référence sur cet objet - on veut être capable d'atteindre cet objet - mais on veut
aussi permettre au ramasse miettes de nettoyer cet objet. Il s'agit donc d'un moyen permettant de
continuer à utiliser l'objet, mais si la saturation de la mémoire est imminente, on permet que
cet objet soit nettoyé.
|
|
|
|
You accomplish this by using a
Reference object as an intermediary between you and the ordinary
reference, and there must be no ordinary references to the object (ones
that are not wrapped inside Reference objects). If the garbage collector
discovers that an object is reachable through an ordinary reference, it will not
release that object.
|
|
Un objet Reference sert donc d'intermédiaire entre le
programme et la référence ordinaire, et aucune référence ordinaire sur cet objet ne doit
exister (mis à part celles encapsulées dans les objets Reference). Si le ramasse
miette découvre qu'un objet est accessible à travers une référence ordinaire, il ne nettoiera pas
cet objet.
|
|
|
|
In the order SoftReference,
WeakReference, and PhantomReference, each one is “weaker”
than the last, and corresponds to a different level of reachability. Soft
references are for implementing memory-sensitive caches. Weak references are for
implementing “canonicalizing mappings”—where instances of
objects can be simultaneously used in multiple places in a program, to save
storage—that do not prevent their keys (or values) from being reclaimed.
Phantom references are for scheduling pre-mortem cleanup actions in a more
flexible way than is possible with the Java finalization
mechanism.
|
|
Dans l'ordre SoftReference, WeakReference
et PhantomReference, chacune d'entre elles est « plus faible » que la
précédente, et correspond à un niveau différent d'accessibilité. Les références douces
(SoftReferences) permettent d'implémenter des caches concernés par les problèmes
de mémoire. Les références faibles (WeakReferences) sont destinées à implémenter
des « mappages canoniques » - où des instances d'objets peuvent être utilisées
simultanément dans différents endroits du programme, pour économiser le stockage - qui n'empêchent
pas leurs clefs (ou valeurs) d'être nettoyées. Les références fantômes
(PhantomReferences) permettent d'organiser les actions de nettoyage pre-mortem
d'une manière plus flexible que ce qui est possible avec le mécanisme de finalisation de
Java.
|
|
|
|
With SoftReferences and
WeakReferences, you have a choice about whether to place them on a
ReferenceQueue (the device used for premortem cleanup actions), but a
PhantomReference can only be built on a ReferenceQueue.
Here’s a simple demonstration:
|
|
Pour les SoftReferences et les
WeakReferences, on peut choisir de les stocker dans une
ReferenceQueue (le dispositif utilisé pour les actions de nettoyage pre-mortem) ou
non, mais une PhantomReference ne peut être créée que dans une
ReferenceQueue. En voici la démonstration :
|
|
|
|
|
//: c09:References.java
// Demonstrates Reference objects
import java.lang.ref.*;
class VeryBig {
static final int SZ = 10000;
double[] d = new double[SZ];
String ident;
public VeryBig(String id) { ident = id; }
public String toString() { return ident; }
public void finalize() {
System.out.println("Finalizing " + ident);
}
}
public class References {
static ReferenceQueue rq= new ReferenceQueue();
public static void checkQueue() {
Object inq = rq.poll();
if(inq != null)
System.out.println("In queue: " +
(VeryBig)((Reference)inq).get());
}
public static void main(String[] args) {
int size = 10;
// Or, choose size via the command line:
if(args.length > 0)
size = Integer.parseInt(args[0]);
SoftReference[] sa =
new SoftReference[size];
for(int i = 0; i < sa.length; i++) {
sa[i] = new SoftReference(
new VeryBig("Soft " + i), rq);
System.out.println("Just created: " +
(VeryBig)sa[i].get());
checkQueue();
}
WeakReference[] wa =
new WeakReference[size];
for(int i = 0; i < wa.length; i++) {
wa[i] = new WeakReference(
new VeryBig("Weak " + i), rq);
System.out.println("Just created: " +
(VeryBig)wa[i].get());
checkQueue();
}
SoftReference s = new SoftReference(
new VeryBig("Soft"));
WeakReference w = new WeakReference(
new VeryBig("Weak"));
System.gc();
PhantomReference[] pa =
new PhantomReference[size];
for(int i = 0; i < pa.length; i++) {
pa[i] = new PhantomReference(
new VeryBig("Phantom " + i), rq);
System.out.println("Just created: " +
(VeryBig)pa[i].get());
checkQueue();
}
}
} ///:~
|
|
//: c09:References.java
// Illustre les objets Reference.
import java.lang.ref.*;
class VeryBig {
static final int SZ = 10000;
double[] d = new double[SZ];
String ident;
public VeryBig(String id) { ident = id; }
public String toString() { return ident; }
public void finalize() {
System.out.println("Finalizing " + ident);
}
}
public class References {
static ReferenceQueue rq= new ReferenceQueue();
public static void checkQueue() {
Object inq = rq.poll();
if(inq != null)
System.out.println("In queue: " +
(VeryBig)((Reference)inq).get());
}
public static void main(String[] args) {
int size = 10;
// La taille peut être choisie via la ligne de commande :
if(args.length > 0)
size = Integer.parseInt(args[0]);
SoftReference[] sa = new SoftReference[size];
for(int i = 0; i < sa.length; i++) {
sa[i] = new SoftReference(
new VeryBig("Soft " + i), rq);
System.out.println("Just created: " +
(VeryBig)sa[i].get());
checkQueue();
}
WeakReference[] wa = new WeakReference[size];
for(int i = 0; i < wa.length; i++) {
wa[i] = new WeakReference(
new VeryBig("Weak " + i), rq);
System.out.println("Just created: " +
(VeryBig)wa[i].get());
checkQueue();
}
SoftReference s = new SoftReference(
new VeryBig("Soft"));
WeakReference w = new WeakReference(
new VeryBig("Weak"));
System.gc();
PhantomReference[] pa = new PhantomReference[size];
for(int i = 0; i < pa.length; i++) {
pa[i] = new PhantomReference(
new VeryBig("Phantom " + i), rq);
System.out.println("Just created: " +
(VeryBig)pa[i].get());
checkQueue();
}
}
} ///:~
|
|
|
|
When you run this program (you’ll
want to pipe the output through a “more” utility so that you can
view the output in pages), you’ll see that the objects are
garbage-collected, even though you still have access to them through the
Reference object (to get the actual object reference, you use
get( )). You’ll also see that the ReferenceQueue always
produces a Reference containing a null object. To make use of
this, you can inherit from the particular Reference class you’re
interested in and add more useful methods to the new type of
Reference.
|
|
Quand on lance ce programme (vous voudrez probablement piper la sortie à
travers un utilitaire « more » afin de pouvoir l'observer page par page), on verra que
les objets sont récupérés par le ramasse miettes, même si on a toujours accès à eux à travers les
objets Reference (pour obtenir la référence réelle sur l'objet, il faut utilise la
méthode get()). On notera aussi que ReferenceQueue renvoie
toujours une Reference contenant un objet null. Pour utiliser les
références, on peut dériver la classe Reference particulière qui nous intéresse et
ajouter des méthodes au nouveau type de Reference.
|
|
|
|
The WeakHashMap
|
|
Le WeakHashMap
|
|
|
|
The containers library has a special
Map to hold weak references: the
WeakHashMap. This class is designed to make the
creation of canonicalized mappings easier. In such a mapping, you are saving
storage by making only one instance of a particular value. When the program
needs that value, it looks up the existing object in the mapping and uses that
(rather than creating one from scratch). The mapping may make the values as part
of its initialization, but it’s more likely that the values are made on
demand.
|
|
La bibliothèque de conteneurs propose une Map spéciale
pour stocker les références faibles : le WeakHashMap. Cette classe est
conçue pour faciliter la création de mappages canoniques. Dans de tels mappages, on économise sur
le stockage en ne créant qu'une instance d'une valeur particulière. Quand le programme a besoin de
cette valeur, il recherche l'objet existant dans le mappage et l'utilise (plutôt que d'en créer un
complètement nouveau). Le mappage peut créer les valeurs comme partie de son initialisation, mais
il est plus courant que les valeurs soient créées à la demande.
|
|
|
|
Since this is a storage-saving technique,
it’s very convenient that the WeakHashMap allows the garbage
collector to automatically clean up the keys and values. You don’t have to
do anything special to the keys and values you want to place in the
WeakHashMap; these are automatically wrapped in WeakReferences by
the map. The trigger to allow cleanup is if the key is no longer in use, as
demonstrated here:
|
|
Puisqu'il s'agit d'une technique permettant d'économiser sur le stockage,
il est très pratique que le WeakHashMap autorise le ramasse miettes à nettoyer
automatiquement les clefs et les valeurs. Aucune opération particulière n'est nécessitée sur les
clefs et les valeurs qu'on veut placer dans le WeakHashMap ; ils sont
automatiquement encapsulés dans des WeakReferences par le
WeakHashMap. Le déclenchement qui autorise le nettoyage survient lorsque la clef
n'est plus utilisée, ainsi que démontré dans cet exemple :
|
|
|
|
|
//: c09:CanonicalMapping.java
// Demonstrates WeakHashMap.
import java.util.*;
import java.lang.ref.*;
class Key {
String ident;
public Key(String id) { ident = id; }
public String toString() { return ident; }
public int hashCode() {
return ident.hashCode();
}
public boolean equals(Object r) {
return (r instanceof Key)
&& ident.equals(((Key)r).ident);
}
public void finalize() {
System.out.println("Finalizing Key "+ ident);
}
}
class Value {
String ident;
public Value(String id) { ident = id; }
public String toString() { return ident; }
public void finalize() {
System.out.println("Finalizing Value "+ident);
}
}
public class CanonicalMapping {
public static void main(String[] args) {
int size = 1000;
// Or, choose size via the command line:
if(args.length > 0)
size = Integer.parseInt(args[0]);
Key[] keys = new Key[size];
WeakHashMap whm = new WeakHashMap();
for(int i = 0; i < size; i++) {
Key k = new Key(Integer.toString(i));
Value v = new Value(Integer.toString(i));
if(i % 3 == 0)
keys[i] = k; // Save as "real" references
whm.put(k, v);
}
System.gc();
}
} ///:~
|
|
//: c09:CanonicalMapping.java
// Illustre les WeakHashMaps.
import java.util.*;
import java.lang.ref.*;
class Key {
String ident;
public Key(String id) { ident = id; }
public String toString() { return ident; }
public int hashCode() {
return ident.hashCode();
}
public boolean equals(Object r) {
return (r instanceof Key)
&& ident.equals(((Key)r).ident);
}
public void finalize() {
System.out.println("Finalizing Key "+ ident);
}
}
class Value {
String ident;
public Value(String id) { ident = id; }
public String toString() { return ident; }
public void finalize() {
System.out.println("Finalizing Value "+ident);
}
}
public class CanonicalMapping {
public static void main(String[] args) {
int size = 1000;
// La taille peut être choisie via la ligne de commande :
if(args.length > 0)
size = Integer.parseInt(args[0]);
Key[] keys = new Key[size];
WeakHashMap whm = new WeakHashMap();
for(int i = 0; i < size; i++) {
Key k = new Key(Integer.toString(i));
Value v = new Value(Integer.toString(i));
if(i % 3 == 0)
keys[i] = k; // Save as "real" references
whm.put(k, v);
}
System.gc();
}
} ///:~
|
|
|
|
The Key class must have a
hashCode( ) and an equals( ) since it is being used as a
key in a hashed data structure, as described previously in this
chapter.
|
|
La classe Key doit fournir les méthodes
hashCode() et equals() puisqu'elle est utilisée comme clef dans
une structure de données hachée, comme décrit précédemment dans ce chapitre.
|
|
|
|
When you run the program you’ll see
that the garbage collector will skip every third key, because an ordinary
reference to that key has also been placed in the keys array and thus
those objects cannot be
garbage-collected.
|
|
Quand on lance le programme, on s'aperçoit que le ramasse miettes évite une
clef sur trois, parce qu'une référence ordinaire sur cette clef a aussi été placée dans le tableau
keys et donc ces objets ne peuvent être nettoyés.
|
|
|
|
Iterators revisited
|
|
Les itérateurs revisités
|
|
|
|
We can now demonstrate the true power of
the Iterator: the ability to separate the
operation of traversing a sequence from the underlying structure of that
sequence. In the following example, the class PrintData uses an
Iterator to move through a sequence and call the
toString( ) method for every object. Two
different types of containers are created—an
ArrayList and a
HashMap—and they are each filled with,
respectively, Mouse and Hamster objects. (These classes are
defined earlier in this chapter.) Because an Iterator hides the structure
of the underlying container, PrintData doesn’t know or care what
kind of container the Iterator comes from:
|
|
Nous pouvons maintenant démontrer la vraie puissance
d'un Iterator : la capacité de séparer l'opération de parcourir une
séquence de la structure sous-jacente de cette séquence. Dans l'exemple suivant, la classe
PrintData utilise un Iterator pour se déplacer à travers une
séquence et appelle la méthode toString() pour chaque objet. Deux types de
conteneurs différents sont créés - une ArrayList et
un HashMap - et remplis, respectivement, avec des objets
Mouse et Hamster (ces classes ont été définies précédemment dans
ce chapitre). Parce qu'un Iterator cache la structure sous-jacente du conteneur
associé, PrintData ne se soucie pas du type de conteneur dont
l'Iterator provient :
|
|
|
|
|
//: c09:Iterators2.java
// Revisiting Iterators.
import java.util.*;
class PrintData {
static void print(Iterator e) {
while(e.hasNext())
System.out.println(e.next());
}
}
class Iterators2 {
public static void main(String[] args) {
ArrayList v = new ArrayList();
for(int i = 0; i < 5; i++)
v.add(new Mouse(i));
HashMap m = new HashMap();
for(int i = 0; i < 5; i++)
m.put(new Integer(i), new Hamster(i));
System.out.println("ArrayList");
PrintData.print(v.iterator());
System.out.println("HashMap");
PrintData.print(m.entrySet().iterator());
}
} ///:~
|
|
//: c09:Iterators2.java
// Les Iterators revisités.
import java.util.*;
class PrintData {
static void print(Iterator e) {
while(e.hasNext())
System.out.println(e.next());
}
}
class Iterators2 {
public static void main(String[] args) {
ArrayList v = new ArrayList();
for(int i = 0; i < 5; i++)
v.add(new Mouse(i));
HashMap m = new HashMap();
for(int i = 0; i < 5; i++)
m.put(new Integer(i), new Hamster(i));
System.out.println("ArrayList");
PrintData.print(v.iterator());
System.out.println("HashMap");
PrintData.print(m.entrySet().iterator());
}
} ///:~
|
|
|
|
|
|
|
|
|
|
|
|
|
