hachage

Une définition du Jargon Français.

Cette définition a été marquée comme étant à revoir. Si le cœur vous en dit...

nom^→ masculin^→  [algorithmie]. En cryptologie c'est le fait d'utiliser une fonction de condensation.

Le terme hachage désigne aussi, parfois, le résultat (une empreinte numérique), toutefois hash est d'ordinaire préféré.

Une infinité de fonctions de condensation existent, donc tout autant de valeurs du hash d'un message donné. Certaines font toutefois l'objet d'une norme ou de conventions.

En anglais : hash, fingerprint ou hashing.

[modifier] Utilité

Cette méthode permet, par exemple, de produire à partir d'une liste d'entiers une valeur plus concise (le hash) qui en est raisonnablement représentative ou caractéristique car les hashes de deux listes aux contenus distincts seront très probablement différents. C'est utile lorsqu'il s'agit de déterminer si une nouvelle liste donnée se trouve ou non déjà dans la base de listes, afin d'éviter de la comparer à chacune des autres. On calcule puis conserve pour cela, au préalable, le hash (par exemple le cumul des valeurs de ses éléments, appelé checksum) du contenu de chaque liste placée dans la base, afin de l'employer en guise d'index. Pour déterminer si une liste se trouve déjà en base il suffira dès lors de calculer son hash puis, sachant que la fonction de hachage produit le même hash pour deux listes identiques, de sélectionner, pour comparaison exhaustive, les seules listes présentes en base qui ont le même hash qu'elle. La comparaison est nécessaire car chaque hash correspond à beaucoup de listes possibles, donc des listes aux contenus différents peuvent correspondre au même hash, sauf si l'on emploie un hash parfait. En pratique on préfère une fonction de hachage plus efficace qu'un checksum car causant moins de collisions (sens 3), par exemple MD5 ou SHA-1.

[modifier] Exemple

La fonction de hachage retenue est un checksum, donc calcule la somme des éléments de la liste.

Nom de liste	Contenu	Hash
A	1, 3, 5	9
B	2, 4, 8	14
C	1, 4, 4	9
D	90, 100, 111	301

A et C, aux contenus distincts, conduisent au même hash. C'est une collision (sens 2). Adopter une autre fonction de hashage pourrait la faire disparaître, par exemple celle qui élève au carré avant d'additionner (le hash de A serait 35, celui de C 33).

Pour déterminer rapidement si une nouvelle liste abritant "6, 7, 11" se trouve ou non dans la base il suffit de calculer son hash (24) puis de le comparer à ceux des listes en base, ce qui n'exige que quatre comparaisons d'entiers. Le fait qu'aucun ne vaut 24 révèle que cette liste n'est pas déjà en base.