Element is present but `Set.contains(element)` returns false

Question

How can an element not be contained in the original set but in its unmodified copy?

The original set does not contain the element while its copy does. See image.

The following method returns true, although it should always return false. The implementation of c and clusters is in both cases HashSet.

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

Debugging has shown that the element is contained in the original, but Set.contains(element) returns false for some reason. See image.

Could somebody please explain to me what's going on?

Answer 1

If you change an element in the Set (in your case the elements are Set<String>, so adding or removing a String will change them), Set.contains(element) may fail to locate it, since the hashCode of the element will be different than what it was when the element was first added to the HashSet.

When you create a new HashSet containing the elements of the original one, the elements are added based on their current hashCode, so Set.contains(element) will return true for the new HashSet.

You should avoid putting mutable instances in a HashSet (or using them as keys in a HashMap), and if you can't avoid it, make sure you remove the element before you mutate it and re-add it afterwards. Otherwise your HashSet will be broken.

An example :

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

The most common reason for this is that the element or key was altered after insertion resulting in a corruption of the underlying data structure.

note: when you add a reference to a Set<String> to another Set<Set<String>> you are adding a copy of the reference, the underlyingSet<String> is not copied and if you alter it these changes which affect the Set<Set<String>> you put it into.

e.g.

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