Fonction de hachage en Java

La fonction de hachage en Java a été créée comme une solution pour définir et renvoyer la valeur d'un objet sous la forme d'un entier, et cette valeur de retour obtenue en sortie de la fonction de hachage est appelée valeur de hachage. Chaque fonction de hachage renvoie un entier de 4 octets comme valeur de retour pour l'objet. Deux objets du même type auront la même valeur entière que la sortie de la fonction de hachage, et de même, différents objets auront des valeurs de hachage différentes. On ne peut pas dériver les objets de la valeur de hachage, ce qui fait de la fonction de hachage une fonction irréversible.

Qu'est-ce qu'une fonction de hachage ?

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Une fonction de hachage peut être définie comme une fonction qui renvoie une valeur entière correspondant à un objet. La fonction de hachage renvoie toujours la même valeur entière pour le même objet. La valeur entière renvoyée par la fonction de hachage est appelée valeur de hachage. Voici les points importants concernant la fonction Hash :

• Renvoie toujours un entier (4 octets) pour un objet.
• Nous ne pouvons pas calculer l'état de l'objet à partir de la valeur de hachage, car les fonctions de hachage sont de nature irréversible.
• Deux objets égaux auront la même valeur de hachage.
• Deux objets inégaux n'ont pas toujours des valeurs de hachage différentes.

Applications de la fonction de hachage

Voici les applications courantes des fonctions de hachage :

1. Structures de données

Presque tous les langages de programmation contiennent des structures de données basées sur le hachage. Par exemple, Java contient une table de hachage, une carte de hachage, un ensemble de hachage et un ensemble d'arbres qui sont basés sur la fonction de hachage. Ces structures de données sont la conception clé-valeur, où chaque clé est unique, alors que la même valeur peut exister pour plusieurs clés.

2. Résumé des messages

Cet algorithme est utilisé dans un contrôle d'intégrité des données. Cet algorithme prend un message de n'importe quelle longueur en entrée et produit des données de longueur fixe (128 bits) en sortie. Des exemples d'algorithmes de synthèse de messages incluent MD2, MD4, MD5 et MD6.

3. Algorithme de hachage sécurisé

Cet algorithme est utilisé pour la sécurité des données et est utilisé dans des applications et des protocoles comme Secure Socket Layer (SSL). SHA-0, SHA-1, SHA-2 et SHA-3 sont des catégories courantes de l'algorithme de hachage sécurisé.

4. Vérification et stockage du mot de passe

Considérons un scénario de connexion dans lequel lorsqu'un mot de passe est saisi pour authentifier un utilisateur, une valeur de hachage du mot de passe saisi est calculée et envoyée sur le réseau au serveur où le hachage de l'original est stocké. Ceci est fait pour garantir qu'aucune détection n'est effectuée lorsqu'un mot de passe est envoyé du client au serveur.

5. Fonctionnement du compilateur

Étant donné que différents mots-clés sont utilisés dans un langage de programmation, afin de différencier ces mots-clés et identifiants, le compilateur utilise un jeu de hachage qui est implémenté à l'aide d'une table de hachage pour stocker tous ces mots-clés et identifiants.

6. Algorithme Rabin-Karp

Il s'agit d'un algorithme de recherche qui utilise le hachage pour rechercher un ou plusieurs modèles dans une chaîne donnée. C'est l'un des algorithmes les plus couramment utilisés.

7. Interfaces comparables et comparatrices

Ces interfaces contiennent des fonctions qui permettent de comparer deux objets à la fois. La valeur de retour de ces fonctions peut être négative, nulle ou positive selon qu'un objet donné est inférieur, égal ou supérieur à l'objet auquel nous comparons. En interne, le comparateur et les interfaces comparables utilisent une fonction de hachage pour comparer les objets les uns des autres.

8. File d'attente prioritaire

La file d'attente prioritaire est différente d'une file d'attente normale qui suit l'ordre FIFO (First in First out). En priorité, les éléments de la file d'attente sont classés dans un ordre personnalisé en fonction de leur priorité, qui est implémentée en interne à l'aide d'un comparable et d'un comparateur dont les internes sont basés sur des fonctions de hachage.

Conception de fonctions de hachage

Voici quelques principes généraux de conception pour créer des fonctions de hachage :

• Une fonction de hachage doit être évaluée efficacement.
• Les valeurs de hachage calculées à partir des fonctions de hachage doivent être uniformément distribuées ; cela permet d'éviter les collisions.
• Le langage de programmation Java fournit une fonction de hachage générale avec la méthode hashCode() dans la superclasse Object.

public int hashCode (){
//Logic goes here
}

Collision de hachage en Java

Une collision de hachage se produit lorsque deux objets ou plus renvoient la même valeur de hachage. Prenons un exemple de carte de hachage Java qui stocke les données dans des paires clé-valeur. Lorsque nous mettons un objet dans une carte de hachage, la valeur de hachage de la clé est calculée et, en fonction de cette valeur de hachage, l'emplacement du compartiment pour stocker l'objet de valeur est trouvé. Les objets ayant des valeurs de hachage différentes doivent aller dans des compartiments différents. Lorsque deux objets ou plus ont la même valeur de hachage, ils sont stockés dans le même emplacement de compartiment à l'aide d'une structure de données supplémentaire appelée liste chaînée. Tous les objets ayant la même valeur de hachage sont chaînés à l’aide d’une liste chaînée. Ce mécanisme est appelé chaînage. Voici les façons de gérer les collisions avec une fonction de hachage :

• Chaînage : Comme déjà évoqué, l'idée derrière le chaînage est de créer une liste chaînée d'objets ayant la même valeur de hachage. Le chaînage est une technique simple mais nécessite une surcharge de mémoire supplémentaire.
• Adressage ouvert : Dans cette technique, tous les éléments sont stockés dans une table de hachage dans laquelle chaque entrée contient soit un enregistrement, soit NULL. Lorsqu'un élément est recherché, chaque entrée de la table de hachage est recherchée pour l'enregistrement souhaité jusqu'à ce que l'enregistrement requis soit trouvé, ou qu'il soit conclu que l'enregistrement n'existe pas dans la table.

Avantages du hachage

Voici les avantages du hachage :

1. Comparez le contenu de deux fichiers facilement et efficacement, sans les ouvrir.
2. Les fonctions de hachage sont utilisées pour vérifier l'intégrité d'un fichier.
3. Grâce au hachage, les opérations de recherche dans les structures de données sont devenues plus rapides.
4. Les fonctions de hachage jouent un rôle essentiel dans la sécurité des données, car la plupart des algorithmes et protocoles de sécurité utilisent le hachage.
5. Le hachage convertit les données en une valeur ou une clé de longueur fixe plus courte, qui représente la chaîne d'origine pouvant être envoyée sur le réseau.

Inconvénients du hachage

Outre les avantages, le hachage présente également certaines limites :

1. Le hachage ne peut pas être implémenté pour trier les données.
2. La collision de hachage ne peut être pratiquement évitée, ce qui conduit à son tour à l'inefficacité.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!