[Java] What are the pros and cons of a TreeSet

Question

Just wondering what the pros and cons of a TreeSet is, if anyone could tell me please? Thanks!

Answer 1

TreeSet:
Pros: sorted, based on a red/black tree algorithm, provides O(log(N)) complexity for operations.
Cons: value must either be Comparable or you need to provide Comparator in the constructor. Moreover, the HashSet implementation provides better performance as it provides ~O(1) complexity.

Answer 2

I guess this datastructure would be using binary tree to maintain data so that ascending order retrieval is possible. In that case, if it tries to keep the tree in balance then the remove operation would be bit costly.

Answer 3

One of the Collection classes. It lets you access the elements in your collection by key, or sequentially by key. It has considerably more overhead than ArrayList or HashMap. Use HashSet when you don’t need sequential access, just lookup by key. Use an ArrayList and use Arrays. sort if you just want the elements in order. TreeSet keeps the elements in order at all times. With ArrayList you just sort when you need to. With TreeSets the key must be embedded in the object you store in the collection. Often you might have TreeSet of Strings. All you can do then is tell if a given String is in the Set. It won’t find you an associated object he way a Treemap will. With a TreeMap the keys and the objects they are associated with are separate.

TreeSet and its brother TreeMap oddly have nothing to do with representing trees. Internally they use a tree organisation to give you an alphabetically sorted Set/Map, but you have no control over links between parents and children.

Internally TreeSet uses red-black trees. There is no need to presort the data to get a well-balanced tree. On the other hand, if the data are sorted (ascending or descending), it won’t hurt as it does with some other types of tree.

If you don’t supply a Comparator to define the ordering you want, TreeSet requires a Comparable implementation on the item class to define the natural order.

Answer 4

Cons: One pitfall with TreeSet is that it implements the Set interface in an unexpected way. If a TreeSet contains object a, then object b is considered part of the set if a.compareTo(b) returns true, even if a.equals(b) is false, so if compareTo and equals isn't implemented in a consistent way, you are in for a bad ride.

This is especially a problem when a method returns a Set, and you don't know if the implementation is a TreeSet or, for instance, a HashSet.

The lesson to learn here is, always avoid implementing compareTo and equals inconsistently. If you need to order objects in a way that is inconsistent with equals, use a Comparator.

Answer 5

TreeSet fragments memory and has additional memory overheads. You can look at the sources and calculate amount of additional memory and amount of additional objects it creates. Of course it depends on the nature of stored objects and you also can suspect me to be paranoiac about memory :) but it's better to not spend it here and there - you have GC, you have cache misses and all of these things are slooow.

Often you can use PriorityQueue instead of TreeSet. And in your typical use case it's better just to sort the array of strings.