Hachage dans la structure de données : fonction, techniques [avec exemples]

Publié: 2021-05-02

Table des matières

introduction

Le hachage est une structure de données importante conçue pour résoudre le problème de la recherche et du stockage efficaces des données dans un tableau. Par exemple, si vous avez une liste de 20 000 numéros et que vous avez donné un numéro à rechercher dans cette liste, vous scannerez chaque numéro de la liste jusqu'à ce que vous trouviez une correspondance.

Il faut beaucoup de temps pour rechercher dans toute la liste et localiser ce numéro spécifique. Ce processus manuel de numérisation prend non seulement du temps, mais est également inefficace. Avec le hachage dans la structure de données, vous pouvez affiner la recherche et trouver le numéro en quelques secondes.

Ce blog vous permettra de mieux comprendre la méthode de hachage, les tables de hachage et le sondage linéaire avec des exemples.

Qu'est-ce que le hachage dans la structure de données ?

Le hachage dans la structure de données est une technique de mappage d'un gros morceau de données dans de petites tables à l'aide d'une fonction de hachage. Elle est également connue sous le nom de fonction de résumé de message. C'est une technique qui identifie de manière unique un élément spécifique à partir d'une collection d'éléments similaires.

Il utilise des tables de hachage pour stocker les données dans un format de tableau. Chaque valeur du tableau a un numéro d'index unique. Les tables de hachage utilisent une technique pour générer ces numéros d'index uniques pour chaque valeur stockée dans un format de tableau. Cette technique s'appelle la technique de hachage.

Il vous suffit de trouver l'index de l'élément souhaité, plutôt que de rechercher les données. Avec l'indexation, vous pouvez parcourir rapidement toute la liste et récupérer l'élément que vous souhaitez. L'indexation aide également à insérer des opérations lorsque vous devez insérer des données à un emplacement spécifique. Quelle que soit la taille de la table, vous pouvez mettre à jour et récupérer des données en quelques secondes.

Le hachage dans une structure de données est un processus en deux étapes.

  1. La fonction de hachage convertit l'élément en un petit entier ou en une valeur de hachage. Cet entier est utilisé comme index pour stocker les données d'origine.
  2. Il stocke les données dans une table de hachage. Vous pouvez utiliser une clé de hachage pour localiser rapidement les données.

Exemples de hachage dans la structure de données

Voici des exemples concrets de hachage dans la structure de données -

  • Dans les écoles, l'enseignant attribue un numéro de matricule unique à chaque élève. Plus tard, l'enseignant utilise ce numéro de matricule pour récupérer des informations sur cet élève.
  • Une bibliothèque contient un nombre infini de livres. Le bibliothécaire attribue un numéro unique à chaque livre. Ce numéro unique aide à identifier la position des livres sur l'étagère.

Checkout : tri dans la structure des données

Fonction de hachage

La fonction de hachage dans une structure de données fait correspondre une taille arbitraire de données à des données de taille fixe. Il renvoie les valeurs suivantes : une petite valeur entière (également appelée valeur de hachage), des codes de hachage et des sommes de hachage.

hachage = hashfunc(clé)

index = hachage % array_size

La fonction has doit satisfaire aux exigences suivantes :

  • Une bonne fonction de hachage est facile à calculer.
  • Une bonne fonction de hachage ne reste jamais bloquée dans le clustering et distribue les clés uniformément sur la table de hachage.
  • Une bonne fonction de hachage évite les collisions lorsque deux éléments ou éléments sont affectés à la même valeur de hachage.

Table de hachage

Le hachage dans la structure de données utilise des tables de hachage pour stocker les paires clé-valeur. La table de hachage utilise ensuite la fonction de hachage pour générer un index. Le hachage utilise cet index unique pour effectuer des opérations d'insertion, de mise à jour et de recherche.

Comment fonctionne le hachage dans la structure de données ?

Dans le hachage, la fonction de hachage fait correspondre des chaînes ou des nombres à une petite valeur entière. Les tables de hachage récupèrent l'élément de la liste à l'aide d'une fonction de hachage. L'objectif de la technique de hachage est de répartir les données uniformément sur un tableau. Le hachage attribue à tous les éléments une clé unique. La table de hachage utilise cette clé pour accéder aux données de la liste.

La table de hachage stocke les données dans une paire clé-valeur. La clé agit comme une entrée pour la fonction de hachage. La fonction de hachage génère alors un numéro d'index unique pour chaque valeur stockée. Le numéro d'index conserve la valeur qui correspond à cette clé. La fonction de hachage renvoie une petite valeur entière en sortie. La sortie de la fonction de hachage est appelée la valeur de hachage.

Comprenons le hachage dans une structure de données avec un exemple. Imaginez que vous ayez besoin de stocker certains éléments (organisés dans une paire clé-valeur) dans une table de hachage de 30 cellules.

Les valeurs sont : (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

La table de hachage ressemblera à ceci :

Numéro de série Clé Hacher Index de tableau
1 3 3 %30 = 3 3
2 1 1 %30 = 1 1
3 40 40%30 = 10 dix
4 5 5%30 = 5 5
5 11 11 %30 = 11 11
6 15 15%30 = 15 15
7 18 18%30 = 18 18
8 16 16%30 = 16 16
9 38 38%30 = 8 8

A lire également : Types de structures de données en Python

Techniques de résolution des collisions

Le hachage dans la structure de données tombe en collision si deux clés se voient attribuer le même numéro d'index dans la table de hachage. La collision crée un problème car chaque index d'une table de hachage est censé stocker une seule valeur. Le hachage dans la structure de données utilise plusieurs techniques de résolution de collision pour gérer les performances d'une table de hachage.

Sondage linéaire

Le hachage dans la structure de données donne un index de tableau qui est déjà occupé pour stocker une valeur. Dans un tel cas, le hachage effectue une opération de recherche et sonde linéairement la prochaine cellule vide.

Exemple de sondage linéaire

Imaginez qu'on vous demande de stocker certains éléments dans une table de hachage de taille 30. Les éléments sont déjà triés dans un format de paire clé-valeur. Les valeurs données sont : (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Le hash(n) est l'indice calculé à l'aide d'une fonction de hachage et T est la taille de la table. Si l'indice de slot = ( hash(n) % T) est plein, alors nous cherchons le prochain index de slot en ajoutant 1 ((hash(n) + 1) % T). Si (hash(n) + 1) % T est aussi plein, alors on essaie (hash(n) + 2) % T. Si (hash(n) + 2) % T est aussi plein, alors on essaie (hash( n) + 3) %T.

La table de hachage ressemblera à ceci :

Numéro de série Clé Hacher Index de tableau Index de tableau après sondage linéaire
1 3 3 %30 = 3 3 3
2 1 1 %30 = 1 1 1
3 63 63 %30 = 3 3 4
4 5 5%30 = 5 5 5
5 11 11 %30 = 11 11 11
6 15 15%30 = 15 15 15
7 18 18%30 = 18 18 18
8 16 16%30 = 16 16 16
9 46 46%30 = 8 16 17

Double hachage

La technique de double hachage utilise deux fonctions de hachage. La deuxième fonction de hachage entre en service lorsque la première fonction provoque une collision. Il fournit un index de décalage pour stocker la valeur.

La formule de la technique de double hachage est la suivante :

(firstHash(key) + i * secondHash(key)) % sizeOfTable

Où i est la valeur de décalage. Cette valeur de décalage reste incrémentée jusqu'à ce qu'elle trouve un emplacement vide.

Par exemple, vous avez deux fonctions de hachage : h1 et h2. Vous devez effectuer les étapes suivantes pour trouver un emplacement vide :

  1. Vérifiez si hash1(key) est vide. Si oui, stockez la valeur sur cet emplacement.
  2. Si hash1(key) n'est pas vide, alors trouvez un autre emplacement en utilisant hash2(key).
  3. Vérifiez si hash1(key) + hash2(key) est vide. Si oui, stockez la valeur sur cet emplacement.
  4. Continuez à incrémenter le compteur et répétez avec hash1(key)+2hash2(key), hash1(key)+3hash2(key), et ainsi de suite, jusqu'à ce qu'il trouve un emplacement vide.

Exemple de double hachage

Imaginez que vous ayez besoin de stocker des éléments dans une table de hachage de taille 20. Les valeurs données sont : (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, je) = (h1 (n) + ih2(n)) mod 20

n h(n,i) = (h'(n) + je 2 ) %20
16 je = 0, h(n,0) = 16
8 je = 0, h(n,0) = 8
63 je = 0, h(n,0) = 3
9 je = 0, h(n,0) = 9
27 je = 0, h(n,0) = 7
37 je = 0, h(n,0) = 17
48 je = 0, h(n,0) = 8

je = 0, h(n,1) = 9

je = 0, h(n,2) = 12

5 je = 0, h(n,0) = 5
69 je = 0, h(n,0) = 9

je = 0, h(n,1) = 10

34 je = 0, h(n,0) = 14
1 je = 0, h(n,0) = 1
Apprenez des cours de développement de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Conclusion

Le double hachage a un coût de calcul élevé, mais il recherche le prochain créneau libre plus rapidement que la méthode de sondage linéaire. Les exemples donnés dans l'article sont uniquement à des fins explicatives. Vous pouvez modifier les déclarations ci-dessus selon vos besoins. Dans ce blog, nous avons découvert le concept de hachage dans la structure des données .

Vous pouvez essayer l'exemple pour renforcer vos connaissances sur la structure des données. Si vous êtes curieux d'en savoir plus sur la structure des données , consultez le cours upGrad Executive PG Program in Full Stack Development . Ce cours est conçu pour les professionnels en activité et offre une formation rigoureuse et un placement dans les meilleures entreprises.

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

Une table de hachage est une implémentation d'un tableau associatif, une structure utilisée en programmation informatique pour implémenter un type de données abstrait (ADT). Dans un type de données abstrait, le programmeur n'a pas besoin de connaître les détails d'implémentation du type de données (comme la façon dont les données sont stockées en mémoire), seulement les opérations qui peuvent être effectuées sur le type de données. Une table de hachage utilise une fonction de hachage pour calculer un index dans un tableau de compartiments ou d'emplacements, à partir duquel la valeur souhaitée peut être trouvée. Les tables de hachage sont utilisées pour implémenter une carte comme des structures de données. Les tables de hachage sont très utilisées dans les ordinateurs modernes pour implémenter des éléments tels que des dictionnaires (comme en python), des tableaux associatifs (comme en php), des tables de hachage Java, etc. Les tables de hachage sont généralement implémentées dans les langages sous la forme d'un tableau de valeurs triées par leurs clés . Cela rend les opérations de recherche et d'insertion/suppression très rapides, car les données sont stockées systématiquement en mémoire.

Quelles sont les applications des fonctions de hachage ?

Les fonctions de hachage sont utilisées pour plusieurs applications en informatique, par exemple la cryptographie et la prise d'empreintes digitales de documents. L'objectif principal d'une fonction de hachage est de mapper de grandes quantités d'entrées sur une sortie de longueur fixe. En cryptographie, le hachage est utilisé pour s'assurer qu'un message ou un document n'a pas été falsifié. Si le document ou le message est modifié de quelque manière que ce soit (même un seul caractère), la valeur de hachage est également modifiée. Il est donc quasiment impossible de créer un document ou un message avec une valeur de hachage donnée.

Quelles sont les techniques de résolution de collision en hachage ?

Les techniques de résolution de collision dans le hachage sont utilisées pour résoudre les collisions dans le hachage. Les techniques de résolution des collisions sont soit le chaînage, soit l'adressage ouvert. En chaînage, on conserve l'ancien élément en place et on insère le nouvel élément dans l'espace disponible suivant. Il s'agit d'une méthode simple de résolution des collisions, mais qui présente l'inconvénient de performances médiocres. Dans l'adressage ouvert, nous remplaçons l'ancien élément par un nouvel élément et marquons l'ancien élément comme une collision.