Cours Java
TD3

Alain Plantec

1 La table de hash (rappels)

Une table de hash est une collection dans laquelle on stocke un emsemble de couples (clé,valeur). La clé et la valeur peuvent être de n'importe quelle classe. A une clé correspond une et une seule valeur. On ne peut pas trouver deux fois la même clé dans une même table de hash.

C'est une collection très intéressante pour stocker et retrouver très rapidement des données suivant des indexes autres que des indexes entiers.

1.1 Représentation schématique

\includegraphics[scale=0.6]{map.eps}
On observe que le point d'entrée est un tableau de listes de taille N. Chaque élément de ce tableau est une liste. Les éléments stockés dans les listes sont des couples (clé,valeur). Pour une clé k, la position p dans le tableau de listes de taille N est calculée de la façon suivante :

p = k.hash()%N

Deux clés différentes peuvent donc avoir le même valeur pour p.

1.2 L'interface Map


public interface Map {
    // creer un couple ('key','value') et le stocker dans la table
    Object put(Object key, Object value);
    // retrouver la valeur associee a la cle 'key'
    Object get(Object key);
    // supprimer le couple dont la cle est 'key'
    Object remove(Object key);
    // tester l'existance d'un couple dont la cle est 'key'
    boolean containsKey(Object key);
    // tester l'existance d'un couple dont la valeur est 'value'
    boolean containsValue(Object value);

    int size();
    boolean isEmpty();

    // copier les couples du map 't'
    void putAll(Map t);
    // vider la table
    void clear();

    // retourner un Set contenant toutes les cles
    Set keySet();
    // retourner une Collection contenant toutes les valeurs
    Collection values();
    // retourner un Set contenant tous les couples
    Set entrySet();

    // la classe interne decrivant un couple
    public interface Entry {
	// retourner la cle
	Object getKey();
	// retourner la valeur
	Object getValue();
	// modifier la valeur
	Object setValue(Object value);
    }
}

2 Développements





Plantec Alain
2002-02-21