Quels sont les hashtables et hashmaps et leurs cas d'utilisation typiques?

Question

J'ai récemment rencontré ces termes quelques fois, mais je ne comprends pas très bien comment ils fonctionnent et quand ils sont généralement appliqués.

Answer 1

Eh bien, réfléchissez de cette façon.

Si vous utilisez un tableau, une structure de données simple basée sur un index et que vous le remplissez de manière aléatoire, la recherche d'une entrée particulière devient une opération de plus en plus coûteuse lorsque vous le remplissez avec des données, car vous devez commencez à chercher d'un bout à l'autre jusqu'à trouver celui que vous voulez.

Si vous souhaitez obtenir un accès plus rapide aux données, vous devez généralement trier le tableau et utiliser une recherche binaire. Cependant, tout en augmentant la vitesse de recherche d’une valeur existante, l’insertion de nouvelles valeurs est lente, car vous devez déplacer des éléments existants lorsque vous devez insérer un élément au milieu.

Par contre, une table de hachage a une fonction qui prend une entrée et la réduit à un nombre, une clé de hachage. Ce nombre est ensuite utilisé comme index dans le tableau et c’est là que vous stockez l’entrée.

Une table de hachage tourne autour d'un tableau, qui au départ était vide. Vide ne veut pas dire longueur nulle, le tableau commence par une taille, mais tous les éléments du tableau ne contiennent rien.

Chaque élément a deux propriétés, data et une clé qui identifie les données. Par exemple, une liste de codes postaux américains serait un code postal - > nom type d'association. La fonction réduit la clé, mais ne considère pas les données.

Ainsi, lorsque vous insérez quelque chose dans la table de hachage, la fonction réduit la clé à un nombre, qui sert d'index dans ce tableau (vide), et c’est là que vous stockez les données, à la fois la clé et le code associé. données.

Ensuite, vous souhaitez rechercher une entrée spécifique pour laquelle vous connaissez la clé. Vous devez donc exécuter la clé à travers la même fonction, obtenir sa clé de hachage, accéder à cet emplacement particulier de la table de hachage et récupérer les données. là-bas.

Selon la théorie, la fonction qui réduit votre clé à une touche de hachage, ce nombre, est beaucoup moins coûteuse en calcul que la recherche linéaire.

Une table de hachage typique ne dispose pas d'un nombre infini d'éléments disponibles pour le stockage. Par conséquent, leur nombre est réduit à un indice qui correspond à la taille du tableau. Une façon de faire est simplement de prendre le module de l'indice par rapport à la taille du tableau. Pour un tableau de taille 10, l'index 0-9 mappera directement vers un index et l'index 10-19 vers le bas de 0 à 9, et ainsi de suite.

Certaines clés seront réduites au même index qu'une entrée existante dans la table de hachage. À ce stade, les clés réelles sont comparées directement, avec toutes les règles associées à la comparaison des types de données de la clé (c'est-à-dire la comparaison d'une chaîne normale par exemple). S'il existe une correspondance complète, vous ignorez les nouvelles données (elles existent déjà) ou vous écrasez (vous remplacez les anciennes données de cette clé), ou vous l'ajoutez (hashtable à valeurs multiples). S'il n'y a pas de correspondance, ce qui signifie que même si les clés de hachage étaient identiques, les clés elles-mêmes ne l'étaient pas, vous trouverez généralement un nouvel emplacement pour stocker cette clé + les données.

La résolution des collisions a de nombreuses implémentations, et la plus simple consiste simplement à aller au prochain élément vide du tableau. Cependant, cette solution simple pose d’autres problèmes, aussi, trouver le bon algorithme de résolution est également un bon exercice pour les hashtables.

Les tables de hachage peuvent également s'agrandir si elles se remplissent complètement (ou presque), généralement en créant un nouveau tableau de la nouvelle taille, en calculant à nouveau tous les index et en plaçant les éléments dans le nouveau tableau. dans leurs nouveaux emplacements.

La fonction qui réduit la clé à un nombre ne produit pas de valeur linéaire, c.-à-d. "AAA" devient 1, puis "AAB" devient 2, donc la table de hachage n'est pas triée par une valeur typique.

Un bon article sur wikipedia est également disponible sur le sujet, ici .

Answer 2

La réponse de Lassevk est très bonne, mais pourrait contenir un peu trop de détails. Voici le résumé. Je omets intentionnellement certaines informations que vous pouvez ignorer en toute sécurité dans 99% des cas.

Il n'y a pas de différence importante entre les tables de hachage et les cartes de hachage 99% du temps.

Les tables de hachage sont magiques

Sérieusement. C'est une structure de données magique qui, sauf , garantit trois choses . (Il existe des exceptions. Vous pouvez en grande partie les ignorer, bien que les apprendre un jour puisse vous être utile.)

1) Tout dans la table de hachage fait partie d'une paire: il existe une clé et une valeur . Vous insérez et extrayez des données en spécifiant la clé sur laquelle vous opérez.

2) Si vous faites quoi que ce soit avec une seule touche sur une table de hachage, c'est incroyablement rapide . Cela implique que put (clé, valeur) , get (clé) , contient (clé) et remove (clé) sont vraiment rapides.

3) Les tables de hachage génériques ne parviennent pas à exécuter des tâches non répertoriées dans le n ° 2 ! (Par "échec", nous entendons qu’ils sont extrêmement lents.)

Quand utilisons-nous les tables de hachage?

Nous utilisons des tables de hachage lorsque leur magie s’adapte à notre problème.

Par exemple, la mise en cache finit souvent par utiliser une table de hachage. Par exemple, supposons que nous avons 45 000 étudiants dans une université et que certains processus doivent conserver des enregistrements pour chacun d'entre eux. Si vous vous référez régulièrement à un étudiant par son numéro d’identification, un ID = > Le cache des étudiants est tout à fait sensé. L’opération que vous optimisez pour ce cache est la recherche rapide .

Les

hachages sont également extrêmement utiles pour stocker les relations entre les données lorsque vous ne voulez pas tout gâcher et modifier les objets eux-mêmes. Par exemple, lors de l’inscription aux cours, il peut être judicieux de pouvoir relier les étudiants aux cours qu’ils suivent. Cependant, pour une raison quelconque, vous ne voudrez peut-être pas que l’objet Student le sache. Utilisez un hachage studentToClassRegistration et conservez-le pendant que vous faites ce que vous devez faire.

Ils font également un premier choix relativement bon pour une structure de données , sauf lorsque vous devez effectuer l'une des opérations suivantes:

Quand ne pas utiliser les tables de hachage

Parcourez les éléments . Les tables de hachage ne font généralement pas très bien l'itération. (Génériques, c’est-à-dire. Des implémentations particulières contiennent parfois des listes chaînées qui sont utilisées pour rendre l’itération plus facile. Par exemple, en Java, LinkedHashMap vous permet d’itérer rapidement des clés ou des valeurs.)

Tri. Si vous ne pouvez pas effectuer une itération, le tri est également une douleur royale.

Aller de la valeur à la clé . Utilisez deux tables de hachage. Croyez-moi, je viens de vous épargner beaucoup de douleur.

Answer 3

si vous parlez en termes de Java, les deux sont des collections qui permettent l'ajout, la suppression et la mise à jour d'objets, et utilisent les algorithmes Hasing en interne.

La différence significative cependant, si nous parlons de Java, est que les hashtables sont intrinsèquement synchronisées et sont donc thread-safe alors que les cartes de hachage ne sont pas une collection thread-safe.

Hormis la synchronisation, le mécanisme interne de stockage et de récupération des objets consiste en un hachage dans les deux cas.

Si vous avez besoin de savoir comment fonctionne le hachage, je vous conseillerais un peu de googler sur Data Structers et les techniques de hachage.

Answer 4

Les tables de hachage / hashmaps associent une valeur (appelée "clé" à des fins d'homonymie) à une autre valeur. Vous pouvez les penser comme une sorte de dictionnaire (mot: définition) ou d’enregistrement de base de données (clé: données).