Java Set Interface: Implementation Choices and Behavior
Understand the Java Set interface contract and how HashSet, LinkedHashSet, TreeSet, and EnumSet differ in ordering, null handling, and concurrency behavior.

Java's Set interface models a collection of unique elements. Unlike List, which permits duplicates and normally preserves insertion order, Set makes uniqueness its core contract. The interface itself says nothing about ordering, iteration behavior, or performance; those decisions are made by the concrete implementation. This article covers the contract, the standard implementations, and the trade-offs that should drive your selection.
What the Set Interface Guarantees
The Set interface extends Collection and adds no new methods. A set cannot contain two elements e1 and e2 such that e1.equals(e2) is true. For hash-based implementations, elements must also follow the hashCode contract: equal objects must have equal hash codes. When you call add with an element that is already present, add returns false and the set remains unchanged.
Set<String> names = new HashSet<>();
System.out.println(names.add("Alice")); // true
System.out.println(names.add("Alice")); // false
System.out.println(names.size()); // 1The interface does not guarantee iteration order. Some implementations maintain a predictable order; others do not. If your code depends on a specific iteration order, choose an implementation that provides it or sort the elements explicitly.
Core Implementations and Their Behavior
The JDK provides several Set implementations, each with distinct characteristics. The most commonly used are HashSet, LinkedHashSet, and TreeSet. There is also EnumSet for enum types and specialized concurrent variants.
HashSet
HashSet is backed by a hash table (actually a HashMap instance). It offers constant-time average performance for add, remove, and contains, assuming a good hash function distributes elements evenly. It makes no guarantees about iteration order; the order can change when the set is resized or elements are rehashed.
Set<Integer> numbers = new HashSet<>();
numbers.add(3);
numbers.add(1);
numbers.add(2);
System.out.println(numbers); // order is not guaranteedLinkedHashSet
LinkedHashSet extends HashSet and maintains a doubly linked list through all entries. This list defines iteration order as the order in which elements were inserted. Re-inserting an element does not change its position. LinkedHashSet costs slightly more memory than HashSet because of the linked list, but its iteration order is predictable.
Set<String> ordered = new LinkedHashSet<>();
ordered.add("first");
ordered.add("second");
ordered.add("third");
System.out.println(ordered); // [first, second, third]TreeSet
TreeSet is backed by a red-black tree. It stores elements in sorted order, either by natural ordering (if the elements implement Comparable) or by a Comparator supplied when the set is created. add, remove, and contains take O(log n) time. TreeSet also provides navigation methods such as first(), last(), floor(), and ceiling().
Set<Integer> sorted = new TreeSet<>();
sorted.add(5);
sorted.add(1);
sorted.add(3);
System.out.println(sorted); // [1, 3, 5]EnumSet
EnumSet is a specialized set for enum types. It is implemented as a bit vector, making it compact and fast. It is abstract, so you create instances through static factory methods such as EnumSet.of(...) or EnumSet.allOf(...). Use it whenever you need a set of enum constants.
enum Status { NEW, IN_PROGRESS, DONE }
Set<Status> active = EnumSet.of(Status.NEW, Status.IN_PROGRESS);Choosing the Right Set Implementation
The choice of implementation depends on what you need beyond uniqueness. The table below summarizes the key differences.
| Implementation | Ordering | Time Complexity (add/remove/contains) | Memory Overhead | Use Case |
|---|---|---|---|---|
HashSet | None | O(1) average | Moderate | General-purpose, no ordering requirement |
LinkedHashSet | Insertion order | O(1) average | Higher than HashSet | When iteration order must match insertion |
TreeSet | Sorted (natural or comparator) | O(log n) | Moderate | When you need sorted iteration or range queries |
EnumSet | Enum constant order | O(1) | Very low | Sets of enum constants |
Use HashSet when you only need uniqueness and do not care about order. Use LinkedHashSet when you need to preserve the order in which elements were added, for example to maintain a history of unique events. Use TreeSet when you need sorted iteration or range operations such as "find all elements greater than X." Use EnumSet for enum values; it is faster and more memory-efficient than general-purpose sets for that case.
Common Operations and Their Costs
The Set interface inherits bulk operations from Collection that support set algebra.
Union
To compute the union of two sets, use addAll. It adds all elements from the argument set to the receiver, ignoring duplicates.
Set<String> a = new HashSet<>(Set.of("a", "b"));
Set<String> b = new HashSet<>(Set.of("b", "c"));
a.addAll(b); // a now contains a, b, cIntersection
retainAll keeps only the elements present in both sets.
Set<String> a = new HashSet<>(Set.of("a", "b"));
Set<String> b = new HashSet<>(Set.of("b", "c"));
a.retainAll(b); // a now contains bDifference
removeAll removes all elements of the argument set from the receiver.
Set<String> a = new HashSet<>(Set.of("a", "b"));
Set<String> b = new HashSet<>(Set.of("b", "c"));
a.removeAll(b); // a now contains aThe time complexity of these operations depends on the underlying implementation. For HashSet, addAll is O(n) average, where n is the size of the argument set, because each insertion is O(1) average. For TreeSet, addAll is O(n log n) because each insertion is O(log n).
Null Elements and Equality Semantics
The Set interface does not require implementations to accept null. HashSet and LinkedHashSet allow one null element. TreeSet and ConcurrentSkipListSet reject null because a sorted structure cannot compare null with other elements. EnumSet rejects null because enum constants are non-null by design.
Equality semantics matter when you store custom objects. In a set, two elements are duplicates when equals returns true. For HashSet, the hash code determines which bucket to inspect, and equals is then used to confirm whether the candidate is already present. If you override equals without hashCode, logically equal objects can land in different buckets and the set will not work correctly.
class Person {
String name;
// equals and hashCode based on name
}
Set<Person> people = new HashSet<>();
people.add(new Person("Alice"));
System.out.println(people.contains(new Person("Alice"))); // true if hashCode is correctConcurrency and Thread Safety
None of the basic Set implementations are thread-safe. If multiple threads access a HashSet or TreeSet and at least one thread modifies it, you must synchronize externally. The simplest approach is to wrap the set with Collections.synchronizedSet:
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());This serializes access to every method, which can become a bottleneck. For higher concurrency, ConcurrentHashMap.newKeySet() returns a thread-safe set backed by a concurrent map. It is a good choice when the set is read frequently and modified occasionally. Note that ConcurrentHashMap.newKeySet() does not allow null elements. For a thread-safe sorted set, ConcurrentSkipListSet provides expected O(log n) performance.
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();Using Set for Deduplication and Set Operations
A common use of Set is deduplication. A HashSet works in a simple loop, but streams provide a declarative alternative:
List<String> withDuplicates = List.of("a", "b", "a", "c");
Set<String> unique = withDuplicates.stream().collect(Collectors.toSet());Collectors.toSet() does not guarantee a particular implementation. If you need insertion order, use Collectors.toCollection(LinkedHashSet::new).
Set operations are also useful for filtering. For example, to find elements in one list that are not in another, convert the second list to a Set and use removeAll or contains. This is more efficient than a nested loop with large collections.
Edge Cases and Maintenance Considerations
- Mutable elements: If an element's
hashCode()orequals()changes after it is added to aHashSet, the set will behave incorrectly. The element can end up in the wrong bucket. Avoid mutating elements stored in a set. - Load factor:
HashSethas a default load factor of 0.75. If you know the approximate size in advance, you can pre-size the set to avoid rehashing overhead:new HashSet<>(expectedSize). - Unmodifiable sets:
Set.of(...)andSet.copyOf(...)create immutable sets. They rejectnulland cannot be modified.Set.ofdoes not guarantee iteration order, so useLinkedHashSetif you need a fixed, predictable order. For an unmodifiable view of an existing set, useCollections.unmodifiableSet(...).
If you code against the Set interface rather than a concrete class, you can swap implementations without changing the rest of your code. Choose the implementation by what you need beyond uniqueness: predictable order, sorted iteration, concurrency, or memory efficiency.
Try matching browser tools
All toolsSmall utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.
Related Java guides
All Java guidesJava Final Keyword: Usage and Behavior
How Java's final keyword works for variables, methods, and classes, with practical examples and decision guidance for using it.
Java Final Variable: Syntax, Behavior, and Use Cases
Understand what a final variable in Java means, how initialization works, and when to use it for constants, immutability, and clearer code.
Java Duration vs Period: When to Use Each
java duration vs period: Compare Java Duration and Period to handle time-based and date-based calculations correctly. Learn syntax, conversion, and pitfalls.
Instance vs Static Variables in Java: Key Differences
Understand the difference between instance and static variables in Java, including memory, lifecycle, and when to use each.
More in Java
All Java guidesThe guides filed next to this one in Java, in library order.