When working with sets in Java, three primary implementations dominate: HashSet
, LinkedHashSet
, and TreeSet
. Each offers unique benefits depending on whether your priority is performance, insertion order, or sorting.
In this tutorial, we’ll compare these classes in depth, looking at their internal architecture, performance characteristics, use cases, and Java version enhancements.
📚 What Are These Sets?
Class | Definition |
---|---|
HashSet | Unordered collection backed by a HashMap |
LinkedHashSet | Insertion-ordered collection backed by a LinkedHashMap |
TreeSet | Sorted collection backed by a TreeMap (Red-Black Tree) |
All three implement the Set
interface and do not allow duplicates.
🧠 Internal Architecture
Feature | HashSet | LinkedHashSet | TreeSet |
---|---|---|---|
Backed By | HashMap | LinkedHashMap | TreeMap (RB Tree) |
Order | ❌ None | ✅ Insertion | ✅ Sorted |
Duplicate Check | equals() + hashCode() |
Same as HashSet | compareTo() or Comparator |
Null Support | ✅ One null | ✅ One null | ❌ Throws NPE unless Comparator handles null |
Thread-safe | ❌ | ❌ | ❌ |
⏱️ Performance Comparison
Operation | HashSet | LinkedHashSet | TreeSet |
---|---|---|---|
add() |
O(1) | O(1) | O(log n) |
remove() |
O(1) | O(1) | O(log n) |
contains() |
O(1) | O(1) | O(log n) |
iterator() |
O(n) | O(n) (in order) | O(n) (sorted) |
Note: TreeSet is slower but provides sorted views and range queries.
💡 When to Use What?
Scenario | Recommended Set |
---|---|
Fastest access, order doesn't matter | HashSet |
Unique elements + insertion order | LinkedHashSet |
Unique + Sorted + Range queries | TreeSet |
🔁 Code Examples
HashSet
Set<String> hashSet = new HashSet<>();
hashSet.add("B");
hashSet.add("A");
System.out.println(hashSet); // [A, B] or [B, A] (unordered)
LinkedHashSet
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("B");
linkedHashSet.add("A");
System.out.println(linkedHashSet); // [B, A]
TreeSet
Set<String> treeSet = new TreeSet<>();
treeSet.add("B");
treeSet.add("A");
System.out.println(treeSet); // [A, B]
🧬 Functional Java with Streams
List<String> names = List.of("b", "a", "c", "a");
Set<String> hash = names.stream().collect(Collectors.toSet());
Set<String> linked = names.stream().collect(Collectors.toCollection(LinkedHashSet::new));
Set<String> tree = names.stream().collect(Collectors.toCollection(TreeSet::new));
❌ Common Pitfalls
- ❌ Expecting order from
HashSet
- ❌ Using
TreeSet
without properComparable
orComparator
- ❌ Adding
null
toTreeSet
without handling comparison
📌 What's New in Java Versions?
Java 8
Collectors.toSet()
,removeIf()
,forEach()
- Lambda & Stream APIs for all sets
Java 9
Set.of(...)
for immutable sets
Java 10
var
support
Java 11–17
- Performance tweaks in core collections
Java 21
- GC and memory layout optimizations impacting all Set types
🔄 Legacy Refactoring Tips
Before:
List<String> list = Arrays.asList("z", "y", "x", "z");
List<String> noDupes = new ArrayList<>();
for (String s : list) {
if (!noDupes.contains(s)) noDupes.add(s);
}
After (LinkedHashSet):
List<String> noDupes = new ArrayList<>(new LinkedHashSet<>(list));
Or TreeSet for sorting:
Set<String> sortedUnique = new TreeSet<>(list);
🧠 Real-World Analogies
- HashSet: A box of unique balls thrown in without order.
- LinkedHashSet: A list of attendees signed in — one entry per person, in sign-in order.
- TreeSet: A sorted guest list in alphabetical order — no duplicates, always ordered.
❓ FAQ – Expert-Level Questions
-
Can these sets contain null values?
- HashSet and LinkedHashSet allow one
null
. TreeSet does not (unless comparator allows it).
- HashSet and LinkedHashSet allow one
-
Which set is fastest?
- HashSet is fastest for
add()
,remove()
, andcontains()
.
- HashSet is fastest for
-
Which set maintains order?
- LinkedHashSet (insertion order) and TreeSet (sorted order).
-
Can I use custom objects in sets?
- Yes. Override
equals()
/hashCode()
for HashSet and LinkedHashSet, andcompareTo()
for TreeSet.
- Yes. Override
-
How do TreeSet and HashSet differ in duplicates?
- HashSet uses hash equality, TreeSet uses comparison logic.
-
Are any of these sets thread-safe?
- No. Use
Collections.synchronizedSet()
or concurrent alternatives.
- No. Use
-
Can I create immutable sets from these?
Set<String> immutable = Set.of("A", "B");
-
What's the default capacity of HashSet?
- 16 with a load factor of 0.75
-
How to safely iterate and remove?
Iterator<String> it = set.iterator(); while (it.hasNext()) { if (condition) it.remove(); }
-
Which one should I use by default?
- Prefer
HashSet
, useLinkedHashSet
orTreeSet
when you need order.
- Prefer
🏁 Conclusion and Key Takeaways
HashSet
is your go-to for fast, unordered, duplicate-free collections.LinkedHashSet
shines when order matters without sorting.TreeSet
excels when natural or custom sorting is needed.- All sets enforce uniqueness but differ in order guarantees and performance.
💡 Pro Tip: Benchmark your use case — don’t blindly choose based on theory.