TD numéro 6 du tronc commun en informatique 1998-99 dirigé par Serge Vaudenay et David Pointcheval.

Hachage

** On cherche à constituer un annuaire téléphonique sous la forme d'une table de hachage. Dans cet exercice, la table de hachage sera un tableau d'objets de type StringListe contenant deux champs contenu1 (celui-ci contiendra le nom d'une personne) et contenu2 (celui-ci contiendra le numéro de téléphone) et un champs suivant. On prend pour fonction de hachage
où c₁c₂...c_n est une chaîne dont les caractères sont transformé en entiers c_i. On se propose de compléter le programme tp06_ex1tmplt.java (
pour télécharger, cliquer ici) qui contient les méthodes prédéfinies suivantes.
1. static RandomAccessFile lecteurFichier(String chemin_fichier)
  qui retourne un objet qui permet de lire un fichier donné par son chemin d'accès.
2. static String lireMot(RandomAccessFile lecteur)
  qui retourne le mot suivant dans le lecteur de fichier donné.
3. static String saisieMot()
  qui permet de saisir une chaîne de caractères au clavier.
4. public static void main(String[] argv)
  qui permet de lancer le programme par
  Le programme hache tout d'abord le fichier spécifié dans une table de hachage, et demande ensuite de saisir des noms au clavier pour les rechercher dans la table.
Les méthodes à compléter sont les suivantes.
1. static void afficheStringListe(StringListe liste)
  affiche une liste.
2. static int hash(String mot)
  hache une chaîne de caractères.
3. static void insere(String mot,String val,StringListe[] hash_tb)
  insè un nouveau nom mot de numéro de téléphone val dans la table de hachage hash_tb.
4. static String recherche(String mot,StringListe[] hash_tb)
  retourne le numéro de téléphone du nom mot trouvé dans la table. (Si le nom n'existe pas, la méthode renvoie null.)
5. static void afficheHashTb(StringListe[] hash_tb)
  affiche la table de hachage.
On pourra se servir du fichier tp06_ex1.tel (pour télécharger, cliquer ici) qui donne un exemple d'annuaire téléphonique.
[Corrigé]
** On cherche à constituer une liste de mots français afin de détecter le fautes d'orthographes dans un texte. Pour cela, on se sert du fichier tp06_ex2.dico (pour télécharger, cliquer ici) qui contient 41254 mots. Le programme s'utilise par
où fichier_texte est un texte sans ponctuations. Le programme affiche les mots qui ne sont pas dans le dictionnaire.
En s'inspirant de l'exercice 1, définir les méthodes suivantes.
1. static RandomAccessFile lecteurFichier(String chemin_fichier)
2. static String lireMot(RandomAccessFile lecteur)
3. static int hash(String mot)
4. static void insere(String mot,StringListe[] hash_tb)
5. static boolean recherche(String mot,StringListe[] hash_tb)
6. public static void main(String[] argv)
Afin de diminuer les collisions dans la table de hachage, on prendra pour fonction de hachage la fonction
[corrigé]