Java TreeSet Not Working as Expected

Question

I built my own class that implements comparable (maybe not relevant) and when I try using a HashSet to store the items, the HashSet sometimes claims that the item is in the HashSet even though it is not. I thought it had to do with reference checks, but I confirmed that is does not. What is wrong?

Vertex class equals and getHashcode:

public class Vertex implements Comparable<Vertex>{

    // some code ...

    @Override
    public boolean equals(Object obj) {
        Vertex other = (Vertex) obj;
        return this.getPosition().equals(other.getPosition());
    }


    @Override
    public int hashCode() {
        int hashCode1 = Integer.parseInt(this.getPosition().getX() + "" + this.getPosition().getY());
        return hashCode1;
    }
}

Position class:

public class Position {
    private int x;
    private int y;


    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object obj) {
        Position other = (Position) obj;
        return this.x == other.x && this.y == other.y;
    }

    @Override
    public String toString() {
        //return String.format("x = %d, y = %d", x, y);
        return String.format("(%d, %d)", x, y);
    }
}

EDIT: Here is the implementation

public static void test(Vertex[][] grid) {
    TreeSet<Vertex> someSet = new TreeSet<Vertex>(){{
       add(new Vertex(new Position(3, 4), false));
        add(new Vertex(new Position(0, 5), false));
    }};
    Vertex v = new Vertex(new Position(2, 5), false);
    if (someSet.contains(v)) {
        System.out.println("error");
    } else {
        System.out.println("ok");
    }
}

The above prints error.

your hashcode is not unique for example it will return same value for two different points i.e. (2,31) & (21,3) — Sanjeev, Sep 27 '16 at 11:44
what are your keys? Are your keys implementing equals and hashcode fully? I — Prasad Kharkar, Sep 27 '16 at 11:44
You should include the code that uses the classes you posted (i.e. the code that creates the HashSet). — Eran, Sep 27 '16 at 11:46
Hashcode doesn't have to be unique, yours is kinda weak tho, try to make it better. Show us how you are using your map, and class for keys. — Shadov, Sep 27 '16 at 11:46
please share what are the keys in your HashSet and what are your contents after adding objects — Prasad Kharkar, Sep 27 '16 at 11:53
Too much code, MCVE please http://stackoverflow.com/help/mcve — Nicolas Filotto, Sep 27 '16 at 11:55
When you're adding an element e1 to a HashSet, the HashSet will first check that an element e2 that satisfies e1.equals(e2) already exists. If it does, the insert will fail. — dsp_user, Sep 27 '16 at 12:05
@dsp_user doesn't the HashSet first go to the bin with the corresponding hashcode? — ljeabmreosn, Sep 27 '16 at 12:08
While that may be true (and it is for a HashMap), it stills calls equals and inserts an element based on equals.(see this https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E)) — dsp_user, Sep 27 '16 at 12:12
Please stop using the [double-brace initialization trick](http://www.jesperdj.com/2016/07/19/dont-use-the-double-brace-initialization-trick/). — Jesper, Sep 27 '16 at 12:13
@NicolasFilotto wow I just realized my problem: My `compareTo` is using a different comparator than my `equals`. Also, TreeSet doesn't use `hashCode`, so it was comparing other aspects of the object. — ljeabmreosn, Sep 27 '16 at 12:22
so I guess you should either add `compareTo` and your answer or simply delete your question — Nicolas Filotto, Sep 27 '16 at 12:25
@NicolasFilotto yes. but I'll just add my own answer in case someone runs into the same problems as I did. — ljeabmreosn, Sep 27 '16 at 12:30
@ljeabmreosn Not directly (that's why it's a comment and not an answer), but you're using the double-brace init trick in your code: `new TreeSet() {{ ... }}`. This trick has some obvious and less obvious disadvantages. — Jesper, Sep 27 '16 at 12:34
You still did not provide the method `compareTo` of the class `Vertex`` — Nicolas Filotto, Sep 27 '16 at 12:46

score 1 · Accepted Answer · edited May 23 '17 at 11:53

1

I figured out the problem. As @NicolasFilotto pointed out, I did not mention the compareTo function. Based on a past post, TreeSet does not use hashCode but rather uses compareTo (I assume for binary searching). That is why my test cases were failing.

edited May 23 '17 at 11:53

Community

1
1

answered Sep 27 '16 at 12:28

ljeabmreosn

970
1
9
26

score 0 · Answer 2 · edited May 23 '17 at 12:24

0

With your hashcode calculation the points (1,12) and (11,2) will be treated as identical.

See best-implementation-for-hashcode-method for advice on hash codes.

edited May 23 '17 at 12:24

Community

1
1

answered Sep 27 '16 at 11:46

OldCurmudgeon

64,482
16
119
213

4

That doesn't violate the contract of hashCode - two non equal objects are allowed to have the same hashCode. Whether it's a good or bad hashCode is a different issue. – Eran Sep 27 '16 at 11:48
I understand this, but doesn't Java handle collisions? – ljeabmreosn Sep 27 '16 at 11:48
2

@ljeabmreosn Java handles collision. It would be easier to answer your question if you posted more relevant code. – Eran Sep 27 '16 at 11:49

Java TreeSet Not Working as Expected

2 Answers2