Pages

Topics

Tools

↑↓navigate↵openescclose
All guides

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.

~5 min readJava
#Set interface#HashSet#TreeSet#Java collections
Illustration of the Java Set interface showing a HashSet, TreeSet, and LinkedHashSet with unique elements and ordering differences.

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.

java
Set<String> names = new HashSet<>(); System.out.println(names.add("Alice")); // true System.out.println(names.add("Alice")); // false System.out.println(names.size()); // 1

The 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.

java
Set<Integer> numbers = new HashSet<>(); numbers.add(3); numbers.add(1); numbers.add(2); System.out.println(numbers); // order is not guaranteed

LinkedHashSet

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.

java
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().

java
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.

java
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.

ImplementationOrderingTime Complexity (add/remove/contains)Memory OverheadUse Case
HashSetNoneO(1) averageModerateGeneral-purpose, no ordering requirement
LinkedHashSetInsertion orderO(1) averageHigher than HashSetWhen iteration order must match insertion
TreeSetSorted (natural or comparator)O(log n)ModerateWhen you need sorted iteration or range queries
EnumSetEnum constant orderO(1)Very lowSets 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.

java
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, c

Intersection

retainAll keeps only the elements present in both sets.

java
Set<String> a = new HashSet<>(Set.of("a", "b")); Set<String> b = new HashSet<>(Set.of("b", "c")); a.retainAll(b); // a now contains b

Difference

removeAll removes all elements of the argument set from the receiver.

java
Set<String> a = new HashSet<>(Set.of("a", "b")); Set<String> b = new HashSet<>(Set.of("b", "c")); a.removeAll(b); // a now contains a

The 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.

java
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 correct

Concurrency 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:

java
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.

java
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:

java
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() or equals() changes after it is added to a HashSet, the set will behave incorrectly. The element can end up in the wrong bucket. Avoid mutating elements stored in a set.
  • Load factor: HashSet has 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(...) and Set.copyOf(...) create immutable sets. They reject null and cannot be modified. Set.of does not guarantee iteration order, so use LinkedHashSet if you need a fixed, predictable order. For an unmodifiable view of an existing set, use Collections.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 tools

Small utilities that fit Java work — they run entirely in this browser tab, so nothing you paste leaves your device.

All Java guides

More in Java

All Java guides

The guides filed next to this one in Java, in library order.