Facteur de charge d’une table de hachage

Ce calculateur effectue cette opération, compare le résultat au seuil que vous choisissez et indique si un redimensionnement est conseillé. Il estime aussi le nombre minimal de compartiments qui placerait les éléments actuels strictement sous ce seuil. Utilisez-le pour examiner une implémentation, planifier la capacité, contrôler l’état observé d’une table ou transformer une politique de redimensionnement en test automatisé reproductible.

Calculez le facteur avec des décomptes cohérents

Saisissez le nombre d’éléments actuellement stockés et celui des compartiments alloués. Le calculateur divise le premier par le second : 600 éléments répartis dans 800 compartiments donnent ainsi un facteur de charge de 0.75, soit 75%. Comptez les entrées logiques plutôt que les compartiments occupés : deux entrées en collision dans un même compartiment restent deux éléments. Utilisez également la capacité réelle de la table, et non le seul nombre de compartiments contenant une entrée. Ces définitions doivent rester cohérentes, car le facteur décrit le nombre moyen d’entrées par compartiment et non le pourcentage de compartiments non vides. Le nombre d’éléments peut être nul, tandis que celui des compartiments doit être un entier positif : une division par zéro ne représente aucun état valide. Effectuez des calculs distincts pour des tables, shards ou partitions indépendants. L’agrégation peut masquer une partition très chargée derrière la capacité disponible ailleurs, même si le rapport global paraît acceptable. La valeur décimale et le pourcentage renvoyés expriment le même rapport sous des formes adaptées au code et aux rapports.

Choisissez et interprétez le seuil de redimensionnement

Le seuil est le facteur de charge auquel votre politique prévoit un redimensionnement. Sa valeur par défaut est 0.75, mais vous pouvez fournir toute valeur finie positive conforme à la conception de la table. Les tables à adressage ouvert nécessitent souvent un seuil inférieur à 1, puisque chaque élément occupe un emplacement et que les séquences de sondage s’allongent à mesure que les places libres disparaissent. Les implémentations par chaînage séparé peuvent fonctionner au-dessus de 1, plusieurs éléments pouvant partager un compartiment, même si le coût des collisions augmente généralement avec le rapport. Le calculateur ne présume aucune stratégie de collision : il applique le seuil fourni. La limite est inclusive, donc le redimensionnement est conseillé lorsque le facteur non arrondi est égal ou supérieur au seuil. La comparaison emploie la valeur complète, tandis que l’affichage arrondit le facteur afin de stabiliser la sortie. Cet écart empêche l’arrondi visuel de modifier une décision proche de la limite. Voyez le résultat comme l’évaluation d’une politique déclarée, pas comme la preuve qu’un seuil convient à toute charge, fonction de hachage, contrainte mémoire ou cible de latence.

Transformez le résultat en décision de capacité

Lorsqu’un redimensionnement est conseillé, le résultat fournit le plus petit nombre mathématique de compartiments qui placerait les éléments actuels strictement sous le seuil choisi. Il correspond à la partie entière inférieure du nombre d’éléments divisé par le seuil, augmentée de un. La sortie indique aussi le nombre de compartiments supplémentaires par rapport à l’allocation actuelle. Il s’agit d’un minimum imposé par la politique, pas nécessairement de la capacité exacte à allouer. De nombreuses tables grandissent géométriquement, souvent en doublant leur capacité ; d’autres exigent une puissance de deux, un nombre premier ou une valeur compatible avec un allocateur fixe. Arrondissez ce minimum vers le prochain format valable, puis anticipez les insertions prochaines afin de ne pas franchir aussitôt le seuil. Si aucun redimensionnement n’est conseillé, le supplément indiqué vaut zéro, même si le minimum calculé est inférieur à l’allocation existante. Pour automatiser la décision, utilisez l’indicateur booléen comme condition stable et conservez les décomptes, le seuil et le facteur dans les journaux. L’API déterministe coûte $0.002 par requête et applique le même calcul que le navigateur.