:: Enseignements :: Licence :: L2 :: 2009-2010 :: Système ::

Tables de hachage génériques

Le but de ce TD est d'améliorer les temps de recherche des mots dans un dictionnaire. La semaine dernière nous avons vu que la complexité du temps de recherche d'un mot dans la liste chaînée est O(n), ce qui n'est pas très satisfaisant.

Exercice 1 - Principe

Le principe que l'on souhaite suivre est de réduire la taille de nos listes afin d'améliorer les temps de recherche. Ainsi, au lieu de mettre tous les éléments dans une seule liste chaînée, nous allons les répartir en plusieurs listes. Par exemple, si nos éléments étaient des entiers, nous pourrions avoir une liste pour les nombres pairs, et une autre pour les nombres impairs. La longueur moyenne des listes serait ainsi divisée par deux, et la recherche irait donc en moyenne deux fois plus vite.

Comme la semaine dernière, nos éléments sont de type arbitraire, et le nombre de listes aussi. Nous allons considérer que le nombre de listes M est fixé lors de la création de notre nouvelle structure de données, que l'on nommera table de hachage.

Mais, comment choisir la liste dans laquelle je dois mettre mon élément ?

Exercice 2 - Fonction de hachage

La fonction de hachage est précisément la fonction qui permet de répondre à notre problématique du choix d'une liste. Ainsi, cette fonction prend pour argument un élément, et renvoie un nombre compris entre 0 et M-1 et qui est toujours le même nombre pour un élément donné.

Mais, il est assez difficile d'écrire une bonne fonction de hachage. En effet, cette fonction doit répartir le plus équitablement possible les éléments entre nos différentes listes possibles. Voici un exemple de fonction de hachage pour les chaînes de caractères:

unsigned int hachage_string(any data,int max) {
unsigned int hash=0,i=0,l=strlen(data.s);
while(i<l) {
	hash=((hash*26) + data.s[i])%max;
	i++;
}
return hash;
}

Il existe bien d'autres fonctions de hachage.

Exercice 3 - Structures de données

Dans le TP sur les listes génériques, nous n'avons pas ajouté les pointeurs de fonctions nécessaires à la structure de liste, afin de ne pas alourdir chacune des cellules. En revanche, nous pouvons stocker ces pointeurs une fois et une seule dans la structure de la table, afin d'éviter de devoir les passer en paramètres à chaque opération. Pour simplifier, nous allons utiliser un type qui regroupe tous les pointeurs de fonctions nécessaires, et nous l'utiliserons dans la structure de table:

typedef void (*free_any)(any);
typedef int (*comparer_any)(any,any);
typedef void (*afficher_any)(any);
typedef unsigned int (*hachage_any)(any data,int max);

typedef struct {
	free_any free;
	comparer_any cmp;
	afficher_any print;
	hachage_any hash;
} Fonctions;


typedef struct {
	Fonctions f;
	unsigned int taille;
	Liste** table;
} Table;

Exercice 4 - Fonctions

Vous écrirez les fonctions suivantes:

Table* creer_table(int n,Fonctions f); qui crée une table de hachage vide;
void liberer_table(Table* t); qui libère toute la mémoire occupée par une table de hachage;
void afficher_table(Table* t); qui affiche les éléments de la table;
any* est_present(Table* t,any data); qui recherche l'élément dans la table. Si l'élément est présent, la fonction renvoie son adresse, sinon elle renvoie NULL;
void ajouter(Table* t,any data); qui ajoute l'élément uniquement s'il n'est pas déjà dans la table.

Naturellement, vous devez réutiliser les fonctions de manipulation de listes génériques que vous avez écrites précédemment.

Exercice 5 - Comparaison avec les listes chaînées

Reprenez le programme dico, mais cette fois-ci en utilisant une table de hachage. Comparez les temps d'exécutions vis-à-vis des listes chaînées et faites varier différentes tailles de table de hachage.

Notamment, vous vérifierez que lorsque M = 1 les temps de recherche sont similaires à ceux obtenus dans le cas d'une liste chaînée.