Collisions de hachage attendues

Lorsque l'on disperse n clés distinctes de façon uniforme dans m cases, certaines partagent un emplacement même à un facteur de charge modeste. L'intuition sous-estime l'occupation : on retient la probabilité du paradoxe des anniversaires qu'au moins une paire entre en collision, puis on traite cette probabilité comme un dénombrement. Cette calculatrice de collisions de hachage attendues répond à une autre question de dimensionnement. Elle s'appuie sur le modèle classique des boules et des urnes — chaque élément choisit une des m cases de manière indépendante et uniforme — et renvoie le nombre attendu de clés en collision, c'est-à-dire celles qui ne sont pas seules dans leur case. À côté de ce chiffre principal, elle indique les clés singleton, les cases occupées et vides, les clés de débordement au-delà du premier occupant, les collisions par paires et le facteur de charge n divisé par m. L'arithmétique est une identité sous forme fermée évaluée en espace logarithmique, entièrement déterministe, sans échantillonnage Monte Carlo ni modèle de langage. Servez-vous-en pour dimensionner une table de hachage, régler un facteur de charge, comparer un espace de hachage 32 bits à un espace plus étroit, ou vérifier une affirmation d'occupation de manuel avant d'engager de la mémoire.

Ce que mesurent les clés en collision attendues dans le modèle boules et urnes

Jetez n boules de façon indépendante et uniforme dans m urnes : vous obtenez le modèle standard d'un hachage uniforme. Une clé en collision est une boule qui partage son urne avec au moins une autre. Ce n'est pas la même grandeur que la probabilité du paradoxe des anniversaires qu'au moins deux boules partagent une urne, ni le nombre de coïncidences par paires.

Pour planifier une capacité, on veut en général un dénombrement : combien de clés, en moyenne, n'obtiennent pas un emplacement privé, combien de cases restent vides tandis que d'autres débordent, et combien de clés supplémentaires s'empilent sur le premier occupant. La linéarité de l'espérance donne des réponses nettes sans simulation. Fixez une clé quelconque.

Les n moins une autres manquent la case de cette clé avec la probabilité un moins un sur m, si bien que la chance que la clé choisie soit singleton vaut (1 − 1/m) élevée à n moins un. Multipliez par n : vous avez le nombre attendu de clés singleton. Soustrayez de n : vous avez le nombre attendu de clés en collision, soit n fois un moins (1 − 1/m) à la n moins un.

Le même argument d'occupation donne le nombre attendu de cases vides, m fois (1 − 1/m) à la n, donc celui des cases occupées. Les clés de débordement sont les éléments au-delà du premier dans chaque case occupée, égales à n moins occupées. Les collisions par paires valent n parmi deux divisé par m, car toute paire donnée tombe ensemble avec la probabilité un sur m.

Le facteur de charge est simplement n sur m. Ensemble, ces chiffres indiquent si une table proposée manque de cases, est seulement occupée, ou paie déjà une taxe de longueur de chaîne qu'un m plus grand supprimerait.

Contrat d'entrée, formules, stabilité numérique et erreurs

Envoyez deux entiers obligatoires : n, le nombre d'éléments, et m, le nombre de cases. Les deux valeurs doivent être des entiers finis dans les limites publiées : n de un à un billion, et m de un à un billion, ce qui couvre les exemples de cours, les maps en mémoire et un espace de hachage 32 bits complet de quatre milliards deux cent quatre-vingt-quatorze millions neuf cent soixante-sept mille deux cent quatre-vingt-seize emplacements.

Après validation, le moteur évalue les puissances de un moins un sur m en espace logarithmique comme l'exponentielle de l'exposant fois log1p de moins un sur m, afin que de grands n et m ne s'effondrent pas vers un zéro silencieux comme le ferait une boucle naïve de multiplications.

Les cas particuliers restent exacts : un seul élément ne collisionne jamais ; une seule case avec deux éléments ou plus fait collisionner toutes les clés ; un exposant zéro est traité comme un, pour que (1 − 1/m) à la puissance zéro ne devienne pas un zéro puissance zéro indéterminé. C'est un oracle de dénombrement attendu sous un hachage uniforme et indépendant, non un simulateur d'une fonction de hachage particulière ni une calculatrice de probabilité de collision.

Planification de capacité, limites, tarif et où les chiffres servent

Utilisez l'outil du navigateur lorsque vous choisissez la taille d'une table, comparez des facteurs de charge ou expliquez à une équipe pourquoi un facteur de charge égal à un laisse encore une grande part de clés partager une case. Augmentez m jusqu'à ce que les clés en collision attendues ou les clés de débordement passent sous votre budget de niveau de service, puis gardez une marge de croissance.

Contrastez le résultat avec une probabilité du paradoxe des anniversaires si vous avez aussi besoin de la chance qu'une collision existe ; cette probabilité sature près de un bien avant que le dénombrement attendu de clés en collision devienne grand, c'est pourquoi les deux outils répondent à des tickets distincts. Les résultats sont pleinement déterministes : les mêmes n et m donnent toujours le même vecteur d'occupation, de sorte que vous pouvez figer des exemples dans des tests et des supports de cours.

Il n'y a ni modèle de langage, ni service externe de statistique, ni aléatoire. Branchez le point d'accès à des tutoriels de tables de hachage, des planificateurs de fragments de cache, des contrôles d'occupation proches de Bloom ou des oracles d'entretien de programmation où vous préférez les identités exactes boules et urnes à des histogrammes d'échantillonnage approximatif qui ne se stabilisent jamais tout à fait.