HashSet vs TreeSet in Java

HashSet and TreeSet both store unique values, but they solve different problems. The main question is whether you need fast membership checks or sorted set behavior.

Quick answer

Use HashSet when you need uniqueness and fast contains, add, and remove operations without caring about order. Use TreeSet when sorted order, range queries, first/last values, or nearest-value navigation are part of the requirement.

For most backend code, HashSet is the default set. TreeSet is a deliberate choice when ordering is worth paying O(log n) for.

Main difference

HashSet is backed by hashing. It uses hashCode() and equals() to decide whether two values are the same.

TreeSet is backed by a sorted tree. It uses natural ordering or a Comparator to keep values sorted.

Set<String> hashSet = new HashSet<>();
hashSet.add("zebra");
hashSet.add("apple");
hashSet.add("mango");

System.out.println(hashSet); // order is not guaranteed

Set<String> treeSet = new TreeSet<>();
treeSet.add("zebra");
treeSet.add("apple");
treeSet.add("mango");

System.out.println(treeSet); // [apple, mango, zebra]

If a client or test depends on iteration order, HashSet is the wrong abstraction.

Performance comparison

Operation	HashSet	TreeSet
add	Average O(1)	O(log n)
contains	Average O(1)	O(log n)
remove	Average O(1)	O(log n)
Sorted iteration	Not guaranteed	O(n) in sorted order
First or last value	Not supported directly	O(log n) or better through NavigableSet
Range queries	Not supported directly	Supported with subSet, headSet, tailSet

HashSet can degrade when hash codes are poor or collisions are extreme, but it is still the normal default for membership checks.

When HashSet fits

Use HashSet when the workflow is about membership, deduplication, or fast lookup.

Set<Long> seenUserIds = new HashSet<>();

for (Long userId : incomingUserIds) {
    if (seenUserIds.add(userId)) {
        processFirstOccurrence(userId);
    }
}

This pattern is common when removing duplicates from IDs, checking whether a feature flag applies to a user, preventing duplicate notifications, or tracking values already processed inside one request.

The set does not promise display order. If you need stable output for users, sort the final result explicitly or use an ordered structure.

When TreeSet fits

Use TreeSet when sorted behavior is part of the business logic.

NavigableSet<Integer> scores = new TreeSet<>();
scores.add(82);
scores.add(95);
scores.add(70);

Integer nextAtLeast90 = scores.ceiling(90); // 95
Integer below80 = scores.lower(80);         // 70

TreeSet is useful for thresholds, leaderboard cutoffs, schedule times, sorted unique names, nearest values, and range checks.

It is also useful when you want deduplication and sorted iteration in one structure. Just remember that the sorting rule defines uniqueness for the tree. A comparator that treats two objects as equal will allow only one of them.

Equality and comparison rules

HashSet relies on equals and hashCode. If those methods are wrong, membership checks can behave incorrectly.

TreeSet relies on comparison. If natural ordering or a comparator says two values compare as 0, the set treats them as duplicates.

Set<String> names = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
names.add("API");
names.add("api");

System.out.println(names.size()); // 1

That may be exactly what you want for case-insensitive uniqueness, but it can surprise teams when the comparator ignores fields that should matter.

Null handling

HashSet allows a single null element.

TreeSet usually does not allow null with natural ordering because it cannot compare null to real values. A custom comparator can define null behavior, but that should be an explicit design choice.

In backend code, storing null in a set often makes logic harder to read. It is usually cleaner to filter nulls before building the set.

Choosing safely

Use HashSet when the main question is membership: have we seen this ID, does this permission exist, or should this duplicate be skipped? Use TreeSet when ordering is part of the requirement: find the next scheduled time, iterate names alphabetically, or query values within a range.

If the requirement says “unique and sorted,” decide whether sorting should happen continuously or only at output time. A TreeSet keeps data sorted as it changes. A HashSet plus a one-time sort can be simpler when writes are frequent and sorted output is rare.

Common mistakes

The first mistake is using TreeSet just to remove duplicates. If sorted behavior is not needed, HashSet is simpler and usually faster.

The second mistake is using HashSet and then expecting stable display order. If order matters, choose a structure that communicates that requirement.

The third mistake is writing a comparator that is inconsistent with the equality you actually care about. In a TreeSet, the comparator decides uniqueness.

The fourth mistake is ignoring mutation. If an object inside a set changes fields that affect hashCode, equals, or ordering, future lookups can fail. Prefer immutable values for set elements.

Related reading

Read Java equals and hashCode Explained for the equality rules behind HashSet, and Time Complexity of Java Collections for the broader complexity table. Read TreeMap vs HashMap in Java when you need key-value lookup with similar ordering decisions. Use the Big-O Cheat Sheet while reviewing collection choices. For the full sequence, browse the Java Collections Learning Path and the Topics map.