Set
A Set is a collection with no duplicate elements and no position. It answers one question well: is this value in the set. Three implementations answer it with three orders and three costs, and the order is the part a program notices first: HashSet has no order at all, LinkedHashSet keeps the order of insertion and TreeSet keeps its elements sorted.
Three sets, three orders
The program adds the same four words in the same order to the three sets and prints each one:
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class Orders {
public static void main(String[] args) {
Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
for (String word : new String[] {"pear", "apple", "fig", "kiwi"}) {
hash.add(word);
linked.add(word);
}
Set<String> tree = new TreeSet<>(hash);
System.out.println("added pear apple fig kiwi");
System.out.println("hash " + hash);
System.out.println("linked " + linked);
System.out.println("tree " + tree);
System.out.println(hash.contains("fig") + " " + hash.size());
}
}
javac -Xlint:all Orders.java
java Orders
added pear apple fig kiwi
hash [apple, pear, kiwi, fig]
linked [pear, apple, fig, kiwi]
tree [apple, fig, kiwi, pear]
true 4
The linked set prints in the order the words went in, which is its promise. The sorted set prints alphabetically, which is the natural order of String. The hash set prints in the order its buckets happen to give, and that order is not a promise at all: it may differ between JDK versions and between two runs with different hash seeds, so code that depends on it is broken even when it looks stable.
Uniqueness and equals
A set decides whether an element is already there with equals and hashCode, so add answers a boolean and a duplicate changes nothing. Two records with the same components are equal, so the second one never enters:
import java.util.LinkedHashSet;
import java.util.Set;
public class Unique {
public static void main(String[] args) {
Set<String> names = new LinkedHashSet<>();
System.out.println(names.add("Ada"));
System.out.println(names.add("Ada"));
System.out.println(names.size());
Set<Point> points = new LinkedHashSet<>();
points.add(new Point(1, 2));
points.add(new Point(1, 2));
points.add(new Point(3, 4));
System.out.println(points);
System.out.println(points.contains(new Point(3, 4)));
}
}
record Point(int x, int y) {
}
javac -Xlint:all Unique.java
java Unique
true
false
1
[Point[x=1, y=2], Point[x=3, y=4]]
true
The first add answers true and the second false, and the size stays one. The two points with the same coordinates are one element, because the record implements equals and hashCode from its components; the third point is a different value and is kept. The last line is contains with a point built a moment ago: the set finds it, because a lookup compares values and not references.
Union, intersection and difference
The three set operations are three methods of Collection: addAll for the union, retainAll for the intersection and removeAll for the difference. Each changes the set it is called on, so the program copies first:
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class Operations {
public static void main(String[] args) {
Set<String> a = new TreeSet<>(Set.of("a", "b", "c", "d"));
Set<String> b = new TreeSet<>(Set.of("c", "d", "e"));
System.out.println("union " + union(a, b));
System.out.println("intersection " + intersection(a, b));
System.out.println("difference " + difference(a, b));
System.out.println("subset " + a.containsAll(Set.of("a", "b")));
}
static Set<String> union(Set<String> a, Set<String> b) {
Set<String> result = new TreeSet<>(a);
result.addAll(b);
return result;
}
static Set<String> intersection(Set<String> a, Set<String> b) {
Set<String> result = new TreeSet<>(a);
result.retainAll(b);
return result;
}
static Set<String> difference(Set<String> a, Set<String> b) {
Set<String> result = new TreeSet<>(a);
result.removeAll(b);
return result;
}
}
javac -Xlint:all Operations.java
java Operations
union [a, b, c, d, e]
intersection [c, d]
difference [a, b]
subset true
The results are printed in sorted order because the copy is a TreeSet; the same three methods on a HashSet would give the same elements in no order. The last line is containsAll, which asks whether every element of the argument is in the set.
TreeSet needs an order
A TreeSet keeps its elements in a red-black tree and compares them as they go in, so every element must be comparable with every other or a comparator must be given. A set of Object can hold a string and a number, and the second add fails when the tree compares them:
import java.util.Set;
import java.util.TreeSet;
public class NotComparable {
public static void main(String[] args) {
Set<Object> objects = new TreeSet<>();
objects.add("text");
try {
objects.add(Integer.valueOf(1));
} catch (ClassCastException e) {
System.out.println("TreeSet: " + e.getClass().getSimpleName());
}
Set<Object> hash = new java.util.HashSet<>();
hash.add("text");
hash.add(Integer.valueOf(1));
System.out.println(hash.size());
}
}
javac -Xlint:all NotComparable.java
java NotComparable
TreeSet: ClassCastException
2
The exception comes from String.compareTo receiving an Integer, and it happens at the add, not at the print. The hash set accepts both because it compares hash codes and then equals, and two objects of different classes are simply not equal. A TreeSet of a type that has no natural order takes a comparator in its constructor, which is lesson 076.
Which set to choose
HashSet is the default: constant-time add, remove and contains, and no order. LinkedHashSet costs a little more memory for the links that keep the insertion order, and its iteration is predictable, which is what a report wants. TreeSet adds order and range queries at logarithmic cost, and it needs comparable elements.
A set is also the right answer to a question about duplicates: a program that wants to know whether a list has repeated values can copy it into a HashSet and compare the two sizes. That is one line, and it is faster than the double loop it replaces.
Exercises
- Add the four words to a TreeSet with a reverse comparator and print the set.
- Put a list with a repeated value into a HashSet and print the two sizes.
- Compute the intersection of the words with the letters of the alphabet.
- Add a record to a TreeSet without a comparator and read the exception, then add one that implements Comparable.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a Set guarantee?
Answer
That no two elements are equal
Uniqueness is the one promise of the interface; order and cost belong to the implementation.
-
Which set keeps the insertion order?
Answer
LinkedHashSet
The links record the order the elements were added in.
-
Which method computes the intersection?
Answer
retainAll
retainAll keeps only the elements the argument also has.
-
What does this program print?
import java.util.LinkedHashSet; import java.util.Set; public class Q1 { public static void main(String[] args) { Set<String> set = new LinkedHashSet<>(); System.out.println(set.add("a")); System.out.println(set.add("a")); System.out.println(set.size()); } }Answer
true then false then 1
The second add is a duplicate, so it answers false and changes nothing.
-
What does this program print?
import java.util.Set; import java.util.TreeSet; public class Q2 { public static void main(String[] args) { Set<String> set = new TreeSet<>(Set.of("c", "a", "b")); System.out.println(set); } }Answer
[a, b, c]
The sorted set puts the strings in their natural order whatever the insertion order was.
-
What does this program print?
import java.util.HashSet; import java.util.Set; public class Q3 { public static void main(String[] args) { Set<String> a = new HashSet<>(Set.of("a", "b")); Set<String> b = new HashSet<>(Set.of("b", "c")); a.retainAll(b); System.out.println(a); } }Answer
[b]
Only b is in both sets, so retainAll leaves one element.
-
What does this program print?
import java.util.LinkedHashSet; import java.util.Set; public class Q4 { public static void main(String[] args) { Set<Point> set = new LinkedHashSet<>(); set.add(new Point(1, 2)); set.add(new Point(1, 2)); System.out.println(set.size()); System.out.println(set.contains(new Point(1, 2))); } } record Point(int x, int y) { }Answer
1 then true
Equal records are one element, and contains finds the equal object.
-
What does a TreeSet give when the elements cannot be compared?
Answer
ClassCastException at the add
The comparison happens while the element is inserted, and it fails there.
-
What does this program print?
import java.util.HashSet; import java.util.List; import java.util.Set; public class Q5 { public static void main(String[] args) { List<String> list = List.of("a", "b", "a", "c", "b"); Set<String> set = new HashSet<>(list); System.out.println(list.size() + " " + set.size()); } }Answer
5 3
The list keeps the duplicates and the set drops them, leaving three values.
-
Why can the order of a HashSet not be relied on?
Answer
It follows the hash buckets, which the JDK does not promise
The iteration order is an implementation detail, so code that depends on it is fragile.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev