Java HashSet contiene duplicati se l'elemento contenuto viene modificato

Diciamo di avere una class e di creare un HashSet che può memorizzare le istanze di questa class. Se si tenta di aggiungere istanze uguali, nella raccolta viene conservata una sola istanza e questo va bene.

Tuttavia, se si dispone di due istanze diverse nell'HashSet, e si prende uno e lo fanno una copia esatta dell'altro (copiando i campi), HashSet contiene 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 dal codice riportto di seguito:

 1 a 1 a 3 c Equals 

C'è un modo per forzare l'HashSet per validationre il suo contenuto in modo da rimuovere le eventuali voci duplicate create come nel precedente scenario?

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

La situazione descritta non è valida. Vedere Javadoc : "Il comportmento di un set non è specificato se il valore di un object viene modificato in modo che interessa confronti uguali mentre l'object è un elemento nell'insieme".

Per aggiungere alla risposta @ EJP, ciò che accadrà nella pratica se si mutano oggetti in un HashSet per renderli duplicati (nel senso del contratto equals / hashcode ) è che la struttura dei dati della tabella hash si romperà.

  • A seconda dei dettagli esatti della mutazione e dello stato della tabella hash, una o entrambe le istanze diventeranno invisibili per la ricerca (ad esempio, contains e altre operazioni). O sia sulla catena di hash errata o perché l'altra istanza compare prima di essa sulla catena di hash. E è difficile prevedere quale istanza sarà visibile … e se rimarrà visibile.

  • Se si esegue l'iterazione dell'insieme, entrambe le istanze saranno ancora presenti … in violazione del contratto Set .

Naturalmente, questo è molto rotto dalla prospettiva dell'applicazione.


Puoi evitare questo problema da:

  • utilizzando un tipo immutabile per i tuoi elementi impostati,
  • facendo una copia degli oggetti come li metti nell'insieme e / o estrai dal set,
  • scrivendo il codice in modo che "sa" non cambiare gli oggetti per la durata …

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


Per inciso, sarebbe davvero difficile "risolvere" questo in modo generale. Non esiste un meccanismo pervasivo in Java per conoscere … o essere notificato … che un certo elemento è cambiato. È ansible implementare un tale meccanismo su una class per class, ma deve essere codificato esplicitamente (e non sarà economico). Anche se avessi un meccanismo simile, cosa faresti? Chiaramente uno degli oggetti dovrebbe essere rimosso dall'insieme … ma quale?

Sei corretto e non credo che vi sia alcun modo per proteggere dal caso in cui si discute. Tutte le collezioni che utilizzano hashing e uguali sono soggette a questo problema. La raccolta non ha alcuna notifica che l'object è stato modificato da quando è stato aggiunto alla raccolta. Penso che la soluzione che delineate è buona.

Se sei così preoccupato per questo problema, forse dovrai ripensare le tue strutture di dati. Ad esempio, è ansible utilizzare oggetti immutabili. Con oggetti immutabili non avresti questo problema.

HashSet non è a conoscenza delle properties; dei suoi membri dopo l'aggiunta dell'object. Se questo è un problema per voi, allora si potrebbe prendere in considerazione rendere GraphEdge immutabile. Per esempio:

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

Nel caso in cui GraphEdge è immutabile, modifica di un risultato di valore nel restituire una nuova istanza, invece di modificare l'istanza esistente.

Oggetti.hashCode è destinato ad essere utilizzato per generare un hascode utilizzando oggetti di parametro. Lo si utilizza come parte del calcolo del codice.

Provare a sostituire l'implementazione di hashCode con i seguenti:

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

Dovrai fare il rilevamento univoco quando ti ripeti la tua list. Fare un nuovo HashSet potrebbe non sembrare il modo giusto per andare, 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(); } }