www.infkoffler.com - Site de cours d'informatique

Accueil

Java Standard Edition

Java EE 5

Visual Basic .Net 2005

Cours Javascript - DOM - DHTML

Nouveautés sur le site

Contacts

Accueil > Java Standard Edition > Les collections(8): HashMap(java.util)

____________________________________________________________________________________________________

Connexion

Les collections(8): HashMap(java.util)

Sommaire :

I) L'implémentation de la classe HashMap (java.util)
  I.1) Les attributs privés de HashMap
  I.2) Les constructeurs
  I.3) La classe interne static (friendly) HashMap.Entry
(Suite dans une autre page)
I.4) Les méthodes de HashMap
  I.4.A) put(K key, V value)
  I.4.B) get(Object key)
  I.4.C) (non public) resize()

En résumé:

HashMap est une map basée sur une table de hachage. HashMap permet les opérations optionnelles(put, etc).
Et elle permet les valeurs null et la clé null (ces deux points ne sont pas autorisés dans Hashtable).
La classe HashMap est en gros équivalent à hashtable, sauf qu'elle n'est pas synchronisée. Elle est apparue avec le framework de collections, au contraire de Hashtable(java.util) qui est là depuis le JDK 1.0 ( d'ailleurs Hashtable a été réajustée pour implémenter l'interface Map, lors de l'apparition du framework de collections avec le JDK 1.2, aussi elle est devenue un membre du framework de collections).

I) L'implémentation de la classe HashMap (java.util)

HashMap hérite de AbstractMap, ce qui se conçoit facilement: elle se sert de l'implémentation minimale fournie qu'est AbstractMap.
Et elle implémente Map, Cloneable et Serializable, que nous avons déjà vu.

I.1) Les attributs privés de HashMap

/**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

/**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

/**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     */
    int threshold;

/**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;

/**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    transient volatile int modCount;

Les trois premiers attributs sont des constantes statiques (elles sont d'ailleurs en majuscules), et ils sont friendly(visible uniquement dans le package java.util).
int DEFAULT_INITIAL_CAPACITY, c'est la grandeur initiale du tableau interne par défaut, 16(entrées) ici, il doit être une puissance de 2.

int MAXIMUM_CAPACITY, par défaut vaut 1<<30, c'est la capacité maximale. Elle doit être une puissance de 2. Ici 1<<30 = 2 puissance 30 = 1 073 741 824(plus d'un milliard).

float DEFAULT_LOAD_FACTOR, est le facteur de chargement par défaut, et vaut 0.75f. Le facteur de chargement(load factor) est utilisé pour calculer le seuil à partir duquel il vaut redimensionner le tableau interne. La formule appliquée pour calculer le seuil (threshold) est capacity * load factor. C'est-à-dire qu'ici, dès que la taille(size) atteint le seuil, on redimensionne (resize) le tableau interne "table". En bref, dès que la taille atteint les 3 quarts de la capacité, on agrandit le tableau.

L'attribut table est un tableau de HashMap.Entry( qui elle-même est une classe static interne friendly héritant de Map.Entry<K,V>) ). C'est le tableau interne, et contient par conséquent les données de la collection. Il est friendly. La longueur de ce tableau(length) doit toujours être une puissance de 2.
La table est redimensionnée si nécessaire.
La propriété table est transient(sa valeur n'est pas sérialisée). Ceci peut paraître étonnant. Ainsi, cela force à sérialiser en utilisant la méthode writeObject de HashMap, qui va "présenter" à sa manière l'écriture des valeurs de l'objet. Et non pas à sérialiser en utilisant ObjectOutputStream.
Comme on aurait pu le croire, nous verrons que la table ne contient pas, dans chacun de ses indexs, chacune des entrées. Sa longueur n'est donc pas le nombre d'entrées. C'est plus complexe que cela. La table est en réalité une table de listes chaînées d'entrées. Dans chaque index de la table, appelé bucket(seau), il y a la référence de la première entrée d'une liste chaînée d'entrées. Toutes les entrées d'une liste chaînée ont un point commun au niveau de leur hash, que nous verrons plus tard. Le tableau contient donc n listes chaînées d'entrées, avec n = table.length.
Nous verrons tout cela dans les prochains chapitres.

L'attribut size représente le nombre d'entrées(paires clé/valeur) dans table.
Remarquons aussi que cette valeur importante est aussi transient.

La propriété int threshold est le seuil dont nous avons déjà parlé.

final float loadFactor est le load factor.

Enfin modCount est classique(compte le nombre de modifications structurelles de la table qui ont eu lieu).

I.2) Les constructeurs

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

// Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
    }
(...)
void init() {
    }

Ce constructeur prend deux paramètres, la capacité initiale, et le loadfactor.
Il effectue d'abord les tests de validité de initialCapacity, puis de loadFactor. En cas de problème de validité, on déclenche une IllegalArgumentException(java.lang).
Ensuite, grâce à la boucle while, on cherche une capacity qui soit <= à la capacité en paramètre, et qui soit une puissance de 2.
Enfin, on cherche la puissance 2 la plus proche(mais pas supérieure) de la capacité voulue par l'utilisateur. Pour cela, on effectue une boucle, qui permet de se rapprocher de plus en plus de la valeur recherchée, grâce à un décalage de une position vers la gauche, ce qui revient à multiplier par 2.
Il ne reste plus ensuite qu'à attribuer aux attributs les valeurs obtenues: loadFactor, threshold( capacity trouvée * loadFactor). Et l'attribut table, en créant un tableau de HashMap.Entry, et de taille capacity.
Tout à la fin, on appelle la méthode init(), qui procède aux initialisations supplémentaires voulues, et qui est vide pour HashMap. Grâce à init(), les classes filles peuvent procéder à des initialisations, simplement en la redéfinissant.
Cette technique est intéressante.
Le constructeur sans paramètre construit une hash map vide, et initialisée avec les valeurs par défaut: 16 pour la capacité, et 0.75 pour le load factor.
C'est un des deux constructeurs requis dans les spécifications de l'interface Map.
Voici le deuxième constructeur requis par Map.
Il prend en paramètre une Map, dont les clés doivent être des sous-classes de K( ou K lui-même bien sûr), et dont les valeurs doivent être des sous-classes de V.
On crée une hash map vide. On choisit comme capacity:
capacity = (size/load factor)+1 , ce qui veut dire capacity-1 = size/loadfactor
(capacity-1)*loadfactor = size
On a choisi capacity, de tel manière à être sûr qu'elle dépasse le seuil. On sait que capacity-1 atteint le seuil d'après l'équation. On est certain alors que capacity dépasse le seuil.
Si la capacity trouvée n'atteint pas le DEFAULT_INITIAL_CAPACITY, on prend ce dernier comme capacité.
Il ne reste plus alors qu'à rajouter dans la map créée, toutes les entrées de la map source.
C'est une méthode privée, qui parcourt la map source grâce à l'itérateur de la vue entry set.
Pour chaque entrée, on crée une entrée correspondante dans notre map, grâce à la méthode privée putForCreate(clé, valeur)
On apprend dans la javadoc que cette méthode est utilisée par les constructeurs(et les pseudo-constructeurs), car elle va directement à l'essentiel, et ne fait pas des actions inutiles dans notre cas, comme des redimensionnements éventuels(on sait qu'on n'en n'aura pas à faire).

Elle appelle, elle-même, la méthode privée createEntry:
Elle crée uniquement un nouvel objet Entry, avec la clé et la valeur données.
Comme pour putForCreate(K key, V value), "This version needn't worry about resizing the table"( cette version ne se préoccupe pas de redimensionner la table).

I.3) La classe interne static (friendly) HashMap.Entry

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

/**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

public final K getKey() {
            return key;
        }

public final V getValue() {
            return value;
        }

public final V setValue(V newValue) {
	    V oldValue = value;
            value = newValue;
            return oldValue;
        }

public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

public final int hashCode() {
            return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

public final String toString() {
            return getKey() + "=" + getValue();
        }

/**
         * This method is invoked whenever the value in an entry is
         * overwritten by an invocation of put(k,v) for a key k that's already
         * in the HashMap.
         */
        void recordAccess(HashMap<K,V> m) {
        }

/**
         * This method is invoked whenever the entry is
         * removed from the table.
         */
        void recordRemoval(HashMap<K,V> m) {
        }
    }

HashMap propose une classe Entry, car elle doit créer des objets Entry. De plus, HashMap.Entry doit avoir la particularité de permettre de construire une liste chaînée d'entrées, c'est-à-dire de posséder un attribut next, qui pointe sur la prochaine entrée.
Bien entendu, elle implémente Map.Entry<K, V>

Regardons ses attributs privés:
La valeur de la clé, pour cette entrée, une constante.
La valeur associée à cette clé.
next contient l'entrée suivante, cela permet de faire une liste chaînée d'entrées.
Enfin hash, un int, contient le hashcode pour cette entrée, et est en constante. Cela permet de retenir le hashcode de l'entrée, afin de ne pas avoir à le recalculer à chaque fois. En effet, à chaque recherche, on le sollicitera.

La classe possède un unique constructeur, à quatre paramètres, qui initialisera directement les quatre attributs: la clé, la valeur, l'entrée suivante, et le hash.

I.4) Les méthodes de HashMap
  I.4.A) put(K key, V value)
  I.4.B) get(Object key)
  I.4.C) (non public) resize()

RETOUR HAUT