Comment le HashSet ne permet-il pas les doublons ?

Question

Je passais par le add méthode de HashSet . Il est mentionné que

Si cet ensemble contient déjà l'élément, l'appel laisse l'ensemble inchangé et renvoie false.

Mais le add enregistre en interne les valeurs dans HashMap

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

El put méthode de HashMap déclare que

Associe la valeur spécifiée à la clé spécifiée dans cette carte. Si la carte contenait précédemment un mappage pour la clé, l'ancienne valeur est remplacée.

Ainsi, si le put méthode de HashMap remplace l'ancienne valeur, comment l HashSet add laisse l'ensemble inchangé en cas de duplication d'éléments ?

Answer 1

PRESENT est juste une valeur fictive - l'ensemble ne se soucie pas vraiment de ce que c'est. Ce que l'ensemble fait Ce qui compte, c'est la carte clés . La logique est donc la suivante :

Set.add(a):
  map.put(a, PRESENT) // so far, this is just what you said
    the key "a" is in the map, so...
      keep the "a" key, but map its value to the PRESENT we just passed in
      also, return the old value (which we'll call OLD)
  look at the return value: it's OLD, != null. So return false.

Maintenant, le fait que OLD == PRESENT n'a pas d'importance -- et notez que Map.put ne change pas la clé, mais seulement la valeur associée à cette clé. Puisque la valeur de la carte clés sont ce que le Set s'intéresse vraiment, le Set est inchangé.

En fait, il y a a Les structures sous-jacentes de l'Union européenne ont été modifiées. Set -- il a remplacé un mappage de (a, OLD) con (a, PRESENT) . Mais ce n'est pas observable de l'extérieur de la Set L'implémentation de l'entreprise. (Et il se trouve que ce changement n'est même pas un vrai changement, puisque OLD == PRESENT ).

Answer 2

La réponse que vous cherchez peut-être se résume au fait que le hashmap de sauvegarde fait correspondre les éléments de l'ensemble à la valeur PRESENT qui est défini dans HashSet.java comme suit :

private static final Object PRESENT = new Object();

Dans le code source de HashMap.put nous avons :

  386     public V put(K key, V value) {
  387         if (key == null)
  388             return putForNullKey(value);
  389         int hash = hash(key.hashCode());
  390         int i = indexFor(hash, table.length);
  391         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  392             Object k;
  393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  394                 V oldValue = e.value;
  395                 e.value = value;
  396                 e.recordAccess(this);
  397                 return oldValue;
  398             }
  399         }
  400 
  401         modCount++;
  402         addEntry(hash, key, value, i);
  403         return null;
  404     }

Comme la clé en question existe déjà, nous prendrons le rendement anticipé à la ligne 397. Mais vous pourriez penser qu'une modification est apportée à la carte à la ligne 395, dans laquelle il semble que nous modifions la valeur d'une entrée de la carte. Cependant, la valeur de value es PRESENT . Mais parce que PRESENT est statique et finale, donc il n'y a qu'une seule instance de ce type ; et donc l'affectation e.value = value ne modifie pas du tout la carte, et donc le jeu, en fait !

Mise à jour :

Une fois qu'un HashSet est initialisé.
- Tous les éléments qu'il contient sont stockés sous forme de clés dans un fichier de type HashMap
- Toutes les valeurs que HashMap n'ont qu'un seul objet qui est PRESENT qui est un champ statique dans HashSet

Answer 3

Comme vous pouvez le constater, le HashSet.add ajoute l'élément au HashMap.put comme une clé et non comme une valeur. La valeur est remplacée dans le HashMap pas la clé.

Answer 4

Ver HashMap#put :

Associe la valeur spécifiée à la clé spécifiée dans cette carte. Si la carte contenait précédemment un mappage pour la clé, l'ancienne valeur est remplacée.

Il remplace la clé par le nouveau de cette façon, il n'y aura pas de doublons dans le fichier HashSet .

Answer 5

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

e est la clé, donc si e est déjà présent put ne reviendra pas null . Par conséquent, add retournera faux.

JavaDoc pour put :

la valeur précédente associée à key, ou null s'il n'y avait pas de correspondance pour key. (Un retour null peut également indiquer que la map a précédemment associé null à key).