element jest obecny, ale `Set.contains (element)` zwraca false

Question

Jak elementem nie być zawarte w pierwotnym planie, ale w jego niezmodyfikowanej kopią?

Oryginalny zestaw nie zawiera elementu podczas jego kopiowania. See image.

Następująca metoda zwraca true, chociaż powinna zawsze powrócić false. Implementacja c i clusters jest w obu przypadkach HashSet.

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

debugowanie wykazały, że element jest zawarte w oryginale, ale Set.contains(element) powraca false z jakiegoś powodu. See image.

Czy ktoś mógłby mi wyjaśnić, co się dzieje?

Answer 1

Jeśli zmienisz element w Set (w przypadku, gdy elementy są Set<String>, więc dodanie lub usunięcie String będzie je zmienić), Set.contains(element) może zawieść go zlokalizować, ponieważ hashCode elementu będzie różni się od tego, co było, gdy element został po raz pierwszy dodany do HashSet.

Podczas tworzenia nowego HashSet zawierający elementy oryginalne elementy zostały dodane na podstawie ich aktualnej hashCode, więc Set.contains(element) zwróci true dla nowego HashSet.

Należy unikać umieszczania zmienne instancji w HashSet (lub używając ich jako klucze w HashMap), a jeśli nie można tego uniknąć, upewnij się usunąć element przed zmutować go i ponownie dodać go później. W przeciwnym razie twój HashSet zostanie zepsuty.

Przykład:

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

Najczęstszym tego powodem jest to, że element lub klucz został zmieniony po wstawieniu, co spowodowało uszkodzenie podstawowej struktury danych.

uwaga: jeśli dodać odwołanie do Set<String> do drugiego Set<Set<String>> dodajesz kopię odniesienia, podstawowe Set<String> nie jest kopiowany, a jeśli zmiany to te zmiany, które wpływają na Set<Set<String>> można umieścić go na.

np.

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

Jeśli podstawowy Set był TreeSet (a może jakaś inna NavigableSet) to jest możliwe, jeśli obiekty są niedoskonale porównywane, aby tak się stało.

Krytycznym punktem jest to, że HashSet.contains wygląda następująco:

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

i map jest HashMap i HashMap.containsKey wygląda następująco:

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

więc używa hashCode klucza do sprawdzenia obecności.

TreeSet jednak używa TreeMap wewnętrznie i to containsKey wygląda następująco:

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

Więc używa Comparator znaleźć klucz.

Tak, w skrócie, jeśli metoda hashCode nie zgadza się z metodą Comparator.compareTo (słownie compareTo powraca 1 podczas gdy hashCode zwraca różne wartości) wtedy zobaczysz tego rodzaju niejasnych zachowań.

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); 
} 

drukuje

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}] 

więc mimo że obiekt jest w TreeSet nie jest znalezienie go, ponieważ nigdy nie zwraca 0 komparator. Jednakże, gdy już jest w HashSet wszystko jest w porządku, ponieważ HashSet używa hashCode, aby go znaleźć i zachowują się w prawidłowy sposób.