HashSet vs TreeSet.

Hook: Interviewers love this question because both classes are “sets,” but they solve different problems: one is built for speed, the other for sorting.

Question: What is the difference between HashSet and TreeSet in Java?

Answer: HashSet stores unique elements and gives fast average-time operations, but it does not keep elements in any order. TreeSet also stores unique elements, but it keeps them sorted either by natural order or by a provided Comparator (a rule for comparing objects). Because of that sorting, TreeSet is slower than HashSet for add/search/remove.

Interview-Ready Answer: “I use HashSet when I want the fastest set operations and I do not care about order. I use TreeSet when I need the elements kept in sorted order or I need range queries like first, last, or ‘all values between A and B’. The trade-off is performance: HashSet is usually O(1) on average, while TreeSet is O(log n) because it is backed by a balanced tree.”

What they are

HashSet is a set implementation backed by a HashMap (a hash table that uses a hash code to find buckets quickly). TreeSet is a set implementation backed by a TreeMap, which uses a TreeMap’s red-black tree (a self-balancing binary search tree that keeps lookup paths short).

How HashSet works under the hood

1. You call add(x).
2. Java asks the element for its hashCode() to pick a bucket.
3. If the bucket is empty, the element is stored immediately.
4. If other elements are already there, Java checks equals() to avoid duplicates.
5. Because it mostly jumps straight to the right bucket, average insertion and lookup are very fast.

Important detail: in modern Java, heavily-collided buckets can be treeified, so the worst collision path is better than old versions. Still, the usual interview answer is O(1) average for HashSet.

How TreeSet works under the hood

1. You call add(x).
2. Java compares x with existing elements using natural ordering (Comparable) or a supplied Comparator.
3. It walks left or right down the red-black tree until it finds the right place.
4. The tree rebalances itself after inserts and deletes so it stays roughly balanced.
5. Because the structure is ordered, operations stay predictable at O(log n).

A subtle point: in a TreeSet, two values are considered “the same” if the comparator says they compare as zero. That means uniqueness is based on comparison, not just equals().

When to use which one

• Use HashSet when you want fast membership checks like “Have I seen this ID before?”
• Use TreeSet when you need sorted output, the smallest/largest element, or range queries such as subSet, headSet, and tailSet.
• If you only need insertion order, neither is the right answer; use LinkedHashSet.

Comparison table

Complexity and practical numbers

• HashSet: average O(1); memory is a bit higher because the hash table uses buckets and resizing. The default load factor is 0.75, which means it grows when about 75% full.
• TreeSet: O(log n) for add/remove/contains. For 1,000,000 items, that means roughly around 20 comparison steps instead of scanning everything.
• For small sets, the difference may not matter. For large hot-path code, the faster average lookup of HashSet is often a big win.

Important edge cases

• HashSet uses both hashCode() and equals(), so if you override one, you should override the other too.
• TreeSet uses ordering. If your Comparator is inconsistent with equals(), you can get surprising duplicates or missing elements.
• TreeSet typically rejects null because it must compare elements to sort them.

Memory Hook: Think of HashSet as a messy locker room with labels for fast finding, and TreeSet as a librarian who alphabetizes every book before shelving it.

Real-world story

Scenario: A checkout service in an e-commerce app receives coupon codes and gift-card IDs during payment.

1. The service uses a HashSet to quickly detect duplicate coupon codes in the same request, because it only needs fast “have I seen this?” checks.
2. Another part of the system uses a TreeSet to keep active discount thresholds sorted, so it can quickly find the best applicable rule for an order amount.
3. When the team accidentally used a TreeSet for every incoming coupon check, CPU usage rose and latency increased because every insert had to maintain sorted order.

What goes wrong: A developer replaces a HashSet with a TreeSet “because sets should be ordered.” The checkout API starts taking longer under load, and logs show more time spent in comparison methods. Users notice slower payment pages, and the business sees more abandoned carts. The bug is not a crash; it is a performance regression caused by choosing sorted order where only uniqueness was needed.

Follow-up & Tricky Questions:

• How does HashSet decide uniqueness? It uses hashCode() to find a bucket and then equals() to check whether the element is already present.
• Why is TreeSet slower than HashSet? Because every operation must walk a sorted tree and keep it balanced, which costs O(log n) instead of average O(1).
• Can TreeSet store custom objects? Yes, if the objects implement Comparable or you supply a Comparator that knows how to order them.
• What is the difference between LinkedHashSet, HashSet, and TreeSet? LinkedHashSet preserves insertion order, HashSet gives no order, and TreeSet keeps sorted order.
• What methods exist only in TreeSet? Navigation methods such as first(), last(), lower(), higher(), floor(), ceiling(), plus range views like subSet().
• Tricky: If a comparator says two elements are equal, but equals() says they are not, what happens? In TreeSet, the comparator wins for set membership, so one of those values may be silently dropped as a duplicate.
• Tricky: Does HashSet keep insertion order if the hash values happen to be sorted? No. Any apparent order is accidental and should not be relied on.
• Tricky: Can TreeSet contain null? With natural ordering, no—because it needs to compare elements. A custom comparator could theoretically handle nulls, but you should be explicit and careful.

Common Mistakes:

• Using TreeSet when only uniqueness is needed. Correction: choose HashSet for faster average performance.
• Assuming HashSet has stable order. Correction: it is unordered; if you need predictable iteration order, use LinkedHashSet.
• Forgetting comparator consistency. Correction: in TreeSet, make sure your comparator defines a total order and does not accidentally collapse different values.
• Confusing equals() with comparison. Correction: HashSet relies on equals() plus hashCode(), while TreeSet relies on ordering.

Memory Hook: Hash = fast, Tree = sorted. Or picture it as: HashSet is a quick drawer, TreeSet is an alphabetized shelf.

Cheat Sheet:

• HashSet = unique elements, no order, average O(1).
• TreeSet = unique elements, sorted order, O(log n).
• HashSet allows one null; TreeSet usually does not.
• TreeSet supports range and navigation operations.
• Use HashSet for speed; use TreeSet for sorted views.

Practice Tasks:

• Create a set of integers and print them from both HashSet and TreeSet to see the order difference.
• Write a custom object with hashCode() and equals(), then store it in a HashSet.
• Build a TreeSet with a custom Comparator and test what happens when the comparator returns 0 for different objects.