Appearance
The Set Family: HashSet, LinkedHashSet, and TreeSet
Before diving into this article, there is one thing worth saying upfront: if you have not yet studied HashMap, LinkedHashMap, and TreeMap, go back and read those first. The reason is not just a formality. HashSet, LinkedHashSet, and TreeSet are literally built on top of those exact Map classes. Once you understand how the Maps work internally, the entire Set family becomes almost trivially simple because you realize it is the same thing, just with a dummy value glued on the side.
This article will connect all those dots and leave you with a complete picture of when to use each Set, how they work under the hood, what traps to avoid, and exactly how to answer every interview question on this topic.
What Is a Set and Why Does It Refuse Duplicates?
A Set is a collection of objects that does not allow duplicate values. You can only have one null value at most, and the elements inside a Set do not follow a guaranteed insertion order unless you specifically choose an implementation that preserves it.
Now here is the key question, the kind that might appear in an interview: why does a Set not allow duplicates? The answer is not just "because that is how Sets are defined." The answer is rooted in the actual implementation. Internally, every Set uses a Map. And in a Map, keys must be unique. So when you add an element to a Set, that element is stored as a key inside the internal Map. Since keys cannot repeat, elements in the Set cannot repeat either. That is the real reason, not a rule imposed from outside, but a natural consequence of the underlying data structure.
A few characteristics that distinguish Set from List are worth naming clearly. A Set has no index. You cannot call set.get(2) the way you would on a List. There is no positional access at all. This also means you cannot access elements by position. You iterate through the whole thing or use contains to check membership.
HashSet: A HashMap With a Dummy Value
Let us look at how HashSet is actually implemented. Open the source code of java.util.HashSet and you will find something like this:
java
public class HashSet<E> implements Set<E> {
// The internal map that does all the real work
private transient HashMap<E, Object> map;
// A single shared dummy object used as the value for every key
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
// The element goes in as a KEY. PRESENT is just a placeholder VALUE.
// If put() returns null, the key was new -> element was successfully added.
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}This is the entire secret. When you call set.add(12), the code internally calls map.put(12, PRESENT). The number 12 becomes a key in the HashMap. The value is just a meaningless dummy object called PRESENT, a single static new Object() that gets reused for every entry.
So a HashSet storing the values 1, 5, 9, 11, 13, and 41 is literally a HashMap where those six numbers are the keys and all six values point to the same useless PRESENT object. You are only interested in the keys. The value side is pure overhead that exists only because HashMap requires it.
This explains everything about HashSet behavior automatically. HashSet does not guarantee order because HashMap does not guarantee order. HashSet does not allow duplicates because HashMap does not allow duplicate keys. HashSet allows one null because HashMap allows one null key. HashSet gives you O(1) average time complexity for add, remove, and contains because HashMap gives you O(1) for those same operations. None of these are separate rules you need to memorize. They all fall out of the underlying HashMap.
java
import java.util.HashSet;
import java.util.Set;
public class HashSetDemo {
public static void main(String[] args) {
Set<Integer> numbers = new HashSet<>();
numbers.add(12);
numbers.add(11);
numbers.add(33);
numbers.add(4);
// Adding 12 again. Internally calls map.put(12, PRESENT).
// Since 12 is already a key, put() returns the old value, not null.
// So add() returns false. No exception. Just silently ignored.
boolean wasAdded = numbers.add(12);
System.out.println("Was 12 added again? " + wasAdded); // false
System.out.println(numbers); // Order is NOT guaranteed
}
}Notice that adding a duplicate does not throw an exception. It simply returns false and does nothing. The key was already present in the internal HashMap so there was nothing to override, and the operation just quietly fails. This is important behavior to know.
The Full Set Family and Their Internal Maps
Every Set implementation in Java wraps a corresponding Map class. This one diagram tells you most of what you need to know:
HashSet wraps HashMap (no order, O(1), allows 1 null)
LinkedHashSet wraps LinkedHashMap (insertion order, O(1), allows 1 null)
TreeSet wraps TreeMap (sorted order, O(log N), no nulls)The pattern is completely consistent. Whatever behavior the Map has, the Set inherits. Whatever the Map cannot do, the Set cannot do either.
java
import java.util.*;
public class SetFamilyComparison {
public static void main(String[] args) {
// HashSet: fastest, no ordering guarantees
Set<String> hashSet = new HashSet<>();
hashSet.add("Banana");
hashSet.add("Apple");
hashSet.add("Cherry");
hashSet.add("Mango");
System.out.println("HashSet: " + hashSet);
// Output order is unpredictable. Could be anything.
// LinkedHashSet: same speed, but preserves the order you inserted
Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Banana");
linkedHashSet.add("Apple");
linkedHashSet.add("Cherry");
linkedHashSet.add("Mango");
System.out.println("LinkedHashSet: " + linkedHashSet);
// Output: [Banana, Apple, Cherry, Mango] - always in insertion order
// TreeSet: sorted alphabetically by default, but slower O(log N)
Set<String> treeSet = new TreeSet<>();
treeSet.add("Banana");
treeSet.add("Apple");
treeSet.add("Cherry");
treeSet.add("Mango");
System.out.println("TreeSet: " + treeSet);
// Output: [Apple, Banana, Cherry, Mango] - always sorted
}
}Run this and you will see LinkedHashSet respects your insertion order exactly, while TreeSet alphabetizes everything automatically regardless of what order you added elements.
LinkedHashSet: Insertion Order Without Duplicates
LinkedHashSet internally wraps a LinkedHashMap. You already know from the LinkedHashMap article that it maintains a doubly linked list on top of the regular hash table structure. That linked list records the order in which keys were inserted. When you iterate over a LinkedHashMap, it walks that linked list, giving you elements in insertion order.
LinkedHashSet inherits this behavior completely. Your elements come back in the exact order you put them in.
java
import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSetDemo {
public static void main(String[] args) {
Set<Integer> scores = new LinkedHashSet<>();
scores.add(277);
scores.add(82);
scores.add(635);
scores.add(14);
scores.add(99);
// Iterating gives back elements in insertion order
for (int score : scores) {
System.out.print(score + " ");
}
// Output: 277 82 635 14 99
}
}One question that sometimes comes up is whether LinkedHashSet can maintain access order the way LinkedHashMap can, where the most recently accessed element moves to the end. The answer is no, and there is a specific reason. When LinkedHashSet creates its internal LinkedHashMap, it never passes the accessOrder flag as true. That boolean is hardcoded to false inside LinkedHashSet's constructor. Even if you wanted to enable access order, LinkedHashSet does not expose that option to you. So LinkedHashSet only ever gives you insertion order. That is the only mode it supports.
Time complexity for LinkedHashSet is O(1) amortized for add, remove, and contains, exactly the same as LinkedHashMap, exactly the same as HashMap.
TreeSet: Always Sorted, Uses TreeMap Internally
TreeSet wraps a TreeMap. TreeMap uses a red black tree internally, which is a type of self balancing binary search tree. Every insert and lookup in a red black tree takes O(log N) time because the tree always stays balanced.
Because TreeSet delegates to TreeMap, and TreeMap always keeps its keys in sorted order, TreeSet always keeps your elements in sorted order. You never have to call sort. You never have to think about it. Every element you add goes exactly where it belongs in the sorted sequence.
java
import java.util.TreeSet;
import java.util.Set;
import java.util.Comparator;
public class TreeSetDemo {
public static void main(String[] args) {
// Natural (ascending) order by default
Set<Integer> ascending = new TreeSet<>();
ascending.add(50);
ascending.add(10);
ascending.add(90);
ascending.add(30);
System.out.println("Ascending: " + ascending);
// Output: [10, 30, 50, 90]
// Descending order using a custom Comparator
Set<Integer> descending = new TreeSet<>(Comparator.reverseOrder());
descending.add(50);
descending.add(10);
descending.add(90);
descending.add(30);
System.out.println("Descending: " + descending);
// Output: [90, 50, 30, 10]
}
}Just like TreeMap accepts a custom Comparator in its constructor, TreeSet does too. You pass the Comparator when creating the TreeSet and from that point on, all elements are sorted according to your custom rule.
One critical limitation: TreeSet cannot store null values. If you try to add null to a TreeSet it throws a NullPointerException. This is again inherited from TreeMap, which cannot compare null with other keys using natural ordering.
Set Math Operations: Union, Intersection, and Difference
The Collection interface gives you three methods that map directly to mathematical set operations. These come up in interviews surprisingly often.
Think about two groups of friends. Set A is your friends from school: Alice, Bob, Charlie. Set B is your friends from work: Bob, Charlie, Diana. Union means everyone from both groups. Intersection means only people who appear in both groups. Difference means people in group A who are not in group B.
Java implements all three:
java
import java.util.HashSet;
import java.util.Set;
public class SetMathOperations {
public static void main(String[] args) {
Set<Integer> setA = new HashSet<>();
setA.add(12);
setA.add(11);
setA.add(33);
setA.add(4);
Set<Integer> setB = new HashSet<>();
setB.add(11);
setB.add(9);
setB.add(88);
setB.add(10);
setB.add(5);
setB.add(12);
// UNION: all unique elements from both sets combined
// addAll() adds every element of setB into a copy of setA
// Duplicates (11 and 12) are silently ignored
Set<Integer> union = new HashSet<>(setA);
union.addAll(setB);
System.out.println("Union: " + union);
// Contains: 4, 5, 9, 10, 11, 12, 33, 88 (all unique elements)
// INTERSECTION: only elements that appear in BOTH sets
// retainAll() removes everything from setA that is NOT in setB
Set<Integer> intersection = new HashSet<>(setA);
intersection.retainAll(setB);
System.out.println("Intersection: " + intersection);
// Contains: 11, 12 (the common elements)
// DIFFERENCE (A minus B): elements in setA that are NOT in setB
// removeAll() removes from setA everything that also appears in setB
Set<Integer> difference = new HashSet<>(setA);
difference.removeAll(setB);
System.out.println("Difference (A - B): " + difference);
// Contains: 33, 4 (what remains after removing 11 and 12)
}
}The important thing to notice is that all three operations work on copies, not on the originals. You create new HashSet<>(setA) first, then call the operation on that copy. If you called setA.addAll(setB) directly you would permanently modify setA, which is usually not what you want.
The methods to remember are:
addAll performs union. Every unique element from both sets ends up in the result.
retainAll performs intersection. Only elements present in both sets are kept; everything else is removed.
removeAll performs difference. Every element that appears in the second set gets removed from the first.
There is a fourth operation worth knowing: containsAll. This checks whether one set is a subset of another. If setA.containsAll(setB) returns true, it means every element of setB is already present in setA.
ConcurrentModificationException: The Trap You Must Know
This is one of the most common bugs beginners write with collections, and it is guaranteed to come up in interviews.
Imagine you are walking through a library collecting book titles, and while you are walking, someone keeps rearranging the shelves. That is essentially what happens when you try to modify a HashSet while iterating over it. The iterator in Java uses a fail fast mechanism. It tracks a modification count inside the collection. Every time you add or remove an element, that count increments. If the iterator detects that the count changed while it was in the middle of iterating, it immediately throws a ConcurrentModificationException.
java
import java.util.*;
public class ConcurrentModificationDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<>(Arrays.asList("A", "B", "C", "D", "E"));
// WRONG: This throws ConcurrentModificationException
// for (String s : set) {
// if (s.equals("B")) {
// set.remove(s); // Modifying the set while iterating!
// }
// }
// CORRECT FIX 1: Use Iterator.remove() which is safe
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
if (s.equals("B")) {
iterator.remove(); // The iterator knows about this removal
}
}
System.out.println("After iterator removal: " + set);
// CORRECT FIX 2: Use removeIf() introduced in Java 8
// Clean, readable, and internally safe
set.removeIf(s -> s.equals("C"));
System.out.println("After removeIf: " + set);
}
}The iterator.remove() approach works because the iterator itself performs the removal. It updates its own internal state to account for the change, so the modification count stays consistent from its perspective.
The removeIf() approach is cleaner and easier to read. Internally it handles the safe removal for you. If you are on Java 8 or later, this is the preferred way.
Note that ConcurrentModificationException is not just a multithreading problem. It happens even in a single thread if you naively modify a collection inside a for each loop. The name is misleading. It really means the collection was modified while an operation that depends on structural stability was in progress.
Thread Safety and What to Do About It
HashSet, LinkedHashSet, and TreeSet are all not thread safe. This again is a direct inheritance from their underlying Map classes. HashMap is not thread safe. LinkedHashMap is not thread safe. TreeMap is not thread safe. So none of the Set implementations are thread safe either.
What does not thread safe mean in practice? If two threads are using the same HashSet at the same time, one reading and one writing, you can get corrupted state, missed updates, or ConcurrentModificationException even without an explicit iterator.
Java gives you two options to handle this.
The first and recommended option for most concurrent code is to use ConcurrentHashMap.newKeySet():
java
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
public class ThreadSafeSetDemo {
public static void main(String[] args) {
// Creates a Set backed by ConcurrentHashMap
// Supports concurrent reads and writes without full locking
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
concurrentSet.add("Node_1");
concurrentSet.add("Node_2");
concurrentSet.add("Node_3");
// Multiple threads can safely add and read simultaneously
System.out.println(concurrentSet);
}
}This approach uses ConcurrentHashMap internally. ConcurrentHashMap uses fine grained locking where only small segments of the hash table are locked at a time, allowing multiple threads to operate concurrently without blocking each other unnecessarily.
The second option is Collections.synchronizedSet(), which wraps any Set with coarse grained locking:
java
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
public class SynchronizedSetDemo {
public static void main(String[] args) {
// Every method call acquires a lock on the entire set
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
syncSet.add("Task_1");
syncSet.add("Task_2");
// Warning: iteration still requires external synchronization
synchronized (syncSet) {
for (String task : syncSet) {
System.out.println(task);
}
}
}
}The synchronized wrapper approach is simpler but coarser. Every method call locks the entire set, meaning only one thread can do anything with it at any given moment. This is safe but can become a bottleneck when many threads need access simultaneously. For high concurrency scenarios, ConcurrentHashMap.newKeySet() scales much better.
The practical takeaway for interviews: when asked for the thread safe version of HashSet, the modern answer is ConcurrentHashMap.newKeySet(). The older answer is Collections.synchronizedSet(new HashSet<>()).
Iterating Over a Set
Since Sets have no index, your iteration options are slightly different from Lists. The standard approaches all work:
java
import java.util.*;
public class SetIterationDemo {
public static void main(String[] args) {
Set<String> fruits = new LinkedHashSet<>(Arrays.asList("Apple", "Mango", "Orange"));
// Method 1: Enhanced for loop
for (String fruit : fruits) {
System.out.println(fruit);
}
// Method 2: Iterator explicitly
Iterator<String> it = fruits.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
// Method 3: forEach with lambda (Java 8+)
fruits.forEach(fruit -> System.out.println(fruit));
// Method 4: Stream (Java 8+)
fruits.stream().forEach(System.out::println);
}
}All four methods work correctly. The enhanced for loop is the most readable for simple cases. The explicit Iterator is the right choice when you need to remove elements while iterating.
Choosing the Right Set
Think about what you actually need before picking an implementation.
When you need maximum performance for add, remove, and contains and do not care about any ordering at all, HashSet is your choice. It is the fastest and most memory efficient of the three. Most applications that just need to track membership or deduplicate a collection use HashSet.
When you need to preserve the order in which elements were added, use LinkedHashSet. The only cost over HashSet is slightly more memory for the linked list that tracks insertion order. Time complexity stays the same.
When you need elements to always be in sorted order and can accept O(log N) operations, use TreeSet. This is the right choice when you need to iterate in a predictable sorted sequence, find the smallest or largest element quickly, or work with range queries.
Full Comparison Table
Here is everything you need to compare the three implementations at a glance:
Feature HashSet LinkedHashSet TreeSet
---------------------------------------------------------------------
Internal structure HashMap LinkedHashMap TreeMap (Red Black Tree)
Iteration order None Insertion order Sorted order
add/remove/contains O(1) average O(1) average O(log N) guaranteed
Null elements 1 null allowed 1 null allowed No null (NullPointerException)
Custom comparator No No Yes (in constructor)
Thread safe No No No
Duplicates allowed No No NoInterview Questions This Topic Covers
Several questions come up repeatedly when interviewers ask about Sets in Java.
Why does Set not allow duplicate elements? Because it uses a Map internally, and Map keys must be unique. The element you add becomes a key in the Map, and since keys cannot repeat, neither can elements.
What is internally stored as the value in a HashSet? A static dummy object called PRESENT, a single new Object() instance shared across all entries. The real data lives in the keys only.
What is the difference between HashSet and LinkedHashSet? Both give O(1) performance and both use hashing. LinkedHashSet additionally maintains a doubly linked list to preserve insertion order. This costs slightly more memory but gives you predictable iteration order.
Why does TreeSet have O(log N) instead of O(1)? Because it uses a TreeMap, which uses a red black tree. Red black trees keep themselves balanced, which guarantees O(log N) worst case for all operations but makes O(1) impossible.
Can TreeSet store null? No. TreeMap cannot compare null with other keys during sorting, so it throws NullPointerException when you try to add null.
What happens when you try to add a duplicate to a Set? The add method returns false. No exception is thrown. The element is silently rejected because the key already exists in the underlying Map.
What is ConcurrentModificationException and when does it happen? It happens when you modify a collection while iterating over it using a standard iterator. The iterator detects that the structure changed and throws this exception. Fix it by using iterator.remove() or removeIf().
What is the thread safe version of HashSet? The modern answer is ConcurrentHashMap.newKeySet(). A secondary option is Collections.synchronizedSet(new HashSet<>()).
What are the three Set math operations and which methods implement them? Union uses addAll(), intersection uses retainAll(), and difference uses removeAll(). To check whether one set is a subset of another, use containsAll().
Why can LinkedHashSet not maintain access order like LinkedHashMap can? Because LinkedHashSet never exposes the accessOrder parameter when constructing its internal LinkedHashMap. That flag is hardcoded to false. Even if you wanted access order, there is no way to enable it through LinkedHashSet. Only insertion order is available.
Putting It All Together
The Set family is not a mystery once you see through the abstraction. HashSet is a HashMap where your data lives in keys and the values are irrelevant dummies. LinkedHashSet is a LinkedHashMap doing the same trick. TreeSet is a TreeMap doing the same trick. All the behavior you observe, the ordering, the performance, the null handling, the thread safety, flows directly from the underlying Map.
This is one of those cases in Java where understanding one layer of the implementation automatically explains three more things above it. If you spent time really understanding HashMap and how it handles hashing, bucketing, collision resolution, and resizing, then you already understand most of how HashSet works. The duplication of effort is minimal.
For practical code, default to HashSet when you just need to track unique elements. Upgrade to LinkedHashSet when insertion order matters to you. Reach for TreeSet when you need elements sorted at all times. And whenever concurrent access is involved, reach for ConcurrentHashMap.newKeySet() instead of any of the three.