This is an Introduction to Java TreeSets. Lean the basic features a TreeSet provides. Also, learn with real life examples, when and how to use TreeSet.
What is TreeSet ?
TreeSet is a type of collection in Java. It implements NavigableSet interface. The NavigableSet extends SortedSet. And, the SortedSet extends Set. Additionally, the TreeSet extends AbstractSet, which in turn extends AbstractCollection. Set is a unique collection of data in Java and so the TreeSet is.
TreeSets are similar to a HashSets. However the TreeSets are sorted. The default sorting order is the natural order of the elements. However, you can customize this by passing a Comparator,
There is no difference the way, you store or remove elements from a TreeSet and HashSet. However, when you iterate the collection, TreeSet iterator traverse the result set in sorted order.
ThreeSets do not allow duplicates, and if you try to insert a duplicate element the TreeSet will ignore it. Similarly, TreeSet do allow null elements. However, you can add only one null in a TreeSet.
Features of TreeSet
Listing down some of the top features of TreeSet:
- They store unique data. Hence they decline duplicate insertions.
- TreeSet sorts the elements based on their natual order.
- However, you can provide a Comparator instance in order to customize sorting.
- TreeSet allows only one null element.
- The operations like add, contains, and remove are constant in time.
- TreeSets are not synchronized by default and you have to synchronize if multiple threads are writing data to the set.
- If you modify a collection once an Iterator is open, it will throw
- Because of the iterators fail-fast behavior, the TreeSets are thread-safe.
- You cannot retrieve a specific element out of TreeSet (like with an Index or Key). You have to iterate over through the elements until you reach to the desired element.
Examples of TreeSet
Firstly, we will create an instance of TreeSet, before adding random strings. Notice that, we are inserting the string “one” two times.
Set<String> treeSet = new TreeSet<>(); treeSet.add("four"); treeSet.add("one"); treeSet.add("two"); treeSet.add("three"); treeSet.add("one");
Let’s print all the elements from the TreeSet.
treeSet.forEach(System.out::println); // Output // four // one // three // two
- The duplicate entry for “one” is ignored by the set.
- All results are sorted in alphabetical order by default.
Customize Order with TreeSets
This is pretty easy. You can use
Collections.reverseOrder() while constructing the TreeSet. This method injects an inbuilt Comparator instance that changes the sorting direction.
Set<String> treeSet = new TreeSet<>(Collections.reverseOrder()); treeSet.add("four"); treeSet.add("one"); treeSet.add("two"); treeSet.add("three"); treeSet.add("one"); treeSet.forEach(System.out::println); ---------- // Output // two // three // one // four
Put Custom Objects in TreeSet
All the Java’s default data types have a natural sorting order. The TreeSet knows it. For example, strings will be sorted in alphabetical order and numbers will be sorted in numerical order. In this section, let’s focus on What happens when yout put custom objects in a TreeSet.
Set<User> treeSet = new TreeSet<>(); treeSet.add(new User(1L, "Tom", "Mills", 29)); // This line gives RunTimeException "User cannot be cast to java.lang.Comparable"
It means, if you want to store a Custom object in TreeSet, it should know how to compare any two instances of the object. And there are two ways to do this.
- Make your User class to implement Comparable interface.
- or, Provide a simple Comparator.
Here, we will see example of Comparator. Using Lambda Expressions you can provide an inline anonymous implementation of Comparator.
Single Field Comparator
Consider, if you want to sort the users by last name.
Set<User> treeSet = new TreeSet<>(Comparator.comparing(User::getLastName)); treeSet.add(new User(1L, "Tom", "Mills", 29)); treeSet.add(new User(1L, "Rob", "Wales", 30)); treeSet.add(new User(1L, "John", "Farley", 29)); treeSet.add(new User(1L, "Ann", "Wills", 31)); treeSet.add(new User(1L, "Bob", "Wills", 20)); treeSet.forEach(System.out::println); ------- // Output // [id: 1, name: John, last name: Farley, age: 29] // [id: 1, name: Ann, last name: Wills, age: 31] // [id: 1, name: Tom, last name: Mills, age: 29] // [id: 1, name: Rob, last name: Wales, age: 30] // [id: 1, name: Bob, last name: Wills, age: 20]
Compare Using two Fields
Now, you want to compare the Users based on the Last Name and then Age.
Set<User> treeSet = new TreeSet<>( Comparator .comparing(User::getLastName) .thenComparing(User::getAge) );
TreeSet and Thread Safety
The ThreeSets are not Synchronised by default. Hence multiple threads in your application can modify them at the same time. Therefore, if one thread is iterating over the ThreeSet and other thread has removed an element or added an element. In such cases instead of returning dirty data, the iterator will throw an
To avoid such exceptions you have to manage synchronisation between simultaneous reads and writes on your own.
Alternatively you can create a normal TreeSet and then synchronize it. For example refer to below code.
Set<Integer> treeSet = new TreeSet<>(); Set<Integer> synchronizedSet = Collections.synchronizedSet(treeSet);
When to Use TreeSet
The main features of TreeSet are the Uniqueness and Sorting. Whenever you have a dataset that has duplicates and it is not sorted, you can use TreeSet for duplicates removal as well as to Sort the dataset..
For example, consider a scenario where you have a collection of requests. Where, each use may raise a request twice. Also, you want to serve the oldest user the first and youngest in the last.
List<UserRequest> userReqeuestList = new ArrayList<>(); // ..populate list Set<UserRequest> userRequestSet = new TreeSet<>( Comparator.comparing( UserRequest::getUserAge).reversed()); // Add all the elements from list into the TreeSet userRequestSet.addAll(userReqeuestList);
In this tutorial of Introduction to Java TreeSet we learnt that TreeSet is an implementation of Set Colleciton in Java. It stores the data in sorted order. However for the custom objects, you can provide your own Sorting logic. Also, we learnt How and where to use the TreeSets.