What is the difference between HashSet and TreeSet?

Both HashSet and TreeSet are part of the Java Collections Framework and implement the Set interface, ensuring that they store unique elements. However, they have significant differences in how they operate. Here’s a comparison:

1. Underlying Data Structure

• HashSet: Uses a HashMap internally to store elements. The elements are hashed and stored based on their hash codes.
• TreeSet: Uses a TreeMap (a Red-Black Tree) internally, ensuring that the elements are sorted in their natural order or by a specified comparator.

2. Order of Elements

• HashSet: Does not maintain any order of elements. The order may change as elements are added or removed.
• TreeSet: Maintains elements in sorted order (natural order or a custom order if a comparator is provided).

3. Performance

• HashSet:
  • Add, Remove, Contains operations are generally O(1) (constant time) on average, assuming a good hash function.
  • Can degrade to O(n) in the worst case if hash collisions occur.
• TreeSet:
  • Add, Remove, Contains operations are O(log n) because it uses a balanced tree for storage.

4. Null Values

• HashSet: Allows one null element.
• TreeSet: Does not allow null elements because it needs to compare elements for ordering, and comparing null causes a NullPointerException.

5. Sorting

• HashSet: Unordered and unsorted.
• TreeSet: Automatically sorts elements. If a natural order is not defined (e.g., for custom objects), you need to provide a Comparator.

6. Use Cases

• HashSet: Use when you just need to ensure uniqueness of elements and do not care about the order or sorting.
• TreeSet: Use when you need unique elements and sorted order.

---

Example

HashSet

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("Banana");
        hashSet.add("Apple");
        hashSet.add("Cherry");

        System.out.println("HashSet: " + hashSet); // Order not guaranteed
    }
}

TreeSet

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");

        System.out.println("TreeSet: " + treeSet); // Sorted order: [Apple, Banana, Cherry]
    }
}

---

Key Differences Table

Feature	HashSet	TreeSet
Order	Unordered	Sorted
Performance	O(1) (average case)	O(log n)
Allows Null?	Yes (1 null element)	No
Uses Comparator?	No	Optional
Use Case	Fast access and uniqueness	Sorted, unique elements