Nous avons déjà dit que, étant donné une fonction de hash raisonnablement bonne, le taux d'occupation de la table doit rester relativement faible pour minimiser le risque de collision. Lorsque la table se remplit, le nombre de collision augmente et la performance se dégrade.

Si nous résolvons les collisions par adressage ouvert, il est clair qu'une table trop remplie provoquera des séquences de sondage très longues.

Le problème se pose aussi avec les résolutions de collision par buckets ou par listes chaînées (qui ne sont pas fondamentalement différentes.) Si un bucket est trop plein, ou si la liste est trop longue, le temps de recherche d'une clef dans ce bucket, ou cette liste, augmentera significativement.

Donc, que faire lorsque la table sature? La réponse évidente, c'est qu'il faut la redimensionner. La question moins évidente, c'est comment le faire. Nous avons seulement deux options: redimensionner ex situ, ou in situ ¹.

Redimensionner ex situ est sûrement la solution la plus facile: il s'agit seulement de créer une autre table de plus grande dimension et d'y transferer toutes les clefs contenues dans la table originale. Il suffit en effet de balayer la premier table, et, pour chaque clef trouvée, l'insérer dans la nouvelle table. Une fois l'opération terminée, on substitue la nouvelle table à l'ancienne, et le tour est joué.

C'est simple, efficace, mais nécessite d'allouer de la mémoire pour les deux tables simultanément. Si chaque entrée de la table contient directement les données, cela peut représenter beaucoup de mémoire. Même si les données contenues dans la table ne sont que des pointeurs vers les vraies données (et que les insertions ne consistent qu'en des transferts de pointeurs) cela pourrait représenter une trop importante utilisation de mémoire et être problématique.

Il nous reste donc à redimensionner in situ, c'est-à-dire à l'intérieur de la table même. On commence par redimensionner la table (grâce à une fonction du genre de realloc) et à allouer à chaque clef dans la table un bit pour indiquer si la clef « sale » ou « propre. » Au début, toutes les clefs sont sales. On balaye le tableau jusqu'à la prochaine clef sale et on la re-hash pour lui trouver une nouvelle location. Si elle attérrit dans une case vide, sa réinsertion est terminée. Si elle atterrit sur une case sale, on échange la clef sale avec la clef maintenant propre, et on réinsère la clef que nous venons de retirer du tableau. Si la clef atterrit sur une clef propre, on utilise la résolution de collision (linéaire, incréments, résidu quadratique, etc.) pour lui trouver une nouvelle adresse.

On peut argumenter que redimensionner in situ est nettement supérieur à la redimension ex situ parce qu'on ne maintient pas deux tables en mémoire pendant l'opération. J'ai plusieurs objections à ce raisonnement. Premièrement, il n'est pas dit que la fonction de réallocation de mémoire (comme realloc) ne fera pas à un certain point une copie du tableau. Deuxièmement, le coût de storage est très amoindri si, au lieu de maintenir l'objet complet dans une entrée, nous n'avons qu'un pointeur. Cela amoindrit aussi de façon importante les temps de transfert: copier un pointeur (un int) coûtera toujours moins cher que de déplacer une plus grande structure en mémoire. Finalement, le rehashing ex situ est beaucoup plus simple que le rehashing in situ.