Java’s Collections Framework offers a rich set of data structures designed to store, retrieve, and manipulate data efficiently. Two standout implementations of the Set interface are HashSet and TreeSet. While both are designed to store unique elements, their underlying mechanisms and performance characteristics are quite distinct. In this post, we will learn the differences between HashSet and TreeSet in Java with examples.
| Criteria | HashSet | TreeSet |
|---|---|---|
| Underlying Data Structure | Hash table | Red-Black tree (a type of balanced binary search tree) |
| Ordering of Elements | No guaranteed order | Elements are sorted according to their natural ordering or by a comparator provided at set creation time |
| Null Elements | Allows one null element | Doesn’t allow any null element (if natural ordering is used or any custom comparator does not permit nulls) |
| Performance | Generally faster for add, remove, and contains operations | Logarithmic time cost for add, remove, and contains operations |
| Duplicates | Does not allow duplicates | Does not allow duplicates |
| Thread Safety | Not synchronized | Not synchronized |
| Use-case | When ordering is not needed, and faster operations are required | When sorting or natural order is important |
Example: Difference Between HashSet and TreeSet in Java
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class HashSetVsTreeSetDemo {
public static void main(String[] args) {
// Create a HashSet and add some elements
Set<String> hashSet = new HashSet<>();
hashSet.add("cherry");
hashSet.add("banana");
hashSet.add("apple");
hashSet.add("date");
System.out.println("HashSet:");
hashSet.forEach(System.out::println);
// Create a TreeSet and add some elements
Set<String> treeSet = new TreeSet<>();
treeSet.add("elephant");
treeSet.add("grape");
treeSet.add("fox");
treeSet.add("honeydew");
System.out.println("\nTreeSet:");
treeSet.forEach(System.out::println);
}
}
Output:
HashSet: cherry banana apple date TreeSet: elephant fox grape honeydew
Explanation:
1. HashSet: A HashSet is an implementation of the Set interface, backed by a hash table (actually a HashMap instance). It does not guarantee the order of elements. This means that the order in which the elements are added is not necessarily the order in which they will be iterated. It offers constant-time performance for the basic operations (add, remove, contains).
2. TreeSet: A TreeSet is a NavigableSet implementation based on a TreeMap. It guarantees the elements to be in ascending order, according to their natural order, or by a comparator provided at the set's creation time. It offers log(n) time complexity for most operations.
3. In the given example, the hashSet does not maintain any order, while the treeSet automatically arranges the strings in their natural order (alphabetically). This is evident in the output where the TreeSet elements are printed in a sorted manner, while the HashSet elements are in a seemingly random order.