HashSet, LinkedHashSet and TreeSet

1 The story

Three ways to keep a guest list

Riya is managing entries for the college fest. Volunteers at three gates scan wristbands, and some guests come in, go out and come back. She needs three things from the same data: how many different guests, who arrived first, and an alphabetical list for the certificates.

Riya

Sir, all three say 4 guests, which is right. But the order is different every time!

Arjun Sir

Because each set keeps a different promise about order. A HashSet puts elements wherever their hash code sends them: fastest, but no meaningful order. A LinkedHashSet also remembers the order they arrived. A TreeSet keeps them sorted.

Riya

And how does each one know Riya's second scan is a duplicate?

Arjun Sir

The hash-based sets ask hashCode and equals, from Lesson 10.3. The TreeSet asks compareTo: if it says 0, that's “the same”. That difference causes some surprising bugs, so let's look closely.

2 Definition

What are HashSet, LinkedHashSet and TreeSet?

Formal definition (write this in exams)

A Set is a collection that contains no duplicate elements. HashSet stores elements in a hash table (it is backed by a HashMap), offers O(1) average add, remove and contains, makes no guarantee about iteration order and permits one null. LinkedHashSet extends HashSet and additionally maintains a doubly linked list through its entries, so it iterates in insertion order. TreeSet implements NavigableSet using a red-black tree (backed by a TreeMap); it keeps elements sorted by natural ordering or a supplied Comparator, with O(log n) operations, and does not permit null. Hash sets detect duplicates with hashCode and equals; TreeSet uses compareTo/compare.

In simple words

Three sets, all without duplicates. HashSet: fastest, jumbled. LinkedHashSet: remembers arrival order. TreeSet: keeps things sorted and can find the nearest value.

Words you'll meet in this lesson

Hash tableAn array of buckets; the hash code picks the bucket (Lesson 11.6 goes deep).

Red-black treeA self-balancing binary search tree: left smaller, right larger, height kept about log n.

Natural orderingThe order from compareTo: numbers ascending, Strings alphabetical.

NavigableTreeSet can answer “nearest”: floor, ceiling, higher, lower.

ViewheadSet/tailSet/subSet return live windows of the set.

Side by side

	`HashSet`	`LinkedHashSet`	`TreeSet`
Order	None guaranteed	Insertion order	Sorted
Inside	HashMap	LinkedHashMap	TreeMap (red-black tree)
add / contains / remove	O(1) average	O(1) average	O(log n)
Duplicate check	hashCode + equals	hashCode + equals	compareTo / Comparator
`null`	One allowed	One allowed	Not allowed (NPE)
Extra	Smallest memory	Predictable output	first, last, floor, ceiling, ranges

Exam tip: HashSet is internally a HashMap whose keys are your elements and whose values are all one shared dummy object (PRESENT). add returns false if the element was already there. TreeSet elements must be Comparable (or you pass a Comparator), otherwise add throws ClassCastException.

3 Types and ways to use it

Using the three sets

HashSet

Membership tests, de-duplication, “seen before?”. Default choice.

speed

LinkedHashSet

Unique items, shown in the order they arrived.

predictable

TreeSet

Sorted unique items, ranges and “nearest” lookups.

sorted

The same input, three outputs

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> scans = List.of("Riya", "Kabir", "Om", "Riya", "Meera", "Kabir");

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

        System.out.println(hash.size() + " " + hash);
        System.out.println(linked.size() + " " + linked);
        System.out.println(tree.size() + " " + tree);
        System.out.println(hash.add("Om") + " " + hash.add("Zoya"));   // false: already there
    }
}

4 [Meera, Riya, Kabir, Om] 4 [Riya, Kabir, Om, Meera] 4 [Kabir, Meera, Om, Riya] false true

The HashSet order comes from the hash codes and the table size; it's stable for the same data and JDK, but never rely on it.

TreeSet's navigation methods

import java.util.List;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> slots = new TreeSet<>(List.of(40, 10, 30, 20));   // minutes past the hour

        System.out.println(slots);                                  // sorted
        System.out.println(slots.first() + " " + slots.last());
        System.out.println(slots.floor(25) + " " + slots.ceiling(25));   // nearest ≤ 25, ≥ 25
        System.out.println(slots.headSet(30) + " " + slots.tailSet(30)); // < 30, ≥ 30
        System.out.println(slots.higher(40));                       // nothing above 40
        System.out.println(slots.descendingSet());
    }
}

[10, 20, 30, 40] 10 40 20 30 [10, 20] [30, 40] null [40, 30, 20, 10]

Set operations: union, intersection, difference

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

public class Main {
    public static void main(String[] args) {
        Set<String> riya = Set.of("java", "sql", "python");
        Set<String> kabir = Set.of("sql", "excel", "python");

        Set<String> union = new TreeSet<>(riya);   union.addAll(kabir);
        Set<String> both = new TreeSet<>(riya);    both.retainAll(kabir);
        Set<String> onlyRiya = new TreeSet<>(riya); onlyRiya.removeAll(kabir);

        System.out.println("Either: " + union);
        System.out.println("Both:   " + both);
        System.out.println("Only Riya: " + onlyRiya);
    }
}

Either: [excel, java, python, sql] Both: [python, sql] Only Riya: [java]

Two classic traps. (1) A custom class in a HashSet without equals/hashCode lets duplicates in (Lesson 10.3). (2) A TreeSet treats elements as equal when compareTo returns 0, even if equals says otherwise: a TreeSet sorted by marks will silently drop a second student with the same marks.

Rule of thumb: HashSet by default; LinkedHashSet when the output order should match the input; TreeSet when you need sorting or “nearest” lookups. Don't sort a HashSet's output by copying into a TreeSet on every request: pick TreeSet once if you always need order.

4 Step by step

How TreeSet.add finds a place

Start at the root
```
slots.add(25);   // tree holds 10, 20, 30, 40
```
The TreeSet's TreeMap compares 25 with the root node using compareTo.
Go left or right
Smaller → go to the left child; larger → right child. Each comparison discards about half of the remaining tree.
compareTo returns 0? It's a duplicate
If any comparison returns 0, the set already “contains” the element: add returns false and nothing changes. This is why TreeSet never calls equals.
Reach an empty spot: insert
The new node becomes a red leaf where the search ended.
Rebalance
If two red nodes are now adjacent, the tree recolours and rotates a few nodes. The height stays at most about 2 log₂(n), so a million elements need only about 20–40 comparisons per operation.

5 See it happen

HashSet vs TreeSet: both views

Left: the same add calls on two sets. Right: buckets in the HashSet and the sorted tree inside the TreeSet.

Same elements, two structures 6 steps

What you see

Behind the screen

6 Real-world use

Sets in real systems

Wherever “each thing once” matters, a set is the natural tool.

Watch it with an example: booking a turf slot

A turf-cricket ground keeps its free evening slots in a TreeSet. Watch it answer “next slot after 6:10” and update itself as slots are booked.

Free slots in a TreeSet 5 steps

Animated example

1. Duplicate detection

Payment gateways ignore repeated transaction IDs, email services avoid sending the same campaign twice, and crawlers skip URLs they've already visited, all with hash sets.

incoming id→seen.add(id)→false = duplicate

2. Permissions and tags

A user's roles, a product's tags or a course's prerequisites are sets. “Does she have ADMIN?” is contains; “common interests” is an intersection.

user roles→roles.contains("ADMIN")→allow

3. Booking free slots

A clinic or turf keeps free time slots in a TreeSet. “Next available after 4:20 pm” is ceiling(time); “all slots before noon” is headSet(noon).

request 16:20→free.ceiling(1620)→16:30

4. “Recent” lists without repeats

Recent searches or recently viewed items use a LinkedHashSet: unique, and in the order the user did them.

search “chai”→LinkedHashSet→shown once, in order

Examples are simplified. Across many servers, duplicate checks usually move to a shared store such as a database unique key.

7 Run the code

Fest entry desk

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] scans = {"Riya", "Kabir", "Om", "Riya", "Meera", "Kabir", "Zoya"};
        Set<String> vip = Set.of("Meera", "Zoya", "Arjun");

        Set<String> arrivals = new LinkedHashSet<>();
        int repeats = 0;
        for (String s : scans) {
            if (!arrivals.add(s)) repeats++;          // add returns false for a duplicate
        }

        Set<String> certificates = new TreeSet<>(arrivals);
        Set<String> vipsPresent = new TreeSet<>(arrivals);
        vipsPresent.retainAll(vip);

        System.out.println("Unique guests: " + arrivals.size() + ", repeat scans: " + repeats);
        System.out.println("Arrival order: " + arrivals);
        System.out.println("Certificates:  " + certificates);
        System.out.println("VIPs present:  " + vipsPresent);
    }
}

Unique guests: 5, repeat scans: 2 Arrival order: [Riya, Kabir, Om, Meera, Zoya] Certificates: [Kabir, Meera, Om, Riya, Zoya] VIPs present: [Meera, Zoya]

LinkedHashSetUnique guests in the order they first arrived.
!arrivals.add(s)Counting duplicates using add's return value.
new TreeSet<>(arrivals)Copy into a TreeSet for an alphabetical list.
retainAll(vip)Intersection: keep only guests who are also VIPs.

8 Line by line

Three sets, one input

This trace is recorded from the real JVM. Watch the HashSet's buckets, the LinkedHashSet's insertion order and the TreeSet's sorted order as the same names arrive, including a repeat.

Worked examples: real problems, solved and traced in memory

Three problems, each solved by the set whose order fits the job.

Example 1Payments · HashSet

Flag duplicate transaction IDs

Problem statement

A payment batch has transaction IDs. List the IDs that appear more than once, each reported once.

Input

["T1", "T2", "T1", "T3", "T2", "T1"]

Expected output

Duplicates: [T1, T2]

Approach

seen: a HashSet of IDs met so far.
If seen.add(id) returns false, it's a repeat: add it to a dups set (so it's reported once).
Print dups using a LinkedHashSet to keep first-detection order.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 2Clinic · TreeSet

Next free appointment

Problem statement

Free slots (minutes after 10:00) are 0, 20, 40, 90. Patients ask for 15 and then 25. Give each the first slot at or after the time asked, and remove it once booked.

Input

free {0, 20, 40, 90}; requests 15, 25

Expected output

15 → 20
25 → 40
Still free: [0, 90]

Approach

Keep free slots in a TreeSet.
A helper book(free, want) uses ceiling and removes the slot.
Print each booking and what's left.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 3Search · LinkedHashSet

Recent searches, newest last, no repeats

Problem statement

A food app shows recent searches without repeats. If a search is repeated, it moves to the end. Searches: dosa, chai, vada, dosa.

Input

dosa, chai, vada, dosa

Expected output

[chai, vada, dosa]

Approach

A LinkedHashSet keeps insertion order.
To move a repeat to the end, remove it first, then add it again.
Print the set.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

9 Quiz and revision

Check yourself

Quick revision

Lesson 11.5 in one screen

Set = no duplicates. add returns false for a duplicate.
HashSet: HashMap inside, O(1) average, no order, one null. LinkedHashSet: + insertion order.
TreeSet: red-black tree (TreeMap), sorted, O(log n), no null, needs Comparable or Comparator.
Duplicates: hash sets use hashCode + equals; TreeSet uses compareTo = 0.
TreeSet extras: first/last, floor/ceiling/lower/higher, headSet/tailSet/subSet, descendingSet, pollFirst.
Set algebra: union addAll, intersection retainAll, difference removeAll.

Interview and viva questions

How does HashSet ensure uniqueness?

add(e) calls map.put(e, PRESENT) on an internal HashMap. The map finds the bucket via e.hashCode() and compares with equals; if an equal key exists, put returns the old value and add returns false. That's why correct equals/hashCode matter.

HashSet vs TreeSet?

HashSet: O(1) average, unordered, allows one null, uses hashCode/equals. TreeSet: O(log n), sorted, no null, uses compareTo/Comparator, and offers navigation methods. Choose TreeSet only when you need ordering or range queries.

Why can a TreeSet lose elements that are not equal?

Because it treats compare(a, b) == 0 as “same element”. If the ordering is not consistent with equals (e.g. sorting students only by marks), two different students with equal marks collapse into one. Add a tie-breaker (e.g. then by roll number).

Is iteration order of HashSet random?

Not random, but unspecified: it depends on hash codes, table size and insertion history, and can change when the set resizes or between JDK versions. Never depend on it; use LinkedHashSet or TreeSet when order matters.

How do you make a thread-safe set?

ConcurrentHashMap.newKeySet() for a concurrent hash set, ConcurrentSkipListSet for a sorted one, or Collections.synchronizedSet(...) for simple cases (Module 12).

Practice problems

Pick the right set for each job and use the set operations. The last three are business tasks.

P1Easy

Count distinct words

How many different words are in "to be or not to be"?

Input

"to be or not to be"

Expected output

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<String> words = new HashSet<>(Arrays.asList("to be or not to be".split(" ")));
        System.out.println(words.size());
    }
}

4

How it works: six words go in; the HashSet keeps the four distinct ones.

P2Easy

Sorted distinct values

Print the distinct marks of {72, 85, 72, 91, 85} from highest to lowest.

Input

{72, 85, 72, 91, 85}

Expected output

[91, 85, 72]

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> m = new TreeSet<>(List.of(72, 85, 72, 91, 85));
        System.out.println(m.descendingSet());
    }
}

[91, 85, 72]

How it works: the TreeSet removes repeats and sorts; descendingSet is a reversed view.

P3Easy

Is every required skill present?

A job needs {java, sql}. A candidate has {java, git, sql}. Check with containsAll.

Input

required {java, sql}

Expected output

true

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<String> need = Set.of("java", "sql");
        Set<String> has = Set.of("java", "git", "sql");
        System.out.println(has.containsAll(need));
    }
}

true

How it works: containsAll is the subset test.

P4Medium

Common and unique subjects

Riya takes {Maths, Physics, CS}; Kabir takes {CS, Biology, Maths}. Print subjects both take and subjects only one of them takes.

Input

two subject sets

Expected output

Both: [CS, Maths], only one: [Biology, Physics]

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<String> r = Set.of("Maths", "Physics", "CS");
        Set<String> k = Set.of("CS", "Biology", "Maths");
        Set<String> both = new TreeSet<>(r); both.retainAll(k);
        Set<String> either = new TreeSet<>(r); either.addAll(k);
        Set<String> onlyOne = new TreeSet<>(either); onlyOne.removeAll(both);
        System.out.println("Both: " + both + ", only one: " + onlyOne);
    }
}

Both: [CS, Maths], only one: [Biology, Physics]

How it works: symmetric difference = union minus intersection.

P5Medium

Closest price

Prices available: {99, 149, 199, 299}. A customer's budget is 180. Find the best price within budget and the cheapest above it.

Input

budget 180

Expected output

Within budget: 149
Just above: 199

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        TreeSet<Integer> prices = new TreeSet<>(List.of(99, 149, 199, 299));
        System.out.println("Within budget: " + prices.floor(180));
        System.out.println("Just above: " + prices.higher(180));
    }
}

Within budget: 149 Just above: 199

How it works: floor = largest ≤ 180; higher = smallest > 180. Both O(log n).

P6Business problem

Unique pin codes served

Deliveries went to pin codes 410210, 400703, 410210, 400614, 400703. Print the distinct pin codes in sorted order and their count.

Input

5 deliveries

Expected output

3 areas: [400614, 400703, 410210]

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] pins = {410210, 400703, 410210, 400614, 400703};
        Set<Integer> served = new TreeSet<>();
        for (int p : pins) served.add(p);
        System.out.println(served.size() + " areas: " + served);
    }
}

3 areas: [400614, 400703, 410210]

How it works: a TreeSet gives distinct and sorted in one structure.

P7Business problem

Customers who stopped buying

Customers last month: {C1, C2, C3, C4}. This month: {C2, C4, C5}. Find churned customers (last month but not this month) and new ones.

Input

two months

Expected output

Churned: [C1, C3], new: [C5]

Show solution and explanation

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<String> last = Set.of("C1", "C2", "C3", "C4");
        Set<String> now = Set.of("C2", "C4", "C5");
        Set<String> churned = new TreeSet<>(last); churned.removeAll(now);
        Set<String> fresh = new TreeSet<>(now); fresh.removeAll(last);
        System.out.println("Churned: " + churned + ", new: " + fresh);
    }
}

Churned: [C1, C3], new: [C5]

How it works: two set differences answer two business questions; HashSet-backed removeAll is fast even for large sets.

P8Business problem

Leaderboard without ties lost

Players with scores: (Riya 92), (Om 85), (Kabir 92). Keep a sorted set by score (highest first) without losing either 92.

Input

3 players

Expected output

Kabir 92
Riya 92
Om 85

Show solution and explanation

import java.util.*;

public class Main {
    record Player(String name, int score) {}

    public static void main(String[] args) {
        Comparator<Player> byScoreThenName =
            Comparator.comparingInt(Player::score).reversed().thenComparing(Player::name);
        TreeSet<Player> board = new TreeSet<>(byScoreThenName);
        board.add(new Player("Riya", 92));
        board.add(new Player("Om", 85));
        board.add(new Player("Kabir", 92));
        for (Player p : board) System.out.println(p.name() + " " + p.score());
    }
}

Kabir 92 Riya 92 Om 85

How it works: the name tie-breaker makes the comparator return 0 only for truly identical players, so both 92s stay. (Records and method references are covered in Lessons 14.5 and 14.1; comparators in 11.8.)

Real-world scenario questions (asked in company interviews)

Set questions test whether you can match a requirement (uniqueness, order, nearest value) to the right implementation, and spot equality bugs.

EdTech · bugJunior

Rank list missing students

A rank list uses new TreeSet<>(byMarksDesc) where the comparator compares only marks. Two students with 92 marks: only one appears. Why, and how do you fix it?

The interviewer is checking: TreeSet uses the comparator for equality.

Show a strong answer

TreeSet treats compare == 0 as a duplicate, so the second 92 is rejected.
Add a tie-breaker: compare marks, then roll number (Comparator.comparing(...).thenComparing(...), Lesson 11.8).
Or keep students in a List and sort it; a set isn't needed for ranking.

Avoid: overriding equals to “fix” it. TreeSet never calls equals.

Healthcare · schedulingFresher

Next free appointment

A clinic stores free appointment times. Patients ask “give me the first slot at or after 4:20 pm”. Which collection and method?

The interviewer is checking: NavigableSet methods.

Show a strong answer

A TreeSet<LocalTime> of free slots; ceiling(LocalTime.of(16, 20)) returns the next slot in O(log n).
Booking removes the slot; cancelling adds it back.
With concurrent bookings, use ConcurrentSkipListSet or database locking so two patients can't take one slot.

Avoid: scanning a sorted list linearly on every request.

Marketing · dataFresher

Customers in both campaigns

Two lists of customer emails (Diwali sale and New Year sale), each with about 2 lakh entries and some duplicates. Marketing wants customers who responded to both. How?

The interviewer is checking: set intersection and normalisation.

Show a strong answer

Normalise emails (trim, lower-case), load one list into a HashSet, copy it and call retainAll with the other: O(n + m) on average.
Use a LinkedHashSet or TreeSet for the result if the report needs a stable order.
For data in a database, an SQL INTERSECT or join may be simpler.

Avoid: nested loops comparing every pair: 40 billion comparisons.

Platform · testsJunior

A test that fails on another machine

A unit test asserts that tagsSet.toString() equals "[java, sql, spark]". It passes locally but fails in CI after a JDK upgrade. Why?

The interviewer is checking: HashSet iteration order isn't a contract.

Show a strong answer

The set is a HashSet; its iteration order depends on hashing and internals, which may differ across versions or capacities.
Compare sets as sets: assertEquals(Set.of("java", "sql", "spark"), tagsSet), which uses equals and ignores order.
If the product needs an order, change the implementation to LinkedHashSet or TreeSet deliberately.

Avoid: “fixing” the expected string to the new order. It will break again.

HashSet, LinkedHashSet and TreeSet

Three ways to keep a guest list

What are HashSet, LinkedHashSet and TreeSet?

Words you'll meet in this lesson

Side by side

Using the three sets

HashSet

LinkedHashSet

TreeSet

The same input, three outputs

TreeSet's navigation methods

Set operations: union, intersection, difference

How TreeSet.add finds a place

Start at the root

Go left or right

compareTo returns 0? It's a duplicate

Reach an empty spot: insert

Rebalance

HashSet vs TreeSet: both views

Sets in real systems

Watch it with an example: booking a turf slot

1. Duplicate detection

2. Permissions and tags

3. Booking free slots

4. “Recent” lists without repeats

Fest entry desk

Three sets, one input

Worked examples: real problems, solved and traced in memory

Flag duplicate transaction IDs

Next free appointment

Recent searches, newest last, no repeats

Check yourself

Quick revision

Lesson 11.5 in one screen

Interview and viva questions

Practice problems

Count distinct words

Sorted distinct values

Is every required skill present?

Common and unique subjects

Closest price

Unique pin codes served

Customers who stopped buying

Leaderboard without ties lost

Real-world scenario questions (asked in company interviews)

Rank list missing students

Next free appointment

Customers in both campaigns

A test that fails on another machine