Collision (informatique)

En informatique, une collision désigne une situation dans laquelle deux données ont un résultat identique avec la même fonction de hachage. Les collisions sont inévitables dès lors que l'ensemble de départ (données fournies) de la fonction de hachage est d'un cardinal strictement supérieur à l'ensemble d'arrivée (empreintes). Ce problème est une déclinaison du principe des tiroirs.

La conséquence de ces collisions dépend de leurs applications. Si les empreintes ont été calculées afin d'identifier des données similaires, telles des chaînes d'ADN, alors les fonctions de hachage seront conçues de telle sorte à maximiser la probabilité des collisions entre des données presque identiques. À l'opposé, si l'objectif est de contrôler l'intégrité des données, tel un fichier que l'on a transféré et dont on veut être sûr qu'aucun bit n'ait été altéré lors du transfert, les fonctions de hachage devront minimiser la probabilité des collisions entre des données presque identiques.

Dans la pratique, les collisions sont en général indésirables. Toute collision dans une table de hachage augmente le coût moyen de recherche d'une donnée dans la table. Lorsque les empreintes sont utilisées pour détecter des fichiers doublons, une collision peut entraîner la suppression définitive d'un fichier si le système ne compare pas les deux fichiers avant de supprimer ce qu'il pense être le doublon. Les collisions représentent également une menace pour la sécurité informatique dans certains systèmes. Il en résulte une recherche importante dans la conception d'algorithmes minimisant le nombre de collisions et/ou rendant plus difficile leur génération.