Consistent results Equals () but inconsistent result TreeMap.containsKey ()

Question

I have the following Node object:

  private class Node implements Comparable<Node>(){ private String guid(); ... public boolean equals(Node o){ return (this == o); } public int hashCode(){ return guid.hashCode(); } public int compareTo(Node o){ return (this.hashCode() - o.hashCode()); } ... } 

And I use it in the following TreeMap :

 TreeMap<Node, TreeSet<Edge>> nodes = new TreeMap<Node, TreeSet<Edge>>(); 

Now the tree map is used in a class called Graph to store nodes that are currently on the graph, as well as a set of their edges (from the Edge class). My problem is when I try to execute:

  public containsNode(n){ for (Node x : nodes.keySet()) { System.out.println("HASH CODE: "); System.out.print(x.hashCode() == n.hashCode()); System.out.println("EQUALS: "); System.out.print(x.equals(n)); System.out.println("CONTAINS: "); System.out.print(nodes.containsKey(n)); System.out.println("N: " + n); System.out.println("X: " + x); System.out.println("COMPARES: "); System.out.println(n.compareTo(x)); } } 

I sometimes get the following:

HASHCODE: true EQUALS: true CONTAINS: false N: foo X: foo COMPARE: 0

Does anyone have an idea what I'm doing wrong? I'm still new to all of this, so I apologize in advance if I miss something simple (I know that hashCode() doesn't matter for TreeMap , but I decided to enable it).

edit1: added information about compareTo() method.

Answer 1

There are a couple of things.

• You have not redefined Object.equals . Use @Override public boolean equals(Object obj) .
• There is a potential integer overflow error in compareTo . This is probably the cause of this particular error. This will break the sort, and therefore the search may not work.
• The compareTo method claims that two instances are equal if the hash code occurs to match (it can be a difficult mistake to catch, without checking the code).

For a problem with integer overflows see the question Why is my simple comparator broken?

Answer 2

TreeSet does not use equals () to determine equality. Instead, a comparator (or comparable) is used. To make it work correctly, you must follow consistency with the rule of equality:

"The order imposed by the comparator c on the set of elements of S is called consistent with the equalities if and only if c.compare (e1, e2) == 0 has the same boolean value as e1.equals (e2) for each e1 and e2 in S "

I think you do not follow this rule (you did not provide an implementation of the compareTo method). When the rule is not respected, the set of trees will not have normal set behavior.

See http://eyalsch.wordpress.com/2009/11/23/comparators/ for more details.

- EDIT -

Now that you have provided your implementation of compareTo, it is clear that it has a drawback. It can return 0 for 2 nodes that are not equal (and have the same hash code). As a result of this, you cannot add 2 elements with the same hash code to your TreeSet!

Answer 3

Check comparator.

containsKey() calls getEntry() , which can rely on a comparator. If it is broken, you can expect inconsistent results.