What is the difference between HashSet, LinkedHashSet and TreeSet?

All three store unique elements, but they differ in ordering and speed. HashSet has no order and is the fastest. LinkedHashSet keeps insertion order with a small extra cost. TreeSet keeps elements sorted, with O(log n) operations.

Key Points: • HashSet: backed by a HashMap; add, remove and contains are O(1) on average; iteration order is unpredictable. • LinkedHashSet: backed by a LinkedHashMap; also O(1), and iterates in insertion order. • TreeSet: backed by a TreeMap (red-black tree); O(log n); sorted by natural order or a Comparator; offers first(), last(), floor(), ceiling() and range views. • HashSet and LinkedHashSet use equals() and hashCode(). TreeSet uses compareTo() or the Comparator, so two elements that compare as 0 count as duplicates. • HashSet and LinkedHashSet allow one null. TreeSet doesn't allow null with natural ordering.

Code Example:

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class SetComparison {

    public static void main(String[] args) {
        List<String> input = List.of("banana", "apple", "cherry", "apple", "date");

        Set<String> linked = new LinkedHashSet<>(input);
        Set<String> tree = new TreeSet<>(input);
        Set<String> hash = new HashSet<>(input);

        System.out.println("LinkedHashSet (insertion order): " + linked);
        System.out.println("TreeSet (sorted): " + tree);
        System.out.println("HashSet size: " + hash.size() + " (order not guaranteed)");

        TreeSet<Integer> scores = new TreeSet<>(List.of(45, 72, 88, 91, 60));
        System.out.println("Lowest: " + scores.first() + ", highest: " + scores.last());
        System.out.println("Highest score below 80: " + scores.lower(80));
    }
}

Output:

LinkedHashSet (insertion order): [banana, apple, cherry, date] TreeSet (sorted): [apple, banana, cherry, date] HashSet size: 4 (order not guaranteed) Lowest: 45, highest: 91 Highest score below 80: 72

Good to Know: A TreeSet with a comparator that is inconsistent with equals() can surprise you. For example, a case-insensitive TreeSet treats "Java" and "JAVA" as the same element, while a HashSet keeps both. The set uses whatever comparison you give it to decide what counts as a duplicate.

Interview Tip: A concise interview answer is:

"HashSet is backed by a HashMap and gives O(1) operations with no ordering. LinkedHashSet adds a linked list to keep insertion order at the same O(1) cost. TreeSet is a red-black tree that keeps elements sorted with O(log n) operations and navigation methods. I pick HashSet by default, LinkedHashSet when order of insertion matters, and TreeSet when I need sorting or range queries."

Next question: When is ArrayList faster than LinkedList, and is LinkedList ever the better choice?

More Java Collections interview questions

All Java Collections questions