Principe
Intuitivement, la recherche d'une chaîne de caractère dans un tableau nécessite la lecture et chacune des cases du tableau et la comparaison avec la chaîne de référence. Cette technique ne pose aucun soucis sur de petites tables.
|
| Figure 1: recherche systématique |
D'un point de vue macroscopique, l'algorithme est en ordre de n (statistiquement n/2), où n est le nombre d'éléments du tableau. A cet ordre, un coefficient multiplicateur correspondant à la méthode de comparaison des chaînes (strcmp()) doit être appliqué. Statistiquement, on trouvera la solution après n/2 * smoy comparaison de caractères, ou smoy est la taille moyenne d'une chaîne de caractères.
Afin diminuer l'ordre de l'algorithme de recherche, on cherche à déplacer le problème. Puisque les chaînes de caractères sont difficiles à comparer, nous allons supposer une fonction particulière qui transforme une chaîne de caractères en un nombre entier. Cette fonction est appelée fonction de hashage. Cette fonction nous permettra de ne plus avoir à comparer deux chaînes, mais deux entiers, ce qui est biensur beaucoup plus rapide.
En poussant le raisonnement un peu plus avant, on pourra même supposer que l'entier en question pourrait même servir d'index en réglant quelques détails techniques.
|
| Figure 2: Fonction de hashage servant d'index |
Il existe deux catéfories de fonctions de hashage. Si la fonction est une application, i.e. est injective, ou encore, si toute chaîne passée
en entrée de cette fonction produit un nombre unique, alors la fonction de hashage est dite parfaite.
Toute fonction de hashage fournissant le même nombre à partir de deux chaînes différentes est dite imparfaite.
D'un point de vue général, on peut penser que les chaînes de caractères n'auront a priori pas toutes la même taille. Et à l'exemple du C, Il n'y a pas de taille maximale pour une chaîne. Cependant, un entier, lui, est limité en taille. S'il est codé sur 32 bits, il ne pourra stocker de manière unique que des chaînes d'au maximum 32 caractères. On peut biensur jongler avec le nombre de caractères réellement admis dans une chaîne de caractères réelle. Cependant, nous resterions dans le cadre du code ascii. Or, dans les chaînes de caractères modernes, un caractère n'est pas obligatoirement codé sur 8bits (comme le code UTF, par exemple).
A contrario, un codage sur 32bits nous donnerait un tableau final de 232 = 4 294 967 296 entrées. Par comparaison, un petit dictionnaire papier comporte de l'ordre de la dizaine de miliers de mots. Indexer dans ce cas un dictionnaire par cette méthode « parfaite » ne prendrait pas en compte les mots de plus de 32 caractères et consommerait 4 294 967 296 * la taille de chaque entrée. Dans l'hypothèse ou chaque case est un pointeur de taille 4 octets, nous devrions réserver 232 * 4 octets, soit 16 Go. Même si la RAM est peu onéreuse et que nos disques durs sont gargantuesques, ce nombre parait un peu éléve. A fortiori si l'on considère que seulement 40 000 mots sont réellement indexés, soit un taux d'occupation de 1 pour 10 000.
Il apparaît donc évident que hormis dans certains cas particuliers, l'utilisation d'une fonction de hashage parfaite n'est pas une bonne solution.
Cependant, si notre fonction de hashage ne peut pas être parfaite, nous allons devoir affronter des collisions. En effet, si 2 chaînes différentes
produisent un même entier, notre index correspondra à 2 chaînes différentes, mais une seule case de tableau. Nous devons donc faire intervenir
un système de chaînage (voir Composants, réutilisation et généricité :
Une application aux listes doublement chaînées) afin d'augmenter la capacité du tableau dans une autre dimension.
|
| Figure 3: gestion des collisions |
Les fonctions de hashage dans leur ensemble sont assez nombreuses et complexes. Elles nous viennent directement de l'univers de la sécurité où elles sont utilisées comme signatures électroniques ou encore comme base de clefs de chiffrement. Elles ont pour but de réduire l'information tout en conservant les traits caractère. Elles sont supposées ne pas avoir de fonction réciproque. Pour n'en citer que quelques unes, nous avons les Message Digest (MD4, MD5), les Secure Hash Algorithm (SHA-1, SHA-2), ou autre RIPEMD.
Cependant, pour implémenter une table de hashage, les nombreuses contraintes de sécurité ne sont pas nécessaires. En général, il suffit de s'assurer que pour l'ensemble des chaînes à indexer, la fonction doit être raisonnablement homogène et ne pas favoriser les collisions. Une fonction classiquement utilisée est la suivante :
int hash_classic(char *name) {
int accum = 0;
int len;
len = strlen(name));
accum = 0;
for (;len > 0; len--) {
accum <<= 1;
accum += (unsigned) (*name++ & 0xFF);
}
return accum;
}
Il est bien évident que la valeur retournée (accum) n'est pas directement utilisable. En effet, accum est un entier (signé ou non). Nous n'alloueront en général jamais un tableau indexable par un entier (232 ou 264 possibilités en fonction du codage de l'entier). Au contraire, nous réserverons un tableau de taille raisonable (nous reverrons cette notion plus loin). Admettons que nous considérions un tableau de 500 cases. Dans ce cas, il faudrait convertir accum pour qu'il ne retourne que des valeurs comprises entre 0 et 499. A cette fin, nous pouvons utiliser l'opération en modulo (%) La dernière ligne de notre fonction classique sera donc :
return accum % 500;
