Probleme – Une table de hachage par chaînage, sur tableaux statiques

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\le \text{libre}\le \text{CAP}$, et seuls les indices $0$ à $\text{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 $<\text{libre}$, terminée par $-1$ ;
• tout couple d'indice $p$ figure dans la liste de la case $h(\text{cle}[p])\mathrm{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 $\alpha =4,22$ :

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 $\alpha$ dépasse un seuil — $1$, ou $2$, selon le compromis mémoire/vitesse voulu —, on alloue une table de $2M$ cases et l'on réinsère toutes les clés. Il ne s'agit pas d'une simple recopie : $h(c)\mathrm{mod}M$ et $h(c)\mathrm{mod}2M$ 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,2M_0,4M_0,\dots$, et celui de rang $k$ coûte $\Theta (2^k{M}_0)$. Le total après $n$ insertions vaut

$$\sum _{k=0}^{\lfloor {\log }_2(n/M_0)\rfloor }c{2}^k{M}_0<2cn=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.