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

Tables de hachage génériques

Le but de ce TD est d'améliorer les temps de recherches 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 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 ?

Remarque: Malheureusement si on souhaite changer ce nombre de listes, il faudra créer une nouvelle table de hachage, y copier les données de l'ancienne table, puis détruire cette dernière.

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(unsigned char *chaine,int max) {
  unsigned int hash = 0, i = 0;
  while(i < strlen(chaine)) {
    hash = ((hash *26) + chaine[i])% max;
    ++i;
  }
  return hash;
}

Il existe bien d'autre fonctions de hachage!

Exercice 3 - Structures de données

Tout d'abord, nous devons modifier la structure Type afin d'y introduire cette fonction de hachage:

struct type {
 int (*compare)(void* e1, void* e2);
 void (*affiche)(void* e1);
 void (*liberation)(void **element);
 int (*hachage)(void *element,int max);
};

La structure de table de hachage sera la suivante:

struct table {
 Type *type;
 unsigned int m; /* Le nombre de listes dans notre table */
 cellule_t ** table; /* Le tableau des listes chaînées contenant nos éléments */
};

Exercice 4 - Fonctions

Il va falloir écrire les fonctions suivantes:

Table* creation_table(Type *type, int taille); qui crée une table de hachage vide.
void destruction_table(Table** table); qui libère la mémoire occupée par une table de hachage.
void affiche_table(Table* table); qui affiche les éléments de la table.
void* recherche_element_dans_table(Table* table, void* element); qui recherche l'élément dans la table. Si l'élément est présent, la fonction renvoie l'élément contenu dans la table sinon elle renvoie NULL.
void supprime_element_dans_table(Table* table, void* element); qui cherche l'élément dans la table et le supprime de la table à chaque fois qu'il est trouvé.
void ajoute_element_dans_table(Table* table, void* element); qui ajoute l'élément uniquement s'il n'est pas déjà dans la table.

Il est évident que vous devez réutiliser les fonctions de manipulations listes que vous avez écrites la semaine dernière~!

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.