It is based on TreeMap
, the main different is that TreeSet
is an implementation of Set
interface and TreeMap
on Map
interface.
This kind of collection sorts your entries just when they are inserted. No need to call sort()
.
The elements are ordered using their natural ordering, or by a Comparator class provided at set creation time, depending on which constructor is used. An example of use is as follows:
Collection<String> userNames = newTreeSet<String>(Collator.getInstance()); countryNames.add("Martin"); countryNames.add("Chris"); countryNames.add("Guzman");
It is important to note that in contrats to aSet
where the ordering is defined in terms of theequals
operation (whether or not an explicit comparator is provided), theTreeSet
instance performs all element comparisons using itscompareTo
(orcompare
) method.
1. Time complexity
Provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
average / worst case | |
space | O(n) |
---|---|
contains | O(log n) |
add | O(log n) |
remove | O(log n) |
2. Advantages
- It is cleaner to implement.
- It is always sorted.
- You cannot have duplicate entries. If you need duplicates, change to a
List
. - So much information in a short declaration,
TreeSet<String>
: this is a sorted collection of Strings without duplicates, and I can be sure that this is true at every moment. - Real performance, in principle, is faster than to insert all elements in a List and next sort them from scratch. The tree insert has a time complexity of O(log(n)), leading to overall O(n*log(n)) (quick or merge sort algorithms). Comparing with other classes:
-
TreeSet
keeps things in object comparison order. The key is defined by the Comparable interface.TreeSet
ImplementsSortedSet
interface that extendsSet
interface which extends theCollection
interface. -
LinkedList
keeps things in the insertion order.LinkedList
ImplementsList
andQueue
interfaces that both of them extends theCollection
interface. -
ArrayList
uses more memory, is faster for some operations.ArrayList
implements theList
interface that extendsCollection
. -
TreeMap
, similarly, removes the need to sort by a key. The map is built in key order during the inserts and maintained in sorted order at all times.TreeMap
implementsSortedMap
that extends theMap
interface.
Highlight that the Java implementation ofTreeSet
is a quite bit slower than using anArrayList
and sort. -
3. Not synchronized
It is not synchronized. If multiple threads access a tree set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSortedSet
method. This is best done at creation time, to prevent accidental unsynchronized access to the set:
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
The iterators returned by this class's iterator
method are fail-fast: if the set is modified at any time after the iterator is created, except through the iterator's own remove
method, the iterator will throw a ConcurrentModificationException
on a best-effort basis Thus, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
The fail-fast behavior of iterators should be used only to detect bugs.Therefore, it would be wrong to write a program that depended on this exception for its correctness. This is so because it is impossible to make any hard guarantees in the presence of unsynchronized concurrent modification.
Remember that in order to write short and bug free code, we have to use the right collection for the right task.
Please, feel free to give me your comments :)