Element ist vorhanden, aber `Set.contains (Element)` gibt false zurück

Question

Wie kann ein Element nicht in der ursprünglichen Menge enthalten sein, sondern in seiner unmodifizierten Kopie?

Das ursprüngliche Set enthält das Element nicht, während seine Kopie funktioniert. See image.

Die folgende Methode gibt true zurück, obwohl sie immer false zurückgeben sollte. Die Implementierung von c und clusters ist in beiden Fällen HashSet.

public static boolean confumbled(Set<String> c, Set<Set<String>> clusters) { 
    return (!clusters.contains(c) && new HashSet<>(clusters).contains(c)); 
} 

Debugging hat gezeigt, dass das Element im Original, aber Set.contains(element) kehrt false aus irgendeinem Grunde enthalten ist. See image.

Könnte mir bitte jemand erklären, was vor sich geht?

Answer 1

Wenn Sie ein Element in der Set ändern (in Ihrem Fall sind die Elemente Set<String>, so dass das Hinzufügen oder Entfernen eines String wird sie aus), Set.contains(element) kann fehlschlagen, um ihn zu suchen, da die hashCode des Elements sein wird anders als es war, als das Element zuerst der HashSet hinzugefügt wurde.

Wenn Sie einen neuen HashSet die Elemente der ursprünglichen enthalten, werden die Elemente auf ihrem aktuellen hashCode Basis hinzugefügt erstellen, wird so Set.contains(element) für die neue HashSet true zurück.

Sie vermeiden sollten wandelbaren Instanzen in einem HashSet (oder ihre Verwendung als Schlüssel in einem HashMap) setzen, und wenn Sie es nicht vermeiden können, stellen Sie sicher, dass Sie das Element entfernen, bevor Sie es mutieren und erneut hinzufügen danach. Andernfalls wird Ihre HashSet beschädigt.

Ein Beispiel:

Set<String> set = new HashSet<String>(); 
set.add("one"); 
set.add("two"); 
Set<Set<String>> setOfSets = new HashSet<Set<String>>(); 
setOfSets.add(set); 
boolean found = setOfSets.contains(set); // returns true 
set.add("three"); 
Set<Set<String>> newSetOfSets = new HashSet<Set<String>>(setOfSets); 
found = setOfSets.contains(set); // returns false 
found = newSetOfSets.contains(set); // returns true 

Answer 2

Der häufigste Grund dafür ist, dass das Element oder der Schlüssel nach dem Einfügen geändert wurde, was zu einer Beschädigung der zugrunde liegenden Datenstruktur führte.

Anmerkung: Wenn Sie einen Verweis auf ein Set<String> zum anderen Set<Set<String>> Sie eine Kopie der Referenz Zugabe, die zugrunde liegenden Set<String> nicht kopiert wird, und wenn Sie es, diese Veränderungen, die Auswirkungen auf verändern die Set<Set<String>> Sie es in setzen.

z.B.

Set<String> s = new HashSet<>(); 
Set<Set<String>> ss = new HashSet<>(); 
ss.add(s); 
assert ss.contains(s); 

// altering the set after adding it corrupts the HashSet 
s.add("Hi"); 
// there is a small chance it may still find it. 
assert !ss.contains(s); 

// build a correct structure by copying it. 
Set<Set<String>> ss2 = new HashSet<>(ss); 
assert ss2.contains(s); 

s.add("There"); 
// not again. 
assert !ss2.contains(s); 

Answer 3

Wenn der primäre Set war ein TreeSet (oder vielleicht einige andere NavigableSet), dann ist es möglich, wenn Ihre Objekte unvollkommen verglichen werden, damit dies geschehen kann.

Der kritische Punkt ist, dass HashSet.contains wie folgt aussieht:

public boolean contains(Object o) { 
    return map.containsKey(o); 
} 

und map ist ein HashMap und HashMap.containsKey wie folgt aussieht:

public boolean containsKey(Object key) { 
    return getNode(hash(key), key) != null; 
} 

so verwendet er die hashCode des Schlüssels für die Anwesenheit zu überprüfen.

A TreeSet verwendet jedoch eine TreeMap intern und es ist containsKey wie folgt aussieht:

final Entry<K,V> getEntry(Object key) { 
    // Offload comparator-based version for sake of performance 
    if (comparator != null) 
     return getEntryUsingComparator(key); 
    ... 

So ist es ein Comparator verwendet den Schlüssel zu finden.

So in der Zusammenfassung, wenn Ihre hashCode Methode mit Ihrer Comparator.compareTo Methode (zB compareTo kehrt 1 während hashCode gibt unterschiedliche Werte) Sie diese Art wird nicht sieht obskuren Verhalten stimmt dann.

class BadThing { 

    final int hash; 

    public BadThing(int hash) { 
     this.hash = hash; 
    } 

    @Override 
    public int hashCode() { 
     return hash; 
    } 

    @Override 
    public String toString() { 
     return "BadThing{" + "hash=" + hash + '}'; 
    } 

} 

public void test() { 
    Set<BadThing> primarySet = new TreeSet<>(new Comparator<BadThing>() { 

     @Override 
     public int compare(BadThing o1, BadThing o2) { 
      return 1; 
     } 
    }); 
    // Make the things. 
    BadThing bt1 = new BadThing(1); 
    primarySet.add(bt1); 
    BadThing bt2 = new BadThing(2); 
    primarySet.add(bt2); 
    // Make the secondary set. 
    Set<BadThing> secondarySet = new HashSet<>(primarySet); 
    // Have a poke around. 
    test(primarySet, bt1); 
    test(primarySet, bt2); 
    test(secondarySet, bt1); 
    test(secondarySet, bt2); 
} 

private void test(Set<BadThing> set, BadThing thing) { 
    System.out.println(thing + " " + (set.contains(thing) ? "is" : "NOT") + " in <" + set.getClass().getSimpleName() + ">" + set); 
} 

druckt

BadThing{hash=1} NOT in <TreeSet>[BadThing{hash=1}, BadThing{hash=2}] 
BadThing{hash=2} NOT in <TreeSet>[BadThing{hash=1}, BadThing{hash=2}] 
BadThing{hash=1} is in <HashSet>[BadThing{hash=1}, BadThing{hash=2}] 
BadThing{hash=2} is in <HashSet>[BadThing{hash=1}, BadThing{hash=2}] 

so, obwohl das Objekt im TreeSet ist es nicht, es zu finden, da der Komparator nie 0 zurückgibt. Sobald es jedoch in HashSet ist, ist alles in Ordnung, weil HashSethashCode verwendet, um es zu finden, und sie verhalten sich in einer gültigen Weise.