coût des méthodes prédéfinies HashMap

**Lamickal** · 31/05/2009, 14h00

Bonjour,

Dans le cadre d'un projet, je cherche à connaître les ordres de grandeur des coûts temporels des méthodes prédéfinies qui s'appliquent à l'implémentation HashMap.

Ainsi, j'ai trouvé sur l'api fournie par Sun (http://java.sun.com/javase/6/docs/ap...l/HashMap.html) que put et get s'effectuaient en temps constant.
Par ailleurs, il est également indiqué

Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).

Mais quelles sont les méthodes concernées par cette phrase ?
Qu'en est-il des méthodes isEmpty, containsKey, keySet, remove (je n'ai réussi qu'à faire des hypothèses, mais sans certitude) ?

Sinon, si vous savez où trouver ce genre d'informations en général quand elle ne sont par l'api fournie par Sun, je suis preneur.

Merci d'avance !

**Fmunch** · 02/06/2009, 10h18

Toutes les méthodes, sauf les insertion qui peuvent engendrer un redimensionnement du tableau ce qui équivaut à une copie de celui-ci cependant celle-ci sont rare.

http://fr.wikipedia.org/wiki/Table_de_hachage

Cependant c'est plus une question d'algo que tu pose plutôt qu'une question spécifique à java.

Les méthodes qui te renvoient un tableau, une liste contenant toutes les données de la hashtable, ont bien entendu un coups proportionnelle au nombre de données : il faut créer une structure de données à côté.

Note cependant que ce qui va être copier c'est les références et pas les données elles même. Il en va de même si tu fessais un trie de chaîne de caractères, c'est les références qui sont ordonné en fonction du contenu des chaînes de caractères.

**tchize_** · 02/06/2009, 10h50

isEmpty: Temps 1:

Code sun :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 	    public boolean isEmpty() { &nbsp;&nbsp;&nbsp;&nbsp;return size() == 0;
    }

containsKey: Temps n, n étant la taille de la hashtable

Code sun :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 	public boolean containsKey(Object key) {         return getEntry(key) != null;
    }       final Entry<K,V> getEntry(Object key) {         int hash = (key == null) ? 0 : hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {             Object k;             if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))                 return e;
        }         return null;
    }

keySet: Temps 1

Code sun :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 	    public Set<K> keySet() {         Set<K> ks = keySet;         return (ks != null ? ks : (keySet = new KeySet()));
    }

remove: Temps n+m, n étant le nombre d'entrées dans la table, m étant le nombre d'éléments par entrée de la table

Code sun :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public V remove(Object key) {
    Iterator<Entry<K,V>> i = entrySet().iterator();
    Entry<K,V> correctEntry = null;
    if (key==null) {
        while (correctEntry==null && i.hasNext()) {
        Entry<K,V> e = i.next();
        if (e.getKey()==null)
            correctEntry = e;
        }
    } else {
        while (correctEntry==null && i.hasNext()) {
        Entry<K,V> e = i.next();
        if (key.equals(e.getKey()))
            correctEntry = e;
        }
    }
 
    V oldValue = null;
    if (correctEntry !=null) {
        oldValue = correctEntry.getValue();
        i.remove();
    }
    return oldValue;
    }
 
 
final Entry<K,V> removeMapping(Object o) {
        if (!(o instanceof Map.Entry))
            return null;
 
        Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
        Object key = entry.getKey();
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
 
        while (e != null) {
            Entry<K,V> next = e.next;
            if (e.hash == hash && e.equals(entry)) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
 
        return e;
    }

Etc, pour les autre méthodes. Suivre le code source de sun.

**Lamickal** · 02/06/2009, 20h46

Bonjour,

Merci Fmunch pour cette réponse, même s'il y a quand même des spécificités algorithmiques liées au langage (par exemple : mémorisation du nombre d'éléments dans une variable, manière d'optimiser la recherche, ou encore le passage par référence).

Merci tchize_, c'est exactement ce que je cherchais. Il ne me reste qu'une question : le code sun se trouve-t-il sur le site de sun (car je ne l'y ai pas trouvé) ?

**tchize_** · 02/06/2009, 20h58

fourni avec le jdk. La pluspart des IDE sont capable de l'afficher. Par exemple, sur eclipse, tu fait ctrl + alt + h, tu tappe hashmap et enter

**Uther** · 02/06/2009, 22h43

Les sources sons normalement contenues dans un fichier src.zip dans le répertoire du JDK

**Fmunch** · 03/06/2009, 00h41

tchize_ :

Le temps de recherche espéré est en temps constant : on espère que l'on a pas de longue liste chainé, on parle aussi de cas moyen. C'est uniquement dans le pire des cas qu'il est proportionnelle à n. Dans ce as il faut sérieusement envisagé de changer de fonction de hashage. Il existe aussi des structure de tableau associatif tels que les arbre binaire qui eux reposent sur la possibilité d'ordonner les éléments, c'est les TreeMap, et les TreeSet

remove : le temps est celui que l'on met à trouver l'élément, on le retire ensuite de la liste chaîné. Voici le code de openJDK 1.7, il réalise la même chose que le code présenté par tchize_ :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
         public synchronized boolean containsKey(Object key) {
             Entry tab[] = table;
             int hash = key.hashCode();
             int index = (hash & 0x7FFFFFFF) % tab.length;
             for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
                 if ((e.hash == hash) && e.key.equals(key)) {
                     return true;
                 }
             }
             return false;
         }

on calcul l'index à l'aide de la fonction de hashage, dont on calcul le reste par division entière par la longueur du tableau, on extrait la valeur tab[index], puis on boucle sur la liste chainé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
         private static class Entry<K,V> implements Map.Entry<K,V> {
            int hash;
            K key;
            V value;
            Entry<K,V> next;
            .....

Le dernier élément est null, c'est la que l'on s'arrête, si l'on insère des éléments en plus on les insère à la fin :

cf : public synchronized V put(K key, V value) {

maintenant il est tard, et je vous souhaite un bon et agréable RTFM. Par contre pour le keySet() je pense que à raison, c'est juste une autre représentation de l'ensemble des clés, il faudrait un peu aller fouiller la classes HashMap pour que les choses soit bien claire.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
         private class KeySet extends AbstractSet<K> {
             public Iterator<K> iterator() {
                 return getIterator(KEYS);
             }
             public int size() {
                 return count;
             }
             public boolean contains(Object o) {
                 return containsKey(o);
             }
             public boolean remove(Object o) {
                 return Hashtable.this.remove(o) != null;
             }
             public void clear() {
                 Hashtable.this.clear();
             }
         }

le code source : http://www.docjar.com/html/api/java/...able.java.html

**tchize_** · 03/06/2009, 10h11

le problème des hashtable / hashmap en java, c'est que leur temps moyen dépend fortement de la qualité de la méthode hashCode dé éléments que tu y stocke

D'ou ma réponse sur le pire des cas. De toutes façon, avec les sources, il peux se faire ses calculs