Selon ma compréhension, je pense:
- Il est parfaitement légal que deux objets aient le même code de hachage.
- Si deux objets sont égaux (en utilisant la méthode equals ()) alors ils ont le même hashcode.
- Si deux objets ne sont pas égaux, ils ne peuvent pas avoir le même code de hachage
Ai-je raison?
Maintenant, si je me trompe, j'ai la question suivante: Le HashMap
utilise en interne le hashcode de l'objet. Donc, si deux objets peuvent avoir le même code de hachage, comment peut-il HashMap
suivre la clé qu'il utilise?
Quelqu'un peut-il expliquer comment l' HashMap
interne utilise le hashcode de l'objet?
java
hashmap
hashcode
hash-function
akshay
la source
la source
Réponses:
Un hashmap fonctionne comme ceci (c'est un peu simplifié, mais il illustre le mécanisme de base):
Il a un certain nombre de "compartiments" qu'il utilise pour stocker les paires clé-valeur. Chaque compartiment a un numéro unique - c'est ce qui identifie le compartiment. Lorsque vous placez une paire clé-valeur dans la carte, la table de hachage examine le code de hachage de la clé et stocke la paire dans le compartiment dont l'identifiant est le code de hachage de la clé. Par exemple: Le code de hachage de la clé est 235 -> la paire est stockée dans le numéro de compartiment 235. (Notez qu'un compartiment peut stocker plus d'une paire clé-valeur).
Lorsque vous recherchez une valeur dans la table de hachage, en lui donnant une clé, elle examinera d'abord le code de hachage de la clé que vous avez donnée. La table de hachage examinera ensuite le compartiment correspondant, puis comparera la clé que vous avez donnée avec les clés de toutes les paires du compartiment, en les comparant avec
equals()
.Vous pouvez maintenant voir comment cela est très efficace pour rechercher des paires clé-valeur dans une carte: par le code de hachage de la clé, la table de hachage sait immédiatement dans quel compartiment chercher, de sorte qu'elle n'a qu'à tester par rapport à ce qu'elle contient.
En regardant le mécanisme ci-dessus, vous pouvez également voir quelles exigences sont nécessaires sur les méthodes
hashCode()
et lesequals()
clés:Si deux clés sont identiques (
equals()
renvoietrue
lorsque vous les comparez), leurhashCode()
méthode doit renvoyer le même nombre. Si les clés ne le respectent pas, les clés égales peuvent être stockées dans différents compartiments et le hashmap ne pourra pas trouver de paires clé-valeur (car il va chercher dans le même compartiment).Si deux clés sont différentes, peu importe que leurs codes de hachage soient identiques ou non. Ils seront stockés dans le même compartiment si leurs codes de hachage sont les mêmes, et dans ce cas, la table de hachage les utilisera
equals()
pour les différencier.la source
hashCode()
méthode renvoie des codes de hachage différents, les méthodesequals()
ethashCode()
de la classe de clé violent le contrat et vous obtiendrez des résultats étranges lorsque vous utilisez ces clés dans aHashMap
.HashMap
, que vous pouvez trouver dans le fichiersrc.zip
dans votre répertoire d'installation JDK.Votre troisième affirmation est incorrecte.
Il est parfaitement légal que deux objets inégaux aient le même code de hachage. Il est utilisé par
HashMap
comme "filtre de premier passage" afin que la carte puisse trouver rapidement les entrées possibles avec la clé spécifiée. Les clés avec le même code de hachage sont ensuite testées pour leur égalité avec la clé spécifiée.Vous ne voudriez pas que deux objets inégaux ne puissent pas avoir le même code de hachage, sinon cela vous limiterait à 2 32 objets possibles. (Cela signifierait également que différents types ne pourraient même pas utiliser les champs d'un objet pour générer des codes de hachage, car d'autres classes pourraient générer le même hachage.)
la source
HashMap
est un tableau d'Entry
objets.Considérez
HashMap
simplement un tableau d'objets.Jetez un œil à ce que
Object
c'est:Chaque
Entry
objet représente une paire clé-valeur. Le champnext
fait référence à un autreEntry
objet si un compartiment en contient plusieursEntry
.Parfois, il peut arriver que les codes de hachage pour 2 objets différents soient identiques. Dans ce cas, deux objets seront enregistrés dans un seul compartiment et seront présentés sous forme de liste liée. Le point d'entrée est l'objet le plus récemment ajouté. Cet objet fait référence à un autre objet avec le
next
champ et ainsi de suite. La dernière entrée fait référence ànull
.Lorsque vous créez un
HashMap
avec le constructeur par défautLe tableau est créé avec une taille 16 et un équilibre de charge par défaut de 0,75.
Ajout d'une nouvelle paire valeur / clé
hash % (arrayLength-1)
où l'élément doit être placé (numéro de godet)HashMap
, la valeur est remplacée.Si le seau a déjà au moins un élément, un nouveau est ajouté et placé dans la première position du seau. Son
next
champ fait référence à l'ancien élément.Effacement
hash % (arrayLength-1)
Entry
. Si un élément souhaité n'est pas trouvé, retourneznull
la source
hash % (arrayLength-1)
ce seraithash % arrayLength
. Mais c'est effectivement le cashash & (arrayLength-1)
. Autrement dit, car il utilise des puissances de deux (2^n
) pour la longueur du tableau, en prenantn
les bits les moins significatifs.int
qui peut bien sûr être négatif, faire du modulo sur un nombre négatif vous donnera un nombre négatifVous pouvez trouver d'excellentes informations sur http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html
Résumer:
HashMap fonctionne sur le principe du hachage
put (clé, valeur): HashMap stocke à la fois la clé et l'objet de valeur en tant que Map.Entry. Hashmap applique le code de hachage (clé) pour obtenir le compartiment. en cas de collision, HashMap utilise LinkedList pour stocker l'objet.
get (key): HashMap utilise le hashcode de Key Object pour trouver l'emplacement du compartiment, puis appeler la méthode keys.equals () pour identifier le nœud correct dans LinkedList et renvoyer l'objet de valeur associé pour cette clé dans Java HashMap.
la source
Voici une description approximative du
HashMap
mécanisme de, pour laJava 8
version, (il peut être légèrement différent de Java 6) .Structures de données
hachage La valeur de hachage est calculée via une
hash()
clé, et elle décide quel compartiment de la table de hachage utiliser pour une clé donnée.Lorsque le nombre d'éléments dans un compartiment est petit, une liste liée individuellement est utilisée.
Lorsque le nombre d'éléments dans un compartiment est important, un arbre rouge-noir est utilisé.
Cours (internes)
Map.Entry
Représente une seule entité sur la carte, l'entité clé / valeur.
HashMap.Node
Version de liste liée du nœud.
Cela pourrait représenter:
Parce qu'il a une propriété de hachage.
HashMap.TreeNode
Version arborescente du nœud.
Champs (internes)
Node[] table
La table bucket, (tête des listes chaînées).
Si un compartiment ne contient pas d'éléments, il est alors nul, ne prend donc que l'espace d'une référence.
Set<Map.Entry> entrySet
Ensemble d'entités.int size
Nombre d'entités.
float loadFactor
Indiquez à quel point la table de hachage est autorisée avant de redimensionner.
int threshold
La prochaine taille à laquelle redimensionner.
Formule:
threshold = capacity * loadFactor
Méthodes (internes)
int hash(key)
Calculez le hachage par clé.
Comment mapper le hachage au compartiment?
Utilisez la logique suivante:
À propos de la capacité
Dans la table de hachage, la capacité signifie le nombre de seaux, il peut être obtenu
table.length
.Peut également être calculé via
threshold
etloadFactor
, donc pas besoin d'être défini comme un champ de classe.Pourrait obtenir la capacité effective via:
capacity()
Les opérations
Trouvez d'abord le compartiment par valeur de hachage, puis bouclez la liste chaînée ou recherchez l'arborescence triée.
Trouvez d'abord le compartiment en fonction de la valeur de hachage de la clé.
Essayez ensuite de trouver la valeur:
Une fois
threshold
atteint, doublera la capacité de la table de hachage (table.length
), puis effectuera un nouveau hachage sur tous les éléments pour reconstruire la table.Cela pourrait être une opération coûteuse.
Performance
La complexité du temps est
O(1)
, car:O(1)
.O(1)
.O(1)
, nonO(log N)
.la source
Le code de hachage détermine le compartiment que la carte de hachage doit vérifier. S'il y a plus d'un objet dans le compartiment, une recherche linéaire est effectuée pour trouver l'élément dans le compartiment égal à l'élément souhaité (à l'aide de la
equals()
méthode).En d'autres termes, si vous avez un code de hachage parfait, l'accès au hashmap est constant, vous n'aurez jamais à parcourir un compartiment (techniquement, vous devrez également avoir des compartiments MAX_INT, l'implémentation Java peut partager quelques codes de hachage dans le même compartiment pour réduire les besoins en espace). Si vous avez le pire code de hachage (renvoie toujours le même numéro), votre accès à la carte de hachage devient linéaire car vous devez rechercher dans chaque élément de la carte (ils sont tous dans le même compartiment) pour obtenir ce que vous voulez.
La plupart du temps, un code de hachage bien écrit n'est pas parfait mais est suffisamment unique pour vous donner un accès plus ou moins constant.
la source
Vous vous trompez sur le point trois. Deux entrées peuvent avoir le même code de hachage mais ne pas être égales. Jetez un œil à l'implémentation de HashMap.get depuis OpenJdk . Vous pouvez voir qu'il vérifie que les hachages sont égaux et que les clés sont égales. Si le point trois était vrai, il serait inutile de vérifier que les clés sont égales. Le code de hachage est comparé avant la clé car le premier est une comparaison plus efficace.
Si vous souhaitez en savoir un peu plus à ce sujet, jetez un coup d'œil à l'article de Wikipedia sur la résolution de collision Open Addressing , qui, je crois, est le mécanisme utilisé par l'implémentation OpenJdk. Ce mécanisme est subtilement différent de l'approche "bucket" mentionnée dans l'une des autres réponses.
la source
Nous voyons donc ici que si les objets S1 et S2 ont tous deux un contenu différent, nous sommes à peu près sûrs que notre méthode Hashcode remplacée générera un Hashcode différent (116232, 11601) pour les deux objets. MAINTENANT car il existe différents codes de hachage, il ne sera même pas la peine d'appeler la méthode EQUALS. Parce qu'un Hashcode différent GARANTIT UN CONTENU DIFFÉRENT dans un objet.
la source
Mise à jour Java 8 dans HashMap-
vous faites cette opération dans votre code -
supposons donc que votre code de hachage soit retourné pour les deux clés
"old"
et qu'il"very-old"
soit le même. Alors que se passera-t-il.myHashMap
est un HashMap, et supposez qu'au départ vous n'avez pas spécifié sa capacité. La capacité par défaut par Java est donc de 16. Donc, dès que vous avez initialisé la table de hachage à l'aide du nouveau mot clé, elle a créé 16 compartiments. maintenant, lorsque vous avez exécuté la première instruction-alors le code de hachage pour
"old"
est calculé, et parce que le code de hachage peut également être un très grand entier, donc, java a fait cela en interne - (le hachage est le code de hachage ici et >>> est le décalage à droite)donc pour donner une image plus grande, il renverra un index, qui serait compris entre 0 et 15. Maintenant, votre paire de valeurs de clé
"old"
et"old-value"
sera convertie en clé d'instance d'objet d'entrée et variable d'instance de valeur. puis cet objet d'entrée sera stocké dans le compartiment, ou vous pouvez dire qu'à un index particulier, cet objet d'entrée serait stocké.FYI- Entry est une classe dans Map interface- Map.Entry, avec ces signature / définition
maintenant, lorsque vous exécutez la prochaine instruction -
et
"very-old"
donne le même code de hachage que"old"
, donc cette nouvelle paire de valeurs clés est à nouveau envoyée au même index ou au même compartiment. Mais comme ce compartiment n'est pas vide, lanext
variable de l'objet Entry est utilisée pour stocker cette nouvelle paire de valeurs clés.et cela sera stocké en tant que liste chaînée pour chaque objet qui a le même code de hachage, mais un TRIEFY_THRESHOLD est spécifié avec la valeur 6. donc après cela, la liste chaînée est convertie en arbre équilibré (arbre rouge-noir) avec le premier élément comme le racine.
la source
Chaque objet Entry représente une paire valeur / clé. Le champ fait ensuite référence à un autre objet Entry si un compartiment a plus d'une entrée.
Parfois, il peut arriver que les codes de hachage pour 2 objets différents soient identiques. Dans ce cas, 2 objets seront enregistrés dans un compartiment et seront présentés comme LinkedList. Le point d'entrée est un objet récemment ajouté. Cet objet fait référence à un autre objet avec le champ suivant et donc un. La dernière entrée fait référence à null. Lorsque vous créez HashMap avec le constructeur par défaut
Le tableau est créé avec une taille 16 et un équilibre de charge de 0,75 par défaut.
(La source)
la source
La carte de hachage fonctionne sur le principe du hachage
La méthode HashMap get (Key k) appelle la méthode hashCode sur l'objet clé et applique le hashValue retourné à sa propre fonction de hachage statique pour trouver un emplacement de compartiment (tableau de sauvegarde) où les clés et les valeurs sont stockées sous la forme d'une classe imbriquée appelée Entry (Map. Entrée). Vous avez donc conclu qu'à partir de la ligne précédente, la clé et la valeur sont stockées dans le compartiment sous la forme d'un objet Entry. Donc, penser que seule la valeur est stockée dans le seau n'est pas correct et ne donnera pas une bonne impression à l'intervieweur.
Si la clé est nulle, les clés nulles sont toujours mappées sur le hachage 0, donc l'index 0.
Si la clé n'est pas nulle, elle appellera la fonction de hachage sur l'objet clé, voir la ligne 4 dans la méthode ci-dessus, c'est-à-dire key.hashCode (), donc après que key.hashCode () renvoie hashValue, la ligne 4 ressemble à
et maintenant, il applique hashValue retourné dans sa propre fonction de hachage.
Nous pouvons nous demander pourquoi nous calculons à nouveau la valeur de hachage à l'aide de hachage (hashValue). La réponse est: il se défend contre les fonctions de hachage de mauvaise qualité.
La valeur de hachage finale est maintenant utilisée pour trouver l'emplacement du compartiment dans lequel l'objet Entry est stocké. Les objets d'entrée sont stockés dans le compartiment comme ceci (hachage, clé, valeur, bucketindex)
la source
Je n'entrerai pas dans les détails du fonctionnement de HashMap, mais je donnerai un exemple afin que nous puissions nous rappeler comment HashMap fonctionne en le reliant à la réalité.
Nous avons Key, Value, HashCode et bucket.
Pendant un certain temps, nous relierons chacun d'eux aux éléments suivants:
Utilisation de Map.get (clé):
Stevie veut se rendre à la maison de son ami (Josse) qui vit dans une villa dans une société VIP, que ce soit JavaLovers Society. L'adresse de Josse est son SSN (qui est différent pour tout le monde). Il existe un index dans lequel nous découvrons le nom de la société sur la base de SSN. Cet index peut être considéré comme un algorithme pour découvrir le HashCode.
Utilisation de Map.put (clé, valeur)
Cela trouve une société appropriée pour cette valeur en trouvant le HashCode, puis la valeur est stockée.
J'espère que cela aide et que cela est ouvert à des modifications.
la source
Ça va être une longue réponse, prenez un verre et lisez la suite…
Le hachage consiste à stocker en mémoire une paire clé-valeur qui peut être lue et écrite plus rapidement. Il stocke les clés dans un tableau et les valeurs dans une LinkedList.
Disons que je veux stocker 4 paires de valeurs clés -
Donc, pour stocker les clés, nous avons besoin d'un tableau de 4 éléments. Maintenant, comment mapper l'une de ces 4 clés à 4 index de tableau (0,1,2,3)?
Ainsi, java trouve le hashCode de clés individuelles et les mappe à un index de tableau particulier. Formules Hashcode est -
Hash et fille !! Je sais à quoi tu penses. Votre fascination pour ce duo sauvage pourrait vous faire manquer une chose importante.
Pourquoi java le multiplie par 31?
Maintenant, comment ce code de hachage est mappé à un index de tableau?
réponse est
Hash Code % (Array length -1)
.“girl”
Est donc mappé à(3173020 % 3) = 1
dans notre cas. qui est le deuxième élément du tableau.et la valeur "ahhan" est stockée dans une LinkedList associée à l'index de tableau 1.
HashCollision - Si vous essayez de trouver
hasHCode
les clés“misused”
et d'“horsemints”
utiliser les formules décrites ci-dessus, vous verrez les deux nous donner la même chose1069518484
. Whooaa !! leçon apprise -Maintenant, la carte de hachage ressemble à -
Maintenant, si un corps essaie de trouver la valeur de la clé
“horsemints”
, java trouvera rapidement le hashCode de celui-ci, le modulera et commencera à rechercher sa valeur dans la LinkedList correspondanteindex 1
. Ainsi, nous n'avons pas besoin de rechercher tous les 4 index de tableau, ce qui accélère l'accès aux données.Mais attendez une seconde. il y a 3 valeurs dans ce LinkedList correspondant Array index 1, comment il découvre laquelle était la valeur pour les «horsemints» clés?
En fait, j'ai menti, quand j'ai dit que HashMap stocke juste des valeurs dans LinkedList.
Il stocke les deux paires de valeurs clés comme entrée de carte. Donc, en réalité, Map ressemble à ceci.
Maintenant, vous pouvez voir En parcourant la LinkedList correspondant à ArrayIndex1, il compare en fait la clé de chaque entrée à celle de cette LinkedList à «horsemints» et quand il en trouve une, il n'en retourne que la valeur.
J'espère que vous vous êtes amusé en le lisant :)
la source
Comme on dit, une image vaut 1000 mots. Je dis: un code vaut mieux que 1000 mots. Voici le code source de HashMap. Méthode Get:
Il devient donc clair que le hachage est utilisé pour trouver le "compartiment" et le premier élément est toujours vérifié dans ce compartiment. Sinon, alors
equals
la clé est utilisée pour trouver l'élément réel dans la liste chaînée.Voyons la
put()
méthode:C'est un peu plus compliqué, mais il devient clair que le nouvel élément est placé dans l'onglet à la position calculée en fonction du hachage:
i = (n - 1) & hash
voicii
l'index où sera placé le nouvel élément (ou c'est le "bucket").n
est la taille dutab
tableau (tableau de "compartiments").Tout d'abord, on essaie de le mettre comme premier élément de ce "seau". S'il y a déjà un élément, ajoutez un nouveau nœud à la liste.
la source