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 :

const int B=256;
const int N=311;

unsigned int h(const string& x) {
  unsigned int v = 0;
  unsigned int i;

  for (i=0; i<x.length(); 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.