Probabilité de collision de hachage

Formule

n est le nombre de valeurs de hachage et b la largeur en bits. Pour n ≤ 10,000, P = 1 − ∏(1 − k/2^b), k = 0…n−1. Pour les nombres plus élevés, P ≈ 1 − exp[−n(n−1)/(2×2^b)]. Si n > 2^b, P = 1.

Estimation des collisions d'anniversaire dans un espace de hachage uniformément aléatoire.

Exemple résolu

Portée et limites

Ce modèle suppose des valeurs de hachage indépendantes et uniformément distribuées. Jusqu’à 10,000 valeurs, le produit des probabilités d’absence de collision est calculé dans l’espace log ; au-delà, l’approximation des anniversaires est utilisée. Un nombre de valeurs supérieur au nombre de sorties possibles garantit une collision. Ce modèle ne constitue ni une preuve de sécurité cryptographique ni un modèle de collisions provoquées par un adversaire.

Les données d'entrée sont vérifiées pour détecter les valeurs manquantes et les plages autorisées. Un résultat hors de la plage numérique finie n'est pas affiché. L'arrondi affecte l'affichage, tandis que le calcul utilise la précision numérique du modèle.

Vérifiez vos unités et vos hypothèses avant de vous fier à un résultat. Modifier une étiquette ne convertit pas une devise ni une unité physique.

Version de la formule.: 769d59f888b0 · Exemple vérifié.: 2026-10-30

Méthodologie

Outils associés