Consistent Equals() results, but inconsistent Tree

Question

I have the following object Node:

    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 currently in the graph, along with a set of their edges (from the class Edge). 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 COMPARES: 0

Anyone have an idea as to what I'm doing wrong? I'm still new to all this, so I apologize in advance if I'm overlooking something simple (I know hashCode() doesn't really matter for TreeMap, but I figured I'd include it).

edit1: added compareTo() method information.

Answer 1

There are a couple of things wrong here.

• You have not overriden 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. It will upset the sorting, and hence the search may well not succeed.
• The compareTo method claims two instances are equal if the hash code happens to match (could be a difficult error to catch, without code review).

For integer overflow issue, see question Why is my simple comparator broken?

Answer 2

TreeSet does not use equals() to determine equality. It uses the Comparator (or Comparable) instead. In order to make it work right, you must follow the consistency with equals rule:

"The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S".

I guess you are not following this rule (you didn't provide the implementation of the compareTo method). When the rule is not followed, the tree set will not have a normal behavior of a Set.

For details see http://eyalsch.wordpress.com/2009/11/23/comparators/.

--EDIT--

Now that you provided your compareTo implementation, is is clear that it has a flaw. It may return 0 for 2 nodes which are not equal (and have the same hashcode). As a result of this, you can't add 2 items with the same hash code into your TreeSet!

Answer 3

Check your comparator.

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