Qu'est ce qu'une fonction de hachage en java?
J'ai vérifier cette page de Wikipédia, mais je ne comprends toujours pas. Quelqu'un peut s'il vous plaît aider mes dim-witted esprit pour comprendre les concepts de hachage table de hachage/table de hachage, et les fonctions de hachage? Quelques exemples aiderait vraiment.
- Ce sujet l'article de wikipédia ne comprenez-vous pas? Sinon, on ne ferait que répéter les mêmes informations.
- L'article semble tout à fait clair pour moi, donc je pense qu'il serait difficile de trouver une explication alternative en général. Pourriez-vous être plus précis sur ce que c'est que vous ne comprenez pas dans cet article?
- Un exemple, un exemple de code permettrait au moins.
Vous devez vous connecter pour publier un commentaire.
L'article de Wikipédia aura beaucoup d'informations techniques, mais une vision simpliste de hachage est quelque chose comme ce qui suit.
Imaginer qu'il y a une fonction magique qui permet de donner un numéro à n'importe quel objet. Compte tenu de l'objet même, elle retourne toujours le même nombre.
Immédiatement vous avez maintenant un moyen rapide de tester si deux objets sont les mêmes: demandez à cette fonction de leurs nombres et de les comparer. Si ils sont différents, alors qu'ils ne sont pas les mêmes.
Mais que faire si ils ont le même nombre? Deux objets différents ont le même nombre?
Oui, c'est possible dans la plupart des scénarios. Disons que la fonction ne peut donner de chiffres entre 1..10, par exemple, et il y a 100 objets différents. Alors bien sûr, certains objets différents doivent avoir le même nombre. C'est ce qu'on appelle une "collision". Une "collision" rend notre rapide test d'égalité, ce n'est pas, autant que possible, nous voulons minimiser sa passe. Une bonne fonction magique est une qui serait essayer de minimiser le nombre de "collision".
Alors quoi d'autre pouvez-vous faire avec ce numéro? Eh bien, vous pouvez l'utiliser pour indexer un tableau. Étant donné un objet, vous pouvez le mettre à l'index donné par le nombre de cette fonction magique. Ce tableau est essentiellement une table de hachage est; cette fonction magique est une fonction de hachage.
Une fonction de hachage est une manière de créer une représentation compacte d'un nombre arbitrairement grand de données. En java avec la méthode hashcode cela signifie en quelque sorte décrivant l'état de votre objet (n'importe quelle taille) dans un int (4 octets). Et il est généralement rédigé de manière à être assez rapide comme expliqué ci-dessous.
Pour simplifier dans les tables de hashage/hashmaps le hashcode sert comme une sorte de bon marché est égal. Prendre deux objets a et b de type Foo permet de dit, de savoir si l'un.equals(b) 500 ms où, comme le calcul de a (économe) hashcode de prendre uniquement les 10ms. Donc, si nous voulons savoir si un.equals(b) au lieu de le faire directement, nous allons d'abord examiner les hashcodes et poser un.hashCode() == b.hashCode(). Notez que cela prendra seulement 20 ms dans notre exemple.
En raison de la définition de l'API de hashcode nous savons que si le hashcode de l'un n'est pas égal à b puis un.equals(b) ne doivent jamais être vrai. Donc, dans notre test ci-dessus, si nous voyons la hashcodes sont inégales puis nous n'avons jamais besoin de faire plus .equals() de test, c'est pourquoi vous devez toujours remplacer hashCode et equals ensemble.
Vous pouvez également voir les références sur l'écriture de "bon" ou "bien distribué" hashcodes. Cela a à voir avec le fait que l'inverse de la précédente déclarations à propos de hashcode et equals n'est pas vrai. Plus précisément un.hashCode() == b.hashCode() n'implique pas nécessairement un.equals(b) l'idée d'un bon hashcode est à vous de réduire la probabilité d'une.hashCode() == b.hashCode() quand un.est égal à(b) est faux. Vous pouvez avoir vu ce dénommé une collision d'une fonction de hachage.
Retour à hashmaps/tables. Elles sont basées sur des paires clé/valeur. Ainsi, lorsque vous ajoutez ou récupérer une valeur que vous fournira une clé. Donc la première chose que la carte a à faire est de regarder pour la clé, ce qui signifie de trouver quelque chose qui .equals() de la touche de vous fournir. Mais comme nous en avons discuté ci-dessus .equals() peut être incroyablement lent, ce qui signifie que les comparaisons peuvent être considérablement accéléré par la vérification de hashcodes premier. Depuis quand les hashcodes sont bien distribué, vous devez savoir rapidement quand x est certainement != y.
Maintenant, en plus de la comparaison hashmaps/tables de réellement utiliser le hashcodes pour organiser leur stockage interne des données, mais je pense que c'est au-delà de la portée de ce que vous cherchez à comprendre à ce point.
Cette livre (et vidéos des conférences) fournir quelques explication sur les algorithmes et structures de données. Il y a quelques conférences sur les fonctions de hachage (Un, Deux). Je recommande.
Cormen http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/chp_6046textcove.jpg
de plus, juste pour info,ce n'est Pas vraiment vrai, comme indiqué par polygenelubricants dans les commentaires.hashCode(), appelée sur une instance deObjectclasse renvoie une adresse de cette instance particulière dans la mémoire.convertingl'adresse interne de l'objet en entier/ce de la mise en œuvre technique estnot required"Objectclasse elle-même.Object.hashCode. Donc, de deux choses sont: (i) il n'est pas l'adresse, c'est une conversion à partir de l'adresse (ii) c'est tout à fait normal, pas de mise en œuvre obligatoire. Gardez à l'esprit que les objets peuvent être déplacés dans l'espace d'adressage trop, ce qui avec la collecte des ordures et de la machine virtuelle, etc, donc il y a certainement quelques couches d'abstraction de là.Une table de hachage est essentiellement un moyen de stocker des données dans un tableau et de le récupérer presque aussi rapide que la recherche de quelque chose dans un tableau par le biais d'un indice, sans perdre trop de place.
L'emploi d'une fonction de hachage est (dans ce contexte) pour calculer l'index de tableau à laquelle un objet est stocké sur la base du contenu de l'objet. Cela signifie qu'elle doit toujours retourner le même résultat pour le même objet, et doit renvoyer des résultats différents pour les différents objets autant que possible. Lorsque deux objets ont le même hash, il est appelé une "collision", et vous avez à traiter les cas spécialement, ce qui rend le truc plus lent.
Le mappage de touches pour les indices d'une table de hachage est appelée fonction de hachage.
Fonction de hachage contient deux parties
Code de hachage de la Carte : Il convertit les clés à l'entier de toute la gamme.
Compression Carte : Il convertit(apporte) ces entiers de la gamme des clés de la table de hachage a.
Prises de http://coder2design.com/hashing/
Fonction de hachage: Si vous passez le même objet à cette fonction un nombre quelconque de fois, que ce soit du texte, binaire ou le numéro, vous obtiendrez toujours le même résultat. Pour la table de hachage fins d'un nombre entier de retourner fonction de hachage est utilisée.
Au-dessus de la fonctionnalité est l'appel de hachage.
Table de hachage: Miracle de la structure de données de l'informatique qui renvoie des résultats de recherche en temps constant O(1). Il est basé sur le concept ci-dessus de hachage.
Donc, il a un meilleur temps d'accès que linkedlist, binaires de recherche, arbres etc.
Pourquoi près de O(1): Elle utilise un tableau comme sa structure de base en interne pour stocker les objets et les tableaux ont la constante de temps d'accès par conséquent, la table de Hachage n'trop.
[Interne]:
Ainsi, elle utilise un tableau de taille fixe en interne et lorsque vous insérez un (Clé, Valeur) de la paire, il calcule la clé de hachage et utilise cette valeur de hachage que l'indice de stocker l' (Clé,Valeur) de la paire dans la matrice. Ensuite, lors de la recherche de l'objet à l'aide de la même clé, il utilise le hachage de nouveau sur la touche index pour la recherche de la clé dans le tableau.
Maintenant, deux objets peuvent avoir la même valeur de hachage, et donc, lors de l'insertion de ces objets dans la table de hachage, il y aura collision. Il y a deux façons de résolution de collision. Vous pouvez consulter ce lien suffisamment de détails sur ce sujet.
FONCTION de HACHAGE:- UNE fonction de hachage prend un groupe de caractères (appelé une clé) et correspond à une valeur d'une certaine longueur (appelé une valeur de hachage ou de hachage). La valeur de hachage est le représentant de l'origine de la chaîne de caractères, mais il est habituellement plus petite que l'originale.
Le hachage est fait pour indexer et rechercher des éléments dans les bases de données, car il est plus facile de trouver le plus court de la valeur de hachage de la plus longue chaîne. Le hachage est également utilisé dans le chiffrement.Ce terme est également connu comme un algorithme de hachage ou d'un message digest fonction.
De HACHAGE de la CARTE:- table de hachage est une collection de classes qui est conçu pour stocker les éléments que les paires clé-valeur. Cartes fournissent une façon de regarder un truc basé sur la valeur de l'autre.
Une table qui est conçu pour stocker efficacement non contigus clés (numéros de compte, numéros de pièces, etc.) qui peut avoir d'importantes lacunes dans leur alphabétiques ou numériques séquences.
TABLE de HACHAGE:- les tables de Hachage sont créés avec un algorithme qui stocke les clés de hachage en seaux, qui contiennent des paires clé-valeur. Depuis les différentes clés de hachage pour le même seau, l'objectif de la table de hachage de la conception est d'étaler les paires clé-valeur uniformément avec chaque seau contenant que quelques-uns des paires clé-valeur possible. Lorsqu'un élément est recherché, sa clé est haché pour trouver le seau, et le seau est alors comparé à trouver la bonne paire clé-valeur.
HashCode()fonction qui retourne une valeur de type entier, est utilisé parHashMapde trouver une bonne seau.