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 "").

 

data t[N];
data empty_data = {""} ;

int is_empty(data d) {
  return strlen(d.key) == 0;
}

void init() {
  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₁(x), h₂(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.

     

int insert(data d) {
  int v = h(d.key);
  int i = 0;
  for (i=0; i<N; i++) {
    if (is_empty (t[(v+i)%N])) {
      t[(v+i)%N] = d;
      break;
    } else if (!strcmp(t[(v+i)%N].key, d.key)) {
      break;       /* ou bien, mise à jour des autres champs */
    } 
  }
  if (i == N) {
    return 0;      /* table pleine, insertion non réalisée */
  } else return 1; /* 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₁(x)], t[h₂(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 char s[]) {
  int v = h(s);
  int i = 0;
  for (i=0; i<N; i++) {
    if (is_empty (t[(v+i)%N])) {
      return empty_data;
    } else if (!strcmp(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)$.