HashSet vs TreeSet vs LinkedHashSet – Comparison Table and Best Use Cases

Illustration for HashSet vs TreeSet vs LinkedHashSet – Comparison Table and Best Use Cases
By Last updated:

When working with sets in Java, three primary implementations dominate: HashSet, LinkedHashSet, and TreeSet. Each offers unique benefits depending on whether your priority is performance, insertion order, or sorting.

In this tutorial, we’ll compare these classes in depth, looking at their internal architecture, performance characteristics, use cases, and Java version enhancements.


📚 What Are These Sets?

Class Definition
HashSet Unordered collection backed by a HashMap
LinkedHashSet Insertion-ordered collection backed by a LinkedHashMap
TreeSet Sorted collection backed by a TreeMap (Red-Black Tree)

All three implement the Set interface and do not allow duplicates.


🧠 Internal Architecture

Feature HashSet LinkedHashSet TreeSet
Backed By HashMap LinkedHashMap TreeMap (RB Tree)
Order ❌ None ✅ Insertion ✅ Sorted
Duplicate Check equals() + hashCode() Same as HashSet compareTo() or Comparator
Null Support ✅ One null ✅ One null ❌ Throws NPE unless Comparator handles null
Thread-safe

⏱️ Performance Comparison

Operation HashSet LinkedHashSet TreeSet
add() O(1) O(1) O(log n)
remove() O(1) O(1) O(log n)
contains() O(1) O(1) O(log n)
iterator() O(n) O(n) (in order) O(n) (sorted)

Note: TreeSet is slower but provides sorted views and range queries.


💡 When to Use What?

Scenario Recommended Set
Fastest access, order doesn't matter HashSet
Unique elements + insertion order LinkedHashSet
Unique + Sorted + Range queries TreeSet

🔁 Code Examples

HashSet

Set<String> hashSet = new HashSet<>();
hashSet.add("B");
hashSet.add("A");
System.out.println(hashSet); // [A, B] or [B, A] (unordered)

LinkedHashSet

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("B");
linkedHashSet.add("A");
System.out.println(linkedHashSet); // [B, A]

TreeSet

Set<String> treeSet = new TreeSet<>();
treeSet.add("B");
treeSet.add("A");
System.out.println(treeSet); // [A, B]

🧬 Functional Java with Streams

List<String> names = List.of("b", "a", "c", "a");

Set<String> hash = names.stream().collect(Collectors.toSet());
Set<String> linked = names.stream().collect(Collectors.toCollection(LinkedHashSet::new));
Set<String> tree = names.stream().collect(Collectors.toCollection(TreeSet::new));

❌ Common Pitfalls

  • ❌ Expecting order from HashSet
  • ❌ Using TreeSet without proper Comparable or Comparator
  • ❌ Adding null to TreeSet without handling comparison

📌 What's New in Java Versions?

Java 8

  • Collectors.toSet(), removeIf(), forEach()
  • Lambda & Stream APIs for all sets

Java 9

  • Set.of(...) for immutable sets

Java 10

  • var support

Java 11–17

  • Performance tweaks in core collections

Java 21

  • GC and memory layout optimizations impacting all Set types

🔄 Legacy Refactoring Tips

Before:

List<String> list = Arrays.asList("z", "y", "x", "z");
List<String> noDupes = new ArrayList<>();
for (String s : list) {
    if (!noDupes.contains(s)) noDupes.add(s);
}

After (LinkedHashSet):

List<String> noDupes = new ArrayList<>(new LinkedHashSet<>(list));

Or TreeSet for sorting:

Set<String> sortedUnique = new TreeSet<>(list);

🧠 Real-World Analogies

  • HashSet: A box of unique balls thrown in without order.
  • LinkedHashSet: A list of attendees signed in — one entry per person, in sign-in order.
  • TreeSet: A sorted guest list in alphabetical order — no duplicates, always ordered.

❓ FAQ – Expert-Level Questions

  1. Can these sets contain null values?

    • HashSet and LinkedHashSet allow one null. TreeSet does not (unless comparator allows it).
  2. Which set is fastest?

    • HashSet is fastest for add(), remove(), and contains().
  3. Which set maintains order?

    • LinkedHashSet (insertion order) and TreeSet (sorted order).
  4. Can I use custom objects in sets?

    • Yes. Override equals()/hashCode() for HashSet and LinkedHashSet, and compareTo() for TreeSet.
  5. How do TreeSet and HashSet differ in duplicates?

    • HashSet uses hash equality, TreeSet uses comparison logic.
  6. Are any of these sets thread-safe?

    • No. Use Collections.synchronizedSet() or concurrent alternatives.
  7. Can I create immutable sets from these?

    Set<String> immutable = Set.of("A", "B");
    
  8. What's the default capacity of HashSet?

    • 16 with a load factor of 0.75
  9. How to safely iterate and remove?

    Iterator<String> it = set.iterator();
    while (it.hasNext()) {
        if (condition) it.remove();
    }
    
  10. Which one should I use by default?

    • Prefer HashSet, use LinkedHashSet or TreeSet when you need order.

🏁 Conclusion and Key Takeaways

  • HashSet is your go-to for fast, unordered, duplicate-free collections.
  • LinkedHashSet shines when order matters without sorting.
  • TreeSet excels when natural or custom sorting is needed.
  • All sets enforce uniqueness but differ in order guarantees and performance.

💡 Pro Tip: Benchmark your use case — don’t blindly choose based on theory.