Calculatrice de Facteur de Charge d'une Table de Hachage (Sondages Attendus : Linéaire, Double, Chaînage)
Le facteur de charge d'une table de hachage et le nombre moyen de sondages d'une recherche — sondage linéaire, double hachage et chaînage — plus la taille de table qui la garde sous une charge choisie.
Résultats
La ligne en pointillé marque la valeur que vous avez saisie.
Ce que fait cet outil
Une table de hachage n'est rapide que tant qu'elle n'est pas trop pleine. En sondage linéaire, chercher une clé absente coûte en moyenne 2,5 sondages à un facteur de charge de 0,5, mais 50,5 à 0,9 ; le double hachage est plus doux (10 à 0,9) et le chaînage se dégrade progressivement, une charge supérieure à 1 signifiant simplement des chaînes plus longues. Les tables à adressage ouvert se redimensionnent donc bien avant d'être pleines, souvent entre 50 % et 75 % de charge. Ce sont les moyennes de Knuth pour une bonne fonction de hachage.
Formule
α = n ÷ m · linear probing: hit ½(1 + 1/(1−α)), miss ½(1 + 1/(1−α)²) · double hashing: hit (1/α) ln(1/(1−α)), miss 1/(1−α) · chaining: hit 1 + α/2, miss α
Variables
| Symbole | Signification | Unité |
|---|---|---|
n | Éléments stockés | — |
m | Taille de la table (cases ou paniers) | — |
ml | Plus grand facteur de charge que vous voulez permettre | — |
LU | Sondage linéaire : sondages si l'élément est absent | — |
LF | Facteur de charge α (éléments ÷ cases) | — |
LS | Sondage linéaire : sondages pour trouver un élément | — |
DS | Double hachage : sondages pour trouver un élément | — |
DU | Double hachage : sondages si l'élément est absent | — |
CS | Chaînage : comparaisons pour trouver un élément | — |
CU | Chaînage : comparaisons si l'élément est absent | — |
SZ | Taille de table qui garde la charge à votre limite | — |
Exemple résolu
- Éléments stockés700
- Taille de la table (cases ou paniers)1000
- Plus grand facteur de charge que vous voulez permettre0,7
- Sondage linéaire : sondages si l'élément est absent6,06
- Facteur de charge α (éléments ÷ cases)0,700
- Sondage linéaire : sondages pour trouver un élément2,17
- Double hachage : sondages pour trouver un élément1,72
- Double hachage : sondages si l'élément est absent3,33
- Chaînage : comparaisons pour trouver un élément1,35
- Chaînage : comparaisons si l'élément est absent0,70
- Taille de table qui garde la charge à votre limite1000
Limites
- La formule suppose des conditions idéales : pas de frottement, pas de résistance de l'air et pas de pertes de rendement sauf si vous les saisissez.
- Le résultat est une estimation fondée uniquement sur les valeurs saisies. Les situations réelles comportent souvent des facteurs que cette calculatrice ignore.