HashSet vs TreeSet: Difference Between HashSet and TreeSet in Java

In this article, we will discuss the difference between HashSet and TreeSet in Java with examples.

HashSet and TreeSet are both implementations of the Set interface in the Java Collections Framework (JCF), but they use different underlying data structures and have different characteristics and use cases.

HashSet is a collection that does not allow duplicate values. It uses a hash table for storage, leveraging the hashing principle to store elements.

TreeSet is a collection that does not allow duplicate values and stores its elements in sorted order.

Key Points of Comparison 

Underlying Data Structure: 

• HashSet is backed by a hash table. 
• TreeSet relies on a red-black tree. 

Order of Elements: 

• HashSet does not guarantee any specific order of its elements.
• TreeSet, being a sorted set, ensures elements are in ascending order (natural ordering) or based on a provided comparator. 

Null Elements: 

• HashSetallows one null element. 
• TreeSet does not allow null elements since it would throw a NullPointerException due to comparison during sorting. 

Performance: 

• HashSet offers constant time performance (O(1)) for basic operations assuming the hash function disperses elements properly among the buckets. 
• TreeSet provides O(log n) performance for most operations due to the tree-based structure. 

Flexibility with Ordering: 

• HashSet does not provide any ordering flexibility as it does not guarantee any specific order. 
• TreeSet allows users to define a custom order using a Comparator. 

Initial Capacity and Load Factor: 

• HashSet supports initial capacity and load factor, which affect its resizing. 
• TreeSet does not consider initial capacity or load factor since it is tree-based.

Practical Examples 

1. Using HashSet:

Set<String> hashSet = new HashSet<>();
hashSet.add("apple");
hashSet.add("banana");
hashSet.add("cherry");
hashSet.add(null);  // This is valid

System.out.println(hashSet); 
// Output can be in any order, e.g., [banana, cherry, apple, null]

2. Using TreeSet:

Set<String> hashSet = new HashSet<>();
Set<String> treeSet = new TreeSet<>();
treeSet.add("apple");
treeSet.add("banana");
treeSet.add("cherry");
// treeSet.add(null);  // This would throw NullPointerException

System.out.println(treeSet); // Output will always be [apple, banana, cherry]

3. Using TreeSet with a Comparator:

Comparator<String> reverseOrder = Comparator.reverseOrder();
Set<String> treeSetWithComparator = new TreeSet<>(reverseOrder);
treeSetWithComparator.add("apple");
treeSetWithComparator.add("banana");
treeSetWithComparator.add("cherry");

System.out.println(treeSetWithComparator); // Output will be [cherry, banana, apple]

Summary Table

Conclusion 

HashSet and TreeSet each bring unique benefits to the table: 

• Use HashSet when you don't need ordered data and want maximum performance. 
• Opt for TreeSet when you require sorted data or need to customize the order based on certain attributes.

Related Interview QA

• Difference Between List and Set in Java
• Difference Between Collection and Collections in Java
  
• Difference Between Array and ArrayList in Java
  
• Difference between ArrayList and LinkedList in Java
• Difference Between HashSet and LinkedHashSet in Java
• Difference Between HashSet and TreeSet in Java
• HashSet vs LinkedHashSet vs TreeSet in Java
• Difference Between HashMap and HashTable in Java
• Difference Between HashSet and HashMap in Java
• HashMap vs LinkedHashMap in Java
• Difference between HashMap, LinkedHashMap, and TreeMap in Java
• Collections vs Streams in Java