A Set stores each element at most once. The three implementations differ only in ordering and speed: hash (no order), linked hash (insertion order), tree (sorted).
Comparison
HashSet | LinkedHashSet | TreeSet | |
|---|---|---|---|
| Backed by | a HashMap (elements are keys) | a LinkedHashMap | a TreeMap (red-black tree) |
| Iteration order | Unspecified | Insertion order | Sorted (natural or Comparator) |
add / remove / contains | O(1) average | O(1) average | O(log n) |
null element | One allowed | One allowed | No (NullPointerException) |
| Needs | equals + hashCode | equals + hashCode | Comparable or a Comparator |
| Extra API | — | reversed(), getFirst() (Java 21) | first, floor, ceiling, headSet, subSet… |
Same input, three orders
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Integer> input = List.of(42, 7, 19, 7, 3, 42);
System.out.println("HashSet " + new HashSet<>(input));
System.out.println("LinkedHashSet " + new LinkedHashSet<>(input));
System.out.println("TreeSet " + new TreeSet<>(input));
Set<String> seen = new HashSet<>();
System.out.println(seen.add("x") + " " + seen.add("x")); // second add is rejected
}
}HashSet [19, 3, 7, 42]
LinkedHashSet [42, 7, 19, 3]
TreeSet [3, 7, 19, 42]
true falseTreeSet as a NavigableSet
import java.util.*;
public class Main {
public static void main(String[] args) {
TreeSet<Integer> ts = new TreeSet<>(List.of(10, 20, 30, 40, 50));
System.out.println(ts.first() + " " + ts.last());
System.out.println(ts.floor(25) + " " + ts.ceiling(25)); // <= 25, >= 25
System.out.println(ts.lower(20) + " " + ts.higher(20)); // < 20, > 20
System.out.println(ts.floor(5)); // none -> null
System.out.println(ts.headSet(30) + " " + ts.tailSet(30)); // [..30) and [30..]
System.out.println(ts.subSet(20, true, 40, true));
System.out.println(ts.descendingSet());
System.out.println(ts.pollFirst() + " -> " + ts);
}
}10 50
20 30
10 30
null
[10, 20] [30, 40, 50]
[20, 30, 40]
[50, 40, 30, 20, 10]
10 -> [20, 30, 40, 50]Trap: forgetting equals/hashCode
import java.util.*;
public class Main {
public static void main(String[] args) {
Set<Point> raw = new HashSet<>();
raw.add(new Point(1, 2));
raw.add(new Point(1, 2));
System.out.println("class without equals/hashCode: " + raw.size());
Set<PointRec> rec = new HashSet<>();
rec.add(new PointRec(1, 2));
rec.add(new PointRec(1, 2));
System.out.println("record: " + rec.size());
}
}
class Point { // uses Object's identity equals/hashCode
final int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
}
record PointRec(int x, int y) {} // records generate equals/hashCode from the fieldsclass without equals/hashCode: 2
record: 1import java.util.*;
public class Main {
public static void main(String[] args) {
Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.addAll(List.of("dog", "cat", "horse"));
System.out.println(byLength); // "cat" looked like a duplicate of "dog"
}
}[dog, horse]How does HashSet guarantee uniqueness?
HashSet vs TreeSet — which and why?
Can you add null to a TreeSet?