Qu'est ce qu'un hachage de la carte dans la programmation et où peut-il être utilisé

D'abord, vous devriez peut-être lire ce l'article.

Lorsque vous utilisez des listes et vous êtes à la recherche d'un point particulier, vous avez normalement pour parcourir la liste complète. C'est très cher quand vous avez de grandes listes.

Une table de hachage peut être beaucoup plus rapide, dans le meilleur des cas, vous obtiendrez l'élément que vous cherchez avec un seul accès.

Comment fonctionne t il? Comme un dictionnaire ... lorsque vous êtes à la recherche pour le mot "table de hachage" dans un dictionnaire, vous n'êtes pas en commençant par le premier mot dans 'un'. Mais plutôt, vous allez tout droit vers l'avant à la lettre "h". Puis à "ha", "a", et ainsi de suite, jusqu'à ce que vous avez trouvé votre mot. Vous utilisez un index dans votre dictionnaire pour accélérer votre recherche.

Une table de hachage n'est fondamentalement la même. Chaque élément sera un index unique (appelé hash). Vous utilisez ce code de hachage pour les recherches. Le hachage peut être un indice dans un normal la liste liée. Par exemple, votre hash pourrait être un certain nombre comme 2130 ce qui signifie que vous devriez regarder à la position 2130 dans votre liste. Une recherche à un indice connu à l'intérieur d'une liste normale est très facile et rapide.

Le problème de l'ensemble de la démarche est le hash function qui attribue cet indice pour chaque élément. Lorsque vous êtes à la recherche d'un élément, vous devriez être en mesure de calculer l'indice à l'avance. Comme dans un vrai dictionnaire, où l'on voit que le mot "table de hachage" commence par la lettre " h " et, par conséquent, vous connaissez la position approximative.

Une bonne fonction de hachage fournit hashcodes qui sont uniformément répartis sur l'espace de tous les possibles hashcodes. Et bien sûr, il essaie d'éviter collisions. Une collision se produit lorsque deux objets différents en obtenir le même hashcode.

En C# par exemple, chaque objet a une GetHashcode() méthode qui fournit une valeur de hachage pour elle (pas forcément unique). Ceci peut être utilisé pour les recherches et le tri dans votre dictionnaire.

Lorsque vous démarrez à l'aide de tables de hachage, vous devriez toujours garder à l'esprit que vous gérer les collisions correctement. Il peut arriver assez facilement dans les grandes tables de hachage que les deux objets ont eu le même hash (peut-être que votre surcharge de GetHashcode() est défectueuse, peut-être quelque chose d'autre est arrivé).

De hachage (dans le noncryptographic sens) est un terme général pour prendre les intrants et la production d'une sortie de l'identifier avec. Un exemple trivial d'une valeur de hachage est l'ajout de la somme des lettres d'une chaîne, j'.e:

f(abc) = 6

Noter que cette triviale de hachage schéma serait de créer une collision entre les cordes abc, bca, ae, etc. Un hachage efficace, le système de produire des valeurs différentes pour chaque chaîne, naturellement.

Hashmaps et les tables de hachage sont des structures de données (comme des tableaux et des listes), que l'utilisation de hachage pour stocker les données. Dans une table de hachage, une table de hachage est produite (soit à partir d'une clé, ou de l'objet lui-même) qui détermine où dans le tableau, l'objet est stocké. Cela signifie que tant que l'utilisateur de la table de hachage est conscient de la clé de récupération de l'objet est extrêmement rapide.

Dans une liste, à titre de comparaison, vous devez en quelque sorte la recherche par le biais de la liste afin de trouver votre recherchée objet. Cela représente aussi l'arrière de tables de hachage, qui est qu'il est très compliqué de trouver un objet dans le sans connaître la clé, parce que l'endroit où l'objet est stocké dans la table n'a pas de pertinence à sa valeur, ni quand il a été insérés.

Hashmaps sont similaires aux tables de hachage, mais qu'un seul exemplaire de chaque objet est stocké dans celui-ci (donc pas de clé doit être fourni, l'objet lui-même est la clé).

C'est bien sûr une explication très simple, donc je vous suggère de lire en profondeur à partir de ce point. J'espère que je n'ai pas fait de bêtises. =)