Informatique T.D 3

Hachage par collisions séparées

Marie-Pierre Béal et Laurent Moll

L’objectif de ce TP est de constituer une table de hachage dont les clés sont des noms d’auteurs de disques compacts. La base de données contenant ces noms est un fichier texte de nom ’Noms’. Les différents noms sont séparés par une fin de ligne. Le fichier contient moins de soixante références et chacune a au plus vingt caractères. On implémentera un hachage dit par collisions séparées. La table sera un tableau t dont les éléments seront des record formés de deux champs. Le premier, nom, contiendra un nom d’auteur, c’est-à-dire la clé. Le deuxième, suiv, un entier qui sera soit −1, soit l’indice d’une case du tableau. On prendra un tableau de taille M = 100, les indices variant de 0 à M−1. Les cases 0 à N−1 seront utilisées pour stocker les clés lorsque l’insertion se fait sans collision et les cases N à M−1 seront utilisées pour les collisions. On désignera par Nc le nombre de collisions et Nbnoms le nombre de noms figurant dans la table. Il y aura débordement de table si on demande une insertion alors que N + Nc ≥ M . On prendra M= 71. Initialement, Nbnoms = Nc = 0, tous les champ suiv sont à −1 et tous les champs nom sont à ’ ’ (chaine vide). La fonction de hachage est à valeurs dans 0 … N−1. On pourraprendre comme fonction de hachage, si s est une chaine de caractères du type string et B = 256 :

h(s) = (ord(s[1]) × B^{length(s)−1} + ord(s[2]) × B^{length(s)−2} + … + ord(s[length(s)])) mod N

Exercice 1.— Commencer par récupérer le fichier Noms par le réseau (Netscape). Un fichier à compléter est également disponible.

Exercice 2.— Ecrire tout d’abord la fonction de hachage h. Puis la procédure insertion qui prend en paramètre une chaine s et insère s dans la table. La chaine s est insérée dans la case d’indice h(s) lorsqu’il n’y a pas collision. En cas de collision la clé est insérée en tête de liste. Les nouveaux noms insérés doivent donc ne pas déja figurer dans la table ou alors ils sont insérés une deuxième fois. En cas de collision lors de l’insertion de s, faire afficher successivement : h(s), t[h(s)].nom et s, ceci pour visualiser la collision.

Exercice 3.— Ecrire une procédure initialisation pour initialiser le tableau et les variables Nbnoms et Nc. Ecrire une procédure transfert qui lit le fichier Noms et appelle insertion pour insérer chaque clé dans la table. Faire afficher Nbnoms, Nc, N. Vérifier ainsi que la procédure insertion et la fonction h marchent bien. Consulter l’annexe pour la manipulation de fichiers textes.

Exercice 4.— Ajouter une fonction recherche de résultat booléen qui teste si une chaine s est une clé de la table. On fera appel à recherche avant d’insérer une nouvelle clé.

Exercice 5.— Ecrire une procédure suppression qui supprime une clé s passée en paramêtre. Les autres procédures doivent fonctionner normalement après une ou plusieurs suppressions.

Enfin, s’il vous reste du temps, écrire un menu permettant de manipuler les différentes actions possibles sur la table, recherche, insertion, suppression, afficher le menu, ou quitter.

Aide à la manipulation de fichiers et des chaines de caractères :

Sur Mac

• Le nom du fichier texte est libre (Noms par exemple). Il faut le placer au même niveau que le fichier projet.

• L’instruction reset(f,'Noms') ouvre le fichier dont le nom sur le disque est Noms. Ce fichier est ensuite repéré dans le programme pascal par le nom de variable f. La variable f sera déclarée de type text. Le fichier est dit ouvert en lecture, c’est-à-dire qu’il est possible de lire les informations contenues dans le fichier, mais pas de les modifier. A chaque instant, lors de l’exécution, une position dans le fichier est pointée par un index de lecture. Cet index est positionné au début du fichier lors de l’ouverure du fichier.

• Pour déclarer une chaine de caractères de longueur au plus 20, faire une déclaration de

type : type chaine= string[20].

• L’instruction readln(f,s) lit une chaîne de caractères dans le fichier f jusqu’au premier caractère de fin de ligne, avance l’index de lecture jusqu’à ce point et assigne la chaîne lue à la variable s.

• Le prédicat eof(f) prend la valeur true quand l’index est sur un caractère de fin de fichier.

Sur PC

• Le nom du fichier texte doit être sauvegardé au niveau du projet avec le préfixe .txt, par

exemple Noms.txt.

• Une chaine courte sera declarée du type type chaine= string[20]. La longueur d’une chaine s est donnée par length(s) ou StrLen(s).

• Pour déclarer un fichier texte, l’ouvrir en lecture, et lire une ligne en l’affectant à une chaine s, on peut écrire :

var f: TextFile;
    s:string[20];
begin
    AssignFile(f,'Noms.txt');
    Reset(f);
    Readln(f,s);
...
    CloseFile(f);
end.