Introduction à la fonction de hachage en Java
Comme nous savons que Java est un langage orienté objet, il devrait donc y avoir un mécanisme pour décrire l'état d'un objet, quelle que soit sa taille. La fonction de hachage en Java a vu le jour pour répondre à cette exigence.
Qu'est-ce qu'une fonction de hachage?
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 de hachage:
- Renvoie toujours un entier (4 octets) pour un objet.
- Nous ne pouvons pas calculer l'état d'objet à partir de la valeur de hachage, c'est-à-dire que 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, des structures de données d'arborescence qui sont basées sur la fonction de hachage. La base de ces structures de données est 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 une donnée de longueur fixe (128 bits) en sortie. Les exemples d'algorithmes de résumé de message 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 tels que 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 des mots de passe
Prenons un scénario de connexion dans lequel lorsqu'un mot de passe est entré pour authentifier un utilisateur, une valeur de hachage du mot de passe entré est calculée et envoyée sur le réseau au serveur où le hachage de l'original est stocké. Cela permet de garantir qu'aucun reniflement n'est effectué 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 identificateurs, le compilateur utilise un ensemble de hachage implémenté à l'aide d'une table de hachage pour stocker tous ces mots clés et identificateurs.
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 comparateurs
Ces interfaces contiennent des fonctions qui sont utilisées pour 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. Le comparateur interne 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 de la file d'attente normale qui suit l'ordre FIFO (premier entré premier sorti). Dans la file d'attente prioritaire, les éléments sont organisés dans un ordre personnalisé en fonction de leur priorité, qui est implémentée en interne à l'aide de comparateurs et de comparateurs qui sont basés sur les 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 réparties uniformément, ce qui 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 ou plusieurs objets 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 plaçons un objet dans une carte de hachage, la valeur de hachage de la clé est calculée et basée sur cet emplacement de compartiment de valeur de hachage pour stocker l'objet de valeur est trouvé. Les objets ayant différentes valeurs de hachage doivent aller dans différents compartiments. Lorsque deux ou plusieurs objets 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 liée. Tous les objets ayant la même valeur de hachage sont chaînés ensemble à l'aide d'une liste liée. Ce mécanisme est appelé chaînage. Voici les façons de gérer les collisions est une fonction de hachage:
- Chaînage: Comme nous l'avons déjà vu, 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
Les avantages du hachage sont les suivants:
- Comparez le contenu de deux fichiers facilement et efficacement, sans les ouvrir.
- Les fonctions de hachage sont utilisées pour vérifier l'intégrité d'un fichier.
- Avec l'aide du hachage, l'opération de recherche dans les structures de données est devenue plus rapide.
- Les fonctions de hachage jouent un rôle vital dans la sécurité des données car la plupart des algorithmes et protocoles de sécurité utilisent le hachage.
- 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 qui peut être envoyée sur le réseau.
Inconvénients du hachage
Outre les avantages, le hachage présente également certaines limites:
- Le hachage ne peut pas être implémenté pour trier les données.
- La collision de hachage ne peut pratiquement pas être évitée, ce qui conduit à son tour à l'inefficacité.
Articles recommandés
Ceci est un guide de la fonction de hachage en Java. Nous discutons ici des applications de la fonction de hachage ainsi que des avantages et des inconvénients. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Déclaration et initialisation de VB.Net
- Programme Java affichant HashMap et TreeMap
- Types de hachage dans le SGBD
- Techniques de stéganographie
- Tableaux en programmation Java
- Hashmap en Java