Problème — Une table de hachage par chaînage, sur tableaux statiques — exercice corrigé d'informatique (MP2I/MPI) (chapitre 12)

1. La structure. Le chaînage sans malloc s'obtient en rangeant tous les couples dans un même tableau, et en chaînant par des indices plutôt que par des pointeurs — l'idée du chapitre chap:sequentielles, appliquée ici.


#define M    1024      /* nombre de cases, une puissance de deux */
#define CAP  8192      /* nombre maximal de couples rangés */
#define LMAX 32

struct table_s {
    char cle[CAP][LMAX];  /* les couples, dans leur ordre d'insertion */
    int  valeur[CAP];
    int  suivant[CAP];    /* indice du couple suivant de la MEME case, ou -1 */
    int  tete[M];         /* indice du premier couple de la case j, ou -1 */
    int  libre;           /* premier indice non encore utilisé */
};
typedef struct table_s table;

Invariant de la structure, et il tient en trois points :

$0 \leq libre \leq CAP$ , et seuls les indices $0$ à $libre - 1$ portent un couple valide ;
pour toute case $j$ , en suivant tete[j] puis les suivant on obtient une liste finie d'indices deux à deux distincts, tous $< libre$ , terminée par $- 1$ ;
tout couple d'indice $p$ figure dans la liste de la case $h (cle [p]) mod M$ , et dans elle seule. C'est ce dernier point qui fait la table : c'est lui que la recherche exploite.

2. Les opérations.


/* Fonction de hachage polynomiale, base 31 : celle que la mesure a retenue. */
unsigned long hache(const char* s) {
    unsigned long h = 0;
    for (int i = 0; s[i] != '\0'; i = i + 1) { h = 31 * h + (unsigned char) s[i]; }
    return h;
}

/* Initialise t à la table vide. Complexité : Theta(M). */
void t_creer(table* t) {
    assert(t != NULL);
    for (int j = 0; j < M; j = j + 1) { t->tete[j] = -1; }
    t->libre = 0;
}

/* Renvoie l'indice du couple de clé c, ou -1 si c est absente.
   Précondition : t bien formée, c chaîne valide de longueur < LMAX.
   Complexité : O(longueur de la chaîne de c), soit O(1 + alpha) en moyenne. */
int t_chercher(const table* t, const char* c) {
    assert(t != NULL && c != NULL);
    int j = (int) (hache(c) % M);
    for (int p = t->tete[j]; p != -1; p = t->suivant[p]) {
        if (strcmp(t->cle[p], c) == 0) { return p; }
    }
    return -1;
}

/* Associe v à c, en ÉCRASANT une liaison antérieure. Renvoie false si la
   table est pleine. Complexité : celle de t_chercher, plus O(1). */
bool t_poser(table* t, const char* c, int v) {
    int p = t_chercher(t, c);
    if (p != -1) { t->valeur[p] = v; return true; }   /* on écrase */
    if (t->libre >= CAP) { return false; }            /* PLEINE : on le DIT */
    int j = (int) (hache(c) % M);
    p = t->libre;
    t->libre = t->libre + 1;
    strncpy(t->cle[p], c, LMAX - 1);
    t->cle[p][LMAX - 1] = '\0';                       /* strncpy ne TERMINE pas */
    t->valeur[p] = v;
    t->suivant[p] = t->tete[j];                       /* insertion EN TÊTE : O(1) */
    t->tete[j] = p;
    return true;
}

Trois points de méthode. L'insertion se fait en tête de chaîne, en $O (1)$ : insérer en queue coûterait la longueur de la chaîne pour rien. La recherche précède l'insertion, pour respecter la sémantique « une valeur par clé » — c'est replace et non add. Et strncpy ne pose pas la sentinelle quand la source est trop longue : on l'écrit à la main, faute de quoi on retrouverait la faute du chapitre chap:langage-c.

Terminaison de t_chercher : le variant est le nombre de couples restants dans la chaîne ; l'invariant garantit qu'elle est finie et sans cycle. Correction : si $c$ est présente, elle est dans la chaîne de sa case par l'invariant, et la boucle la parcourt entièrement.

3. Les mesures. $4321$ mots français, $M = 1024$ , donc $α = 4, 22$ :

	mesuré	prévu
recherche fructueuse (les $4321$ mots)	$3, 11$ sondages	$1 + α /2 = 3, 11$
recherche infructueuse ( $10000$ mots absents)	$4, 30$ sondages	$α = 4, 22$
plus longue chaîne	$13$	—

La prévision tombe juste à deux décimales pour la recherche fructueuse. Et il faut mesurer les deux recherches : elles n'ont pas le même coût, et c'est l'infructueuse — celle qui parcourt toute la chaîne — qui domine dans un correcteur orthographique ou un pare-feu, où la réponse est le plus souvent « absent ».

4. Le redimensionnement. Quand $α$ dépasse un seuil — $1$ , ou $2$ , selon le compromis mémoire/vitesse voulu —, on alloue une table de $2 M$ cases et l'on réinsère toutes les clés. Il ne s'agit pas d'une simple recopie : $h (c) mod M$ et $h (c) mod 2 M$ sont deux cases différentes, donc chaque clé doit être re-hachée.

Le coût amorti, par le même argument que le tableau dynamique du chapitre chap:algo-prog. Partant de $M_{0}$ cases, les redimensionnements ont lieu quand $n$ atteint $M_{0}, 2 M_{0}, 4 M_{0}, \dots$ , et celui de rang $k$ coûte $Θ (2^{k} M_{0})$ . Le total après $n$ insertions vaut

$k = 0 \sum ⌊ l o g_{2} (n / M_{0})⌋ c 2^{k} M_{0} < 2 c n = O (n),$

soit $O (1)$ amorti par insertion. C'est encore la croissance géométrique qui télescope la somme : doubler la taille, et non l'augmenter d'une constante.

Ce que le tableau statique interdit. Avec CAP fixé à la compilation, on ne redimensionne pas : la table est pleine, et t_poser rend false. C'est le prix du « sans allocation dynamique » que demande le programme, et il faut le dire à l'appelant plutôt que de le taire — d'où le type de retour bool, qui n'est pas décoratif. Une structure à capacité bornée doit rendre compte de sa saturation, sans quoi les données disparaissent en silence.

Problème — Une table de hachage par chaînage, sur tableaux statiques

Énoncé

Corrigé

Exercices semblables