Table de hachage dans la structure de données: exemple Python

Table des matières:

Anonim

Qu'est-ce que le hachage?

Un hachage est une valeur qui a une longueur fixe, et il est généré à l'aide d'une formule mathématique. Les valeurs de hachage sont utilisées dans la compression des données, la cryptologie, etc. Dans l'indexation des données, les valeurs de hachage sont utilisées car elles ont une taille de longueur fixe, quelles que soient les valeurs utilisées pour les générer. Il fait que les valeurs de hachage occupent un espace minimal par rapport à d'autres valeurs de longueurs variables.

Une fonction de hachage utilise un algorithme mathématique pour convertir la clé en hachage. Une collision se produit lorsqu'une fonction de hachage produit la même valeur de hachage pour plusieurs clés.

Dans ce didacticiel sur l'algorithme, vous apprendrez:

  • Qu'est-ce que le hachage?
  • Qu'est-ce qu'une table de hachage?
  • Fonctions de hachage
  • Qualités d'une bonne fonction de hachage
  • Collision
  • Opérations de table de hachage
  • Exemple de table de hachage Python
  • Explication du code de la table de hachage
  • Exemple de dictionnaire Python
  • Analyse de complexité
  • Applications du monde réel
  • Avantages des tables de hachage
  • Inconvénients des tables de hachage

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

Un HASH TABLE est une structure de données qui stocke des valeurs à l'aide d'une paire de clés et de valeurs. Chaque valeur se voit attribuer une clé unique générée à l'aide d'une fonction de hachage.

Le nom de la clé est utilisé pour accéder à sa valeur associée. Cela rend la recherche de valeurs dans une table de hachage très rapide, quel que soit le nombre d'éléments dans la table de hachage.

Fonctions de hachage

Par exemple, si nous voulons stocker les enregistrements des employés et que chaque employé est identifié de manière unique à l'aide d'un numéro d'employé.

Nous pouvons utiliser le numéro d'employé comme clé et affecter les données d'employé comme valeur.

L'approche ci-dessus nécessitera un espace libre supplémentaire de l'ordre de (m * n 2 ) où la variable m est la taille du tableau et la variable n est le nombre de chiffres pour le numéro d'employé. Cette approche introduit un problème d'espace de stockage.

Une fonction de hachage résout le problème ci-dessus en obtenant le numéro d'employé et en l'utilisant pour générer une valeur entière de hachage, des chiffres fixes et en optimisant l'espace de stockage. Le but d'une fonction de hachage est de créer une clé qui sera utilisée pour référencer la valeur que nous voulons stocker. La fonction accepte la valeur à enregistrer puis utilise un algorithme pour calculer la valeur de la clé.

Voici un exemple de fonction de hachage simple

h(k) = k1 % m

ICI,

  • h (k) est la fonction de hachage qui accepte un paramètre k. Le paramètre k est la valeur pour laquelle nous voulons calculer la clé.
  • k 1 % m est l'algorithme de notre fonction de hachage où k1 est la valeur que nous voulons stocker et m est la taille de la liste. Nous utilisons l'opérateur module pour calculer la clé.

Exemple

Supposons que nous ayons une liste avec une taille fixe de 3 et les valeurs suivantes

[1,2,3]

Nous pouvons utiliser la formule ci-dessus pour calculer les positions que chaque valeur doit occuper.

L'image suivante montre les index disponibles dans notre table de hachage.

Étape 1)

Calculez la position qui sera occupée par la première valeur comme ceci

h (1) = 1% 3

= 1

La valeur 1 occupera l'espace sur l' index 1

Étape 2)

Calculez la position qui sera occupée par la deuxième valeur

h (2) = 2% 3

= 2

La valeur 2 occupera l'espace sur l' index 2

Étape 3)

Calculez la position qui sera occupée par la troisième valeur.

h (3) = 3% 3

= 0

La valeur 3 occupera l'espace sur l' index 0

Résultat final

Notre table de hachage remplie sera désormais la suivante.

Qualités d'une bonne fonction de hachage

Une bonne fonction de hachage doit avoir les qualités suivantes.

  • La formule de génération du hachage doit utiliser la valeur des données à stocker dans l'algorithme.
  • La fonction de hachage doit générer des valeurs de hachage uniques, même pour les données d'entrée qui ont la même quantité.
  • La fonction doit minimiser le nombre de collisions. Les collisions se produisent lorsque la même valeur est générée pour plusieurs valeurs.
  • Les valeurs doivent être distribuées de manière cohérente sur l'ensemble des hachages possibles.

Collision

Une collision se produit lorsque l'algorithme génère le même hachage pour plusieurs valeurs.

Regardons un exemple.

Supposons que nous ayons la liste de valeurs suivante

[3,2,9,11,7]

Supposons que la taille de la table de hachage est de 7, et nous utiliserons la formule (k 1 % m) où m est la taille de la table de hachage.

Le tableau suivant montre les valeurs de hachage qui seront générées.

Clé Algorithme de hachage (k 1 % m) Valeur de hachage
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Comme nous pouvons le voir à partir des résultats ci-dessus, les valeurs 2 et 9 ont la même valeur de hachage et nous ne pouvons pas stocker plus d'une valeur à chaque position.

Le problème donné peut être résolu en utilisant le chaînage ou le sondage. Les sections suivantes traitent en détail du chaînage et de la détection.

Chaînage

Le chaînage est une technique utilisée pour résoudre le problème de collision en utilisant des listes chaînées qui ont chacune des index uniques.

L'image suivante montre à quoi ressemble une liste chaînée

Les deux et 9 occupent le même index, mais ils sont stockés sous forme de listes chaînées. Chaque liste a un identifiant unique.

Avantages des listes chaînées

Voici les avantages des listes chaînées:

  • Les listes chaînées ont de meilleures performances lors de l'insertion de données car l'ordre d'insertion est O (1).
  • Il n'est pas nécessaire de redimensionner une table de hachage qui utilise une liste chaînée.
  • Il peut facilement accueillir un grand nombre de valeurs tant que l'espace libre est disponible.

Sondage

L'autre technique utilisée pour résoudre les collisions est le sondage. Lors de l'utilisation de la méthode de sondage, si une collision se produit, nous pouvons simplement passer à autre chose et trouver un emplacement vide pour stocker notre valeur.

Voici les méthodes de sondage:

Méthode Description
Palpage linéaire Tout comme son nom l'indique, cette méthode recherche les emplacements vides de manière linéaire en partant de la position où la collision s'est produite et en avançant. Si la fin de la liste est atteinte et qu'aucun emplacement vide n'est trouvé. Le sondage commence au début de la liste.
Sondage quadratique Cette méthode utilise des expressions polynomiales quadratiques pour trouver le prochain créneau libre disponible.
Double hachage Cette technique utilise un algorithme de fonction de hachage secondaire pour trouver le prochain emplacement libre disponible.

En utilisant notre exemple ci-dessus, la table de hachage après l'utilisation du sondage apparaîtrait comme suit:

Opérations de table de hachage

Voici les opérations prises en charge par les tables de hachage:

  • Insertion - cette opération est utilisée pour ajouter un élément à la table de hachage
  • Recherche - cette opération est utilisée pour rechercher des éléments dans la table de hachage à l'aide de la clé
  • Suppression - cette opération est utilisée pour supprimer des éléments de la table de hachage

Opération d'insertion de données

L'opération d'insertion est utilisée pour stocker des valeurs dans la table de hachage. Lorsqu'une nouvelle valeur est stockée dans la table de hachage, un numéro d'index lui est attribué. Le numéro d'index est calculé à l'aide de la fonction de hachage. La fonction de hachage résout toutes les collisions qui se produisent lors du calcul du numéro d'index.

Rechercher une opération de données

L'opération de recherche est utilisée pour rechercher des valeurs dans la table de hachage à l'aide du numéro d'index. L'opération de recherche renvoie la valeur liée au numéro d'index de recherche. Par exemple, si nous stockons la valeur 6 à l'index 2, l'opération de recherche avec le numéro d'index 2 renverra la valeur 6.

Supprimer l'opération de données

L'opération de suppression est utilisée pour supprimer une valeur d'une table de hachage. Pour supprimer l'opération se fait à l'aide du numéro d'index. Une fois qu'une valeur a été supprimée, le numéro d'index est rendu libre. Il peut être utilisé pour stocker d'autres valeurs à l'aide de l'opération d'insertion.

Exemple d'implémentation de table de hachage avec Python

Regardons un exemple simple qui calcule la valeur de hachage d'une clé

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Explication du code de la table de hachage

ICI,

  1. Définit une fonction hash_key qui accepte les paramètres key et m.
  2. Utilise une opération de module simple pour déterminer la valeur de hachage
  3. Définit une variable m qui est initialisée à la valeur 7. C'est la taille de notre table de hachage
  4. Calcule et imprime la valeur de hachage de 3
  5. Calcule et imprime la valeur de hachage de 2
  6. Calcule et imprime la valeur de hachage de 9
  7. Calcule et imprime la valeur de hachage de 11
  8. Calcule et imprime la valeur de hachage de 7

L'exécution du code ci-dessus produit les résultats suivants.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Exemple de dictionnaire Python

Python est livré avec un type de données intégré appelé Dictionary. Un dictionnaire est un exemple de table de hachage. Il stocke les valeurs à l'aide d'une paire de clés et de valeurs. Les valeurs de hachage sont automatiquement générées pour nous et toutes les collisions sont résolues pour nous en arrière-plan.

L'exemple suivant montre comment utiliser un type de données de dictionnaire en python 3

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

ICI,

  1. Définit une variable de dictionnaire employé. Le nom de la clé est utilisé pour stocker la valeur John Doe, l'âge stocke 36 et la position stocke la valeur Business Manager.
  2. Récupère la valeur du nom de la clé et l'imprime dans le terminal
  3. Met à jour la valeur de la position clé à la valeur Software Engineer
  4. Imprime les valeurs du nom et de la position des clés
  5. Supprime toutes les valeurs stockées dans notre dictionnaire variable employé
  6. Imprime la valeur de l'employé

L'exécution du code ci-dessus produit les résultats suivants.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Analyse de complexité

Les tables de hachage ont une complexité temporelle moyenne de O (1) dans le meilleur des cas. La complexité temporelle dans le pire des cas est O (n). Le pire des cas se produit lorsque de nombreuses valeurs génèrent la même clé de hachage et que nous devons résoudre la collision en sondant.

Applications du monde réel

Dans le monde réel, les tables de hachage sont utilisées pour stocker des données pour

  • Bases de données
  • Tableaux associatifs
  • Ensembles
  • Cache mémoire

Avantages des tables de hachage

Voici les avantages / avantages de l'utilisation des tables de hachage:

  • Les tables de hachage ont des performances élevées lors de la recherche de données, de l'insertion et de la suppression de valeurs existantes.
  • La complexité temporelle des tables de hachage est constante quel que soit le nombre d'éléments dans la table.
  • Ils fonctionnent très bien même lorsqu'ils travaillent avec de grands ensembles de données.

Inconvénients des tables de hachage

Voici les inconvénients de l'utilisation des tables de hachage:

  • Vous ne pouvez pas utiliser une valeur nulle comme clé.
  • Les collisions ne peuvent pas être évitées lors de la génération de clés à l'aide de. fonctions de hachage. Les collisions se produisent lorsqu'une clé déjà utilisée est générée.
  • Si la fonction de hachage a de nombreuses collisions, cela peut entraîner une diminution des performances.

Résumé:

  • Les tables de hachage sont utilisées pour stocker des données à l'aide d'une paire de clés et de valeurs.
  • Une fonction de hachage utilise un algorithme mathématique pour calculer la valeur de hachage.
  • Une collision se produit lorsque la même valeur de hachage est générée pour plusieurs valeurs.
  • Le chaînage résout les collisions en créant des listes liées.
  • Le sondage résout la collision en trouvant des emplacements vides dans la table de hachage.
  • Le sondage linéaire recherche le prochain créneau libre pour stocker la valeur à partir du créneau où la collision s'est produite.
  • Le sondage quadratique utilise des expressions polynomiales pour trouver le prochain créneau libre lorsqu'une collision se produit.
  • Le double hachage utilise un algorithme de fonction de hachage secondaire pour trouver le prochain emplacement libre lorsqu'une collision se produit.
  • Les tables de hachage ont de meilleures performances par rapport aux autres structures de données.
  • La complexité temporelle moyenne des tables de hachage est O (1)
  • Un type de données de dictionnaire en python est un exemple de table de hachage.
  • Les tables de hachage prennent en charge les opérations d'insertion, de recherche et de suppression.
  • Une valeur nulle ne peut pas être utilisée comme valeur d'index.
  • Les collisions ne peuvent pas être évitées dans les fonctions de hachage. Une bonne fonction de hachage minimise le nombre de collisions qui se produisent pour améliorer les performances.