Detailed explanation
HashSet, LinkedHashSet, and TreeSet implement Java’s Set interface, so they represent collections without duplicate elements. Their main differences are iteration order, performance, and how they identify duplicates. For input List.of(3, 1, 2), HashSet has no guaranteed iteration order, LinkedHashSet iterates as [3, 1, 2], and TreeSet iterates as [1, 2, 3]. An observed HashSet order is not a contract: it may change as elements, capacity, or implementation details change.
HashSet is backed by a HashMap, which stores set elements as map keys. It uses hashCode() to locate a bucket and equals() to distinguish keys within it. Adding, removing, and checking membership take expected O(1) time when hashes are well distributed; this is not an unconditional worst-case guarantee. Modern Java implementations can convert heavily collided buckets into tree structures under suitable conditions. LinkedHashSet uses a LinkedHashMap backing structure that also maintains a doubly linked list of entries. This preserves insertion order while retaining expected O(1) basic operations, at the cost of extra memory. Adding an existing element through add() does not move it; removing and adding it again places it last.
TreeSet is backed by a TreeMap implemented as a red-black tree. It maintains elements in their natural order, usually defined by Comparable, or according to a supplied Comparator. Its add(), remove(), and contains() operations take O(log n) time. Comparisons returning zero identify duplicates, even when equals() returns false, so ordering should be consistent with equals() to satisfy the general Set contract. TreeSet also supports navigation and range operations such as floor(), ceiling(), and subSet().
HashSet and LinkedHashSet allow one null element. TreeSet with natural ordering rejects null; a comparator that explicitly supports null can permit it. None of these implementations is inherently thread-safe. Choose HashSet for membership checks without ordering requirements, LinkedHashSet for predictable insertion-order traversal, and TreeSet for sorted traversal or range queries. Interviewers typically expect these trade-offs, plus awareness that mutable fields used in hashing or comparison can break reliable lookup after insertion.
Key points to remember
- HashSet: no iteration-order guarantee; expected O(1) add, remove, and contains.
- LinkedHashSet: insertion-order iteration using linked entries; expected O(1) basic operations with extra memory overhead.
- TreeSet: sorted iteration using a red-black tree; O(log n) add, remove, and contains.
- Hash-based sets use hashCode() and equals(); TreeSet treats a comparison result of zero as a duplicate.
- HashSet and LinkedHashSet allow null; TreeSet requires a null-supporting comparator to allow it.
Common mistakes candidates make
- Calling HashSet order random or assuming its observed order is guaranteed.
- Claiming HashSet operations are always O(1), regardless of collisions and resizing.
- Assuming TreeSet uses equals() for duplicate detection or accepts arbitrary objects without a valid ordering.
Likely follow-up questions
What happens if a TreeSet comparator compares employees only by salary?
Two employees with the same salary compare as zero, so the second insertion is rejected even if they are different employees. Add an appropriate tie-breaker and ensure the complete ordering is consistent with equals().
What happens if an element changes after insertion?
Changing fields used by hashCode() or equals() can make HashSet and LinkedHashSet lookups unreliable. Changing fields used for TreeSet ordering can invalidate its ordering; remove the element before modifying those fields, then reinsert it.
When is LinkedHashSet preferable to TreeSet?
Use LinkedHashSet when deduplicating values while preserving the order in which they first appeared, such as entries in an imported file. Use TreeSet when you need sorted output, nearest-element queries, or range views.
Interview tip: Compare iteration order, time complexity, and duplicate detection first, then give one practical use case for each implementation.