Le facteur de charge, et ce qu'il permet de prévoir

1. Les cases vides. Une case donnée reçoit une clé donnée avec probabilité $1/m$ ; elle reste vide après $n$ tirages indépendants avec probabilité $(1-1/m{)}^n$, qui vaut $e^{-\alpha }$ à la limite, où $\alpha =n/m$. Le nombre moyen de cases vides est donc

$$m(1-\frac{1}{m}{)}^n\approx m{e}^{-\alpha }.$$

Le cas $\alpha =1$ mérite d'être retenu : même en dimensionnant la table exactement au nombre de clés, $e^{-1}\approx 37\%$ des cases restent vides — et donc $37\%$ des clés se pressent ailleurs. On ne remplit jamais une table de hachage uniformément.

2. Le coût des recherches.

• Infructueuse : on parcourt toute la chaîne de la case visée, dont la longueur moyenne est $\alpha$. Coût : $1+\alpha$ comparaisons — le $1$ pour le calcul du haché.
• Fructueuse : la clé cherchée est à une position moyenne de $1+\alpha /2$ dans sa chaîne. Plus précisément, si la $i$-ième clé insérée trouve $(i-1)/m$ clés en moyenne devant elle, le coût moyen sur les $n$ clés vaut $1+\frac{1}{n}{\sum }_{i=1}^n\frac{i-1}{m}=1+\frac{n-1}{2m}\approx 1+\alpha /2$.

Dans les deux cas, le coût dépend de $\alpha$ et pas de $n$. C'est tout le principe : on redimensionne dès que $\alpha$ dépasse un seuil, et le coût reste borné. La recopie coûte $\Theta (n)$, mais elle est amortie sur les $n/2$ insertions qui l'ont précédée — exactement le calcul du tableau dynamique du chapitre chap:algo-prog.

3. Les mesures. Table à chaînage écrite en C, $4321$ mots, $m=1024$, donc $\alpha =4,22$ :

Et sur le remplissage, par tirage uniforme :

La théorie tombe juste à quatre chiffres. Ce n'est pas une coïncidence, c'est ce que veut dire « en moyenne » : ces formules décrivent le comportement d'une table dont la fonction de hachage disperse bien, et rien d'autre. Avec h_somme de l'exercice précédent, elles seraient fausses d'un facteur $4$.