Java HashSet contiene duplicati se l'elemento contenuto viene modificato

Question

Supponiamo di avere una classe e di creare un HashSet che può memorizzare questa istanza di questa classe. Se si tenta di aggiungere istanze uguali, nella raccolta viene mantenuta una sola istanza e ciò va bene.

Tuttavia se si dispone di due istanze diverse nell'HashSet e ne si prende una e ne si fa una copia esatta dell'altro (copiando i campi), HashSet conterrà quindi due istanze duplicate.

Ecco il codice che dimostra questo:

public static void main(String[] args) 
    { 
     HashSet<GraphEdge> set = new HashSet<>(); 
     GraphEdge edge1 = new GraphEdge(1, "a"); 
     GraphEdge edge2 = new GraphEdge(2, "b"); 
     GraphEdge edge3 = new GraphEdge(3, "c"); 

     set.add(edge1); 
     set.add(edge2); 
     set.add(edge3); 

     edge2.setId(1); 
     edge2.setName("a"); 

     for(GraphEdge edge: set) 
     { 
      System.out.println(edge.toString()); 
     } 

     if(edge2.equals(edge1)) 
     { 
      System.out.println("Equals"); 
     } 
     else 
     { 
      System.out.println("Not Equals"); 
     } 
    } 

    public class GraphEdge 
    { 
     private int id; 
     private String name; 

     //Constructor ... 

     //Getters & Setters... 

     public int hashCode() 
     { 
     int hash = 7; 
     hash = 47 * hash + this.id; 
     hash = 47 * hash + Objects.hashCode(this.name); 
     return hash;  
     } 

     public boolean equals(Object o) 
     { 
      if(o == this) 
      { 
       return true; 
      } 

      if(o instanceof GraphEdge) 
      { 
       GraphEdge anotherGraphEdge = (GraphEdge) o; 
       if(anotherGraphEdge.getId() == this.id && anotherGraphEdge.getName().equals(this.name)) 
       { 
        return true; 
       } 
      } 

       return false; 
     } 
    } 

L'output del codice precedente:

1 a 
1 a 
3 c 
Equals 

C'è un modo per forzare il HashSet per convalidare il suo contenuto in modo che eventuali voci duplicate creato come nello scenario precedente viene rimosso?

Una possibile soluzione potrebbe essere quella di creare un nuovo hashset e copiare il contenuto da un hashset a un altro in modo che il nuovo hashset non contenga duplicati, tuttavia non mi piace questa soluzione.

Answer 1

La situazione che descrivi non è valido. Vedere il Javadoc: "Il comportamento di un set non viene specificato se il valore di un oggetto viene modificato in un modo che influisce su confronti uguali mentre l'oggetto è un elemento nel set."

Answer 2

Objects.hashCode è pensato per essere utilizzato per generare un hascode utilizzando oggetti parametro. Lo stai utilizzando come parte del calcolo hascode.

provare a sostituire l'implementazione del hashCode con il seguente:

public int hashCode() 
{ 
    return Objects.hashCode(this.id, this.name); 
} 

Answer 3

Sei corretto e non penso che ci sia un modo per proteggersi dal caso che discuti. Tutte le raccolte che utilizzano hashing e uguali sono soggette a questo problema. La raccolta non ha notificato che l'oggetto è cambiato da quando è stato aggiunto alla raccolta. Penso che la soluzione che hai delineato sia buona.

Se sei così interessato a questo problema, forse hai bisogno di ripensare le tue strutture dati. Potresti usare oggetti immutabili, per esempio. Con oggetti immutabili non avresti questo problema.

Answer 4

HashSet non è a conoscenza delle proprietà dei suoi membri che cambiano dopo che l'oggetto è stato aggiunto. Se questo è un problema per te, allora potresti prendere in considerazione l'ipotesi di rendere immutabile GraphEdge. Ad esempio:

GraphEdge edge4 = edge2.changeName("new_name"); 

Nel caso in cui GraphEdge è immutabile, cambiando di conseguenza valore restituendo una nuova istanza piuttosto cambiando l'istanza esistente.

Answer 5

È necessario eseguire il rilevamento univoco al momento della iterazione dell'elenco. Fare un nuovo HashSet potrebbe non sembrare la strada giusta da percorrere, ma perché non provare questo ... e forse non utilizzare un HashSet per cominciare ...

public class TestIterator { 
    public static void main(String[] args) { 
     List<String> list = new ArrayList<String>(); 

     list.add("1"); 
     list.add("1"); 
     list.add("2"); 
     list.add("3"); 

     for (String s : new UniqueIterator<String>(list)) { 
      System.out.println(s); 
     } 
    } 
} 

public class UniqueIterator<T> implements Iterable<T> { 
    private Set<T> hashSet = new HashSet<T>(); 

    public UniqueIterator(Iterable<T> iterable) { 
     for (T t : iterable) { 
      hashSet.add(t); 
     } 
    } 

    public Iterator<T> iterator() { 
     return hashSet.iterator(); 
    } 
} 

Answer 6

Per aggiungere alla risposta di @ EJP, cosa accadrà in pratica se si muta gli oggetti in un HashSet per renderli duplicati (nel senso del contratto equals/hashcode) è che la struttura dei dati della tabella hash si interromperà.

• A seconda dei dettagli esatti della mutazione, e lo stato della tabella hash, uno o entrambi i casi diventa invisibile per ricerca (ad esempio contains e altre operazioni). O si trova sulla catena hash sbagliata o perché l'altra istanza appare prima nella catena hash. Ed è difficile prevedere quale istanza sarà visibile ... e se rimarrà visibile.

• Se si itera l'insieme, entrambe le istanze saranno ancora presenti ... in violazione del contratto Set.

Naturalmente, questo è molto rotto dal punto di vista dell'applicazione.

---

È possibile evitare questo problema sia:

• utilizzando un tipo immutabile, per i vostri elementi del set,
• fare una copia degli oggetti come li metti nel set e/o tirare fuori del set,
• scrivere il codice in modo che "sa" di non modificare gli oggetti per la durata ...

Dal punto di vista della correttezza e della robustezza, la prima opzione è chiaramente la migliore.

---

Per inciso, sarebbe davvero difficile "risolvere" questo in modo generale. Non c'è alcun meccanismo pervasivo in Java per sapere ... o essere avvisati ... che qualche elemento è cambiato. È possibile implementare un tale meccanismo su una classe per classe, ma deve essere codificato esplicitamente (e non sarà economico). Anche se tu avessi un tale meccanismo, cosa faresti? Chiaramente uno degli oggetti dovrebbe ora essere rimosso dal set ... ma quale?