Hachage par adressage ouvert

La table de hachage est implémentée comme un tableau $t$ dont les cases vont contenir les objets. Initialement, la table est vide, c'est-à-dire chaque case contient un objet spécial vide (par exemple, un objet dont la clé est la chaîne vide "").

const data empty_data = {""} ;

bool is_empty(data d) {
  return d.key.length() == 0;
}

void init(int N, data t[]) {
  int i;

  for (i=0; i<N; i++) {
    t[i] = empty_data;
  }
}

Puis des opérations d'insertion sont réalisées. Si un objet de clé $x$ doit être inséré, et que $t[h(x)]$ est vide, alors l'insertion se fait à cette place ; si par contre $t[h(x)]$ est déjà occupé, et que le contenu a une clé différente de $x$, alors on calcule des valeurs de hachage supplétives $h_1(x)$, $h_2(x)$, ...jusqu'à ce que l'on trouve $t[h_i(x)]$ vide ou contenant un objet de clé $x$.

Pour générer ces nouvelles valeurs de hachage, la méthode la plus simple est le hachage linéaire, qui choisit $h_i(x) = (h(x)+i) \mathop{\normalfont\mathrm{mod}}\nolimits N$, ce qui revient à essayer les cases suivant $t[h(x)]$. Il y a d'autres méthodes (hachage quadratique, double hachage, hachage aléatoire) qui ont de meilleures capacités de dispersion.

bool insert(const data& d, int N, const data t[]) {
  int v = h(d.key);
  int i;

  for (i=0; i<N; i++) {
    if (is_empty (t[(v+i)%N])) {
      t[(v+i)%N] = d;  // insertion à la ième place disponible
      break;
    } else if (t[(v+i)%N].key == d.key) {
      break;           // ou bien, mise à jour des autres champs 
    } 
  }
  if (i == N) {
    return false;      // table pleine, insertion non réalisée 
  } else {
    return true;       // objet déjà dans la table ou inséré 
  }
}

De même, pour chercher un objet de clé $x$, on teste les objets en $t[h(x)]$, et éventuellement en $t[h_1(x)]$, $t[h_2(x)]$, etc, jusqu'à ce que la clé de l'objet qui s'y trouve soit égale à $x$, ou bien que l'objet soit vide. Dans le cas où la table permet aussi des suppressions, il faut remplacer un objet supprimé par un objet spécial supprimé, distinct de l'objet vide ; en insertion, on utilisera la première case vide ou supprimé, tandis qu'en recherche, on ne s'arrêtera qu'à la première case vide.

data& search(const string s, int N, const data t[]) {
  int v = h(s);
  int i;

  for (i=0; i<N; i++) {
    if (is_empty (t[(v+i)%N])) {
      return empty_data;
    } else if (t[(v+i)%N].key == s) {
      return t[(v+i)%N];
    } 
  }
  return empty_data;      // objet non trouvé 
}

Il est clair que la complexité dans le pire des cas est de $N$ opérations, $N$ étant la taille de la table. On définit le taux de chargement d'une table de hachage de taille $N$ contenant $n$ objets comme la fraction $\alpha = n/N$ ; on a toujours $0\le \alpha\le 1$. Pour donner une estimation asymptotique de la complexité des opérations, on fait tendre $n$ et $N$ vers l'infini, à $\alpha$ constant. On montre que, sous une hypothèse d'uniformité, le nombre moyen d'accès nécessaires pour une recherche négative est d'au plus $1/(1-\alpha)$ et pour une recherche positive de $\frac{1}{\alpha}\log \frac{1}{1-\alpha} + \frac{1}{\alpha}$. Par exemple pour une table à moitié pleine, on doit s'attendre à faire 2 accès pour la recherche d'un objet ne se trouvant pas dans la table, et et à faire 3,387 accès s'il s'y trouve. Il s'agit bien d'un algorithme en $\Theta(1)$.