Calculateur de code de hachage Fowler-Noll-Vo FNV1-32

La fonction de hachage 32 bits FNV-1 fait partie de la famille de fonctions de hachage Fowler–Noll–Vo (FNV), conçue pour un hachage rapide tout en maintenant une bonne distribution des valeurs de hachage. Il est couramment utilisé dans des applications telles que les tables de hachage, les sommes de contrôle et les recherches de données. Il produit un code de hachage de 32 bits (4 octets), souvent représenté sous la forme d'un nombre hexadécimal à 8 chiffres.

Divulgation complète : je n'ai pas écrit l'implémentation spécifique de la fonction de hachage utilisée sur cette page. Il s'agit d'une fonction standard incluse avec le langage de programmation PHP. J'ai seulement créé l'interface Web pour la rendre accessible au public ici pour plus de commodité.

À propos de l'algorithme de hachage 32 bits Fowler-Noll-Vo FNV-1

Je ne suis pas mathématicien, mais je vais essayer d'expliquer cette fonction de hachage en utilisant une analogie que mes collègues non mathématiciens peuvent comprendre. Si vous préférez une explication scientifiquement correcte et mathématiquement effrayante, je suis sûr que vous pouvez la trouver ailleurs ;-)

Tout d'abord, considérons l'algorithme FNV-1 comme une recette pour préparer un smoothie spécial. Chaque ingrédient que vous ajoutez (comme des fruits, du lait ou du miel) représente un élément de données, comme des lettres, des chiffres ou même un fichier entier.

Maintenant, l'objectif est de mélanger ces ingrédients d'une manière très spécifique afin que même le plus petit changement dans la recette (comme l'ajout d'une bleuet supplémentaire) donne au smoothie un goût complètement différent. C'est ainsi que fonctionnent les fonctions de hachage : elles créent une « saveur » unique (ou valeur de hachage) pour chaque ensemble unique d'ingrédients (ou de données d'entrée).

L'algorithme FNV-1 fait cela en suivant un processus en plusieurs étapes :

Étape 1 : Commencez par une base (base décalée)

Pensez à ça comme si vous versiez une base de smoothie spéciale dans votre mixeur. Cette base est toujours la même, peu importe les ingrédients que vous ajoutez. Dans FNV-1, ça s'appelle la « base de décalage » - juste un numéro de départ fantaisiste.

Étape 2 : ajouter les ingrédients un par un (traitement des données)

Maintenant, vous commencez à ajouter vos ingrédients, un à la fois - disons une fraise, puis une banane, puis du miel. Chacun d'eux représente un octet de données.

Étape 3 : Mélanger avec un multiplicateur secret (le FNV Prime)

Après avoir ajouté chaque ingrédient, vous appuyez sur le bouton de mélange, mais voici le truc : le mélangeur multiplie tout par un « nombre magique » secret appelé le nombre premier FNV. Ça aide vraiment à bien mélanger les choses.

Étape 4 : ajoutez une touche de magie (opération XOR)

Avant d’ajouter l’ingrédient suivant, vous saupoudrez un peu de poussière magique (c’est l’opération XOR). C'est comme changer la saveur de manière inattendue, en s'assurant que même de petits changements font une grosse différence.

Étape 5 : Répétez jusqu'à ce que vous ayez terminé

Vous continuez à mélanger et à saupoudrer de magie après chaque nouvel ingrédient jusqu'à ce que vous ayez tout traité.

Étape 6 : Smoothie final (valeur de hachage)

Lorsque vous avez terminé, vous versez le smoothie. Le goût final (la valeur de hachage) est unique à cette combinaison exacte d’ingrédients. Si vous aviez ajouté ne serait-ce qu'une seule bleuet de plus, le goût aurait été complètement différent.

La version présentée ici est la version originale FNV-1 32 bits. Il existe également une version améliorée du FNV-1a 32 bits disponible : Calculateur de code de hachage Fowler-Noll-Vo FNV1a-32