Adressage ouvert : la suppression naïve casse la recherche

Elle échoue. Mesuré sur une table de $16$ cases avec trois clés de haché $5$ : après l'insertion, les trois sont trouvées ; après la suppression naïve de la deuxième, la première est toujours trouvée et la troisième ne l'est plus — alors qu'elle est toujours dans le tableau, à sa place.

Pourquoi. La recherche s'arrête sur la première case vide, et c'est ce qui la rend correcte et terminante : une case vide sur le chemin prouve que la clé n'a jamais été insérée, puisqu'elle s'y serait posée. Supprimer en remettant une case à « vide » crée donc un faux témoignage : la case dit « rien n'est passé par ici », alors que $c_3$ y est passée et a continué plus loin. La chaîne de sondage est coupée en deux, et tout ce qui est au-delà devient invisible.

C'est un défaut particulièrement traître, parce que la table reste cohérente en apparence : les données sont là, l'invariant de forme est respecté, la recherche ne plante pas — elle rend simplement « absent » pour des clés présentes, et seulement pour certaines.

La parade : la pierre tombale. On distingue trois états de case au lieu de deux.

int etat[M];      /* 0 = jamais occupee, 1 = occupee, 2 = PIERRE TOMBALE */

/* Recherche : on s'arrete sur une case JAMAIS occupee, on traverse les tombales. */
int chercher(const char* c) {
    int j = (int) (hache(c) % M);
    for (int k = 0; k < M; k = k + 1) {
        int i = (j + k) % M;
        if (etat[i] == 0) { return -1; }                        /* preuve d'absence */
        if (etat[i] == 1 && strcmp(cle[i], c) == 0) { return i; }
        /* etat[i] == 2 : on CONTINUE, la chaine n'est pas coupee */
    }
    return -1;
}
/* Suppression : on marque, on n'efface pas. */
void retirer(const char* c) {
    int i = chercher(c);
    if (i != -1) { etat[i] = 2; }
}

Mesuré : avec la pierre tombale, les deux clés restantes sont retrouvées.

Ce que la pierre tombale coûte. Une case tombale est libre à l'insertion mais occupée à la recherche : elle allonge les chaînes de sondage sans contenir de donnée. Un cycle de $n$ insertions et $n$ suppressions remplirait la table de tombales et ferait dégénérer toutes les recherches. On compte donc les tombales, et l'on reconstruit la table quand elles deviennent trop nombreuses — ce qui, amorti, reste en $O(1)$ par opération.

La leçon générale. L'adressage ouvert range dans une case des informations qui ne lui appartiennent pas : la position d'une clé y dépend de l'histoire des insertions, pas de la seule clé. Toute opération qui réécrit cette histoire — et la suppression en est une — doit préserver ce qu'elle porte. Le chaînage n'a pas ce problème : chaque case y est indépendante des autres, et la suppression y est un simple retrait de liste. C'est une raison de fond de préférer le chaînage, et c'est le choix que fait Hashtbl.