A HashSet in Java is a hash table that refuses to hold two elements that it considers to be the same. Two elements are the same when they are equal according to their own equals method, and the set finds them in roughly the constant time because it hashes each element to find the right bucket instead of comparing against everything that it holds.
The previous lesson in this module covered "Why Is HashMap the Default Choice for Key-Value Data?", and the next lesson in this module is about "How Do Comparators Sort Lists Any Way You Want?".
How does a set decide that two things are the same?
It does it by the equals contract, and not by the object identity. If your element type does not override equals and hashCode, then two objects with the identical contents are still two different elements as far as the set is concerned, and it will happily store both of them.
import java.util.HashSet;
import java.util.Set;
public class HashSetEqualsDemo {
static class Tag {
private final String name;
Tag(String name) {
this.name = name;
}
}
static class ProperTag {
private final String name;
ProperTag(String name) {
this.name = name;
}
@Override
public boolean equals(Object other) {
return other instanceof ProperTag tag && name.equals(tag.name);
}
@Override
public int hashCode() {
return name.hashCode();
}
}
public static void main(String[] args) {
Set<Tag> plain = new HashSet<>();
plain.add(new Tag("java"));
plain.add(new Tag("java"));
System.out.println("without equals and hashCode the set holds: " + plain.size());
Set<ProperTag> proper = new HashSet<>();
proper.add(new ProperTag("java"));
proper.add(new ProperTag("java"));
System.out.println("with equals and hashCode the set holds: " + proper.size());
}
}The output is this.
without equals and hashCode the set holds: 2
with equals and hashCode the set holds: 1Both of the tags hold the string "java", yet the first set has two elements. The second set has one, because the overrides let the set recognise that the two objects stand for the same thing. The same rule governs the keys of a HashMap, and it applies to the strings and the boxed numbers out of the box. That is why new HashSet<>(List.of("a", "b", "a")) has two elements without any extra work from you.
What does add return, and why should you care?
It returns a boolean that says whether the element was new. It is false when an equal element was already present. Most of the code ignores the result, but it is the natural way to notice a duplicate without paying for a separate contains call.
import java.util.HashSet;
import java.util.Set;
public class HashSetBasicsDemo {
public static void main(String[] args) {
Set<String> languages = new HashSet<>();
System.out.println("add java: " + languages.add("java"));
System.out.println("add python: " + languages.add("python"));
System.out.println("add java again: " + languages.add("java"));
System.out.println("size: " + languages.size());
System.out.println("contains java: " + languages.contains("java"));
System.out.println("contains ruby: " + languages.contains("ruby"));
System.out.println("remove java: " + languages.remove("java"));
System.out.println("remove java again: " + languages.remove("java"));
System.out.println("left inside: " + languages);
Set<String> frozen = Set.of("a", "b");
try {
frozen.add("c");
} catch (UnsupportedOperationException e) {
System.out.println("Set.of is fixed size: " + e.getClass().getSimpleName());
}
}
}The output is this.
add java: true
add python: true
add java again: false
size: 2
contains java: true
contains ruby: false
remove java: true
remove java again: false
left inside: [python]
Set.of is fixed size: UnsupportedOperationExceptionBoth of add and remove report whether they changed anything, which makes a set usable as a quick duplicate detector. The last line is a separate point. The set that is returned by Set.of is immutable, so an attempt to modify it throws UnsupportedOperationException rather than silently doing nothing.
How do the three set types differ?
All three of them enforce the uniqueness. They differ in the order that they hand their elements back to you, and that is the only thing to choose on.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class SetOrderingDemo {
public static void main(String[] args) {
List<String> words = List.of("delta", "alpha", "charlie", "bravo", "alpha");
Set<String> hashed = new HashSet<>(words);
Set<String> linked = new LinkedHashSet<>(words);
Set<String> sorted = new TreeSet<>(words);
System.out.println("HashSet order: " + hashed);
System.out.println("LinkedHashSet order: " + linked);
System.out.println("TreeSet order: " + sorted);
System.out.println("sizes: " + hashed.size() + " " + linked.size() + " " + sorted.size());
Set<String> unique = new LinkedHashSet<>(new ArrayList<>(words));
System.out.println("deduplicated but still in first-seen order: " + unique);
}
}The output is this.
HashSet order: [bravo, alpha, delta, charlie]
LinkedHashSet order: [delta, alpha, charlie, bravo]
TreeSet order: [alpha, bravo, charlie, delta]
sizes: 4 4 4
deduplicated but still in first-seen order: [delta, alpha, charlie, bravo]The LinkedHashSet line is the insertion order, and the TreeSet line is the alphabetical order. The HashSet line is neither, and that is not a bug. A hash set makes no promise about the order, and the order that you see depends on the hash codes of the elements and on the size of the table. Write the test, and not the order.
How do you remove the duplicates from a list?
You pass the list to a set and you take the result back as a list. Using LinkedHashSet keeps the first-seen order, which is usually what a person means by "remove the duplicates".
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
public class DedupDemo {
public static void main(String[] args) {
List<String> raw = new ArrayList<>(List.of("fig", "apple", "fig", "date", "apple"));
List<String> unique = new ArrayList<>(new LinkedHashSet<>(raw));
System.out.println("original: " + raw);
System.out.println("deduplicated: " + unique);
System.out.println("removed " + (raw.size() - unique.size()) + " duplicate(s)");
}
}The output is this.
original: [fig, apple, fig, date, apple]
deduplicated: [fig, apple, date]
removed 2 duplicate(s)Swapping LinkedHashSet for HashSet deduplicates just as well but it loses the order, and swapping it for TreeSet gives you the alphabetical order instead. The set that you pick here is a decision about the order that you want, and not about the duplicates that you want to lose.
How do you use a set with the other collections?
A set also answers questions about the other collections. The method containsAll tells you whether one collection holds every element of another, the method retainAll keeps only the elements that appear in both, and the method removeAll drops the ones that do not. Each of them changes the set in place, so you call retainAll on a copy if the original has to survive. These three methods are the clearest way to express "the common tags" or "the students in both groups" without writing a nested loop by hand.
A set is also a good companion to a list. When a list is long and you keep asking whether an item is in it, then you build a set from it once and you test against that instead. The list keeps the order and the duplicates that you need for the display, and the set answers the membership question quickly. That pairing shows up constantly in the real code, wherever the same data is both displayed and filtered.
When is a set the wrong tool?
A set cannot hold the duplicates and it cannot be indexed. If your data legitimately repeats, such as a list of transactions where the same customer appears several times, or a list of scores, then a set is the wrong shape. Building one silently drops the data that you meant to keep. Use a list for the raw data and a set only when you need a quick membership answer.
There is one more trap. The elements must not change while they are in the set, for exactly the same reason that the map keys must not. If you mutate an element so that its hash code changes, then the set can no longer find it. Treat the set elements as immutable.
Set rules in brief
- The duplicates are rejected based on equals and
hashCode, and not on the object identity. - The calls add and remove return whether they changed anything.
- A HashSet makes no promise about the iteration order. LinkedHashSet keeps the insertion order and TreeSet keeps the sorted order.
- The elements must not be mutated while they are in the set.
- A set cannot hold the duplicates and it cannot be indexed. That is a feature when you want the uniqueness and it is a bug when you do not.
Try it yourself: write a program that reads twelve words from a string array, adds each one to a HashSet and prints the result of every add call, so that you can see exactly which words were the repeats. Then build a LinkedHashSet from the same array and print it, checking that the first occurrence of each word comes first. Finally, print the size of all three of the set types and confirm that they agree.