Fonction de hachage

    

Voici un exemple simple de fonction de hachage sur des chaînes de longueur l à valeurs dans l'intervalle [0,N-1] :

$$h(x) = \sum_{i=0}^{l-1} x[i] B^{l-1-i} \mathop{ \normalfont \mathrm{mod}}\nolimits N$$

où B est une puissance de 2 (pour faciliter le calcul, par exemple B=256) et N est un nombre premier (pour éviter des collisions << arithmétiques >>) ; la fonction suivante retourne un unsigned int pour garantir que la valeur est positive et prend en argument une chaîne de longueur arbitraire :

#define B 256
#define N 311

unsigned int h(char x[]) {
  unsigned int v = 0;
  int i;

  for (i=0; x[i] != '\0'; i++) {
    v = (v*B + x[i]) % N;
  }
  return v;
}

On dit que h(x) est la valeur de hachage associée à la clé x.

Comme la fonction de hachage h n'est pas injective, il faut savoir traiter les collisions, c'est-à-dire le cas de deux clés $x\not= y$ayant la même valeur de hachage h(x) = h(y). Il existe deux sortes de techniques de résolution, selon que l'espace mémoire disponible est illimité ou pas.