Table de hachage - Définition

Fonction de Hachage

Une fonction de hachage permet de transformer une clé en une valeur de hachage (un index), donnant ainsi la position d'un élément dans le tableau. Si la clé n'est pas un entier naturel, il faut trouver un moyen de la considérer comme un entier naturel. Par exemple, si la clé est de type Chaine de caractères, on peut ajouter la position dans l'alphabet de chaque lettre pour obtenir un entier naturel. Il suffit ensuite de transformer cet entier en index par différentes façons. Par exemple, en prenant le reste de la division de l'entier par le nombre d'éléments dans le tableau.

Voici l'une des fonctions de hachage les plus puissantes écrite par Daniel J. Bernstein (en langage C) :

      unsigned long hash(unsigned char *str)      {      	unsigned long hash = 5381;      	while(*str!='\0') {      	        int c = *str;                      /* hash = hash*33 + c */                      hash = ((hash << 5) + hash) + c;                      str++;              }      	return hash;      }