Why is set.contains not using overriden equals() method?

Question

I have a class like this:

class Vertex {
    char v;
    char w;
    int cost;

    public Vertex(char v, char w, int cost){
        this.v = v;
        this.w = w;
        this.cost = cost;
    }

    @Override
    public String toString(){
        return "["+v+" "+w+" "+cost+"]";
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Vertex vertex = (Vertex) o;
        return (v == vertex.v && w == vertex.w) || (w == vertex.v && v == vertex.w);
    }

    @Override
    public int hashCode() {
        return Objects.hash(v, w);
    }
}

I am trying to have the equals() return true when two vertexes are equal or opposite equal. Meaning it should return true if there is a vertex (v,w) and (w,v).

My equals() is symmetric and reflexive as it should be, but still the set.contains() return false for (v,w) and (w,v) case.

I would appreciate any help.

Answer 1

Your class violates the general contract for hashCode(), not equals(). Set.contains() uses hashCode() to achieve O(1) time.

The general contract for hashCode() states that equal objects must have equal hash codes. However, in your case, [v=1, w=2] and [v=2, w=1] are considered equal, but they have different hash codes. You'd be calling Objects.hash(1, 2) and Objects.hash(2, 1) respectively.

You should change your hash code implementation to make it independent of the order of v and w. One way to do this is to hash the smaller one first:

return Objects.hash(Math.min(v, w), Math.max(v, w));