J'ai check out Cette page Wikipedia sur elle, mais je ne comprends toujours pas . Quelqu'un peut-il aider mon esprit atténué à comprendre les concepts de hachage, de hashtable / hashmap et de hachamps? Quelques exemples aideraient vraiment.
8 Réponses :
L'article Wikipedia aura beaucoup d'informations techniques, mais une vision simpliste du hachage est quelque chose comme ce qui suit.
Imaginez qu'il y a une fonction magique pouvant donner un numéro à n'importe quel objet. Compte tenu du même objet, il renvoie toujours le même numéro.
Immédiatement Maintenant, vous avez un moyen rapide de tester si deux objets sont les mêmes: Demandez cette fonction pour leurs chiffres et comparer. S'ils sont différents, alors ils ne sont pas les mêmes.
Mais que s'ils ont le même numéro? Deux objets différents pourraient-ils avoir le même numéro?
Oui, cela est possible dans la plupart des scénarios. Disons que la fonction ne peut donner que des chiffres compris entre 1..10, par exemple, et il y a 100 objets différents. Ensuite, bien sûr, certains objets différents doivent avoir le même numéro. C'est ce qu'on appelle une "collision". Une "collision" rend notre test d'égalité rapide non aussi utile, donc autant que possible, nous voulons minimiser son événement. Une bonne fonction magique est une bonne fonction qui essaierait de minimiser le nombre de "collision".
Que pouvez-vous faire d'autre avec ce nombre? Eh bien, vous pouvez l'utiliser pour indexer un tableau. Compte tenu d'un objet, vous pouvez le mettre à l'index indiqué par le numéro de cette fonction magique. Ce tableau est essentiellement ce qu'est une hache; Cette fonction magique est une fonction de hachage.
Ce livre livre (et Contacter des conférences vidéo ) fournit une grande explication des algorithmes et des structures de données. Il y a des conférences sur les fonctions de hachage ( 1 , 2 ). Je recommanderais ça.
(Source: mit.edu )
aussi, juste fyi, hashcode () , appelé une instance de objet class renvoie une adresse de cette instance particulière en mémoire. Pas vraiment vrai, comme indiqué par Polygégraphiques dans les commentaires.
FYI, votre FYI est une demi-vérité. De Java.sun.com / Javase / 6 / Docs / API / Java / Lang / ... - " Conversion L'adresse interne de l'objet dans un entier / cette technique de mise en œuvre est non requis "
Je suis intrigué. Pourriez-vous s'il vous plaît être plus précis? :)
Mais n'est-ce pas une recommandation pour les classes, qui remplacent cette méthode? Au lieu de cela, je parle d'instances de la classe de la classe elle-même.
Lisez la phrase entière. Cette citation est directement sur objet.hashcode . Donc, deux choses sont: (i) ce n'est pas l'adresse, c'est une conversion de l'adresse (II) qui n'est que la mise en œuvre typique et non obligatoire. Gardez à l'esprit que les objets peuvent également être déplacés dans l'espace d'adressage également, ce que la collecte des ordures et la machine virtuelle, etc., il y a donc certainement quelques couches d'abstraction.
Une hache est essentiellement un moyen de stocker quoi que ce soit dans un tableau et la récupérer presque aussi vite que de regarder quelque chose dans un tableau via un index, sans perdre trop d'espace.
Le travail d'une fonction de hachage est (dans ce contexte) pour calculer l'index de la matrice à laquelle un objet sera stocké, en fonction du contenu de l'objet. Cela signifie, il doit toujours renvoyer le même résultat pour le même objet et renvoyer différents résultats pour différents objets autant que possible. Lorsque deux objets différents ont le même hachage, cela s'appelle une "collision", et vous devez traiter ces cas spécialement, ce qui rend le tout plus lent.
Une fonction de hachage est un moyen de créer une représentation compacte d'une quantité de données de manière arbitraire importante. En Java avec la méthode HashCode, cela signifie en quelque sorte décrire l'état de votre objet (quelle que soit sa taille) dans un int (4 octets). Et est généralement écrit pour être assez rapide comme expliqué ci-dessous.
Pour simplifier dans les hashtables / HASHMAPS, le HashCode sert de sorte d'équivalent bon marché. Prenez deux objets A et B de type FOO permettent de déterminer si A.Equals (B) prend 500 ms où calculer un hashcode (efficace) ne prend que 10 ms. Donc, si nous voulons savoir si A.Equals (B) au lieu de le faire directement, nous examinerons les hashcodes et demandez à A.HashCode () == B.HashCode (). Notez que cela ne prendra que 20 ms dans notre exemple.
En raison de la définition de l'API de HashCode, nous savons que si Vous pouvez également voir des références sur la rédaction de "bons" ou "haussages" bien distribués ". Cela concerne le fait que l'inverse des déclarations précédentes concernant le hashcode et les égaux n'est pas vrai. Plus spécifiquement Retour aux hashmaps / tables. Ceux-ci sont basés sur des paires de clés / de valeur. Ainsi, lorsque vous ajoutez ou récupérez une valeur, vous allez fournir une clé. Donc, la première chose que la carte doit faire est de rechercher la clé, ce qui signifie de trouver quelque chose de ce que vous fournissez. Mais comme nous en avons discuté ci-dessus () peut être incroyablement lent, ce qui signifie que des comparaisons peuvent être considérablement accélérées en vérifiant d'abord les hachices. Étant donné que les hashcodes sont bien distribuées, vous devez connaître rapidement quand X est définitivement! = Y.
Maintenant, en plus de la comparaison HashMaps / Tables utilise réellement les Hashcodes pour organiser leur stockage interne des données, mais je pense que cela dépasse la portée de ce que vous cherchez à comprendre à ce stade.
Le mappage des clés des indices d'une table de hachage est appelé fonction de hachage. La fonction de hachage contient deux parties
pris de http://coder2design.com/hashing/
Fonction de hachage: Si vous passez le même objet à cette fonction un nombre de fois, que ce soit du texte, du binaire ou du numéro, vous obtenez toujours la même sortie. Pour la Table de hausse, une fonction de hachage de retour entier est utilisée.
La fonctionnalité ci-dessus appelle hachage.
Table de hachage: structure de données miracle de la science informatique qui renvoie le résultat de la recherche en temps constant ou O (1). Il est basé sur le concept de hachage ci-dessus. Donc, il a un meilleur temps d'accès que celui de LinkedList, des arbres de recherche binaires, etc.
Pourquoi presque O (1): il utilise un tableau comme une structure de base en interne pour stocker les objets et que les tableaux ont donc une durée d'accès constante, la table de hachage aussi.
[Basic interne]: Ainsi, il utilise une gamme de taille fixe en interne et lorsque vous insérez une paire (clé, valeur), elle calcule la clé Hash et utilise cette valeur de hachage comme index pour stocker la paire (touche, valeur) dans le tableau. Ensuite, lorsque vous recherchez l'objet à l'aide de la même clé, il utilise à nouveau le hachage de la clé en tant qu'index pour rechercher la clé dans la matrice. Maintenant, deux objets peuvent avoir la même valeur de hachage et donc, tout en insérant ces objets dans la table de hachage, il y aura une collision. Il existe deux manières de la résolution de collision. Vous pouvez faire référence à ce lien pour une discussion suffisamment détaillée sur ce sujet.
Fonction de hachage: - Une fonction de hachage prend un groupe de caractères (appelé une touche) et le mappe à une valeur d'une certaine longueur (appelée valeur de hachage ou hachage). La valeur de hachage est représentative de la chaîne d'origine de caractères, mais est normalement inférieure à celle d'origine. Le hachage est fait pour l'indexation et la localisation d'éléments dans des bases de données car il est plus facile de trouver la valeur de hachage plus courte que la chaîne la plus longue. Le hachage est également utilisé dans le cryptage. Ce terme est également appelé algorithme de hachage ou fonction de digère de message.
Carte de hachage: - HASHMAP est une classe de collection conçue pour stocker des éléments comme paires de clés. Les cartes fournissent un moyen de rechercher une chose basée sur la valeur d'une autre.
une table de recherche conçue pour stocker efficacement des clés non contiguës (numéros de compte, numéros de pièce, etc.) pouvant avoir de larges lacunes dans leurs séquences alphabétiques ou numériques.
Table de hachage: - Les tables de hachage sont créées avec un algorithme qui stocke les touches dans des godets de hachage, qui contiennent des paires de la valeur clé. Étant donné que différentes clés peuvent accéder au même seau, le but de la conception de table de hachage est de répartir les paires de la valeur de clé uniformément avec chaque godet contenant le moins de paires de valeur de clé. Lorsqu'un élément est levé, sa clé est hachée pour trouver le godet approprié et le godet est ensuite comparé à la recherche de la bonne paire de forces de clé.
hashcode () fonction, qui renvoie une valeur entière, est utilisé par hashmap pour trouver un godet correct.
Qu'en est-il de l'article Wikipedia, n'est-ce pas compris? Sinon, nous allions simplement répéter les mêmes informations.
L'article me semble évident, alors je voudrais donc avoir du mal à proposer une explication alternative en général. Pourriez-vous être plus précis sur ce que vous ne comprenez pas dans cet article?
Un exemple ou un échantillon de code aiderait au moins.