Laboratoire 13 : Tables de hachage

Lectures préalables

• Section 10 (Tables de hachage) des notes de cours.

Objectifs

• Implémenter une classe Dictionnaire basée sur une table de hachage.
• Expérimenter std::unordered_map dans la bibliothèque standard.

---

Partie A

Début

Téléchargez lab13.zip.

Compilez avec la commande: make

Opérateur []

1. Complétez l'opérateur [] de la classe Dictionnaire. Vous n'aurez besoin que de la version non constante.
2. Utilisez une stratégie de gestion de collision interne et linéaire pour commencer.
3. Testez avec la fonction test1.

Fonction de hachage

• La fonction Date::hash() n'est peut-être pas la meilleure.
• Une façon d'évaluer la fonction est de compter le nombre de tentatives totales dans l'opérateur [].
• Assurez-vous que ++nbTentatives a été placé au bon endroit lors de la tâche précédente.
• Modifiez la fonction Date::hash() pour obtenir les plus petites valeurs possible dans la fonction test2.
• Il n'y a que 3 cas testés dans la fonction test2. Vous pouvez en ajouter d'autres.

---

Partie B

Comparaison: arbre binaire de recherche vs table de hachage

Écrivez un programme qui détermine et affiche la co-occurrence de deux mots la plus fréquente dans un texte envoyé dans l'entrée standard. Une co-occurrence de deux mots est définie comme une paire de mots qui apparaissent dans une même phrase. Dans le texte ci-bas, la co-occurrence la plus fréquente est la paire («livres», «bibliothèque»). Pour faciliter la lecture avec le flux d'entrée C++ std::istream, les caractères de ponctuation ont été encadrés d'espaces blancs.

Plusieurs livres sur les structures de données sont disponibles à la bibliothèque .
Dans une bibliothèque , on retrouve beaucoup de livres .
Marc a écrit des livres que je n ' ai pas pu trouver à la bibliothèque .
Le cours INF3105 porte sur les structures de données .

Le fichier lab13b.cpp contient une base pour lire l'entrée mot par mot et détecte les fins de phrase.

Pour rendre le problème plus intéressant, on pourrait ignorer les mots fréquents tels que: «une», «les», «des», «qui», «ils», «elle», etc.

Commencez en utilisant la classe std::map. Le truc est d'utiliser des compteurs en imbriquant deux dictionnaires : map<string, map<string, int> >.

Ensuite, testez votre programme en chronométrant le temps requis avec quelques tests.

make
time ./lab13b < texte1.txt
time ./lab13b < texte2.txt
time ./lab13b < texte3.txt
time ./lab13b < texte4.txt

Enfin, changez map par std::unordered_map. Et refaites les tests ci-haut et observez les différences de temps.