Comparaison de plusieurs façons de juger les mêmes éléments de Hashmap, Hashset, Treemap et Treeset à Java
1.1 Hashmap
Voyons d'abord comment les éléments sont stockés dans Hashmap. Chaque élément stocké dans la carte est une paire de valeurs de clé comme la valeur clé, et est ajouté via la méthode de put. De plus, la même clé n'aura qu'une valeur qui lui est associée dans la carte. La méthode de put est définie dans la carte comme suit.
V put (clé k, valeur v);
Il est utilisé pour stocker une paire de valeurs de clé comme la valeur clé. La valeur de retour est l'ancienne valeur stockée dans la carte par la clé. S'il n'existe pas auparavant, il reviendra null. C'est ainsi que la méthode de put hashmap est implémentée.
public v put (k key, v valeur) {if (key == null) return putFornullKey (value); int hash = hash (key); int i = indexfor (hash, table.length); pour (entrée <k, v> e = table [i]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.Value; e.Value = valeur; e.recordAccess (this); Retour OldValue; }} modCount ++; Addentry (hachage, clé, valeur, i); retourner null; }À partir de ce qui précède, nous pouvons voir que lors de l'ajout de la combinaison de valeurs de clé correspondante, si la clé correspondante existe déjà, la valeur correspondante sera modifiée directement et l'ancienne valeur sera renvoyée. Lorsque vous jugez si la clé existe, le code de hash de la clé est d'abord comparé, puis le code de hash de la clé est comparé aux égaux ou égaux. Nous ne pourrons peut-être pas le voir ici. À partir du code ci-dessus, nous comparons le code de hash de Map.Entry et le code de hash de Key. En fait, nous pouvons voir que MAP.Entry HashCode est en fait le code de hash de sa clé. Si la clé correspondante n'existe pas à l'origine, Addentry sera appelé pour ajouter la valeur de clé correspondante à la carte. Le hachage de paramètre passé par Addentry est le code de hash-code correspondant à la clé. Ensuite, jetons un coup d'œil à la définition de la méthode de l'addentry.
void Addentry (int hash, k key, v valeur, int bucketIndex) {if ((size> = threshold) && (null! = table [bucketIndex])) {redimensit (2 * table.length); hash = (null! = key)? hash (clé): 0; BucketIndex = indexFor (hash, table.length); } createEntry (hash, key, valeur, bucketIndex); } void CreateEntry (int hash, k key, Vale V, int bucketIndex) {entrée <k, v> e = table [bucketIndex]; table [bucketIndex] = nouvelle entrée <> (hachage, clé, valeur, e); taille ++; }Le cœur d'Addentry est d'appeler CreateEntry pour créer un objet MAP.Entry représentant la valeur de clé correspondante et le stocker. De toute évidence, le tableau ci-dessus est un tableau de map.Entry. Map.Entry utilise un hachage de propriété pour enregistrer le code de hash de la clé correspondante. Jetons un coup d'œil au constructeur de Map.Entry appelé ci-dessus.
Entrée (int h, k k, v v, entrée <k, v> n) {value = v; suivant = n; clé = k; hash = h; }De toute évidence, il enregistre le code de hash correspondant à la clé, à la valeur et à la clé correspondantes.
Après avoir compris comment HashMap stocke les éléments, il est plus facile de voir comment HashMap stocke les éléments. Il existe deux méthodes principales dans Hashmap pour déterminer si les éléments sont les mêmes. L'un consiste à déterminer si la clé est la même, et l'autre est de déterminer si la valeur est la même. En fait, lors de l'introduction de la façon dont HashMap stocke les éléments, nous avons introduit comment HashMap détermine si la clé d'élément est la même. Autrement dit, tout d'abord, le code de hash est le même, et deuxièmement, les clés sont égales ou égales. La détermination de la question de savoir si la clé est la même dans la carte est effectuée via la méthode CONTAINSKEY (), et son implémentation dans HashMap est la suivante.
public boolean contientKey (clé d'objet) {return getEntry (key)! = null; } Entrée finale <k, v> GetEntry (clé d'objet) {int hash = (key == null)? 0: Hash (clé); pour (entrée <k, v> e = table [indexfor (hash, table.length)]; e! = null; e = e.next) {objet k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e; } return null; }Il est évident qu'il détermine d'abord si le code de hash de la clé est le même, puis détermine si la clé est égale ou égale.
La valeur utilisée dans MAP est jugée par la méthode CONTAINSVALUE, et son implémentation dans Hashmap est la suivante.
public boolean contientValue (valeur objet) {if (value == null) return contientNullValue (); Entrée [] tab = table; for (int i = 0; i <tab.length; i ++) pour (entrée e = tab [i]; e! = null; e = e.next) if (value.equals (e.value)) return true; retourne false; }De toute évidence, la valeur de la forme non nul est jugée par les égaux de la valeur, et la forme nul est aussi longue qu'elle est égale, c'est-à-dire que la valeur dans l'élément enregistré est nul.
1.2 Hashset
Après avoir su comment HashMap stocke les éléments et détermine si les éléments sont les mêmes, il est plus facile de voir comment HashSet détermine si les éléments sont les mêmes.
Les éléments du hashset sont en fait enregistrés via HashMap. Chaque objet HashSet détient une référence à l'objet HashMAP correspondant. Lors de l'ajout et de la suppression d'éléments au hashset, il est effectué via le hashmap qu'il contient. Lors de l'enregistrement d'un élément, il enregistre l'élément correspondant comme la clé du hashmap détenu. La valeur correspondante est un objet constant, donc lors de l'enregistrement, il utilise la logique de déterminer si les éléments sont les mêmes. Lors de la détermination de la question de savoir si un élément est inclus, il appelle également la méthode CONTAINSKEY du hashmap détenu pour porter des jugements.
Le booléen public contient (objet o) {returnmap.containsKey (o); }Les amis intéressés peuvent consulter le code source de Hashset.
1.3 Treemap
Les éléments stockés dans Treemap sont commandés et triés selon la clé. Treemap a deux façons de trier les éléments stockés. L'un consiste à trier le comparateur qu'il tient, et l'autre est de trier la clé qui implémente l'interface comparable. La première méthode est préférée. Lorsque le comparateur tenu (la valeur par défaut est nul) est nul, la deuxième méthode est utilisée. Treemap a plusieurs constructeurs, à travers lesquels le comparateur qu'il détient peut être initialisé. Voyons d'abord comment Treemap sauve des éléments. La méthode de put est implémentée comme suit.
public v put (k key, v valeur) {entrée <k, v> t = root; if (t == null) {compare (key, key); // type (et possible null) vérifier root = new entrée <> (clé, valeur, null); taille = 1; modCount ++; retourner null; } int cmp; Entrée <k, v> parent; // Comparateur divisé et comparateur de chemins comparables <? super k> cpr = comparateur; if (cpr! = null) {do {parent = t; CMP = cpr .......... if (cmp <0) t = t.left; elseif (cmp> 0) t = t.Right; else return t.setValue (valeur); } while (t! = null); } else {if (key == null) thrownew nullpointerException (); Comparable <? super k> k = (comparable <? super k>) touche; faire {parent = t; cmp = k ..compareto (t.key); if (cmp <0) t = t.left; elseif (cmp> 0) t = t.Right; else return t.setValue (valeur); } while (t! = null); } Entrée <k, v> e = nouvelle entrée <> (clé, valeur, parent); if (cmp <0) parent.left = e; else Parent.Right = e; FIXAFTERInSertion (E); taille ++; modCount ++; retourner null; }À partir de l'implémentation ci-dessus, nous pouvons voir que le premier élément sera stocké directement. Les éléments suivants sont divisés en deux situations, l'une est le cas où le comparateur tenu n'est pas vide, et l'autre est le cas où le comparateur tenu est vide. Lorsque le comparateur n'est pas vide, le comparateur déterminera l'emplacement de l'élément stocké. Une chose importante est que lorsque le résultat de la comparaison de la clé de l'élément existant avec la clé de l'élément stocké actuel est 0, il sera considéré que la clé de l'élément actuellement stocké existe déjà dans la carte d'origine, puis la valeur correspondant à la clé d'origine est modifiée en nouvelle valeur, puis l'ancienne valeur est renvoyée directement. Lorsque le comparateur tenu est vide, l'emplacement de l'élément sera déterminé par la méthode de comparaison de la clé qui implémente l'interface comparable. Une chose similaire à l'utilisation du comparateur est que lorsque la clé d'origine est comparée à la touche nouvellement stockée est 0, il sera considéré que la clé nouvellement stockée existe déjà dans la carte d'origine, et la valeur de la clé d'origine correspondante sera modifiée directement, et la paire de valeurs de clé ne sera plus stockée. En fait, la principale logique d'implémentation de la méthode CONTAINSKEY qui détermine si l'élément existe est similaire, et l'implémentation spécifique est la suivante.
public boolean contientKey (clé d'objet) {return getEntry (key)! = null; } Entrée finale <K, V> GetEntry (clé d'objet) {// Version basée sur le comparateur de déchargement pour des biens de performances if (Comparator! = NULL) return GetEntryusingComparator (key); if (key == null) thrownew nullpointerException (); Comparable <? super k> k = (comparable <? super k>) touche; Entrée <k, v> p = root; while (p! = null) {int cmp = k.compareto (p.key); if (cmp <0) p = p.left; elseif (cmp> 0) p = p.Right; else return p; } return null; }Étant donné que la logique de Treemap pour déterminer si un élément existe consiste à déterminer si le résultat après comparer le comparateur ou comparable est 0, nous devons être particulièrement prudents lorsque vous utilisez Treemap pour implémenter une logique similaire aux égaux.
La logique de Treemap ContintainValue est de déterminer si la valeur correspondante est égale? Similaire à Hashmap. Les amis intéressés peuvent vérifier le code source de Treemap.
1,4 arbre
Treeset est également une implémentation de Set. Les éléments stockés ne sont pas répétés et sont commandés. Par défaut, les éléments stockés doivent implémenter l'interface comparable, car par défaut, les éléments seront comparés en tant qu'objets comparables. Treeset peut également être utilisé pour comparer les éléments qui y sont stockés via le comparateur. Ceci peut être réalisé en passant dans un objet de comparateur ou un Treemap tenant un objet de comparateur lors de la construction d'un arbre. La mise en œuvre de Treeset est similaire à celle de Hashset. Il détient également une référence à une carte, mais il ne fait pas référence à un hashmap, mais Treemap. L'ajout et la suppression des éléments dans Treeset sont tous mis en œuvre par le Treemap qu'ils détiennent. Par conséquent, similaire à Hashset, la façon de déterminer si les éléments dans Treeset sont les mêmes est cohérent avec TreeMap, et est également déterminé par comparateur ou comparable, plutôt que la méthode égale traditionnelle. Les amis intéressés peuvent vérifier le code source de Treeset.
Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!