Topic 12: Collections in Java - Set

📖 7 min read · 🎯 Advanced · 🧭 Prerequisites: android-event-handling, collections-in-java-queue

Why this matters

Here's the thing — every app you build will deal with data that shouldn't repeat. Think about a list of users who liked a post, or the unique cities your customers come from, or the permissions a user has been granted. If you use a regular List for this, you have to manually check for duplicates every single time. That's messy and slow. Java's Set interface solves this automatically — it simply refuses to store the same value twice. In this lesson we'll look at three flavors — HashSet, LinkedHashSet, and TreeSet — and you'll learn exactly when to reach for each one.

What You'll Learn

• What the Set interface guarantees and why it matters for duplicate-free collections
• How HashSet delivers constant-time performance at the cost of ordering
• How LinkedHashSet preserves insertion order while still rejecting duplicates
• How TreeSet keeps elements sorted automatically using natural ordering or a custom Comparator

The Analogy

Think of a Set like a guest list for an exclusive event — every name on the list must be unique. It doesn't matter how many times someone tries to RSVP; they appear exactly once. A HashSet is like a bouncer who checks names in any random order — fast, but unpredictable. A LinkedHashSet is like a bouncer with a stamp machine who notes the exact order each guest arrived. A TreeSet is like a bouncer who insists on seating everyone alphabetically regardless of when they showed up. Same rule (no duplicates), three very different personalities at the door.

Chapter 1: Introduction to Sets

A Set is a collection that does not allow duplicate elements. Java's java.util package provides several concrete implementations of the Set interface, each trading off ordering guarantees against performance characteristics.

Key Implementations of the Set Interface

1. HashSet

   • Does not maintain any element order.
   • Offers constant-time (O(1)) performance for the basic operations: add, remove, contains, and size.
   • Best default choice when ordering is irrelevant and speed matters.

2. LinkedHashSet

   • Maintains insertion order — elements iterate in the sequence they were added.
   • Offers predictable iteration order at a small memory overhead over HashSet.
   • Best when you need both duplicate prevention and stable iteration order.

3. TreeSet

   • Maintains elements in sorted order — either natural ordering (via Comparable) or a supplied Comparator.
   • Offers log-time cost (O(log n)) for add, remove, and contains.
   • Best when you need a sorted, duplicate-free collection.

graph TD
    SI[Set Interface] --> HS[HashSet\nNo order · O of 1]
    SI --> LHS[LinkedHashSet\nInsertion order · O of 1]
    SI --> TS[TreeSet\nSorted order · O log n]

Chapter 2: Using HashSet

HashSet is the most commonly used Set implementation. It hashes each element to determine its bucket, which is why lookup and insertion are both effectively instant regardless of collection size — but also why iteration order is unpredictable.

Example: Using HashSet

Create a Java file HashSetExample.java to experiment with HashSet.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        // Creating a HashSet
        Set<String> hashSet = new HashSet<>();

        // Adding elements to the HashSet
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Cherry");
        hashSet.add("Apple"); // Duplicate element, will be ignored

        // Displaying the HashSet
        System.out.println("HashSet: " + hashSet);

        // Iterating over the HashSet
        System.out.print("Iterating over HashSet: ");
        for (String fruit : hashSet) {
            System.out.print(fruit + " ");
        }
        System.out.println();

        // Checking if an element exists
        System.out.println("Contains 'Banana': " + hashSet.contains("Banana"));
        System.out.println("Contains 'Grapes': " + hashSet.contains("Grapes"));

        // Removing an element
        hashSet.remove("Cherry");
        System.out.println("After removing 'Cherry': " + hashSet);

        // Getting the size of the HashSet
        System.out.println("Size of HashSet: " + hashSet.size());
    }
}

Compile and run:

javac HashSetExample.java
java HashSetExample

Notice that "Apple" is added twice but appears only once in the output. The printed order of elements may vary between runs — HashSet makes no ordering promises.

Chapter 3: Using LinkedHashSet

LinkedHashSet extends HashSet by maintaining a doubly-linked list running through its buckets. This extra structure records the order in which elements were inserted, so iteration always reproduces that sequence.

Example: Using LinkedHashSet

Create a Java file LinkedHashSetExample.java to experiment with LinkedHashSet.

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        // Creating a LinkedHashSet
        Set<String> linkedHashSet = new LinkedHashSet<>();

        // Adding elements to the LinkedHashSet
        linkedHashSet.add("Apple");
        linkedHashSet.add("Banana");
        linkedHashSet.add("Cherry");
        linkedHashSet.add("Apple"); // Duplicate element, will be ignored

        // Displaying the LinkedHashSet
        System.out.println("LinkedHashSet: " + linkedHashSet);

        // Iterating over the LinkedHashSet
        System.out.print("Iterating over LinkedHashSet: ");
        for (String fruit : linkedHashSet) {
            System.out.print(fruit + " ");
        }
        System.out.println();

        // Checking if an element exists
        System.out.println("Contains 'Banana': " + linkedHashSet.contains("Banana"));
        System.out.println("Contains 'Grapes': " + linkedHashSet.contains("Grapes"));

        // Removing an element
        linkedHashSet.remove("Cherry");
        System.out.println("After removing 'Cherry': " + linkedHashSet);

        // Getting the size of the LinkedHashSet
        System.out.println("Size of LinkedHashSet: " + linkedHashSet.size());
    }
}

Compile and run:

javac LinkedHashSetExample.java
java LinkedHashSetExample

Unlike HashSet, this will consistently print [Apple, Banana, Cherry] — insertion order is preserved on every run.

Chapter 4: Using TreeSet

TreeSet stores elements in a red-black tree, which keeps them sorted at all times. When you iterate, elements arrive in ascending natural order (for String, that is alphabetical). You can pass a custom Comparator to the constructor if you need a different sort order.

Example: Using TreeSet

Create a Java file TreeSetExample.java to experiment with TreeSet.

import java.util.Set;
import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // Creating a TreeSet
        Set<String> treeSet = new TreeSet<>();

        // Adding elements to the TreeSet
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");
        treeSet.add("Apple"); // Duplicate element, will be ignored

        // Displaying the TreeSet
        System.out.println("TreeSet: " + treeSet);

        // Iterating over the TreeSet
        System.out.print("Iterating over TreeSet: ");
        for (String fruit : treeSet) {
            System.out.print(fruit + " ");
        }
        System.out.println();

        // Checking if an element exists
        System.out.println("Contains 'Banana': " + treeSet.contains("Banana"));
        System.out.println("Contains 'Grapes': " + treeSet.contains("Grapes"));

        // Removing an element
        treeSet.remove("Cherry");
        System.out.println("After removing 'Cherry': " + treeSet);

        // Getting the size of the TreeSet
        System.out.println("Size of TreeSet: " + treeSet.size());
    }
}

Compile and run:

javac TreeSetExample.java
java TreeSetExample

Even though "Banana" was inserted first, the output will be [Apple, Banana, Cherry] — TreeSet silently re-orders elements as they are inserted.

Chapter 5: Choosing the Right Set

All three reject duplicates — that guarantee is the contract of the Set interface itself, not an implementation detail.

🧪 Try It Yourself

Task: Build a SetComparisonDemo that adds the same five strings ("Mango", "Kiwi", "Peach", "Mango", "Kiwi") to all three set types and prints each set on its own line.

Success criterion: Your output shows exactly three unique fruits per set, but the order differs: HashSet is unpredictable, LinkedHashSet prints [Mango, Kiwi, Peach], and TreeSet prints [Kiwi, Mango, Peach].

Starter snippet:

import java.util.*;

public class SetComparisonDemo {
    public static void main(String[] args) {
        List<String> input = List.of("Mango", "Kiwi", "Peach", "Mango", "Kiwi");

        Set<String> hashSet       = new HashSet<>(input);
        Set<String> linkedHashSet = new LinkedHashSet<>(input);
        Set<String> treeSet       = new TreeSet<>(input);

        System.out.println("HashSet:       " + hashSet);
        System.out.println("LinkedHashSet: " + linkedHashSet);
        System.out.println("TreeSet:       " + treeSet);
    }
}

Compile with javac SetComparisonDemo.java and run with java SetComparisonDemo. Confirm the sizes are all 3 and that TreeSet output is alphabetically sorted.

🔍 Checkpoint Quiz

Q1. Which Set implementation should you choose when you need to iterate elements in the exact order they were added, while still preventing duplicates?

A) HashSet B) LinkedHashSet C) TreeSet D) ArrayList

Q2. Given the following code, what will System.out.println(set.size()) print?

Set<String> set = new TreeSet<>();
set.add("Z");
set.add("A");
set.add("M");
set.add("A");
System.out.println(set.size());

A) 4 B) 3 C) 2 D) 1

Q3. What will this snippet print?

Set<String> set = new TreeSet<>();
set.add("Banana");
set.add("Apple");
set.add("Cherry");
for (String s : set) System.out.print(s + " ");

A) Banana Apple Cherry B) Apple Banana Cherry C) Cherry Banana Apple D) Order is unpredictable

Q4. Your Android app needs to track a unique set of recently visited screen names and always display them in the order the user first visited them. Which Set implementation fits best, and why?

A1. B) LinkedHashSet — it wraps a hash table with a linked list that records insertion order, giving you O(1) operations plus predictable iteration.

A2. B) 3 — "A" is added twice but a Set silently ignores the duplicate, leaving {A, M, Z} with size 3.

A3. B) Apple Banana Cherry — TreeSet sorts elements in natural (alphabetical) order regardless of insertion sequence.

A4. LinkedHashSet — it rejects duplicates (ensuring each screen name appears only once) and preserves the insertion order (so the display reflects the user's first-visit sequence). HashSet would lose the order; TreeSet would alphabetize instead of preserving visit order.

🪞 Recap

• A Set is a collection that rejects duplicate elements — this is the core contract of the Set interface.
• HashSet offers O(1) add/remove/contains with no ordering guarantee — the best default for pure uniqueness enforcement.
• LinkedHashSet preserves insertion order at a small overhead cost, ideal when iteration sequence matters.
• TreeSet keeps elements sorted at all times using natural ordering or a Comparator, but costs O(log n) per operation.
• All three implementations are interchangeable through the Set<E> interface — you can swap the concrete type without changing the rest of your code.

📚 Further Reading

• Java Set Interface — Oracle Docs — the source of truth on every method the Set contract provides
• Java Collections Framework Overview — how Set, List, and Queue fit into the broader framework
• Effective Java, 3rd Edition — Item 58: For-each loops — Bloch's canonical guidance on iterating collections safely and idiomatically
• ⬅️ Previous: Collections in Java - Queue
• ➡️ Next: Custom UI Components