Skip to content

Intermediate · The collections framework · topic 32 of 60 · 20 min

Sets: HashSet, LinkedHashSet and TreeSet

Explanation

A Set stores each element at most once. HashSet is the fastest and has no guaranteed order, LinkedHashSet keeps insertion order, and TreeSet keeps elements sorted. Uniqueness relies on equals and hashCode (or compareTo for TreeSet). contains is very fast for HashSet. addAll, retainAll and removeAll give union, intersection and difference.

Why sets?

Many questions are about uniqueness and membership: how many unique visitors came today, has this coupon already been used, which customers bought both products? A Set answers these directly. Adding an element that is already present simply does nothing (add returns false).

java
Set<String> visitors = new HashSet<>();
visitors.add("asha@mail.com");
visitors.add("ravi@mail.com");
boolean added = visitors.add("asha@mail.com");   // false: already there
System.out.println(visitors.size());            // 2
System.out.println(visitors.contains("ravi@mail.com"));   // true, very fast

Three implementations, three orders

SetOrder when you loopSpeed of add/containsNeeds
HashSetNo guaranteed orderO(1) averageequals and hashCode
LinkedHashSetInsertion orderO(1) averageequals and hashCode
TreeSetSorted (natural or Comparator)O(log n)compareTo / Comparator
java
List<String> cities = List.of("Pune", "Delhi", "Agra", "Pune", "Delhi");
System.out.println(new HashSet<>(cities));        // some order, e.g. [Delhi, Agra, Pune]
System.out.println(new LinkedHashSet<>(cities));  // [Pune, Delhi, Agra]
System.out.println(new TreeSet<>(cities));        // [Agra, Delhi, Pune]

TreeSet<Integer> fares = new TreeSet<>(List.of(450, 120, 980, 300));
System.out.println(fares.first() + " " + fares.last());   // 120 980
System.out.println(fares.ceiling(400));                     // 450 (smallest >= 400)

Set operations

java
Set<String> boughtTea = new HashSet<>(Set.of("Asha", "Ravi", "Meena"));
Set<String> boughtCoffee = Set.of("Ravi", "Kabir");

Set<String> both = new HashSet<>(boughtTea);
both.retainAll(boughtCoffee);          // intersection: [Ravi]
Set<String> either = new HashSet<>(boughtTea);
either.addAll(boughtCoffee);           // union: 4 names
Set<String> teaOnly = new HashSet<>(boughtTea);
teaOnly.removeAll(boughtCoffee);       // difference: [Asha, Meena]
These methods change the set they are called on, so copy first.

Sets of your own objects

Sets decide "is this already here?" with equals and hashCode (HashSet, LinkedHashSet) or with compareTo / a Comparator (TreeSet). Records get correct equals and hashCode automatically, which makes them ideal set elements. A TreeSet of your own class needs either a Comparable class or a Comparator passed to the constructor; otherwise adding the first element throws ClassCastException.

java
record Visit(String phone, java.time.LocalDate day) {}
Set<Visit> uniqueVisits = new HashSet<>();
uniqueVisits.add(new Visit("9876543210", java.time.LocalDate.of(2026, 10, 19)));
uniqueVisits.add(new Visit("9876543210", java.time.LocalDate.of(2026, 10, 19)));   // duplicate, ignored
System.out.println(uniqueVisits.size());   // 1

Set<String> unmodifiable = Set.of("UPI", "CARD", "COD");   // Java 9+: no duplicates or nulls allowed in the call

Set.of throws IllegalArgumentException if you pass the same element twice, and NullPointerException for null. Its iteration order is deliberately unspecified, so never rely on it.

Careful: A HashSet of your own objects only removes duplicates if the class overrides BOTH equals and hashCode (module 4). And never change an object's fields that affect hashCode while it is inside a HashSet: the set will no longer find it, and contains and remove silently fail.
Think of it like this: A Set is like the guest register at a wedding entrance where each family signs only once: if they come back after dinner, the register does not get a second line. A TreeSet is the same register kept in alphabetical order.
Tip: Turning a List into a Set is the quickest way to remove duplicates. Use LinkedHashSet if the first-seen order matters for display.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Sets: HashSet, LinkedHashSet and TreeSet · 1/6

Sets

In this lesson you will keep unique values with Sets.

Prefer a video by a teacher? Find free videos on “java set hashset linkedhashset treeset difference” on YouTube ↗

In real life: One coupon per customer

A food app gives a ₹100 welcome coupon once per phone number. The service keeps used phone numbers in a Set and checks contains before applying the coupon (in production this check is backed by the database with a unique constraint).

java
Set<String> couponUsedBy = new HashSet<>();
boolean apply(String phone) {
    return couponUsedBy.add(phone);   // true the first time, false afterwards
}

Practice (0/3 done)

Task 1 · Question

What does this print? Set<Integer> s = new TreeSet<>(List.of(5, 3, 5, 1, 3)); System.out.println(s);

Task 2 · Code · Python

The same idea in Python, which runs here: write common_customers(a, b) that returns the sorted list of names present in both lists, without duplicates (the intersection).

Task 3 · Practice

Given two lists of student roll numbers (those who attended Monday and those who attended Tuesday), print: students who attended both days, students who attended at least one day (sorted), and students who attended only Monday. Use HashSet and TreeSet with retainAll, addAll and removeAll.

Quick quiz

Question 1

1.Which Set keeps insertion order?

Question 2

2.What does set.add(x) return if x is already present?

Question 3

3.Which method gives the intersection when called on a copy of set A?

Question 4

4.TreeSet operations like add and contains take…

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

Which Set keeps insertion order?

Answer: LinkedHashSet

LinkedHashSet remembers insertion order.

What does set.add(x) return if x is already present?

Answer: false

add returns false when nothing changed.

Which method gives the intersection when called on a copy of set A?

Answer: retainAll(B)

retainAll keeps only elements also in B.

TreeSet operations like add and contains take…

Answer: O(log n)

TreeSet is a balanced tree (red-black).

What does HashSet::insert return when the value is already present?Related

Answer: false

insert returns false if the set already had the value.

From HashMap and HashSet

Default Object.equals behaves like…Related

Answer: ==, same object only

Without overriding, equals checks identity.

From toString, equals, hashCode and records

What does HashSet<T>.Add return for a value already in the set?Related

Answer: false

false means nothing was added.

From Collections: List, Dictionary, HashSet, Queue and Stack

a.compareTo(b) returns a negative number. What does it mean?Related

Answer: a comes before b

Negative means a sorts first.

From Sorting with Comparable and Comparator

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Maps: HashMap, LinkedHashMap and TreeMap →

Next steps

  1. 3 more topics in “The collections framework” before its exam: Maps: HashMap, LinkedHashMap and TreeMap, Sorting with Comparable and Comparator, Queues, stacks and priority queues.
  2. Module 7 exam: The collections framework · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Lambdas, streams and files. 60 topics left in the course before the final exam.

← Previous: Collections overview and List