TD — Séance 3 — Tables de hachage

Codes, insertions, sondages, suppression et rehash

TD 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

Appliquer à la main, sur des données nouvelles, les mécanismes du cours : calcul d’un hashCode et de l’indice d’une case, insertion par chaînage séparé et par sondage linéaire, suppression par pierre tombale, rehash, contrat equals / hashCode. Chaque réponse se donne sous la forme demandée (tableau, état de la table, nombre de comparaisons ou de sondages) et se justifie en une ou deux phrases.

Conventions. La compression est celle du cours, (h & 0x7fffffff) % m. Pour une clé entière positive, la méthode Integer.hashCode() rend la valeur de l’entier, et l’indice est \(k\bmod m\). Le chaînage ajoute en queue de liste. Le sondage linéaire examine les cases \(h(k), h(k)+1, \dots\) modulo \(m\) ; chaque case examinée compte pour un sondage. Une recherche en chaînage compte une comparaison par nœud examiné.

Exercice 1 : codes et compressions

Les codes des caractères utiles sont K = 75, a = 97, n = 110, e = 101, L = 76, m = 109, i = 105. Aides : \(31\times75=2\,325\) ; \(31\times2\,422=75\,082\) ; \(31\times75\,192=2\,330\,952\) ; \(2^{31}=2\,147\,483\,648\) ; \(2^{32}=4\,294\,967\,296\).

  1. Calculer "Kane".hashCode() par le schéma de Horner ; donner \(h\) après chaque caractère.
  2. En déduire l’indice de "Kane" dans une table de 16 cases, puis de 10 cases.
  3. Le schéma de Horner appliqué à "Lamine" sans limite de taille donne \(2\,268\,748\,648\). Montrer que cette valeur ne tient pas dans un int et en déduire "Lamine".hashCode().
  4. Pour \(m=10\), calculer h % 10, Math.floorMod(h, 10), (h & 0x7fffffff) % 10 et Math.abs(h) % 10. Aides : \(2\,026\,218\,648=10\times202\,621\,864+8\) ; \(2^{31}-2\,026\,218\,648=121\,265\,000\).
  5. Même question pour \(m=16\), sachant que \(2\,026\,218\,648=16\times126\,638\,665+8\). Expliquer pourquoi trois des quatre écritures coïncident ici, et non pour \(m=10\).
  6. Quelle valeur rend Math.abs(Integer.MIN_VALUE) % 10 ? Que se passe-t-il si cette valeur sert d’indice ?

Exercice 2 : une trace de chaînage séparé

Le service de scolarité range sept numéros de dossier dans une table à chaînage séparé de \(m=11\) cases, sans redimensionnement. On insère, dans cet ordre, 31, 52, 17, 74, 9, 40 et 63.

  1. Calculer les sept indices.
  2. Donner l’état final de la table (une liste par case, dans l’ordre de la liste).
  3. Donner, pour chaque clé, le nombre de comparaisons d’une recherche réussie, puis leur moyenne.
  4. Compter les comparaisons de get(63), get(85) et get(96).
  5. Calculer \(\alpha\) et comparer la moyenne de (c) à \(1+(n-1)/(2m)\).
0 1 2 3 4 5 6 7 8 9 10

Exercice 3 : la même trace par sondage linéaire

On insère les mêmes clés, dans le même ordre, dans une table à sondage linéaire de \(m=11\) cases, sans redimensionnement.

  1. Compléter le tableau d’insertion ci-dessous.
  2. Donner l’état final de la table et les clusters (cases occupées consécutives, en tenant compte du retour de la case 10 à la case 0).
  3. Calculer le nombre moyen de sondages d’une recherche réussie et le comparer à \(S(7/11)\).
  4. Donner les cases visitées et le nombre de sondages de get(63) et de get(85) ; comparer le second à \(U(7/11)\).
  5. Comparer les coûts des recherches de 63 et de 85 à ceux de l’exercice 2.
clé \(h\) cases examinées case sondages
31
52
17
74
9
40
63
0 1 2 3 4 5 6 7 8 9 10

Exercice 4 : suppression par pierre tombale

On part de la table finale de l’exercice 3. Une pierre tombale (tombstone), notée X, marque une case dont la clé a été supprimée. Les règles sont les suivantes :

  • remove(k) cherche \(k\) et remplace sa case par X, sans jamais la vider ;
  • get(k) examine les cases comme d’habitude, passe les X sans s’arrêter, et ne s’arrête que sur \(k\) ou sur une case vide ;
  • put(k, v) cherche \(k\) jusqu’à une case vide en retenant le premier X rencontré ; si \(k\) est absente, elle est rangée dans ce X, ou, à défaut, dans la case vide.
  1. On vide la case de 74 sans précaution. Quelles cases get(63) visite-t-elle, et que rend-elle ?
  2. On repart de la table de l’exercice 3 et l’on supprime 74 par remove. Donner l’état de la table.
  3. Donner les cases visitées et le nombre de sondages de get(63), puis de get(85).
  4. On exécute put(96, …), puis put(41, …). Pour chacune, donner les cases examinées et la case choisie, puis l’état final.
  5. Une table qui reçoit beaucoup de suppressions accumule des X. Pourquoi faut-il les compter avec les paires pour décider d’un rehash ? Que deviennent-ils pendant le rehash ?

Exercice 5 : rehash

Une table à chaînage séparé compte \(m=4\) cases ; son seuil est \(0{,}75\). On insère, dans cet ordre et en queue de liste, 13, 6, 21, 8, 30, 17 et 2, en doublant \(m\) dès que \(\alpha>0{,}75\) après une insertion.

  1. Compléter le tableau ci-dessous.
  2. Donner l’état de la table juste après chaque rehash.
  3. Combien de copies les rehashs font-ils au total ? Quel est le facteur de charge final ?
  4. La même table, partant de \(m=4\), reçoit 60 clés distinctes. À quelles insertions double-t-elle ? Donner les valeurs finales de \(m\) et de \(\alpha\), et le nombre total de copies ; établir, pour \(m_0=4\), la borne analogue à la borne \(2N+K-7\) du cours (le rehash numéro \(j\), pour \(j=0,1,\dots,K\), a lieu à l’insertion \(3\cdot2^j+1\)), puis la vérifier.
clé case \(n\) \(n/m\) avant le test rehash ? \(m\) après
13
6
21
8
30
17
2

Exercice 6 : le contrat equals / hashCode

La scolarité identifie un étudiant par son matricule. Quatre versions de la classe Etudiant sont écrites ; toutes ont deux champs matricule et nom de type String et un constructeur qui les recopie.

  • A : equals compare les matricules ; hashCode n’est pas redéfini.
  • B : equals compare les matricules ; hashCode rend nom.hashCode().
  • C : equals compare les matricules ; hashCode rend matricule.hashCode().
  • D : equals compare matricule et nom ; hashCode rend Objects.hash(matricule, nom) ; le champ nom n’est pas final.

Pour les versions A, B et C, le programme suivant est exécuté (Etudiant désignant la version étudiée) :

Set<Etudiant> inscrits = new HashSet<>();
inscrits.add(new Etudiant("2026-0417", "Ndeye Fall"));
inscrits.add(new Etudiant("2026-0417", "Ndèye Fall"));
System.out.println(inscrits.size());
System.out.println(inscrits.contains(new Etudiant("2026-0417", "N. Fall")));

  1. Pour chacune des versions A, B et C, prévoir les deux lignes écrites et dire si le contrat est respecté.

  2. Pour la version B, que rend inscrits.contains(new Etudiant("2026-0417", "Ndeye Fall")) ? Expliquer pourquoi la réponse n’est pas la même qu’avec "N. Fall".

  3. Pour la version D, on exécute :

    Set<Etudiant> inscrits = new HashSet<>();
Etudiant d = new Etudiant("2026-0417", "Ndeye Fall");
inscrits.add(d);
d.nom = "Ndeye Fall Diop";
System.out.println(inscrits.size());
System.out.println(inscrits.contains(d));

    Prévoir les deux lignes écrites et expliquer. Quelle règle sur les clés cette situation enfreint-elle ?

  4. Écrire, pour la version C, une méthode equals et une méthode hashCode qui respectent le contrat, en une instruction par ligne.

Exercice 7 : le nombre de cases vides

On range \(n\) clés dans \(m\) cases sous l’hypothèse du hachage uniforme (chaque clé tombe dans chaque case avec la probabilité \(1/m\), indépendamment des autres), par chaînage séparé.

  1. Montrer qu’une case donnée reste vide avec la probabilité \((1-1/m)^n\), et en déduire le nombre moyen de cases vides.
  2. Montrer que, pour \(m\) grand, cette probabilité vaut environ \(e^{-\alpha}\).
  3. Calculer le nombre moyen de cases vides pour \(n=6\,000\) et \(m=8\,000\), par la formule exacte puis par l’approximation. Aide : \(e^{-0{,}75}\approx0{,}4724\).
  4. Le nombre moyen de cases non vides est-il égal à \(n\) ? Que mesure l’écart entre les deux ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet