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.