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.

Au fait, avec cette fonction de hachage, vous ne l'appelez jamais explicitement. C'est quelque chose qui se passe dans les coulisses du langage Go, mais juste pour comprendre, il existe une fonction de hachage qui le fait. Voici donc un exemple de ce à quoi peut ressembler une table de hachage. Donc, en haut, nous avons ce petit tableau, un trousseau de clés et des valeurs. Donc, mes 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. Donc, si vous regardez en bas à droite, vous avez essentiellement un tableau d'une certaine taille et celui-ci est petit, mais ce n'est qu'un exemple. Vous avez donc un tableau et les valeurs x, y et z sont toutes placées dans des emplacements différents à l'intérieur de cette structure. Donc, et je les place arbitrairement, Y est à l'emplacement un, et X à l'emplacement trois, Z est à l'emplacement cinq, n'est-ce pas ? Ils se trouvent donc dans un endroit arbitraire, dans des emplacements à l'intérieur de la structure. Maintenant, sur la gauche, vous pouvez voir les clés Joe, Jane et Pat. Maintenant, entre les deux, il y a cette fonction de hachage et la fonction de hachage, elle prend la clé et détermine dans quel emplacement elle va placer la valeur correspondante. Donc, je l'ai dessiné dans la ligne, donc si vous regardez Joe, il y a une flèche bleue qui entre dans la fonction de hachage, puis pointe vers le troisième emplacement, le troisième. Joe est donc associé au slot 3 qui a la valeur x, puis Jane, la fonction de hachage calculera un dans ce cas. 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 cinq, puis vous placez sa valeur z dans l'emplacement cinq. C'est donc l'idée qui sous-tend une table de hachage. Donc, la raison pour laquelle c'est une bonne chose est quelque chose comme un tableau ou une tranche, n'est-ce pas ? Vous pouvez accéder aux choses en temps constant, mais 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 toutes uniques et constantes, vous pouvez utiliser une clé. Donc, normalement, s'il s'agissait d'un tableau, si je veux accéder à l'entrée 1, à l'élément 1, je devrais dire le nom du tableau puis le mettre entre crochets. Dans ce cas, je peux dire brackets Joe ou bracket Jane ou bracket Pat ou quelque chose comme ça. C'est donc vraiment utile, la dénomination 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 de chiffres arbitraires. Les chiffres n'ont aucune signification particulière par rapport à l'application que vous écrivez, où Joe, Jane et Pat sont des personnes et ils ont une sorte de signification dans l'esprit du programmeur. Cela facilite donc le codage. Donc, des avantages. Les avantages sont les tables de recherche rapides par rapport aux listes. C'est donc un avantage par rapport à une liste que vous trouveriez dans une autre langue. Recherche plus rapide dans les listes car dans une liste, il s'agit d'une recherche temporelle linéaire. Cela signifie donc 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. Là où ce sont des temps constants, cela ressemble beaucoup plus à un tableau, non ? 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. Maintenant, une autre chose à ce sujet est que vous pouvez 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. L' inconvénient est donc 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 se hachent au même emplacement. Donc, Joe et Jane, si la fonction de hachage fait correspondre les deux à l'emplacement deux, alors vous avez une collision. Ensuite, la valeur de Joe et la valeur de James doivent toutes deux être placées dans le même emplacement. Il existe maintenant des moyens de gérer ces collisions. Vous pouvez les mettre tous les deux dedans et les mettre dans une liste liée ou quelque chose comme ça, mais lorsqu'il y a des collisions, la vitesse ralentit un peu, n'est-ce pas ? Parce que ces collisions doivent être gérées d'une manière ou d'une autre. Donc, 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, mais je dois dire que les collisions sont rares car la fonction de hachage est créée de telle sorte que les collisions sont très rares, d'accord ? C'est donc un inconvénient possible des collisions, mais cela ne vous posera probablement pas beaucoup de problèmes.

◁ Précédent | ⌂ Retour au sommaire | Suivant ▷