It is based on
TreeMap, the main different is that
TreeSet is an implementation of
Set interface and
This kind of collection sorts your entries just when they are inserted. No need to call
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 a
Setwhere the ordering is defined in terms of the
equalsoperation (whether or not an explicit comparator is provided), the
TreeSetinstance performs all element comparisons using its
1. Time complexity
Provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
|average / worst case|
- It is cleaner to implement.
- It is always sorted.
- You cannot have duplicate entries. If you need duplicates, change to a
- 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:
Highlight that the Java implementation of
TreeSetkeeps things in object comparison order. The key is defined by the Comparable interface.
SortedSetinterface that extends
Setinterface which extends the
LinkedListkeeps things in the insertion order.
Queueinterfaces that both of them extends the
ArrayListuses more memory, is faster for some operations.
Listinterface that extends
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.
SortedMapthat extends the
TreeSetis a quite bit slower than using an
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 :)