Voici un exemple simple de fonction de hachage sur des chaînes de
longueur à valeurs dans l'intervalle
:
#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 est la valeur de hachage associée à la clé
.
Comme la fonction de hachage n'est pas injective, il faut savoir
traiter les collisions, c'est-à-dire le cas de deux clés
ayant la même valeur de hachage
. Il existe deux sortes de
techniques de résolution, selon que l'espace mémoire disponible est
illimité ou pas.