Collections Set — HashSet, TreeSet, LinkedHashSet, SortedSet, and NavigableSet

In this tutorial, you will learn about Collections Set. We cover key concepts, practical examples, and best practices to help you master this topic.

Java Set interface represents collections with no duplicate elements, with implementations optimized for fast membership testing and ordering requirements. Sets ensure that no element appears more than once — they are the mathematical set abstraction implemented in Java.

What You'll Learn

• HashSet: constant-time operations via Hash Table
• TreeSet: sorted set via red-black tree
• LinkedHashSet: insertion-ordered set
• SortedSet and NavigableSet interfaces

Why It Matters

Sets are essential for deduplication, membership testing, and mathematical set operations (union, intersection, difference). Choosing the right implementation affects both correctness (ordering guarantees) and performance.

Real-World Use

Sets model permissions (unique roles per user), track visited URLs in web crawlers, store unique tags on blog posts, and implement mathematical set operations in analytics.

The Set Interface

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple"); // ignored — duplicate
System.out.println(set.size()); // 2

boolean contains = set.contains("Apple"); // true
set.remove("Banana");

Sets use equals() and hashCode() to determine equality. Custom objects must implement both correctly.

HashSet

Backed by a HashMap:

Set<String> hashSet = new HashSet<>();
hashSet.add("Zebra");
hashSet.add("Apple");
hashSet.add("Monkey");
hashSet.add("Banana");
System.out.println(hashSet); // unordered output

Characteristics

• O(1) for add, remove, contains (assuming good hash distribution)
• No ordering guarantees (except no guarantee at all)
• Allows one null element
• Load factor (default 0.75) controls resizing

How HashSet Works Internally

Each element is stored as a key in a HashMap with a constant dummy value. The hash code determines the bucket. If two elements have the same hash code (collision), they are stored in a Linked List or tree (since Java 8, trees for large buckets).

LinkedHashSet

Extends HashSet with a linked list maintaining insertion order:

Set<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Zebra");
linkedHashSet.add("Apple");
linkedHashSet.add("Monkey");
System.out.println(linkedHashSet); // [Zebra, Apple, Monkey] — insertion order

When to Use

• When you need predictable iteration order
• When order of insertion matters (recently used items, audit trails)
• Slightly more memory than HashSet due to the linked list

TreeSet

Backed by a TreeMap (red-black tree), elements are sorted:

Set<String> treeSet = new TreeSet<>();
treeSet.add("Zebra");
treeSet.add("Apple");
treeSet.add("Monkey");
System.out.println(treeSet); // [Apple, Monkey, Zebra] — sorted alphabetically

Characteristics

• O(log n) for add, remove, contains
• Elements must implement Comparable or a Comparator must be provided
• Does not allow null elements (since compareTo throws NullPointerException)
• Implements SortedSet and NavigableSet

Custom Comparator

Set<Person> byAge = new TreeSet<>(Comparator.comparingInt(Person::age));
byAge.add(new Person("Alice", 30));
byAge.add(new Person("Bob", 25));
byAge.add(new Person("Charlie", 35));
// Ordered by age: Bob (25), Alice (30), Charlie (35)

SortedSet Interface

TreeSet implements SortedSet which adds ordering methods:

SortedSet<Integer> sorted = new TreeSet<>(Set.of(1, 3, 5, 7, 9));
sorted.first();         // 1
sorted.last();          // 9
sorted.headSet(5);      // [1, 3] — elements < 5
sorted.tailSet(5);      // [5, 7, 9] — elements >= 5
sorted.subSet(3, 7);    // [3, 5] — elements >= 3 and < 7
SortedSet<Integer> descending = sorted.descendingSet(); // [9, 7, 5, 3, 1]

NavigableSet Interface

Extends SortedSet with navigation methods:

NavigableSet<Integer> nav = new TreeSet<>(Set.of(1, 3, 5, 7, 9));
nav.lower(5);    // 3 — greatest element < 5
nav.floor(5);    // 5 — greatest element <= 5
nav.ceiling(6);  // 7 — least element >= 6
nav.higher(7);   // 9 — least element > 7
nav.pollFirst(); // 1 — retrieves and removes first
nav.pollLast();  // 9 — retrieves and removes last

Set Operations

Java does not have built-in set operations, but you can implement them with standard API:

Set<Integer> set1 = new HashSet<>(Set.of(1, 2, 3));
Set<Integer> set2 = new HashSet<>(Set.of(2, 3, 4));

// Union
Set<Integer> union = new HashSet<>(set1);
union.addAll(set2);  // [1, 2, 3, 4]

// Intersection
Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2);  // [2, 3]

// Difference
Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2);  // [1]

Common Mistakes

1. Using mutable objects as set elements. If an object's equals()/hashCode() changes while it is in a set, the set becomes corrupted and contains() returns wrong results.
2. Forgetting to implement hashCode() when using HashSet. Without a proper hashCode(), all objects go to the same bucket, degenerating to O(n) performance.
3. Adding null to a TreeSet. Throws NullPointerException because compareTo is called on the null element.
4. Assuming iteration order of HashSet. HashSet makes no ordering guarantees — the order can even change between JVM runs.
5. Using Set.of() and trying to modify it. Set.of() returns an immutable set. Any mutation throws UnsupportedOperationException.

Practice Questions

1. What is the difference between HashSet, LinkedHashSet, and TreeSet?
HashSet: fastest (O(1)), no ordering. LinkedHashSet: O(1), insertion order. TreeSet: O(log n), sorted order.

2. How does HashSet handle hash collisions?
Elements with the same hash code are stored in a linked list or balanced tree (Java 8+, when bucket exceeds threshold).

3. What is the performance of contains() on TreeSet?
O(log n), because TreeSet is backed by a red-black tree.

4. What does SortedSet.subSet(from, to) return?
A view of the set containing elements from from (inclusive) to to (exclusive).

5. Why does adding null to a TreeSet throw an exception?
TreeSet uses compareTo() or Comparator.compare() for ordering, and both throw NullPointerException when called with null.

Challenge Question:
Write a method Set<Integer> findDuplicates(int[] array) that returns all values that appear more than once. Use a Set to track seen values and a second Set for duplicates. Then write a method Set<Integer> symmetricDifference(Set<Integer> a, Set<Integer> b) that returns elements in either set but not both.

FAQ

Mini Project

Write a program SetDemo.java that:

1. Creates a HashSet of 10,000 random integers and measures how long contains() takes
2. Creates a TreeSet of the same integers and measures contains() — compare to HashSet
3. Creates a LinkedHashSet of strings and shows insertion order is preserved
4. Demonstrates SortedSet operations: first(), last(), headSet(), tailSet(), subSet()
5. Demonstrates NavigableSet operations: lower(), floor(), ceiling(), higher()
6. Implements union, intersection, and difference on two sets of integers
7. Shows the bug when using a mutable object (like StringBuilder) as a set element

What's Next

Sets manage unique elements, but many applications need key-value associations. Lesson 25 covers Map collections — HashMap, TreeMap, LinkedHashMap, EnumMap, and IdentityHashMap — for fast lookups by key.