Le principe de travail de Hashmap est une question d'entrevue Java courante ces dernières années. Presque tous les programmeurs Java savent Hashmap, sait où utiliser Hashmap et connaît la différence entre hashtable et hashmap. Alors pourquoi cette question d'entrevue est-elle si spéciale? En effet, cette question est très profonde. Cette question apparaît souvent dans les entretiens avancés ou intermédiaires. Les banques d'investissement préfèrent poser cette question et peuvent même vous demander de mettre en œuvre HashMap pour examiner vos compétences en programmation. L'introduction de lamale concurrente et d'autres ensembles synchrones rend ce problème plus compliqué. Commençons le voyage de l'exploration!
Prenons d'abord quelques questions simples
"Avez-vous utilisé Hashmap?" "Qu'est-ce que Hashmap? Pourquoi l'avez-vous utilisé?"
Presque tout le monde répondra "oui", puis répondra certaines fonctionnalités de HashMap, comme HashMap peut accepter les valeurs et les valeurs de clés nuls, tandis que le hashtable ne peut pas; Hashmap est non synchronisé; Hashmap est rapide; Et HashMap stocke les paires de valeurs clés, etc. Cela montre que vous avez utilisé Hashmap et que vous le connaissez assez. Mais l'intervieweur a pris un virage rapide et a commencé à poser des questions délicates à partir de maintenant, sur les détails plus de base de Hashmap. L'intervieweur peut poser les questions suivantes:
"Savez-vous comment fonctionne Hashmap?" "Savez-vous comment fonctionne la méthode get () de Hashmap?"
Vous pourriez répondre: "Je n'ai pas recherché en détail l'API Java standard, vous pouvez consulter le code source Java ou ouvrir JDK." "Je peux trouver la réponse avec Google."
Mais certains enquêteurs peuvent être en mesure de répondre: "Hashmap est basé sur le principe du hachage. Nous utilisons PUT (clé, valeur) pour stocker des objets dans Hashmap et utilisons Get (Key) pour obtenir des objets de Hashmap. Lorsque nous passons les clés et les valeurs à la méthode Put (), nous appelons d'abord le Hashcode () la méthode de l'entrée, et l'objectif de Hashcode retourné est utilisé pour trouver l'emplacement du bail pour stocker l'objectif." Le point clé ici est de souligner que HashMap stocke les objets clés et la valeur des objets dans le seau comme map.entry. Cela aide à comprendre la logique de l'obtention d'objets. Si vous ne réalisez pas cela ou que vous pensez à tort que vous stockez des valeurs dans des seaux, vous ne répondez pas à la logique de la façon d'obtenir des objets de Hashmap. Cette réponse est tout à fait correcte, et cela montre également que l'intervieweur connaît le hachage et le fonctionnement de HashMap. Mais ce n'est que le début de l'histoire. Lorsque l'intervieweur rejoint des scènes réelles que les programmeurs Java doivent rencontrer chaque jour, les mauvaises réponses apparaissent fréquemment. La question suivante peut concerner la détection de collision dans Hashmap et la solution à la collision:
"Que se passe-t-il lorsque le code de hash de deux objets est le même?" De là, la vraie confusion commence, et certains intervieweurs répondront à ce que le HashCode est le même, les deux objets sont égaux et que le hashmap lancera des exceptions, ou ils ne seront pas stockés. Ensuite, l'intervieweur peut leur rappeler qu'il existe deux méthodes: equals () et hashcode (), et leur dire que même si le code de hash est le même, ils peuvent ne pas être égaux. Certains intervieweurs peuvent abandonner, tandis que d'autres peuvent continuer à avancer. Ils ont répondu: "Parce que le HashCode est le même, leur position de seau est la même et que la« collision »se produira. Parce que HashMap utilise une liste liée pour stocker des objets, cette entrée (l'objet Map.Entry contenant des paires de valeurs de clé) sera stocké dans la liste liée." Cette réponse est très raisonnable. Bien qu'il existe de nombreuses façons de gérer les collisions, cette méthode est la plus facile et c'est la méthode de traitement de Hashmap. Mais l'histoire n'est pas encore terminée, et l'intervieweur continuera à demander:
"Si le code hashcode des deux clés est le même, comment obtenez-vous l'objet de valeur?" L'intervieweur répondra: lorsque nous appelons la méthode get (), HashMap utilisera le code hashcode de l'objet clé pour trouver l'emplacement du seau, puis obtenir l'objet de valeur. L'intervieweur lui rappelle que si deux objets de valeur sont stockés dans le même seau, il donne la réponse: la liste liée sera traversée jusqu'à ce que l'objet de valeur soit trouvé. L'intervieweur demandera, parce que vous n'avez pas d'objet de valeur à comparer, comment avez-vous déterminé si vous devez trouver l'objet de valeur? À moins que l'intervieweur stocke les paires de valeurs clés dans la liste liée jusqu'à ce que HashMap les stocke dans la liste liée, ils ne pourront pas répondre à cette question.
Certains des enquêteurs qui se souviennent de ce point de connaissance important diront qu'après avoir trouvé l'emplacement du seau, ils appellent la méthode Keys.equals () pour trouver le nœud correct dans la liste liée et enfin trouver l'objet de valeur. La réponse parfaite!
Dans de nombreux cas, les enquêteurs feront des erreurs dans ce lien car ils confondent les méthodes HashCode () et Equals (). Parce qu'avant ce HashCode () apparaît à plusieurs reprises, et la méthode equals () n'apparaît que lors de l'obtention de l'objet de valeur. Certains excellents développeurs souligneront que l'utilisation d'objets immuables et déclarés comme finaux, et l'utilisation de méthodes appropriées Equals () et HashCode () réduiront la survenue de collisions et améliorera l'efficacité. L'immuabilité permet de mettre en cache le code de hash de différentes caches, ce qui augmentera la vitesse d'obtention de l'objet entier. L'utilisation de classes en wrapper comme String et Interger comme clés est un très bon choix.
Si vous pensez que c'est ici, vous serez surpris lorsque vous entendrez la question suivante. "Et si la taille de HashMap dépasse la capacité définie par le facteur de charge?" À moins que vous ne sachiez vraiment comment fonctionne HashMap, vous ne répondez pas à cette question. La taille du facteur de charge par défaut est de 0,75. C'est-à-dire que lorsqu'une carte remplit des seaux à 75%, comme d'autres classes de collecte (telles que ArrayList, etc.), un tableau de seau qui fait deux fois plus de taille du hashmap d'origine sera créé pour redimensionner la carte et mettre l'objet d'origine dans le nouveau tableau de seau. Ce processus est appelé remaniement car il appelle la méthode de hachage pour trouver le nouvel emplacement du seau.
Si vous pouvez répondre à cette question, la question suivante vient: "Comprenez-vous quels problèmes y a-t-il pour redimensionner Hashmap?" Vous ne pourrez peut-être pas y répondre. À l'heure actuelle, l'intervieweur vous rappellera que lors du multi-threading, il peut y avoir une condition de course.
Lors du redimensionnement de HashMap, il y a en effet une concurrence conditionnelle, car si les deux fils constatent que HashMap doit être redimensionné, ils essaieront de redimensionner en même temps. Pendant le processus de redimensionnement, l'ordre des éléments stockés dans la liste liée sera inversé, car lors du passage à la nouvelle position de seau, Hashmap ne place pas les éléments à la fin de la liste liée, mais à la tête, qui doit éviter la traversée de la queue. Si la compétition conditionnelle se produit, il y a un cercle vicieux. Pour le moment, vous pouvez demander à l'intervieweur pourquoi il est si étrange que vous ayez besoin d'utiliser Hashmap dans un environnement multithread? :)
Les lecteurs enthousiastes contribuent plus de questions sur Hashmap:
1. Pourquoi les classes de wrapper comme la chaîne et l'interger sont-elles adaptées comme clés? La classe wrapper comme String et Interger est la plus appropriée en tant que clé de hashmap, et String est la plus couramment utilisée. Parce que la chaîne est immuable et finale, et les méthodes equals () et hashcode () ont été réécrites. D'autres classes en wrapper ont également cette fonctionnalité. L'immuabilité est nécessaire car pour calculer HashCode (), vous devez empêcher la valeur de la valeur clé. Si la valeur clé renvoie un HashCode différent lors de la mise en place et de l'obtention, vous ne pouvez pas trouver l'objet que vous souhaitez du hashmap. L'immuabilité présente d'autres avantages tels que la sécurité des fils. Si vous pouvez garantir que le HashCode est inchangé simplement en déclarant un champ comme final, veuillez le faire. Parce que les méthodes Equals () et HashCode () sont utilisées lors de l'obtention d'objets, il est très important de réécrire correctement ces deux méthodes. Si deux objets inégaux renvoient des codes de hashcodes différents, les chances de collision seront plus petites, ce qui peut améliorer les performances de HashMap.
2. Pouvons-nous utiliser des objets personnalisés comme clés? Il s'agit d'une extension de la question précédente. Bien sûr, vous pouvez utiliser n'importe quel objet comme des clés tant qu'il suit les règles de définition des méthodes equals () et hashcode () et ne changera pas à nouveau une fois l'objet inséré dans la carte. Si cet objet personnalisé est immuable, il satisfait déjà la condition en tant que clé car elle ne peut pas être modifiée après sa création.
3. Pouvons-nous utiliser CocurrentHashmap pour remplacer le hashtable? Il s'agit d'une autre question d'interview très populaire, car de plus en plus de gens utilisent concurrenthashmap. Nous savons que le hashtable est synchronisé, mais la synchronisation concurrenthashmap est meilleure car elle verrouille une partie de la carte basée sur le niveau de synchronisation. ConcurrenthashMap peut certainement remplacer le hashtable, mais le hashtable offre une sécurité de fil plus forte. Consultez ce blog pour voir la différence entre le hachage et le concurrenthashmap.
Personnellement, j'aime beaucoup cette question parce que la profondeur et l'étendue de cette question n'impliquent pas directement des concepts différents. Jetons un coup d'œil à ce que sont les points de connaissances sur la conception de ces questions:
Résumer
Comment fonctionne Hashmap
Hashmap est basé sur le principe de hachage, et nous stockons et obtenons des objets via des méthodes put () et get (). Lorsque nous passons la paire de valeurs clés à la méthode put (), il appelle la méthode HashCode () de l'objet clé pour calculer le HashCode, puis trouve la position du godet pour stocker l'objet de valeur. Lors de l'obtention de l'objet, la paire de valeurs clés correcte se trouve via la méthode equals () de l'objet clé, puis l'objet de valeur est renvoyé. HashMap utilise des listes liées pour résoudre le problème de collision. Lorsqu'une collision se produit, l'objet sera stocké dans le nœud suivant de la liste liée. HashMap stocke des objets de paire de valeurs de clé dans chaque nœud de liste lié.
Que se passe-t-il lorsque le code de hash de deux objets clés différents est le même? Ils seront stockés dans la liste liée au même emplacement du seau. La méthode equals () de l'objet clé est utilisée pour trouver des paires de valeurs clés.
Parce que HashMap présente de nombreux avantages, j'ai utilisé HashMap comme cache dans les applications de commerce électronique. Parce que Java est beaucoup utilisé dans le domaine financier et que pour des considérations de performance, nous utilisons souvent Hashmap et ConcurrentHashMap. Vous pouvez voir plus d'articles sur Hashmap:
La différence entre hashmap et hashtable
La différence entre hashmap et hashset
Lien original: JavareVisited Traduction: importnew.com - Tang Xiaojuan Lien de traduction: http://www.importnew.com/7099.html