TD3 - Tables d'associations, supplément

5.  Liste d'association générique

Écrire une classe Assoc2 pour construire des listes d'associations génériques (pour tous types de clés et de valeurs) en utilisant la classe Object.

Une solution.

Écrire aussi une classe TableAssoc2 qui implémente l'interface Table suivante :

interface Table 
{
    // Acc`es dans la table (renvoie la valeur associ'ee `a une cl'e).
    public Object get (Object key) ;

    // Cr'ation/mise `a jour d'une association cl'e->valeur.
    public void put (Object key, Object val) ;

    // Test si une association est pr'esente pour une cl'e donn'ee.
    public boolean containsKey (Object key) ;
}

Une solution.

6.  Table de hachage sans librairie java

Les tables de hachage comment ça marche ? Nous proposons tout d'abord de programmer une table de hachage de capacité fixée n à la main. Elle sera constituée d'un tableau de n listes d'associations. Toute association de clé k sera stockée dans la liste d'index k.hashCode () modulo la capacité de la table.

Une solution.

Pour plus de maniabilité, ajuster maintenant la capacité de la table automatiquement en fonction d'un taux de remplissage f. Si le nombre d'associations stockées dans la table dépasse f fois la capacité, alors la table est reconstruite en une nouvelle table de capacité double.

Une solution.

Écrire une méthode KeysEnumeration keys () qui permette de parcourir toutes les clés de la table. Pour cela, on utilisera une classe KeysEnumeration :

class KeysEnumeration implements java.util.Enumeration
{
   ...

    public boolean hasMoreElements () {
        ...
    }

    public Object nextElement () {
        ...
    }

}

implements java.util.Enumeration signifie simplement qu'on va définir les méthode attendues pour une énumération : boolean hasMoreElements () et Object nextElement (). KeysEnumeration sera donc un cas particulier de l'interface java.util.Enumeration, ce qui autorisera l'écriture de for (java.util.Enumeration e = t.keys () ; ... quand t est une table de hachage de votre cru.

Une solution.

Optimisez votre code pour faire mieux que java.util.Hashtable.

Une solution (optimisation de put pour ne chercher qu'une fois la clé et de toString avec StringBuffer).