Une table de hachage à chaînage démarre avec 8 cases. Elle double de taille dès qu'une insertion ferait dépasser au facteur de charge la valeur 0,75. Doubler signifie allouer un tableau deux fois plus grand et y ranger à nouveau, une par une, toutes les clés déjà présentes.
On y insère 100 clés distinctes, une par une.
Rappel
Le facteur de charge est . Ranger une clé dans une case compte pour un rangement, qu'il s'agisse d'une nouvelle clé ou d'une clé déplacée lors d'un doublement.
Objectif
Suivre l'évolution de la table jusqu'à la centième insertion, et en déduire le coût moyen d'une insertion.