Voici un exemple simple de fonction de hachage sur des chaînes de
longueur à valeurs dans l'intervalle
:
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 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.