Apprenez à programmer en C

Les listes chaînées ont un gros défaut lorsqu'on souhaite lire ce qu'elles contiennent : il n'est pas possible d'accéder directement à un élément précis. Il faut parcourir la liste en avançant d'élément en élément jusqu'à trouver celui qu'on recherche. Cela pose des problèmes de performance dès que la liste chaînée devient volumineuse.

Comprenez l'intérêt d'une table de hachage

Les listes chaînées permettent d'ajouter ou de supprimer des cases à tout moment. Toutefois, elles ont quand même un gros défaut : si on cherche à récupérer un élément précis de la liste, il faut parcourir celle-ci en entier jusqu'à ce qu'on le retrouve !

Imaginons une liste chaînée qui contienne des informations sur des élèves : leur nom, leur âge et leur moyenne. Chaque élève sera représenté par une structure  Eleve  .

Si je veux retrouver les informations sur Luc Doncieux, il va falloir parcourir toute la liste pour se rendre compte qu'il était à la fin :

Dans cet exemple, notre liste chaînée ne contient que quatre éléments. L'ordinateur retrouvera Luc Doncieux très rapidement. Mais imaginez que celui-ci se trouve à la fin d'une liste chaînée de 10 000 éléments ! Ce n'est pas acceptable de devoir parcourir jusqu'à 10 000 éléments pour retrouver une information.

C'est là que les tables de hachage entrent en jeu.

Si vous vous souvenez bien, les tableaux ne connaissaient pas ce problème. Pour accéder à l'élément d'indice 2 dans mon tableau, il me suffisait d'écrire ceci :

int tableau[4] = {12, 7, 14, 33};
printf("%d", tableau[2]);

Si on lui donne tableau[2], l'ordinateur va directement à la case mémoire où se trouve stocké le nombre 14. Il ne parcourt pas les cases du tableau une à une.

Il y a un défaut important avec les tableaux dont on n'a pas beaucoup parlé jusqu'ici : les cases sont identifiées par des numéros qu'on appelle des indices. Il n'est pas possible de demander à l'ordinateur : "Dis-moi quelles sont les données qui se trouvent à la caseLuc Doncieux ".

Pour retrouver l'âge et la moyenne de Luc Doncieux, on ne peut donc pas écrire :

tableau["Luc Doncieux"];

Ce serait pourtant pratique de pouvoir accéder à une case du tableau rien qu'avec le nom ! Eh bien avec les tables de hachage, c'est possible !

Un tableau reste un tableau, et celui-ci ne fonctionne qu'avec des indices numérotés.

Imaginez un tableau dans lequel chaque case a un indice et possède un pointeur vers une structure de type Eleve :

Si on veut retrouver la case correspondant à Luc Doncieux, il faut transformer son nom en indice du tableau, et donc associer chaque nom à un numéro de case :

• Julien Lefebvre = 0 ;

• Aurélie Bassoli = 1 ;

• Yann Martinez = 2 ;

• Luc Doncieux = 3.

Il faut écrire une fonction qui prend en entrée une chaîne de caractères, fait des calculs avec, puis retourne en sortie un numéro correspondant à cette chaîne.

Ce numéro sera l'indice de la case dans notre tableau :

Écrivez une fonction de hachage

Toute la difficulté consiste à écrire une fonction de hachage correcte. Comment transformer une chaîne de caractères en un nombre unique ?

Tout d'abord, mettons les choses au clair : une table de hachage ne contient pas 4 cases comme sur mes exemples, mais plutôt 100, 1 000 ou même plus. Peu importe la taille du tableau, la recherche de l'élément sera aussi rapide.

Imaginons donc un tableau de 100 cases dans lequel on va stocker des pointeurs vers des structures Eleve.

Eleve* tableau[100];

Nous devons écrire une fonction qui, à partir d'un nom, génère un nombre compris entre 0 et 99 (les indices du tableau). C'est là qu'il faut être inventif. Il existe des méthodes mathématiques très complexes pour "hacher" des données, c'est-à-dire les transformer en nombres.

Vous pouvez inventer votre propre fonction de hachage. Ici, pour faire simple, je vous propose d'additionner les valeurs ASCII de chaque lettre du nom, c'est-à-dire pour Luc Doncieux, de faire la somme suivante :

'L' + 'u' + 'c' + ' ' + 'D' + 'o' + 'n' + 'c' + 'i' + 'e' + 'u' + 'x'

On va toutefois avoir un problème : cette somme dépasse 100 ! Comme notre tableau ne fait que 100 cases, si on s'en tient à ça, on risque de sortir des limites du tableau.

Pour régler le problème, on peut utiliser l'opérateur modulo %  . Vous vous souvenez de lui ? Il donne le reste de la division !

Si on fait le calcul :

sommeLettres % 100

… on obtiendra forcément un nombre compris entre 0 et 99.

Par exemple, si la somme fait 4 315, le reste de la division par 100 est 15. La fonction de hachage retournera donc 15.

Voici à quoi pourrait ressembler cette fameuse fonction :

int hachage(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= 100;

    return nombreHache;
}

Si on lui envoie hachage("Luc Doncieux")  , elle renvoie 55. Avec hachage("Yann Martinez")  , on obtient 80.

Grâce à cette fonction de hachage, vous savez donc dans quelle case de votre tableau vous devez placer vos données ! Lorsque vous voudrez y accéder plus tard pour en récupérer les données, il suffira de hacher à nouveau le nom de la personne pour retrouver l'indice de la case du tableau où sont stockées les informations !

Cela donnerait par exemple :
infosSurLuc = rechercheTableHachage(tableau, "Luc Doncieux");

Gérez les collisions

Deux raisons peuvent expliquer une collision.

1. La fonction de hachage n'est pas très performante. C'est notre cas : nous avons écrit une fonction très simple (mais néanmoins suffisante) pour nos exemples. Les fonctions MD5 et SHA1 mentionnées plus tôt sont de bonne qualité car elles produisent très peu de collisions. SHA1 est aujourd'hui préférée à MD5 car c'est celle des deux qui en produit le moins.

2. Le tableau dans lequel on stocke nos données est trop petit. Si on crée un tableau de 4 cases et qu'on souhaite stocker 5 personnes, on aura à coup sûr une collision, c'est-à-dire que notre fonction de hachage donnera le même indice pour deux noms différents.

Si une collision survient, pas de panique ! Deux solutions s'offrent à vous, au choix :

1. L'adressage ouvert.

2. Et le chaînage.

Solution 1 : l'adressage ouvert

S'il reste de la place dans votre tableau, vous pouvez utiliser la technique dite du hachage linéaire. Le principe est simple. La case est occupée ? Pas de problème, allez à la case suivante. Ah, elle est occupée aussi ? Allez à la suivante !

Ainsi de suite, continuez jusqu'à trouver la prochaine case libre dans le tableau. Si vous arrivez à la fin du tableau, retournez à la première case et continuez.

Solution 2 : le chaînage

Une autre solution consiste à créer une liste chaînée à l'emplacement de la collision. Vous avez deux données (ou plus) à stocker dans la même case ? Utilisez une liste chaînée et créez un pointeur vers cette liste depuis le tableau :

Bien entendu, on en revient au défaut des listes chaînées : s'il y a 300 éléments à cet emplacement du tableau, il va falloir parcourir la liste chaînée jusqu'à trouver le bon.

En résumé

• Les listes chaînées sont flexibles, mais il peut être long de retrouver un élément précis à l'intérieur car il faut les parcourir case par case.

• Les tables de hachage sont des tableaux. On y stocke des données à un emplacement déterminé par une fonction de hachage.

• La fonction de hachage prend en entrée une clé (ex. : une chaîne de caractères) et retourne en sortie un nombre.

• Ce nombre est utilisé pour déterminer à quel indice du tableau sont stockées les données.

• Une bonne fonction de hachage doit produire peu de collisions, c'est-à-dire qu'elle doit éviter de renvoyer le même nombre pour deux clés différentes.

• En cas de collision, on peut utiliser l'adressage ouvert (recherche d'une autre case libre dans le tableau) ou bien le chaînage (combinaison avec une liste chaînée).

Toutes les bonnes choses ont une fin, et c’est malheureusement le cas de ce cours.

Merci de l'avoir suivi !

Téléchargez la fiche résumé du cours

Comme le langage C n’a plus de secret pour vous, laissez-vous tenter par le C++ !

Poursuivez votre apprentissage avec le C++

Pourquoi ne pas apprendre le C++ ?

C'est un langage cousin du C et bonne nouvelle, j'ai aussi créé des cours sur le sujet !

Avec ce que vous venez d'apprendre sur le C, vous ne serez pas dépaysé, et vous comprendrez rapidement les premiers chapitres !

Grâce au C++, vous pourrez faire de la programmation orientée objet (POO). C'est un petit peu complexe au premier abord, mais cette façon de programmer vous permet ensuite d'être très efficace !