Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 12

HashSet vs. LinkedHashSet vs. TreeSet: Ordering and Performance

Recommended resources

Hello! Welcome back to our module on Java Collections & Problem-Solving.

In the last lesson, we dissected the practical performance differences between ArrayList and LinkedList, establishing that the best choice depends on a nuanced understanding of their internal data structures and the hardware they run on.

Today, we will apply this same analytical approach to the Set interface. The question "Compare HashSet, LinkedHashSet, and TreeSet" is a cornerstone of Java interviews. By the end of this lesson, you will be able to move beyond simple definitions and explain their crucial trade-offs in ordering and performance, grounding your answer in how they are built internally.

1. The Set Interface: The Uniqueness Contract

Before comparing the implementations, let's solidify the core principle of any Set: it's a collection that does not allow duplicate elements.

All three classes we're discussing today—HashSet, LinkedHashSet, and TreeSet—implement the Set interface. This means they all share this fundamental characteristic. The add(E element) method will return false if you try to add an element that is already present in the set.

How is uniqueness determined?

  • For HashSet and LinkedHashSet, uniqueness is determined by the hashCode() and equals() methods. Two objects o1 and o2 are considered duplicates if o1.hashCode() == o2.hashCode() and o1.equals(o2) is true.
  • For TreeSet, uniqueness is determined by the compareTo() method (from the Comparable interface) or the compare() method (from a Comparator). Two objects are duplicates if the comparison method returns 0.

2. A Tale of Three Sets: Comparison and Trade-offs

The best way to understand these classes is to compare them side-by-side. The following article provides an excellent overview with clear code examples and a summary table.

Difference and similarities between HashSet, LinkedHashSet and TreeSet in Java

Please read this article from GeeksforGeeks. It systematically breaks down the definition, internal workings, and behavior of each of the three Set implementations.

Read the sections introducing each Set (HashSet, LinkedHashSet, TreeSet) and pay close attention to the final 'Differences' table. This table is a concise summary perfect for interview preparation. Focus on how each Set handles ordering, its time complexity, and its internal data structure.

Now that you have a solid overview, let's consolidate and add some deeper-level insights that are crucial for senior-level interviews.

3. The Secret Ingredient: The Underlying Map

The single most important concept for explaining the behavior of these sets is understanding their internal data structure. Each Set implementation is secretly backed by a Map implementation.

  • HashSet is backed by a HashMap.
  • LinkedHashSet is backed by a LinkedHashMap.
  • TreeSet is backed by a TreeMap.

When you add an element to a Set, you are actually adding a new entry to the backing Map. The element you provide becomes the key in the map, and the value is a constant, dummy object that serves as a placeholder (internally, it's a private static final object called PRESENT).

This Set-is-a-Map concept explains everything:

Set Implementation Backing Map Ordering Performance (add, remove, contains) Nulls Allowed?
HashSet HashMap None. Iteration order is unpredictable. O(1) average time. Yes (one)
LinkedHashSet LinkedHashMap Insertion Order. Iterates in the order elements were added. O(1) average time (slightly slower than HashSet). Yes (one)
TreeSet TreeMap Sorted Order. Iterates in natural sorted order or by a Comparator. O(log n) time. No

Let's break down the implications.

HashSet: The Need for Speed

Because it's backed by a HashMap, HashSet offers the best performance for general-purpose use. When you add an element, its hashCode() is used to find a "bucket," and the element is placed there. This makes adding, removing, and checking for existence incredibly fast, assuming a good hash function. The trade-off is the complete lack of ordering.

Choose HashSet when: You need to store unique items and performance is critical, but you do not care about the iteration order.

LinkedHashSet: Order in the Court

This class extends HashSet and uses a LinkedHashMap as its backing store. A LinkedHashMap is a HashMap that also maintains a doubly-linked list running through all its entries. This list preserves the order in which elements were inserted. The result is a Set that is nearly as fast as HashSet for insertions and lookups, but with the added benefit of predictable, insertion-ordered iteration.

Choose LinkedHashSet when: You need the performance of a hash-based set but must also iterate through elements in the order they were added. A common use case is building a unique set of items from a stream of data where the original order is significant.

TreeSet: The Natural Order

TreeSet uses a TreeMap, which is a Red-Black Tree data structure. This structure keeps the elements (which are the keys of the TreeMap) in a sorted order at all times. Every time you add or remove an element, the tree rebalances itself to maintain the sort order and guarantee O(log n) performance for operations.

Because it needs to compare elements to sort them, it cannot handle null values (this would result in a NullPointerException).

A key advantage, often overlooked, is that TreeSet implements the NavigableSet interface. This provides powerful methods for searching that are not available in other sets.

Java Collections Interview Questions and Answers - New Version

The sorted nature of TreeSet enables more than just sorted iteration. Watch this short clip to see how NavigableSet methods allow for sophisticated searching.

Watch from 38:06 to 39:47. Note the methods like lower(), floor(), higher(), and ceiling(). Understanding these can help you stand out in an interview by suggesting TreeSet for problems involving range queries or finding nearest neighbors.

Choose TreeSet when: You need your unique elements to always be in sorted order, or you need to perform efficient range searches (e.g., "find all users with an age between 30 and 40").

4. Visual Summary and Interview Guide

This image provides a concise cheat sheet for remembering the core differences, which is perfect for last-minute interview prep.

HashSet vs TreeSet vs LinkedHashSet Comparison
This image summarizes the key characteristics, use cases, and pitfalls of each `Set` implementation. Note the clear guidance on "When to use it".

How to structure your interview answer:

  1. Start with the common ground: "All three implement the Set interface, which means they store unique elements."
  2. State the primary difference: "Their main difference lies in how they order their elements and their resulting performance characteristics."
  3. Detail each one:
    • "HashSet is the fastest, offering O(1) performance, but provides no ordering guarantees. It's the best general-purpose Set."
    • "LinkedHashSet also offers O(1) performance and maintains insertion order. It's ideal when you need a unique set that remembers the sequence in which items were added."
    • "TreeSet is the slowest at O(log n), but it keeps elements sorted at all times. This makes it perfect for when you need sorted data or need to perform range queries."
  4. Add the "pro" detail: "These behaviors are a direct result of their internal data structures: HashSet uses a HashMap, LinkedHashSet uses a LinkedHashMap, and TreeSet uses a TreeMap."
Test your understanding!

For each scenario, which Set implementation would you choose? Explain your reasoning.

  1. You are processing a large log file and need to collect all unique IP addresses that made a request. You just need the final count and the unique list; order doesn't matter.
  2. You are implementing a "Recently Played Songs" feature in a music app. Each song should appear only once in the list, and the list should be ordered from most recently played to least recently played.
  3. You are building a real-time leaderboard for a game. You need to store the unique scores of players, and the board must always display the scores in descending order.
Show answer
  1. HashSet. The key requirements are uniqueness and performance. Since order is not important, HashSet is the ideal choice due to its O(1) average time complexity for add and contains operations, making it the most efficient for processing a large file.
  2. LinkedHashSet. This scenario requires both uniqueness (a song shouldn't be in the list multiple times) and insertion order (to show the most recent first). LinkedHashSet is perfectly suited for this. When a song is played, you can remove it from the set and then add it back, which moves it to the end of the internal linked list, effectively marking it as the "most recent".
  3. TreeSet. The requirements are uniqueness and sorted order. A TreeSet can be initialized with a Comparator (e.g., Comparator.reverseOrder()) to keep the scores sorted in descending order automatically. This is far more efficient than sorting a list every time a new score is added. The O(log n) insertion time is a great trade-off for having a perpetually sorted collection.

Conclusion

You now have a deep, practical understanding of Java's core Set implementations. You can confidently explain not just what they do, but why they do it, based on their underlying data structures.

Key Takeaways:

  • The choice between HashSet, LinkedHashSet, and TreeSet is a trade-off between performance and ordering.
  • HashSet: Fastest performance (O(1)), no order. The default choice.
  • LinkedHashSet: Fast performance (O(1)), maintains insertion order.
  • TreeSet: Slower performance (O(log n)), maintains sorted order.
  • This behavior is a direct consequence of their backing Map implementations: HashMap, LinkedHashMap, and TreeMap, respectively.

In our next lesson, we will pivot from data structure theory to practical application. You will learn to "Solve the 'Two Sum' problem and its variations using a HashMap for efficient lookups," a problem that is a staple of coding interviews and a perfect demonstration of the power of hash-based collections.