Il y a tout de même un problème. Oh, un tout petit problème, un de ceux qui ne se posent qu'en théorie, jamais en pratique. Le nombre de seaux (« cases » du tableau) est nécessairement limité, contrairement au nombre de chaînes de caractères qu'il est possible de construire. Il existe donc forcément, pour une fonction h et une chaîne c1 données, une chaîne c2 telle que h(c1) = h(c2) = n.
Allez, on joue sur les mots : cette phrase est fausse =D En effet, soit une fonction de hachage h à valeurs dans un ensemble, disons {1,...,k}. Je définis la fonction h' par h'("Bonjour !") = 0, et h'(c) = h(c) si c != "Bonjour !". C'est une fonction de hachage à valeurs dans {0,...,n}, mais pour si on prend c1 = "Bonjour !", alors il n'existe pas de chaîne c2 vérifiant h'(c1) = h'(c2) =)
Bon, après on peut aussi jouer encore plus sur les mots et considérer que la formule "pour toute fonction h, pour toute chaîne c1, il existe une chaîne c2 telle que h(c1) = h(c2)" est toujours vraie, vu qu'il suffit de choisir c2=c1 pour que ça marche.
Voilà, c'était la contribution utile de la soirée.
# Remarque stupide de théoricien
Posté par DeeTay . En réponse à la dépêche Le colonel Moutarde, sur la table (de hachage), avec un livre de maths. Évalué à 9.
Allez, on joue sur les mots : cette phrase est fausse =D En effet, soit une fonction de hachage h à valeurs dans un ensemble, disons {1,...,k}. Je définis la fonction h' par h'("Bonjour !") = 0, et h'(c) = h(c) si c != "Bonjour !". C'est une fonction de hachage à valeurs dans {0,...,n}, mais pour si on prend c1 = "Bonjour !", alors il n'existe pas de chaîne c2 vérifiant h'(c1) = h'(c2) =)
Bon, après on peut aussi jouer encore plus sur les mots et considérer que la formule "pour toute fonction h, pour toute chaîne c1, il existe une chaîne c2 telle que h(c1) = h(c2)" est toujours vraie, vu qu'il suffit de choisir c2=c1 pour que ça marche.
Voilà, c'était la contribution utile de la soirée.