collision java HashMap
Je lisais sur le fonctionnement de hashmap. Je lisais le "Que se passera-t-il si deux objets différents ont le même hashcode".
Selon lui, si deux objets ont le même hashcode, les deux seront stockés dans LinkedList mais pour autant que je sache si deux hashCode alors le précédent sera remplacé par un nouveau(corrigez-moi si je me trompe).
Quelqu'un peut-il mettre plus de lumière sur la façon dont HashMap utilise l'objet comme clé en interne et ce qui se passera si deux objets ont le même hashcode et comment les deux objets seront récupérés avec get()?
4 réponses
Non, le premier n'est pas remplacé tout simplement parce que le second a le même hashCode.
Il ne sera remplacé que s'il est également égal (comme indiqué par equals). Sinon, les deux valeurs seront conservées dans la liste liée.
Lors de la récupération d'une clé, Tous les nœuds avec le même hashCode seront comparés à la clé fournie jusqu'à ce que l'un soit égal alors sa valeur sera retournée (en utilisant la méthode equals).
Si aucune clé dans la carte n'est égale, vous obtiendrez null.
Le seul problème que vous avez si de nombreux objets ont le même hashCode (ou plus précisément le même hashCode modulo la taille de l'interne Entry[] table) est que la liste liée sera toujours lue, ce qui est plus lent (et défait le but de toute table de hachage). C'est pourquoi il est important lors de la conception d'une méthode hashcode de s'assurer que les entiers générés sont bien distribués.
Laissez-moi vous expliquer le travail de hashmap.
Fonctionnement de la méthode put:
HashMap Fonctionne sur le principe du hachage, nous avons put() et get() méthode pour stocker et récupérer la forme d'objet HashMap. Lorsque nous passons une clé et une valeur à la méthode put() pour stocker sur HashMap, elle utilise la méthode Key object hashcode() pour calculer le hashcode et en appliquant un hachage sur ce hashcode, elle identifie l'emplacement du compartiment pour stocker l'objet value. Lors de la récupération, il utilise l'objet clé méthode égale pour trouver la paire de valeurs de clé correcte et l'objet de valeur de retour associé à cette clé. HashMap utilise la liste liée en cas de collision et l'objet sera stocké dans le nœud suivant de la liste liée.
HashMap stocke également les deux tuple clé + valeur dans chaque nœud de la liste liée
De Travail de la méthode get:
Lorsque nous passons l'objet clé et valeur à la méthode put() sur Java HashMap, l'implémentation de HashMap appelle la méthode hashCode sur L'objet clé et applique le hashcode retourné dans son propre fonction de hachage pour trouver un emplacement de compartiment pour stocker l'objet D'entrée, un point important à mentionner est que HashMap en Java stocke à la fois l'objet clé et la valeur en tant que carte.L'entrée dans le seau. Si plus d'un objet D'entrée trouvé dans le compartiment, il appellera ke.méthode égale à chaque nœud dans le même compartiment.
En supposant que vous suivez les règles pour Définir hashCode et equals, le scénario que vous avez décrit n'entraînera pas de perte de données. Tout au plus, les performances se dégraderont au fil du temps.
Dans le HashMap Java, ils pourraient utiliser plusieurs façons de le faire. De mon ancienne classe de Structures de données CS 201 pendant les âges sombres:
1) chaque compartiment dans la carte de hachage peut devenir la tête d'une liste liée contenant toutes les entrées ajoutées qui ont la même valeur de hachage. Une collision lors de l'ajout signifie que vous ajoutez la nouvelle entrée à la fin de la liste liée. La recherche signifie que vous devez vérifier linéairement tous ceux de n'importe quelle liste liée une fois que vous avez haché dans le seau pour cela.
2) si une collision se produit et le magasin est conceptuellement un tableau, vous pouvez simplement itérer à partir de ce point jusqu'à ce que vous trouviez un endroit vide et y ajoutiez la nouvelle entrée. Pour la recherche, cela signifie que si vous trouvez que le compartiment de hachage est occupé, vous devez comparer linéairement à partir de ce point à l'endroit vide suivant dans le tableau qui soutient la carte de hachage.
Dans les deux cas, la performance se dégrade s'il y a plusieurs entrées avec le même hachage. Dans le cas général, cela signifie qu'une fonction de hachage (utilisé pour générer le code de hachage) renvoie un petit nombre de valeurs possibles, les performances se dégradent à mesure que la carte se remplit. Le Java HashMap a profité de 50 ans de recherche sur de telles choses pour être un bon ajustement au cas général des données générales entrant dans une carte hachée.
Note @dystroy a fait un commentaire sur la règle selon laquelle vous ne pouvez pas avoir deux entrées dans la carte avec cette correspondance selon la méthode equals ().