Table de hachage dans la structure de données : Python Exemple
Sarah Chen
Qu'est-ce que le hachage ?
Un hachage est une valeur qui a une longueur fixe et qui est générée à 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 longueur fixe quelles que soient les valeurs qui ont été utilisées pour les générer. Cela permet aux valeurs de hachage d'occuper 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.
Qu'est-ce qu'une table de hachage ?
A TABLE DE HACHAGE est une structure de données qui stocke les 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é permet d'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 souhaitons stocker les dossiers 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 attribuer les données de l'employé comme valeur.
L'approche ci-dessus nécessitera un espace libre supplémentaire de l'ordre de (m*n2) où la variable m est la taille du tableau, et la variable n est le nombre de chiffres du 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 servira à référencer la valeur que l'on souhaite stocker. La fonction accepte la valeur à enregistrer puis utilise un algorithme pour calculer la valeur de la clé.
Ce qui suit est 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é.
- k1 % 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 de module pour calculer la clé.
Exemple
Supposons que nous ayons une liste d'une taille fixe de 3 et les valeurs suivantes
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 index 1
Étape 2) Calculer la position qui sera occupée par la deuxième valeur
h(2) = 2 % 3
= 2
La valeur 2 occupera l'espace sur 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 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 ayant le même montant.
- La fonction doit minimiser le nombre de collisions. Des collisions se produisent lorsque la même valeur est générée pour plusieurs valeurs.
- Les valeurs doivent être réparties 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
Supposons que la taille de la table de hachage soit de 7, et nous utiliserons la formule (k1 % 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.
| ACTIVITES | Algorithme de hachage (k1 % 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 d'après les 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 du sondage.
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 dont chacune a des index uniques.
L'image suivante visualise à quoi ressemble une liste chaînée
2 et 9 occupent le même index, mais ils sont stockés sous forme de listes chaînées. Chaque liste possède 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 de l'espace libre est disponible.
Sondage
L’autre technique utilisée pour résoudre les collisions est le sondage. Lorsque vous utilisez la méthode de sondage, si une collision se produit, nous pouvons simplement continuer et trouver un emplacement vide pour stocker notre valeur.
Voici les méthodes de sondage :
| Méthode | Description |
|---|---|
| Sondage linéaire | 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 emplacement libre disponible. |
| Double Hachage | Cette technique utilise un algorithme de fonction de hachage secondaire pour trouver le prochain emplacement disponible libre. |
En utilisant notre exemple ci-dessus, la table de hachage après avoir utilisé le sondage apparaîtrait comme suit :
Opérations sur les tables de hachage
Voici les Operations prises en charge par les tables de hachage :
- Insertion - Cette Operation est utilisée pour ajouter un élément à la table de hachage
- Recherche - Cette Operation permet de rechercher des éléments dans la table de hachage à l'aide de la clé
- Suppression - Cette Operation 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.
Opération de recherche 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.
Opération de suppression de données
L'opération de suppression est utilisée pour supprimer une valeur d'une table de hachage. Pour supprimer la OperaLa suppression se fait à l'aide du numéro d'index. Une fois qu'une valeur a été supprimée, le numéro d'index est libéré. Il peut être utilisé pour stocker d'autres valeurs à l'aide de l'opération d'insertion.
Implémentation de table de hachage avec Python Exemple
Regardons un exemple simple qui calcule la valeur de hachage d'une clé
def hash_key( key, m):
return key % m
m = 7
print(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,
- Définit une fonction hash_key qui accepte les paramètres key et m.
- Utilise une opération de module simple pour déterminer la valeur de hachage
- Définit une variable m qui est initialisée à la valeur 7. C'est la taille de notre table de hachage
- Calcule et imprime la valeur de hachage de 3
- Calcule et imprime la valeur de hachage de 2
- Calcule et imprime la valeur de hachage de 9
- Calcule et imprime la valeur de hachage de 11
- 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 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Exemple de dictionnaire
Python est livré avec un type de données intégré appelé Dictionnaire. 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 vous pouvez utiliser un type de données de dictionnaire dans 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,
- Définit une variable de dictionnaire employe. 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.
- Récupère la valeur du nom de la clé et l'imprime dans le terminal
- Met à jour la valeur du poste clé vers la valeur Software Engineer
- Imprime les valeurs du nom et de la position des clés
- Supprime toutes les valeurs stockées dans notre variable de dictionnaire employé
- 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 plusieurs valeurs génèrent la même clé de hachage et que nous devons résoudre la collision par sondage.
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 offrent 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 lorsque vous travaillez 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. Des collisions se produisent lorsqu'une clé déjà utilisée est générée.
- Si la fonction de hachage présente 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 chaînées.
- Le sondage résout les collisions en trouvant des emplacements vides dans la table de hachage.
- Le sondage linéaire recherche le prochain emplacement libre pour stocker la valeur à partir de l'emplacement où la collision s'est produite.
- Le sondage quadratique utilise des expressions polynomiales pour trouver le prochain emplacement libre lorsqu'une collision se produit.
- Double le 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.
