PublishedBEG-030-L03

Sets

Lesson 3 of 9
10 min read
Beginner

On This Lesson 11 topics

Lesson Overview
Learning Objectives
Written Explanation
Examples
Backend Insight
Common Mistakes
Exercises
Mini Challenge
Summary & Next Lesson
References
Practice

Lesson Overview

A list lets the same value appear as often as you like. Sometimes that is exactly wrong: the e-mail addresses in a mailing list, the ids of users who logged in today, the distinct words in a document. You want each value once, and you want to ask "is this one in there?" quickly.

That is the job of the Set. A set never holds two equal elements. You also meet its three main implementations: HashSet (fastest, no promised order), LinkedHashSet (keeps insertion order), and TreeSet (keeps elements sorted).

This lesson builds on Lessons 1 and 2, and on equals and hashCode from BEG-026: a set decides "same element" using them, which is why the broken HashSet demo in that module misbehaved.

Learning Objectives

By the end of this lesson you will be able to:

Create a Set<String> and use add, contains, remove, size, and isEmpty.
Use the boolean result of add to detect a duplicate.
Choose between HashSet, LinkedHashSet, and TreeSet by the ordering you need.
Remove duplicates from a list, with or without keeping the original order.
Combine two sets with addAll, retainAll, and removeAll (union, intersection, difference).
Explain why a set needs correct equals and hashCode on its elements.

Written Explanation

What a set promises

A Set is a collection with no duplicate elements. Adding a value that is already present changes nothing, and add tells you so by returning false.

java

Set<String> tags = new HashSet<>();
tags.add("java");    // true: it was new
tags.add("java");    // false: already there, set unchanged

A set has no positions. There is no get(i) on a Set, because the interface does not promise any order. You can ask contains(x), loop over it with for-each, and remove(x), but you cannot say "the third element".

Methods you will use:

Method	Meaning
`add(x)`	Adds `x` if absent. Returns `true` if the set changed
`contains(x)`	Is an equal element present?
`remove(x)`	Removes the equal element. Returns `true` if it was there
`size()`, `isEmpty()`	As for lists
`addAll(other)`	Union: adds every element of `other`
`retainAll(other)`	Intersection: keeps only elements that are also in `other`
`removeAll(other)`	Difference: removes every element that is in `other`

What "duplicate" means

Two elements are duplicates when equals says they are equal. For String, Integer, and other library classes, that works by content. For your own classes, you must override equals and hashCode consistently (BEG-026). If you skip that, two objects with the same data count as different, and the set quietly fills with "duplicates". When you see a HashSet or a HashMap key behave strangely, check those two methods first.

Three implementations, three orderings

Class	Order of iteration	Typical use
`HashSet`	None promised (it may even change over time)	Fast membership tests when order is irrelevant
`LinkedHashSet`	Insertion order	Unique values, in the order first seen
`TreeSet`	Sorted (natural order, or a comparator)	Unique values, always sorted

The LinkedHashSet documentation says its iteration order is insertion order, and contrasts that with the "unspecified, generally chaotic ordering" of HashSet. So never write code that depends on a HashSet's printed order, even if one run looks tidy.

Speed, in words: HashSet and LinkedHashSet do add, contains, and remove in roughly constant time for typical data, meaning the time barely grows with the set size. A TreeSet guarantees logarithmic time (the time grows very slowly as the set grows) and costs a little more per operation, in exchange for sorted order. Both are far better than scanning a list when you ask "is it in there?".

How HashSet achieves that speed is the subject of BEG-040 and BEG-041; today it is enough to know that it uses hashCode() first and equals second.

A TreeSet compares elements with compareTo (or a comparator) rather than equals. Two elements that compare as equal are treated as the same. This is rarely visible with strings and numbers, but it is the reason TreeSet needs elements that can be compared with one another. A TreeSet also offers extras such as first() and last(), available when the variable is declared as TreeSet rather than Set.

Removing duplicates from a list

The one-liner you will use constantly: build a set from the list.

java

List<String> deduped = new ArrayList<>(new LinkedHashSet<>(in));

Use LinkedHashSet when you want to keep the first-seen order, TreeSet when you want the result sorted, and HashSet only when order does not matter. The list-copy constructors new ArrayList<>(collection) and new HashSet<>(collection) accept any collection.

`null` and sets

HashSet and LinkedHashSet accept one null. A TreeSet using natural ordering throws a NullPointerException if you add null. In practice, avoid null elements anywhere in collections.

Examples

Example 1: `add` returns a signal (simple)

java

Set<String> tags = new HashSet<>();
System.out.println(tags.add("java"));
System.out.println(tags.add("java"));
tags.add("spring");
System.out.println(tags.size() + " " + tags.contains("spring") + " " + tags.contains("go"));
System.out.println(tags.remove("java") + " " + tags.remove("java"));

Output:

text

true
false
2 true false
true false

The second add returned false and the size stayed at 2 after adding spring. The first remove found java, the second did not.

Example 2: same data, three sets (practical)

java

List<String> in = List.of("pear", "apple", "pear", "fig", "apple", "kiwi");
Set<String> h = new HashSet<>(in);
Set<String> l = new LinkedHashSet<>(in);
Set<String> t = new TreeSet<>(in);
System.out.println("Hash:   " + h);
System.out.println("Linked: " + l);
System.out.println("Tree:   " + t);
List<String> deduped = new ArrayList<>(l);
System.out.println(deduped);

Output on the JDK 21 used for this lesson:

text

Hash:   [apple, pear, kiwi, fig]
Linked: [pear, apple, fig, kiwi]
Tree:   [apple, fig, kiwi, pear]
[pear, apple, fig, kiwi]

Each set holds four elements, since duplicates were dropped. The HashSet order looks arbitrary, and your Java version may print a different order; that is allowed. LinkedHashSet kept first-seen order and TreeSet sorted alphabetically. The last line is the de-duplicated list, still in first-seen order.

Example 3: cleaning e-mails and finding repeated words (realistic)

java

String[] raw = {"Ana@Mail.com", "omar@mail.com", "ana@mail.com ",
                "lina@mail.com", "omar@mail.com"};
Set<String> clean = new TreeSet<>();
int dups = 0;
for (String e : raw) {
    String norm = e.trim().toLowerCase();
    if (!clean.add(norm)) dups++;
}
System.out.println(clean + " duplicates=" + dups);

Set<String> seen = new HashSet<>();
Set<String> dupWords = new TreeSet<>();
for (String w : "to be or not to be".split(" ")) {
    if (!seen.add(w)) dupWords.add(w);
}
System.out.println(dupWords);

Output:

text

[ana@mail.com, lina@mail.com, omar@mail.com] duplicates=2
[be, to]

Two ideas from this example. First, normalize before adding: Ana@Mail.com and ana@mail.com only become duplicates after trim() and toLowerCase(). Second, the if (!seen.add(w)) idiom finds repeats in a single pass, using the return value of add.

Backend Insight

Sets appear wherever "have we seen this?" is the question: de-duplicating ids in a batch import, tracking which users have already been notified, checking a requested role against a set of allowed roles, or collecting distinct tags. A permissions check against a Set<String> of roles is fast and reads clearly, while the same check on a list scans every role.

Two design points matter for real systems. First, the definition of "same" is a business decision: is Ana@Mail.com the same customer as ana@mail.com? Normalize deliberately, as in Example 3. Second, when elements are your own classes, a correct equals and hashCode is not optional; it is what makes a set work. JPA entities in later modules have their own cautions here, which is why BEG-026 treated this contract so carefully.

Common Mistakes

Mistake 1: Using a `List` and checking `contains` before every `add`

Slow and noisy: if (!list.contains(x)) list.add(x);
Better: use a Set and call add(x), which already ignores duplicates.

Mistake 2: Relying on `HashSet` order

A HashSet promises no order. If a test passes only because the printed order happened to look right, it is a latent bug. Use LinkedHashSet or TreeSet when order matters.

Mistake 3: Expecting `get(i)` on a set

A Set has no index. If you need "the nth element", you want a List; if you want sorted access with first() and last(), declare the variable as TreeSet.

Mistake 4: Elements without `equals` and `hashCode`

A HashSet<Money> whose class overrides neither method will treat two equal-looking Money objects as different. Implement both together, as in BEG-026.

Mistake 5: Forgetting that `TreeSet` uses comparison, not `equals`

A TreeSet with a case-insensitive comparator treats Bob and bob as the same element, even though equals says they differ. This is intended, but surprising if you did not expect it.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. What does this print?

java

Set<Integer> s = new LinkedHashSet<>();
System.out.println(s.add(3) + " " + s.add(1) + " " + s.add(3) + " " + s);

Show solution A1

A1. true true false [3, 1]. The second add(3) is a duplicate; the set keeps insertion order, so it prints [3, 1].

A2. Which set class keeps elements sorted? Which keeps insertion order? Which promises no order?

Show solution A2

A2. TreeSet sorts; LinkedHashSet keeps insertion order; HashSet promises no order.

A3. Why can you not call get(1) on a Set?

Show solution A3

A3. A Set has no positions and promises no order, so the interface has no index-based method.

Level B: Application

B1. Given x = {b, c, d} and y = {c, d, e} (as TreeSet<String>), write code that produces the intersection, the union, and x minus y, without changing x or y. Give the three results.

Show solution B1

B1.

java

Set<String> both = new TreeSet<>(x); both.retainAll(y);
Set<String> any = new TreeSet<>(x); any.addAll(y);
Set<String> onlyX = new TreeSet<>(x); onlyX.removeAll(y);

Results: [c, d], [b, c, d, e], [b]. We copy x first because retainAll, addAll, and removeAll change the set they are called on.

B2. Write static boolean hasDuplicates(List<Integer> xs) using a Set, in one line if you can.

Show solution B2

B2.

java

static boolean hasDuplicates(List<Integer> xs) {
    return new HashSet<>(xs).size() != xs.size();
}

For [1, 2, 3] it returns false; for [1, 2, 1] it returns true.

B3. You have a list of product tags that must be shown without repeats, in the order a customer first typed them. Which class do you use, and how do you build the result?

Show solution B3

B3. A LinkedHashSet, which drops repeats and keeps first-seen order: List<String> shown = new ArrayList<>(new LinkedHashSet<>(typedTags));.

Level C: Challenge

C1. A TreeSet<String> is created with new TreeSet<>(String.CASE_INSENSITIVE_ORDER). Predict the output of System.out.println(ci.add("Bob") + " " + ci.add("bob") + " " + ci);, and explain the second value.

Show solution C1

C1. true false [Bob]. The comparator treats Bob and bob as equal (it returns 0), so the second add is rejected and the first spelling stays.

C2. A teammate says: "I put my Customer objects in a HashSet, and the same customer appears twice." List the two most likely causes and how you would check each.

Show solution C2

C2. (1) Customer overrides equals but not hashCode, or neither, so two equal customers hash differently or compare as different. Check by calling equals and hashCode on two customers with the same data. (2) The fields used by equals and hashCode differ slightly, such as a trailing space or different case in a name, or a field was changed after the object was added to the set. Check by printing both objects and the fields used in equals.

Mini Challenge

Write a program that reads this text (as a string in your code): the quick brown fox jumps over the lazy dog the end. Split it on spaces and build three things:

The set of distinct words, sorted alphabetically.
The set of distinct words in first-seen order.
The set of words that appear more than once, found in one loop with the if (!seen.add(w)) idiom.

Check your work: sorted output starts with brown, the first-seen set starts with the, and the repeated set contains only the.

Summary & Next Lesson

Key takeaways

A Set never holds duplicates; add returns false when the value was already there.
A set has no positions: use contains, remove, and iteration, not get(i).
HashSet: fast, no order. LinkedHashSet: insertion order. TreeSet: sorted.
Build a set from a list to remove duplicates; addAll, retainAll, and removeAll give union, intersection, and difference.
Equality for sets depends on equals and hashCode (or the comparator for a TreeSet).

Next lesson

The next lesson, "Maps", adds a value to each unique key: the phone-book container behind most lookup code.

Self-check

What does add return when the element is already in the set?
Which set would you pick for unique names that must stay sorted?
Which set keeps the order in which elements were first added?
How does new ArrayList<>(new HashSet<>(list)) change a list?
Why might two equal-looking objects both appear in a HashSet?

Show answers

false, and the set is unchanged.
TreeSet.
LinkedHashSet.
It removes duplicates, and the order of the result is not guaranteed.
Their class does not override equals and hashCode consistently, so the set treats them as different.

References

Oracle, Java SE 21 API, LinkedHashSet. Supports insertion-order iteration and the contrast with the unspecified ordering of HashSet; it also shows copying a set with order preserved.
Oracle, Java SE 21 API, TreeSet. Supports sorted iteration, guaranteed log(n) add/remove/contains, and comparison by compareTo or a comparator instead of equals.
Oracle, Java SE 21 API, Collection. Supports contains being defined with equals.
Oracle, Java SE 21 API, HashSet. Supports no guaranteed iteration order, constant-time add/remove/contains/size (assuming good hashing), one permitted null, and add returning false for an existing element.
Outputs were produced by compiling and running the examples with JDK 21. The HashSet order shown is one real run and is not guaranteed.

Practice

Apply this lesson with the module's lab, exercises and quiz.

Lab and exercises Quiz

Marking a lesson complete is optional and you can undo it any time. Your progress stays in this browser.

Continue to next lesson

Lesson Overview

Learning Objectives

Written Explanation

What a set promises

What "duplicate" means

Three implementations, three orderings

Removing duplicates from a list

null and sets

Examples

Example 1: add returns a signal (simple)

Example 2: same data, three sets (practical)

Example 3: cleaning e-mails and finding repeated words (realistic)

Backend Insight

Common Mistakes

Mistake 1: Using a List and checking contains before every add

Mistake 2: Relying on HashSet order

Mistake 3: Expecting get(i) on a set

Mistake 4: Elements without equals and hashCode

Mistake 5: Forgetting that TreeSet uses comparison, not equals

Exercises

Level A: Foundation

Level B: Application

Level C: Challenge

Mini Challenge

Summary & Next Lesson

Key takeaways

Next lesson

Self-check

References

Practice

`null` and sets

Example 1: `add` returns a signal (simple)

Mistake 1: Using a `List` and checking `contains` before every `add`

Mistake 2: Relying on `HashSet` order

Mistake 3: Expecting `get(i)` on a set

Mistake 4: Elements without `equals` and `hashCode`

Mistake 5: Forgetting that `TreeSet` uses comparison, not `equals`