A Legacy Notes Developer's journey into madness.

Learning XPages

TreeSet.add() fails to add custom objects

Devin Olson  July 3 2013 05:10:44 PM
Here is a quick tip.  

In Java, when you construct your own objects which implement Comparable, and use a TreeSet to contain them, you need to watch out for .equals() vs. .compareTo().  

Here is a really stupid class

public class MyClass implements Comparable {
        private final String Key;

        public MyClass(String key) {
                Key = key;
        }

        public String getKey() {
                return this.Key;
        }

        public int compareTo(MyClass arg0) {
                return 0;
        }

        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((Key == null) ? 0 : Key.hashCode());
                return result;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (!(obj instanceof MyClass))
                        return false;
                MyClass other = (MyClass) obj;
                if (Key == null) {
                        if (other.Key != null)
                                return false;
                } else if (!Key.equals(other.Key))
                        return false;
                return true;
        }
}



And here is some code to create several instances of MyClass and throw them into a TreeSet:

public void loadTreeSet() {
        MyClass thing1 = new MyClass("1");
        MyClass thing2 = new MyClass("2");
        MyClass thing3 = new MyClass("3");

        TreeSet treeset = new TreeSet();
        treeset.add(thing1);
        treeset.add(thing2);
        treeset.add(thing3);

        System.out.println(treeset.size());
}


Anybody care to guess what what prints out?  The answer is 1.  The other MyClass objects NEVER get added to the TreeSet.  The reason for this has to do with how the TreeSet implements it's own internal map.  Java Set objects which rely upon Comparable interface of their elements do not check for an .equals() method of the element.  They only check the compareTo() method.  Because MyClass always returns a zero (which is interpreted as EQUIVALENT for ordering), the Set cannot determine where to place subsequent entries, and so simply does not add them.  

The add() method returns false when adding thing2 and thing3.  

What is the lesson learned here?   When writing your own .compareTo() methods, only return a zero if the elements are TRULY equal to one another.  If for all other intents and purposes two instances of your object would sort to exactly the same position you MUST NOT return a zero if you want them to both be included in any Comparable set.  An easy hack is to (after all your other comparison logic still shows the objects as equivalent) simply compare their hashcodes.  (You HAVE properly implemented .hashCode() and .equals() RIGHT?)  

Hope this helps!
-Devin.