TP — Séance 3 — Tables de hachage

Écrire, tester et mesurer une table de hachage en Java

TP de la séance 3 de Structures de données et algorithmes avancés : du tableau indexé au coût moyen constant.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Écrire les deux tables du cours, ChainedHashMap (chaînage séparé) et LinearProbingMap (sondage linéaire), avec le rehash et la suppression par pierre tombale ; les faire passer par les tests JUnit fournis ; puis mesurer leur coût et le comparer aux formules du cours (\(1+\alpha/2\) et \(\alpha\) pour le chaînage, formules de Knuth pour le sondage). Durée : une séance de TP.

À rendre. Le dépôt Git du projet (les deux classes complétées, les tests au vert) et un compte rendu d’une à deux pages qui répond aux questions marquées Observer, Expliquer et Modifier, en recopiant les sorties obtenues.

Préparation

Le TP se fait dans l’environnement Docker du cours (Java 17, Gradle 8, JUnit 5). Sur la machine, décompresser le code de départ, TP_S03_code_depart.zip, dans ~/dsa : le dossier TP_S03_code_depart/ apparaît. Le conteneur se lance depuis ce dossier :

cd ~/dsa
docker run -it --rm -v "$(pwd):/workspace" elbachirtoure/dsa-java:v2.0

Sous Windows (Git Bash), la commande docker run est précédée de MSYS_NO_PATHCONV=1. Dans le conteneur :

cd /workspace
new-project tp-s03
cd tp-s03
cp -r ../TP_S03_code_depart/. .
rm src/test/java/MainTest.java

Le code de départ contient six fichiers, cinq dans src/main/java/ et TableHachageTest.java dans src/test/java/ : la copie les range dans le projet, en remplaçant le Main.java créé par new-project, et rm supprime le MainTest.java créé par new-project. Le dépôt Git du projet se crée dans tp-s03 : git init -b main et l’identité locale, comme à l’étape 7 du TP-1.

Fichier Rôle
Map.java l’interface du type abstrait Map (put, get, remove, containsKey, size)
ChainedHashMap.java chaînage séparé : méthodes à écrire aux étapes 1 et 2
LinearProbingMap.java sondage linéaire : méthodes à écrire aux étapes 3 et 4
Plaque.java une clé à deux hashCode possibles (étape 6), fournie
Main.java programmes d’observation et de mesure, fournis
TableHachageTest.java neuf tests JUnit, fournis

Les méthodes à écrire contiennent une consigne en commentaire et lèvent UnsupportedOperationException ; tout le reste est fourni. Les deux commandes du TP sont :

gradle --no-daemon test
gradle --no-daemon run --args="rehash"

Observer. Lancer les tests avant d’écrire la moindre ligne : combien échouent, et avec quelle exception ?

Étape 1 : le chaînage séparé

ChainedHashMap range ses paires dans un tableau de listes chaînées. Un nœud porte une clé, une valeur et le nœud suivant ; une case vide contient null. Les champs et le constructeur sont fournis :

private Noeud<K, V>[] table;
private int n;
private final double seuil;

public long comparaisons;                       // comparaisons de cles
public long copies;                             // reinsertions (rehash)
public int redimensionnements;

Écrire, dans l’ordre, indice, get, containsKey, put et remove, en suivant les consignes en commentaire. get et containsKey ajoutent 1 à comparaisons pour chaque nœud examiné. put remplace la valeur d’une clé présente et rend l’ancienne ; sinon, il ajoute un nœud en queue de la liste, augmente n, puis appelle verifierCharge(), qui reste vide jusqu’à l’étape 2.

  1. Observer. Lancer les tests : les cinq tests dont le nom commence par chainage, sauf chainageRehash, doivent passer. Le test chainageCollision insère "Aa" et "BB" : que vaut longueurMax(), et pourquoi ?
  2. Modifier. Remplacer provisoirement, dans indice, le masque par Math.abs(cle.hashCode()) % table.length. Quel test échoue, avec quel message ? Revenir au masque.
  3. Expliquer. Pourquoi containsKey n’est-elle pas écrite return get(cle) != null; ? Donner une clé et une valeur pour lesquelles cette écriture répond faux.
  4. Expliquer. Dans remove, quels sont les deux cas à distinguer, et pourquoi ?

Étape 2 : le rehash

Écrire verifierCharge : si seuil > 0 et que \(n/m\) dépasse le seuil, doubler la table. Écrire ensuite redimensionner : allouer un tableau neuf, remettre n à 0, augmenter redimensionnements, puis réinsérer chaque paire de l’ancien tableau par put, en augmentant copies à chaque réinsertion.

  1. Observer. Le test chainageRehash doit passer. Lancer ensuite gradle --no-daemon run --args="rehash", qui insère 50 matricules E2026-001 à E2026-050 dans une table de 4 cases, et recopier sa sortie.
  2. Expliquer. À quelles insertions la table double-t-elle ? Retrouver ces valeurs par le calcul, sans regarder la sortie.
  3. Expliquer. Pourquoi redimensionner remet-elle n à 0 avant de réinsérer ? Que se passerait-il si l’on recopiait chaque liste dans la même case du nouveau tableau, sans appeler put ?
  4. Expliquer. Comparer le nombre total de copies à la borne du cours pour \(m_0=4\) (le rehash numéro \(j\) a lieu à l’insertion \(3\cdot2^j+1\)). Combien de copies par insertion en moyenne ?

Étape 3 : le sondage linéaire

LinearProbingMap range au plus une paire par case, dans deux tableaux cles et vals. Le compteur sondages compte les cases examinées par chercher, la méthode qui sert à get et à containsKey. Le seuil par défaut est \(0{,}5\).

private static final Object TOMBE = new Object();   // pierre tombale

private Object[] cles;
private Object[] vals;
private int n;                                      // paires presentes
private int tombes;                                 // pierres tombales

Écrire indice, chercher, put (sans pierre tombale pour l’instant) et redimensionner. Le rehash a lieu quand (n + tombes) / m dépasse le seuil.

  1. Observer. Les tests sondagePutGet et sondageRehash doivent passer. Dans sondagePutGet, les clés 3, 14 et 25 vont dans une table de 11 cases : dessiner la table et expliquer les valeurs 3 et 4 attendues pour sondages.
  2. Expliquer. Pourquoi chercher ne peut-elle jamais tourner sans fin dans une table dont le seuil est \(0{,}5\) ?
  3. Expliquer. À l’aide des formules de Knuth, justifier le choix d’un seuil de \(0{,}5\) pour le sondage linéaire, alors que le chaînage accepte \(0{,}75\).

Étape 4 : la suppression par pierre tombale

Vider la case d’une clé supprimée couperait le chemin des clés rangées plus loin. remove remplace donc la clé par TOMBE. chercher passe les pierres tombales sans s’arrêter ; put cherche la clé jusqu’à une case vide en retenant la première pierre tombale rencontrée, et range une clé absente dans cette tombe plutôt que dans la case vide. Le rehash fait disparaître les pierres tombales.

  1. Observer. Écrire remove, compléter chercher et put ; les neuf tests doivent passer. Lancer gradle --no-daemon run --args="tombe" et recopier les quatre lignes écrites.
  2. Expliquer. Commenter chaque ligne : quelle case contient la pierre tombale, comment get(41) la traverse, où 61 est rangée et pourquoi.
  3. Modifier. Remplacer provisoirement, dans remove, TOMBE par null. Que rend get(41) ? Quel test échoue ? Revenir à TOMBE.
  4. Expliquer. Pourquoi le test de rehash compte-t-il les pierres tombales avec les paires ?

Étape 5 : les coûts mesurés

Le mode mesures de Main tire des numéros de téléphone fictifs (graine 2026). Pour plusieurs valeurs de \(\alpha\), il remplit une table de \(m=12\,007\) cases sans rehash, mesure le nombre moyen de sondages d’une recherche réussie (toutes les clés insérées) et d’une recherche infructueuse (\(6\,000\) clés absentes), et les compare aux formules ; il fait ensuite la même mesure en chaînage, en comptant les comparaisons.

gradle --no-daemon run --args="mesures"
gradle --no-daemon run --args="mesures 12000"
  1. Observer. Recopier les deux tableaux de la première commande. Tracer, sur un même graphique, les sondages en échec mesurés et la courbe \(U(\alpha)\).
  2. Expliquer. De \(\alpha=0{,}75\) à \(\alpha=0{,}9\), par combien le coût d’une recherche infructueuse est-il multiplié, en sondage et en chaînage ? Relier ce résultat aux clusters.
  3. Observer. Lancer la seconde commande, avec \(m=12\,000\) : comparer aux mesures avec \(m=12\,007\).
  4. Expliquer. \(12\,007\) est premier, \(12\,000=2^5\times3\times5^3\). Calculer \(31\bmod32\) et en déduire ce que vaut le code d’une chaîne modulo 32 en fonction de ses caractères ; expliquer pourquoi des numéros de téléphone se répartissent mal entre les cases quand \(m\) est un multiple de 32.

Étape 6 : un hashCode qui ignore une partie de la clé

Une plaque d’immatriculation sénégalaise se compose d’une région, d’un numéro et d’une série, comme DK 1234 AB. La classe Plaque fournie a deux hashCode, choisis par le champ statique bonCode : le premier ne lit que la région, le second lit les trois champs. Le mode plaques range \(2\,000\) plaques de Dakar dans une ChainedHashMap, avec l’un puis l’autre code.

  1. Observer. Lancer gradle --no-daemon run --args="plaques" et recopier les deux lignes.
  2. Expliquer. Les deux codes respectent-ils le contrat equals / hashCode ? Pourquoi le premier est-il pourtant inutilisable ? Relier la valeur \(1\,000{,}5\) à une formule du cours.
  3. Modifier. Écrire un troisième hashCode, sans Objects.hash, par le schéma de Horner sur les trois champs (\(h\leftarrow31\,h+\dots\)), une instruction par ligne, et vérifier qu’il donne une plus longue liste de 2 ou 3 nœuds.

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet