HashSet not removing existing element

Question

I have a class Output which basically contains a BitSet with overides on hashCode and equals. Then I have a HashSet of Outputs and I do the following operations :

Set<Output> outputs = new HashSet<>();
Output o1 = new Output();
o1.flip(3);
Output o2 = new Output();
o2.flip(1);
o2.flip(3);
outputs.add(o1);
outputs.add(o2);

If I do a print(outputs) I get

[Output@5a1, Output@5a3]

Now if I do

o2.flip(1);

I get

[Output@5a3, Output@5a3]

which of course, is the normal behavior of a Set, since the Set can't be aware that the hashcode of an element has changed.

If I now do

outputs.remove(o1);

I get

[Output@5a3]

Perfect!

But if I do it again

outputs.remove(o1); //or outputs.remove(o2);

it returns false and I still have [Output@5a3]

And this is strange since if I do

outputs.contains(o1) -> false

which may explain the remove behavior, altough I don't understand why it returns false since if I do

    for(Output o : outputs) {
        System.out.println(o.equals(o1));
    }

It outputs true.

Any ideas why this happens?

The complete code:

class Output {
    BitSet values;

    public Output() {
        values = new BitSet(4);
    }

    public void flip(int index) {
        values.flip(index);
    }

    public int hashCode() {
        int hash = 3;
        hash = 67 * hash + Objects.hashCode(this.values);
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Output)) {
            return false;
        }
        Output other = (Output) obj;
        return this.values.equals(other.values);
    }
}
public class Main {
    public static void main(String args[]) {
        Set<Output> outputs = new HashSet<>();
        Output o1 = new Output();
        o1.flip(3);
        Output o2 = new Output();
        o2.flip(1);
        o2.flip(3);
        outputs.add(o1);
        outputs.add(o2);
        System.out.println(outputs);
        o2.flip(1);
        System.out.println(outputs);
        outputs.remove(o1);
        System.out.println(outputs);
        outputs.remove(o1);
        System.out.println(outputs);
        for (Output o : outputs) {
            System.out.println(o.equals(o1));
        }
    }
}

Output:

[Output@5a1, Output@5a3]
[Output@5a3, Output@5a3]
[Output@5a3]
[Output@5a3]
true

Answer 1

When you mutate an element of a HashSet (or a key in a HashMap), the hashCode of that element may change (and in your example, the hashCode depends on the hashCode of the BitSet member, which you changed).

However, the HashSet is not aware of that change, and therefore doesn't move the element to the bin corresponding with the new hashCode.

Therefore, when you search for that element, the search is performed using the new hashCode (HashSet search always begins with the hashCode - only after finding the bin that contains all the elements having that hashCode, equals() is used to find the right element), and it fails, since the element is still located in the bin matching the original hashCode.

That's the reason it is a bad idea to mutate elements of a HashSet.