Fonction de hachage

Quand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages. Les valeurs sont généralement utilisées pour être les indices d'une table de taille raisonnable appelée table de hachage. Le hachage ou adressage de stockage dispersé est donc l'utilisation d'une fonction de hachage pour créer les indices d'une table de hachage. Les fonctions de hachage sont utilisées dans les applications de stockage et d'indexation de données pour accéder aux données en un temps réduit, en fait quasi-constant. Elles requièrent un espace de stockage à peine plus grand que l'espace total requis pour les données. Ainsi, le hachage est une forme d'accès aux données efficace en termes de calcul et d'espace de stockage. L'intérêt des fonctions de hachage repose sur de bonnes propriétés statistiques. En effet, le comportement dans le pire des cas est mauvais, mais il se manifeste avec une probabilité extrêmement faible, en fait négligeable, et le comportement dans le cas moyen est optimal (collision minimale ). Les fonctions de hachage sont liées (et souvent confondues avec) les sommes de contrôle, les clés de contrôle, les empreintes numériques, la compression avec perte, les générateurs de nombres aléatoires, les codes correcteur et les chiffrements. Bien que les concepts se chevauchent dans une certaine mesure, chacun a ses propres utilisations et exigences et est conçu et optimisé différemment.