What is the difference between HashSet, LinkedHashSet, and TreeSet?

• HashSet: backed by HashMap, no ordering guarantee, O(1) average add/contains/remove
• LinkedHashSet: backed by LinkedHashMap, maintains insertion order, O(1) average with slight memory overhead for linked list pointers
• TreeSet: backed by TreeMap (Red-Black tree), maintains sorted order (natural or Comparator), O(log n) operations, provides NavigableSet interface
• All three enforce uniqueness: HashSet/LinkedHashSet use hashCode+equals; TreeSet uses compareTo

What is the difference between HashSet, LinkedHashSet, and TreeSet?

All three implement the Set interface and enforce uniqueness. They differ in ordering and performance.

| Feature | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| Backing structure | HashMap | LinkedHashMap | TreeMap (Red-Black tree) |
| Ordering | None | Insertion order | Sorted (natural/Comparator) |
| add() | O(1) | O(1) | O(log n) |
| contains() | O(1) | O(1) | O(log n) |
| remove() | O(1) | O(1) | O(log n) |
| Null element | One allowed | One allowed | Not allowed (NPE with Comparable) |
| Memory per element | ~32 bytes | ~40 bytes | ~48 bytes |
| Equality | hashCode + equals | hashCode + equals | compareTo |
| NavigableSet | No | No | Yes |

package com.bank.demo;

import java.util.*;

public class SetComparisonDemo {
    public static void main(String[] args) {
        List<String> accounts = List.of("CUR3001", "SAV2001", "FD4001", "LON5001");

        Set<String> hashSet = new HashSet<>(accounts);
        Set<String> linkedSet = new LinkedHashSet<>(accounts);
        Set<String> treeSet = new TreeSet<>(accounts);

        System.out.println("HashSet:       " + hashSet);       // unpredictable order
        System.out.println("LinkedHashSet: " + linkedSet);     // insertion order
        System.out.println("TreeSet:       " + treeSet);       // sorted
    }
}

HashSet:       [FD4001, LON5001, CUR3001, SAV2001]
LinkedHashSet: [CUR3001, SAV2001, FD4001, LON5001]
TreeSet:       [CUR3001, FD4001, LON5001, SAV2001]

When do you use each one?

| Use case | Best choice | Why |
|---|---|---|
| Fast membership testing | HashSet | O(1), lowest memory |
| Unique elements + insertion order | LinkedHashSet | O(1), deterministic iteration |
| Sorted unique elements | TreeSet | O(log n), sorted iteration |
| Range queries ("accounts between A and F") | TreeSet | NavigableSet API |
| Deduplication preserving first occurrence | LinkedHashSet | Insertion order, rejects duplicates |
| Enum constants | EnumSet | Bit vector, fastest possible |
| Thread-safe set | ConcurrentHashMap.newKeySet() | Lock-free concurrent |

package com.bank.service;

import java.util.*;

public class SetUseCaseDemo {
    public static void main(String[] args) {
        // HashSet: blocked accounts – fast membership check
        Set<String> blocked = new HashSet<>(Set.of("SAV9999", "CUR8888"));
        System.out.println("Is blocked: " + blocked.contains("SAV2001"));

        // LinkedHashSet: preserve registration order
        Set<String> registrations = new LinkedHashSet<>();
        registrations.add("Rajesh");
        registrations.add("Priya");
        registrations.add("Amit");
        System.out.println("Registration order: " + registrations);

        // TreeSet: sorted account listing with range queries
        TreeSet<String> sortedAccounts = new TreeSet<>(Set.of(
            "SAV2001", "CUR3001", "FD4001", "LON5001", "SAV2002"
        ));
        System.out.println("Sorted: " + sortedAccounts);
        System.out.println("First: " + sortedAccounts.first());
        System.out.println("Last: " + sortedAccounts.last());
        System.out.println("Before FD4001: " + sortedAccounts.lower("FD4001"));
        System.out.println("After FD4001: " + sortedAccounts.higher("FD4001"));
        System.out.println("Range [CUR..SAV): " + sortedAccounts.subSet("CUR3001", "SAV2001"));
    }
}

Is blocked: false
Registration order: [Rajesh, Priya, Amit]
Sorted: [CUR3001, FD4001, LON5001, SAV2001, SAV2002]
First: CUR3001
Last: SAV2002
Before FD4001: CUR3001
After FD4001: LON5001
Range [CUR..SAV): [CUR3001, FD4001, LON5001]

What are the NavigableSet methods in TreeSet?

TreeSet implements NavigableSet, which provides powerful query methods:

• first() / last(): smallest / largest element.
• lower(e): greatest element strictly less than e.
• floor(e): greatest element less than or equal to e.
• ceiling(e): smallest element greater than or equal to e.
• higher(e): smallest element strictly greater than e.
• subSet(from, to): elements in range [from, to).
• headSet(e): elements less than e.
• tailSet(e): elements greater than or equal to e.
• descendingSet(): reverse-order view.
• pollFirst() / pollLast(): remove and return smallest / largest.

What are common mistakes?

Mistake 1: Using TreeSet without Comparable

// WRONG: Account does not implement Comparable
class Account { String id; }
Set<Account> set = new TreeSet<>();
set.add(new Account()); // ClassCastException!

// CORRECT: provide a Comparator
Set<Account> set = new TreeSet<>(Comparator.comparing(a -> a.id));

Mistake 2: Inconsistent compareTo and equals in TreeSet

// TreeSet uses compareTo for equality, not equals!
// If compareTo returns 0 but equals returns false,
// TreeSet considers them the same (removes the "duplicate")
// but HashSet considers them different.
// Always keep compareTo consistent with equals.

What should a senior engineer know?

- TreeSet equality is based on compareTo, not equals. Two elements are considered equal by TreeSet if compareTo() returns 0, even if equals() returns false. This is a subtle difference from HashSet.

- LinkedHashSet access-order mode. LinkedHashMap supports access-order mode (move to end on access), but LinkedHashSet does not expose this. If you need access-ordered uniqueness, use LinkedHashMap directly.

- ConcurrentSkipListSet. The thread-safe equivalent of TreeSet. It uses a skip list instead of a Red-Black tree and supports NavigableSet.

What are common interview follow-up questions?

• "Which Set preserves insertion order?" – LinkedHashSet.
• "Which Set keeps elements sorted?" – TreeSet.
• "What is the time complexity of TreeSet operations?" – O(log n).
• "Can TreeSet contain null?" – No, if using natural ordering (null.compareTo throws NPE).
• "What is NavigableSet?" – Extended SortedSet with floor/ceiling/lower/higher methods.