What is the difference between TreeSet and HashSet?

TreeSet stores elements in sorted order and uses a red-black tree for this. HashSet does not guarantee element order and is based on a hash table.

Main differences:

• Element order: TreeSet is ordered in ascending order, HashSet is not.
• Performance: For most operations (add, remove, contains), HashSet has an average complexity of O(1), whereas TreeSet is O(log n).
• Implementation: TreeSet uses TreeMap, where elements are stored as keys. HashSet uses HashMap, where elements are stored as keys, and values are dummy objects.
• Null storage: HashSet allows one null element. TreeSet does not allow null, as comparison of elements requires their heterogeneity.
• Element comparison: TreeSet requires elements to implement the Comparable interface or a comparator to be provided. HashSet requires correct implementation of equals() and hashCode() methods for elements.

Example usage:

import java.util.HashSet;
import java.util.TreeSet;

public class SetDifference {

    public static void main(String[] args) {
        // HashSet - unordered
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Orange");
        System.out.println("HashSet: " + hashSet); // Order may vary

        // TreeSet - sorted
        TreeSet<String> treeSet = new TreeSet<>();
        treeSet.add("Apple");
        treeSet.add("Banana");
        treeSet.add("Orange");
        System.out.println("TreeSet: " + treeSet); // Always sorted
    }
}

Comparison table:

Aspect	HashSet	TreeSet
Order	Not guaranteed	Sorted
Performance	Average O(1)	Average O(log n)
Internal structure	Hash table (HashMap)	Red-black tree (TreeMap)
Null elements	Allows one null	Does not allow null
Element requirements	equals(), hashCode()	Comparable or Comparator