wikinotes

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
{{tag>dev go golang}}


Notes et transcriptions du cours "[[https://www.coursera.org/learn/golang-getting-started/home/welcome|Démarrer avec Go]]" proposée par 
[[https://uci.edu/|University of California, Irvine]] disponible sur la plateforme [[https://www.coursera.org/|coursera]].

====== Les tables de hachage (hash table) ======


===== Principe de fonctionnement =====

Une table de hachage est une structure de données utilisée dans de nombreux langages. C'est une structure de données très utile qui vous permet d'accéder rapidement à de grands ensembles de données.

La table de hachage contient généralement des paires clé-valeur. Cette table de hachage contient donc de nombreuses valeurs, mais chaque valeur est associée à une clé unique.

Par exemple, le numéro de sécurité sociale et le e-mails. Le numéro de sécurité sociale peut servir de clé unique désignant une personne, puis la valeur peut être son adresse e-mail. Donc ça fait une paire.

La clé doit être unique, c'est fondamental. Un autre exemple : les coordonnées GPS et l'adresse. Chaque adresse peut être associée à un ensemble unique de coordonnées GPS. Les coordonnées GPS peuvent être utilisées comme clé, puis l'adresse de votre domicile comme valeur, celle-ci peut être unique ou non. Un nom de rue n'est pas forcement unique, mais les coordonnées GPS sont être uniques (ou la clé doit être unique).

Une table de hachage est donc destinée à stocker ces paires clé-valeur, et il est important que chaque clé soit unique. Ainsi, une fonction de hachage est définie et utilisée pour prendre une clé et calculer un emplacement dans la table de hachage afin d'insérer la valeur en fonction de la clé.

Vous pouvez vous représenter une table de hachage comme (je déteste le dire) un grand tableau. Elle contient de nombreux emplacements où vous pouvez y mettre des valeurs. Désormais, l'emplacement dans lequel la valeur est stockée est basé sur la clé.

Une fonction de hachage est utilisée pour traiter la clé et générer le numéro de l'emplacement dans lequel vous souhaitez insérer la valeur. Ainsi, une fonction de hachage est une fonction qui prend comme argument la clé et renvoie l'emplacement où vous souhaitez mettre la valeur.

En pratique, cette fonction de hachage, vous ne l'appelez jamais explicitement. C'est quelque chose qui se passe dans les coulisses du langage Go, mais pour comprendre, il existe une fonction de hachage qui le fait.

Voici donc un exemple de ce à quoi peut ressembler une table de hachage.

{{exemple_hash_table_go.png}}

Sur cette illustration, nous avons un petit tableau, un ensemble de clés et des valeurs. Les clés sont "Joe" , "Jane" et "Pat", ce sont toutes des clés uniques, leurs chaînes sont uniques, et il y a des valeurs "x", "y" et "z", elles sont arbitraires. "Joe" est donc associé à "x", "Jane" à "y", "Pat" associé à "z", et je veux mettre ces trois paires clé-valeur dans ma table de hachage.

En bas à droite, vous avez un tableau d'une certaine taille (ici celui-ci est petit, mais ce n'est qu'un exemple). Dans ce tableau, les valeurs "x", "y" et "z" sont toutes placées dans des emplacements différents à l'intérieur de cette structure.

Dans l'exemple ils sont placés arbitrairement à l'intérieur de la structure, "y" est à l'emplacement 1, "x" à l'emplacement 3, "z" est à l'emplacement 5. Sur la gauche, vous pouvez voir les clés "Joe", "Jane" et "Pat". Entre les deux, il y a la fonction de hachage : elle prend la clé et détermine dans quel emplacement elle va placer la valeur correspondante.

Ce traitement est représenté par la ligne : il y a une flèche bleue qui entre dans la fonction de hachage, puis pointe vers l'emplacement. "Joe" est donc associé à l'emplacement 3 de la structure qui contient la valeur "x". Pour "Jane", la fonction de hachage détermine l'emplacement 1. Ainsi, l'emplacement 1 a la valeur "y" de "Jane", et de même avec "Pat", "Pat" est associé par le biais de la fonction de hachage à l' emplacement 5, la valeur "z" est placée dans l'emplacement 5.

C'est donc l'idée de fonctionnement d'une table de hachage. Un avantage de la table de hachage est qu'elle s'utilise un peu comme un tableau (array) ou une tranche (slice). Le temps d'accès aux emplacements de la structure est constant et vous n'avez pas besoin d'utiliser d'index pour y accéder.

Vous pouvez utiliser des clés arbitraires tant que les clés sont uniques et constantes. S'il s'agissait d'un tableau, pour accéder au premier élément, je devrais écrire %%anArray[0]%%. Dans le cas de la table de hachage, je peux écrire %%anHashTable["Joe"]%%.

C'est donc vraiment utile, la dénomination de la clé est utile pour plusieurs raisons. L'une des raisons est qu'il est plus facile pour un programmeur de se souvenir de "Joe", "Jane" et "Pat" plutôt que d'un nombre arbitraire qui leur serait associé. Les chiffres n'ont aucune signification particulière par rapport à l'application que vous écrivez, alors que "Joe", "Jane" et "Pat" sont des personnes et ils ont une sorte de signification dans l'esprit du programmeur. La table de hachage peut faciliter le codage.


===== Avantages et inconvénients =====

Un avantage des tables de hachage par rapport aux listes est le temps de recherche d'un élément. La recherche est plus rapide que dans les listes car dans une liste, te temps de recherche est linéaire. Cela signifie que si vous voulez trouver un élément dans une liste, vous devez commencer par le début de la liste et passer au suivant, puis au suivant et continuer à comparer jusqu'à ce que vous trouviez celui que vous recherchez, celui qui correspond. C'est du temps linéaire : plus la liste est longue, plus il faut de temps pour trouver des éléments dans la liste en moyenne. Pour la table de hachage, le temps de recherche est constants, cela ressemble beaucoup plus à un tableau. En gros, vous prenez l'index, plutôt la clé, vous utilisez la fonction de hachage qui prend un temps constant et qui vous donne l'index et vous passez directement à cet index. Il s'agit donc d'une recherche en temps constant plutôt qu'en temps linéaire comme vous le trouveriez dans une liste.

Autre avantage au sujet des clés, la possibilité d'utiliser une clé arbitraire, donc c'est mieux que, disons, des tranches ou des tableaux où vous devriez utiliser des entiers. Vous pouvez utiliser des clés arbitraires et ces clés peuvent avoir une certaine signification pour le programmeur ou l'application.


L' inconvénient est que vous pouvez avoir ce que l'on appelle des collisions à l'intérieur de votre table de hachage. La collision se produit donc lorsque deux clés différentes produisent un hachage identique et pointent donc le même emplacement. Si on utilise les clés "Joe" et "Jane", et si la fonction de hachage fait correspondre ces clés à l'emplacement 2, alors vous avez une collision : la valeur de "Joe" et la valeur de "Jane" doivent toutes deux être placées dans le même emplacement.

Le langage Go gère en interne ces collisions mais la vitesse ralentit un peu, parce que ces collisions doivent être gérées d'une manière ou d'une autre. Vous n'avez pas à vous soucier de la façon dont elles sont gérées, cela est intégré à Go, mais cela peut vous ralentir, notons que les collisions sont rares car la fonction de hachage est conçue de telle sorte que les collisions sont très rares. C'est donc un inconvénient possible des collisions, mais cela ne vous posera probablement pas beaucoup de problèmes.


[[320_slice_variable|◁ Précédent]] |
[[000_start|⌂ Retour au sommaire ]] |
[[330_map|Suivant ▷ ]]
wikinotes

Outils pour utilisateurs

Outils du site

Outils de la page
