Collisions de hachage
Les fonctions de hachage ne sont pas parfaites ; il arrive parfois que des données complètement différentes produisent le même résultat de hachage. Cela contredit l’idée d’une correspondance un-à-un entre les entrées et la valeur de hachage. Il est donc possible que différentes chaînes de caractères ou paires de nombres aboutissent à la même valeur de hachage. Ces collisions peuvent entraîner des problèmes de sécurité ainsi que des problèmes de performance, selon le contexte. Par exemple, une fonction de hachage très simple qui associe une paire d’entiers à une valeur de hachage peut attribuer la même valeur de hachage à de nombreuses paires (a, b) :
Voici plusieurs exemples de paires
(a, b) produisant la même valeur de hachage :- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Ainsi, si l’on dispose d’une liste de paires spécialement conçues pour donner le même résultat de hachage, on se retrouvera avec de nombreuses collisions. Dans ce cas, rechercher une valeur ou vérifier la présence d’une paire
(a, b) dans une liste pourrait s’avérer très inefficace, voire incorrect en fonction de l’implémentation.Les collisions de hachage peuvent également représenter une faille de sécurité. Les mots de passe des utilisateurs sont en général stockés sous forme de hachage afin de ne pas les exposer en clair si la base de données est piratée. Mais si la fonction de hachage n’est pas suffisamment robuste et génère de nombreuses collisions, il devient alors possible de compromettre un compte sans deviner le véritable mot de passe. Si le hachage d’un mot de passe aléatoire coïncide avec le hachage du mot de passe original, le système considère qu’il s’agit de la même personne.
Une bonne fonction de hachage cherche à minimiser ces collisions. En général, les fonctions de hachage intégrées se comportent plutôt bien pour des entrées aléatoires. Toutefois, si les données d’entrée sont d’un type particulier ou que le problème impose des exigences spécifiques, il peut être nécessaire de mettre en œuvre sa propre fonction de hachage.
Défi : Vérifier les collisions
Étant donné une fonction de hachage
h qui associe une paire d’entiers (a, b) à un entier, on vous demande de déterminer si h est suffisamment fiable. Le programme doit vérifier s’il se produit des collisions et afficher Yes en l’absence de collisions, ou No dans le cas contraire. La fonction de hachage est définie comme suit :Entrée
La première ligne de l’entrée contient un entier
n (1 ≤ n ≤ 10 000), qui indique le nombre de paires.Les
n lignes suivantes contiennent des paires d’entiers séparées par un espace (0 ≤ ≤ ). Il est garanti que toutes les paires fournies sont uniques.Sortie
Le programme doit imprimer
Yes si la fonction h(a, b) est bonne pour les données fournies (c’est-à-dire qu’elle n’a généré aucune collision), ou No dans le cas contraire.Exemples
Entrée | Sortie |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB