matriz - numeros repetidos en un arreglo java

¿Cómo HashSet no permite duplicados?

Question

Estaba revisando el método add de HashSet . Se menciona que

Si este conjunto ya contiene el elemento, la llamada deja el conjunto sin cambios y devuelve falso.

Pero el método add guarda internamente los valores en HashMap

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

El método put de HashMap establece que

Asocia el valor especificado con la clave especificada en este mapa. Si el mapa contenía previamente una asignación para la clave, se reemplaza el valor anterior.

Entonces, si el método put de HashMap reemplaza el valor anterior, ¿cómo el método HashSet add deja el conjunto sin cambios en caso de elementos duplicados?

Answer 1

Como puede ver, el método HashSet.add agrega el elemento a HashMap.put como una clave, no como un valor. El valor se reemplaza en HashMap no en la clave.

Answer 2

Desde javadocs para HashMap.put (), "Asocia el valor especificado con la clave especificada en este mapa. Si anteriormente el mapa contenía una asignación para la clave, se reemplaza el valor anterior".

Por lo tanto, el valor del mapa será reemplazado, (que es un campo estático constante en la clase HashSet, y así se reemplaza la misma instancia), y la clave del mapa se mantiene intacta (que, de hecho, es el elemento de la colección Set)

Answer 3

La respuesta que puede estar buscando se reduce al hecho de que el hashmap de respaldo mapea los elementos del conjunto al valor PRESENT que se define en HashSet.java siguiente manera:

private static final Object PRESENT = new Object();

En el código fuente para HashMap.put tenemos:

  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     }

Debido a que la clave en cuestión ya existe, tomaremos el retorno anticipado en la línea 397. Pero podría pensar que se está realizando un cambio en el mapa en la línea 395, en la que parece que estamos cambiando el valor de una entrada en el mapa. Sin embargo, el valor del value está PRESENT . Pero como PRESET es estático y final, solo hay una instancia; ¡entonces la asignación e.value = value realidad no cambia el mapa, y por lo tanto el conjunto, en absoluto!

Answer 4

Ver HashMap#put :

Asocia el valor especificado con la clave especificada en este mapa. Si el mapa contenía previamente una asignación para la clave, se reemplaza el valor anterior.

Reemplaza la clave con el nuevo valor, de esta manera, no habrá duplicados en el HashSet .

Answer 5

PRESENT es solo un valor ficticio: al conjunto realmente no le importa qué es. Lo que importa al conjunto son las teclas del mapa. Entonces la lógica es así:

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.

Ahora, el hecho de que OLD == PRESENT no importa, y tenga en cuenta que Map.put no cambia la clave, solo el valor asignado a esa clave. Como las claves del mapa son lo que realmente le importa al Set , el Set se modifica.

De hecho, ha habido algún cambio en las estructuras subyacentes del Set : reemplazó un mapeo de (a, OLD) con (a, PRESENT) . Pero eso no es observable desde fuera de la implementación del Set . (Y sucede que ese cambio ni siquiera es un cambio real, ya que OLD == PRESENT ).

Answer 6

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

e es la clave, entonces, si e ya está presente, put no devolverá null . Por lo tanto, add devolverá falso.

JavaDoc para put :

el valor anterior asociado con la clave, o nulo si no había una asignación para la clave. (Un retorno nulo también puede indicar que el mapa asociaba previamente nulo con la clave).