Set Implementations: Uniqueness Without the Repetition
How HashSet, LinkedHashSet, and TreeSet each enforce uniqueness differently under the hood, plus the specialized EnumSet and BitSet for narrower but much faster use cases.
Learning objectives
- Explain why HashSet is internally just a HashMap<E, Object> wrapper and what that implies about its performance and ordering
- Describe how LinkedHashSet adds predictable insertion-order iteration on top of HashSet's bucket structure
- Explain how TreeSet maintains sorted order via a backing red-black tree and the NavigableSet operations it exposes
- Choose correctly between HashSet, LinkedHashSet, and TreeSet based on ordering and performance requirements
- Recognize when EnumSet or BitSet is a strictly better fit than a general-purpose Set
A wedding planner keeping a guest list has one non-negotiable rule: nobody appears on the list twice, no matter how many times their name gets submitted by different family members. The planner doesn't actually care what order the names end up in on the final printed sheet — just that duplicates get silently rejected the moment someone tries to add a name that's already there.
That's the entire job description of Set<E>: a Collection that enforces no duplicates, full stop, with nothing else promised about ordering. But three very different planners could run this guest list, and each makes a different trade-off between speed and structure.
The first planner keeps names in numbered pigeonholes based on a formula computed from each name — "Hassan" always goes in pigeonhole 14, "Priya" always goes in pigeonhole 37 — so checking "is this name already on the list?" means computing the formula once and looking in exactly one pigeonhole, nearly instant regardless of how many names are on the list. The catch: the pigeonhole numbers have nothing to do with when names were added or their alphabetical order, so reading the list back out gives names in a seemingly random, formula-driven order. This is HashSet.
The second planner uses the same pigeonhole trick for fast duplicate checking, but also keeps a separate thread strung through every pigeonhole in the exact order names were added, so reading the list back gives you the true submission order while still getting the pigeonhole speed for duplicate checks. This is LinkedHashSet — same hashing strategy underneath, plus a linked list stitched on top purely for predictable iteration order.
The third planner refuses to use pigeonholes at all and instead keeps names in a carefully balanced family tree of comparisons — is this name alphabetically before or after that one — so the list can always be read back in sorted order, and operations like "give me the next name after 'Marcus'" are answerable directly instead of requiring a full scan. The cost is that every insertion now involves a handful of comparisons to find the right spot and possibly rebalance the tree, slower than an instant pigeonhole lookup but still efficient. This is TreeSet.
All three honor the exact same Set contract — no duplicates — and all three are drop-in replacements for each other at the interface level. The difference that matters is entirely about what you get back when you read the set out, and how fast insertion and lookup are along the way.
Open the actual JDK source for HashSet<E> and you'll find it has almost no logic of its own. Internally, it holds a single field: private transient HashMap<E, Object> map;. Every Set operation is a thin wrapper around a HashMap operation: add(element) calls map.put(element, PRESENT) where PRESENT is a single shared dummy Object used as a placeholder value nobody ever reads; contains(element) calls map.containsKey(element); remove(element) calls map.remove(element). The "set" is really just "a map whose values are all the same meaningless placeholder, and whose keys are the actual elements you care about."
This is worth internalizing fully because it means every characteristic of HashMap — covered in depth in the map topics of this vertical — transfers directly to HashSet. Lookups, insertions, and deletions are all O(1) average case, driven by hashCode() to pick a bucket and equals() to resolve collisions within that bucket. Iteration order is unspecified and can change between runs, between JVM versions, and even within the same run if the set resizes. And just like HashMap, every element placed into a HashSet must have a correct, consistent equals()/hashCode() pair, or the "no duplicates" guarantee silently breaks — an object that's logically equal to one already in the set but reports a different hash code will be stored as if it were distinct, because the set never even looks in the right bucket to find the "duplicate."
LinkedHashSet<E> extends HashSet<E> and changes essentially one thing: internally, it swaps the plain HashMap for a LinkedHashMap, which maintains a doubly-linked list threading through every entry in insertion order (or access order, if configured that way — covered in the LinkedHashMap topic). This buys predictable iteration order — elements come back out in the order they were first inserted, with re-insertion of an existing element not changing its position — at a small, constant memory and performance overhead per entry for maintaining the extra links. For the common case of "I want fast lookups but I also want to print this set back out in a sensible, repeatable order," LinkedHashSet is almost always the right default over plain HashSet, and the performance cost is small enough that reaching for it by default is a defensible habit, not a premature optimization.
The one thing neither HashSet nor LinkedHashSet gives you is any relationship between elements beyond "equal or not equal" — there's no notion of "greater than" built into either, which is exactly the gap TreeSet fills.
💻 Code example
package collections.sets; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.Set; /** * Demonstrates that HashSet's iteration order is unspecified while * LinkedHashSet preserves insertion order -- using the exact same elements * inserted in the exact same sequence into both. */ public class HashSetVsLinkedHashSet { public static void main(String[] args) { String[] cities = {"Mumbai", "Oslo", "Cairo", "Lima", "Tokyo"}; Set<String> hashSet = new HashSet<>(); Set<String> linkedHashSet = new LinkedHashSet<>(); for (String city : cities) { hashSet.add(city); linkedHashSet.add(city); } // Iteration order here is driven by each string's hashCode() modulo // the table size -- it has no relationship to insertion order and // should never be relied upon. System.out.println("HashSet order (unspecified): " + hashSet); // LinkedHashSet threads a linked list through insertion order on // top of the same hash-bucket lookup speed -- this will always // print Mumbai, Oslo, Cairo, Lima, Tokyo, in that exact order. System.out.println("LinkedHashSet order (insertion): " + linkedHashSet); // Re-inserting an existing element does NOT move its position in a // LinkedHashSet -- only genuinely new elements get appended. linkedHashSet.add("Oslo"); System.out.println("After re-adding 'Oslo': " + linkedHashSet); } }
TreeSet<E> is backed internally by a TreeMap<E, Object> — the same "a Set is really a Map with a dummy value" pattern as HashSet, just on top of a different map. Instead of hashing, every insertion is placed using comparisons: either the natural ordering from Comparable<E> (every element must implement it, or you get a ClassCastException the first time two elements are compared) or an explicit Comparator<E> supplied to the constructor. The backing structure is a red-black tree, a self-balancing binary search tree that guarantees O(log n) for insertion, deletion, and lookup even in the worst case — never degrading to O(n) the way an unbalanced binary search tree can under adversarial insertion order. The map-and-sorted-maps topic in this vertical covers the red-black tree's rebalancing rules in depth; for TreeSet's purposes, the guarantee to remember is simply "always O(log n), always sorted."
Because TreeSet implements NavigableSet<E>, it exposes operations no hash-based set can answer efficiently: first() and last() for the extremes, floor(e) and ceiling(e) for the nearest element not-greater-than or not-less-than a given value, higher(e) and lower(e) for strict versions of the same, and headSet(e)/tailSet(e)/subSet(from, to) for live, backed sub-views of a range. These make TreeSet the correct tool for problems like "find the smallest booking time greater than or equal to this request" or "give me every score between 70 and 90" — a HashSet can only answer those by scanning every element, while TreeSet answers them in O(log n) using the tree structure directly.
EnumSet<E extends Enum<E>> is a highly specialized set that only ever holds values of a single enum type, and its internal representation is a bit vector — one bit per possible enum constant, packed into a single long (or an array of them, for enums with more than 64 constants). Membership testing, adding, and removing are all genuinely O(1) bitwise operations, and because the bits are laid out in the enum's declared constant order, iteration is automatically sorted by declaration order with no comparison logic needed at all. For any set whose element type is a fixed, known enum — representing active permission flags, days of the week a schedule runs on, feature toggles — EnumSet is both faster and more memory-compact than HashSet<MyEnum> by a wide margin, and there's essentially no reason to reach for HashSet over it once the element type is an enum.
BitSet generalizes the same bit-vector idea beyond enums to arbitrary non-negative integer indices, and notably does not implement the Set interface at all — it predates the Collections Framework and uses its own API (set(index), clear(index), get(index)). It's the right tool when you're tracking membership over a large, dense range of integer IDs (say, "which of these 10 million user IDs have logged in today") where a HashSet<Integer> would waste enormous memory boxing each Integer into its own heap object, while a BitSet needs only one bit per index and supports extremely fast bitwise set operations (and, or, xor) across entire ranges at once.
💻 Code example
package collections.sets; import java.util.*; /** * TreeSet's NavigableSet operations, and EnumSet's bit-vector-backed * membership for a fixed enum universe. */ public class TreeSetAndEnumSetDemo { enum Permission { READ, WRITE, EXECUTE, DELETE, ADMIN } public static void main(String[] args) { // --- TreeSet: sorted order plus range/navigation queries --- NavigableSet<Integer> bookingTimes = new TreeSet<>( List.of(900, 930, 1000, 1030, 1100, 1300) ); System.out.println("All times (sorted automatically): " + bookingTimes); System.out.println("Earliest slot at/after 1015: " + bookingTimes.ceiling(1015)); // 1030 System.out.println("Latest slot before 1000: " + bookingTimes.lower(1000)); // 930 System.out.println("Slots between 930 and 1100 (exclusive end): " + bookingTimes.subSet(930, 1100)); // [930, 1000, 1030] // --- EnumSet: O(1) bitwise membership over a fixed enum universe --- EnumSet<Permission> adminPermissions = EnumSet.of( Permission.READ, Permission.WRITE, Permission.ADMIN ); EnumSet<Permission> allPermissions = EnumSet.allOf(Permission.class); EnumSet<Permission> readOnlyDiff = EnumSet.complementOf(adminPermissions); System.out.println("Admin permissions: " + adminPermissions); System.out.println("Everything NOT granted to admin: " + readOnlyDiff); System.out.println("Has EXECUTE? " + adminPermissions.contains(Permission.EXECUTE)); // false // Iteration order always follows declaration order, never insertion order. for (Permission p : allPermissions) { System.out.print(p + " "); } } }
Q: What is HashSet actually implemented as, internally?
A: A thin wrapper around a HashMap<E, Object>, where every element is stored as a map key and the value is a single shared, meaningless placeholder object. Every HashSet operation delegates directly to the corresponding HashMap operation.
Q: What does LinkedHashSet add on top of HashSet, and at what cost?
A: A doubly-linked list threaded through every entry in insertion order, giving predictable, repeatable iteration order, at a small constant memory/performance overhead per entry. It's internally a LinkedHashSet wrapping a LinkedHashMap the same way HashSet wraps a HashMap.
Q: What does TreeSet guarantee that HashSet can't, and what's the complexity trade-off?
A: Sorted iteration order (by natural ordering or a supplied Comparator) plus navigation operations like floor, ceiling, and range sub-views, backed by a red-black tree. The cost is O(log n) for insert/delete/lookup instead of HashSet's average O(1), because every operation needs tree comparisons rather than a single hash computation.
Q: When should you reach for EnumSet or BitSet instead of a general-purpose Set?
A: EnumSet whenever the element type is a fixed enum — it's a bit-vector giving O(1) operations and automatic declaration-order iteration, strictly better than HashSet<MyEnum>. BitSet for tracking membership over a large, dense range of non-negative integers, where boxing each value into a HashSet<Integer> would waste far more memory than one bit per index.
Want a visual for this concept?
Generate a diagram tailored to “Set Implementations: Uniqueness Without the Repetition” — the AI picks whichever visual (flowchart, comparison, sequence, etc.) best fits.
Sign in to generate a visual →