The Comparable and Comparator Interfaces

Suppose a program reads a long text and must report every distinct word in alphabetical order, with each word appearing exactly once. A list can do this, but the programmer must do all the bookkeeping. Before storing each new word, the program must check it against everything already stored, and after every insertion it must keep the whole collection sorted.

Java offers a more direct tool for this job. The Java library includes two classes, TreeSet and HashSet, that are built to hold collections where repetition is not allowed. They differ sharply in what else they guarantee about the elements they hold. Before comparing them, it helps to understand the idea they share, because that idea determines what a set does when you try to put the same thing in twice. This article covers that shared rule first, then the ordering guarantee of TreeSet and the comparison interfaces it depends on, and finally the different trade-offs of HashSet.

The rule is enforced by the set itself, not by the code that uses it. A set implements all the methods of the general Collection interface, so it offers the familiar operations, but each one is carried out in a way that guarantees no element appears twice. The concrete consequence is easy to state: if a set is asked to add an object that is already one of its elements, the call has no effect. The set does not grow, does not store a second copy, and does not signal an error. Duplicate insertion is simply absorbed.

The diagram shows the set before and after the second add(3). Nothing in the set changes: the element is still 3 and the size is still 1. The set rejects the duplicate silently, which is the behavior the defining rule requires.

Java provides two classes that implement the Set interface: java.util.TreeSet and java.util.HashSet. Both obey the no-duplicates rule. What separates them is the extra promise each one makes about order and about how the elements are organized internally. Those promises are where the real design decision lies.

A TreeSet has one property beyond being a set: its elements are arranged into ascending sorted order. An Iterator, or a for-each loop, running over a TreeSet always visits the elements in ascending order. Programmers never need to request sorting. The order is a standing property of the collection, maintained at every insertion.

How can a set keep its elements in order while still finding and inserting them quickly? Internally, a TreeSet stores its elements in something similar to a binary sort tree. In a binary sort tree, each node holds one element, and the elements in its left subtree are smaller while those in its right subtree are larger. The source adds one important qualification: the tree is balanced, so the left and right subtrees of any node are at about the same size.

The figure is an illustration of the balanced shape described by the source. Notice that the root sits roughly in the middle of the values, so searching from the root cuts the remaining candidates in a similar way on either side. Every new element is placed by walking down this tree and comparing it with the nodes it meets, which is why the set must be able to compare its elements.

The payoff of balance is a guarantee on running time. The source states that inserting, deleting, and searching are all efficient in a TreeSet, with worst-case run time Θ(log(n)), where n is the number of items in the set. The logarithm grows slowly, so doubling the number of elements adds only a small, fixed amount of work per operation rather than doubling it. This is why a TreeSet can remain efficient as it grows while still delivering its elements in sorted order.

A sorted order cannot be produced unless the set can decide which of two elements comes first. For that reason, a TreeSet cannot hold arbitrary objects with no further preparation. The set needs an ordering rule, and the source names two routes for supplying one.

Follow one insertion through the tree from the previous figure. The set already holds 1, 2, 3, 4, 5, 6, and 7. Now the program adds 5 again. The set does not know this is a duplicate in advance. It must walk down the tree and use compareTo() at each node it meets, and each result tells it whether to move left or right.

The sequence diagram shows the three comparisons in order. Comparing 5 with 4 gives a positive result, so the search continues to the right. Comparing 5 with 6 gives a negative result, so the search moves left. Comparing 5 with the node holding 5 gives zero, which means the comparison considers the two objects the same. The set therefore absorbs the insertion and does not change.

A detail here surprises many learners. A TreeSet does not use the equals() method to decide whether two objects are the same. It uses compareTo() or compare() instead. Two objects that are not equal can still be treated as the same by a comparison, if the comparison rule considers them equal for ordering purposes. The source notes that this is less likely with a properly defined compareTo(), but it remains possible.

Consider a comparator for mailing addresses that compares only zip codes. Two different addresses in the same zip code compare as equal. Since the TreeSet trusts the comparison, only one of those addresses can be stored. The source describes this outcome as clearly not right. The lesson is that the programmer must make sure compareTo() or compare() is defined in a reasonable way for the objects placed in a TreeSet, so that the comparison matches the programmer's idea of what counts as the same element.

A HashSet takes a different route. It stores its elements in a hash table, a data structure that the source sets aside for discussion in the following section. What matters at this point is the behavior it produces. The operations of finding, adding, and removing elements are implemented very efficiently in hash tables, more so than in a TreeSet. A programmer who needs fast membership checks and does not care about order will usually find a HashSet the better fit.

The price of that speed is order. The elements of a HashSet are not stored in any particular order. Because the set never arranges its contents, it has no need to compare elements at all, so the elements do not need to implement the Comparable interface. They do, however, need to define a proper hash code, which the source explains in the next section. The lack of a defined order also means that you should not rely on any ordering when you loop through a HashSet.

The choice between the two sets depends on what the task needs. The table below compares the properties the source emphasizes. Both classes refuse duplicates, so the decision usually turns on order and on the cost of operations.

A useful rule of thumb follows from the table. If the program must print or process the elements in sorted order, choose a TreeSet and make sure its elements have a sound comparison. If the program only needs to ask whether an element is present and never needs ordered output, a HashSet is usually the better choice because of its efficient operations and its freedom from comparison requirements.