Set Collections in Java

Master the Set interface, HashSet, LinkedHashSet, TreeSet, and set operations including uniqueness guarantees for the OCP 21 exam.

Table of Contents

• 1. Set Interface
• 2. HashSet
• 3. LinkedHashSet
• 4. TreeSet
• 5. Set Operations
• 6. Uniqueness Guarantees
• 7. Set Implementations Comparison
• 8. Exam Key Points

1. Set Interface

The Set interface extends Collection and represents a collection that contains no duplicate elements.

1.1 Set Characteristics

• No Duplicates: Cannot contain duplicate elements
• Unordered: Most implementations don't guarantee order (except LinkedHashSet, TreeSet)
• No Index: Elements cannot be accessed by index
• Null Elements: May allow null (implementation-dependent)

1.2 Common Set Implementations

• HashSet : Hash table implementation, no order
• LinkedHashSet : Hash table + linked list, insertion order
• TreeSet : Red-black tree, sorted order

2. HashSet

HashSet is a hash table implementation of the Set interface. It provides constant-time performance for basic operations.

2.1 Creating HashSet

Example:

import java.util.*;
// Create empty HashSet Set<
String>
set1 = new HashSet<
>
();
// Create with initial capacity Set<
String>
set2 = new HashSet<
>
(16);
// Create with initial capacity and load factor Set<
String>
set3 = new HashSet<
>
(16, 0.75f);
// Create from collection Set<
String>
set4 = new HashSet<
>
(Arrays.asList("A","B","C"));
// Using Set.of() (Java 9+) - immutable Set<
String>
set5 = Set.of("A","B","C");

2.2 HashSet Features

• Uses hash table for storage
• No guaranteed order
• O(1) average time for add, remove, contains
• Allows one null element
• Not thread-safe
• Uses equals() and hashCode() for uniqueness

3. LinkedHashSet

LinkedHashSet extends HashSet and maintains insertion order using a linked list.

3.1 Creating LinkedHashSet

Example:

import java.util.*;
// Create LinkedHashSet Set<
String>
set = new LinkedHashSet<
>
();
set.add("Apple");
set.add("Banana");
set.add("Cherry");
// Maintains insertion order for (String item : set) {
    System.out.println(item);
    // Apple, Banana, Cherry (in order) } // Create from collection Set<
String>
set2 = new LinkedHashSet<
>
(Arrays.asList("A","B","C"));

3.2 LinkedHashSet Features

• Maintains insertion order
• Hash table + linked list structure
• O(1) average time for operations
• Slightly more memory overhead than HashSet
• Allows one null element

4. TreeSet

TreeSet is a NavigableSet implementation based on a red-black tree. Elements are stored in sorted order.

4.1 Creating TreeSet

Example:

import java.util.*;
// Create TreeSet (natural ordering) Set<
String>
set1 = new TreeSet<
>
();
set1.add("Banana");
set1.add("Apple");
set1.add("Cherry");
// Elements stored in sorted order: Apple, Banana, Cherry // Create with Comparator Set<
String>
set2 = new TreeSet<
>
(Comparator.reverseOrder());
set2.add("Apple");
set2.add("Banana");
// Elements: Banana, Apple (reverse order) // Create from collection Set<
Integer>
set3 = new TreeSet<
>
(Arrays.asList(3, 1, 4, 1, 5));
// set3 = [1, 3, 4, 5] (sorted, duplicates
removed)

4.2 TreeSet Features

• Elements stored in sorted order
• O(log n) time for operations
• Does not allow null elements
• Elements must be Comparable or provide Comparator
• Implements NavigableSet (provides navigation methods)

4.3 NavigableSet Methods

Example:

TreeSet<
Integer>
set = new TreeSet<
>
();
set.addAll(Arrays.asList(10, 20, 30, 40, 50));
// Navigation methods Integer lower = set.lower(25);
// 20 (greatest <
25) Integer floor = set.floor(25);
// 20 (greatest <
= 25) Integer higher = set.higher(25);
// 30 (least >
25) Integer ceiling = set.ceiling(25);
// 30 (least >
= 25) // First and last Integer first = set.first();
// 10 Integer last = set.last();
// 50 // Poll first/last (remove and return) Integer polled = set.pollFirst();
// 10 (removed) Integer polled2 = set.pollLast();
// 50 (removed) // Head, tail, subSet views Set<
Integer>
head = set.headSet(30);
// [20] (elements <
30) Set<
Integer>
tail = set.tailSet(30);
// [30, 40] (elements >
= 30) Set<
Integer>
sub = set.subSet(20, 40);
// [20, 30] (20 <
= x <
40)

5. Set Operations

5.1 Adding Elements

Example:

Set<
String>
set = new HashSet<
>
();
// Add element (returns true if added, false if duplicate) boolean added1 = set.add("Apple");
// true boolean added2 = set.add("Banana");
// true boolean added3 = set.add("Apple");
// false (duplicate) // Add all from collection set.addAll(Arrays.asList("Cherry","Date","Cherry"));
// set = [Apple, Banana, Cherry, Date] (duplicates
ignored)

5.2 Removing Elements

Example:

Set<
String>
set = new HashSet<
>
();
set.addAll(Arrays.asList("Apple","Banana","Cherry"));
// Remove element boolean removed = set.remove("Banana");
// true // Remove all set.removeAll(Arrays.asList("Cherry","Date"));
// Removes"Cherry" // Remove if condition set.removeIf(s -> s.startsWith("A"));
// Removes"Apple" // Retain all (intersection) Set<
String>
set2 = new HashSet<
>
(Arrays.asList("Apple","Banana"));
set.retainAll(set2);
// Keeps only elements in both sets // Clear set.clear();
// Removes all
elements

5.3 Set Operations (Union, Intersection, Difference)

Example:

Set<
String>
set1 = new HashSet<
>
(Arrays.asList("A","B","C"));
Set<
String>
set2 = new HashSet<
>
(Arrays.asList("B","C","D"));
// Union (addAll) Set<
String>
union = new HashSet<
>
(set1);
union.addAll(set2);
// [A, B, C, D] // Intersection (retainAll) Set<
String>
intersection = new HashSet<
>
(set1);
intersection.retainAll(set2);
// [B, C] // Difference (removeAll) Set<
String>
difference = new HashSet<
>
(set1);
difference.removeAll(set2);
// [A]

5.4 Retrieving Elements

Example:

Set<
String>
set = new HashSet<
>
();
set.addAll(Arrays.asList("Apple","Banana","Cherry"));
// Check if contains boolean hasApple = set.contains("Apple");
// true // Size int size = set.size();
// 3 // Iteration (no guaranteed order for HashSet) for (String item : set) {
    System.out.println(item);
} // Using iterator Iterator<
String>
it = set.iterator();
while (it.hasNext()) {
    String item = it.next();
    it.remove();
    // Remove current element } // Convert to array String[] array = set.toArray(new
String[0]);

6. Uniqueness Guarantees

Sets use equals() and hashCode() to determine uniqueness.

6.1 equals() and hashCode()

Example:

// String uses equals() for comparison Set<
String>
set = new HashSet<
>
();
set.add("Hello");
set.add("Hello");
// Duplicate - not added set.add(new String("Hello"));
// Still duplicate (equals() returns true) // set.size() = 1 // Custom class must override equals() and hashCode() class Person {
    private String name;
    private int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
@Override public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null || getClass() != obj.getClass()) return false;
    Person person = (Person) obj;
    return age == person.age && Objects.equals(name, person.name);
}
@Override public int hashCode() {
    return Objects.hash(name, age);
}
} Set<
Person>
people = new HashSet<
>
();
people.add(new Person("Alice", 30));
people.add(new Person("Alice", 30));
// Duplicate - not added people.add(new Person("Bob", 25));
// Different -
added

6.2 TreeSet Uniqueness

TreeSet uses compareTo() or Comparator for uniqueness (not equals()).

Example:

// TreeSet uses compareTo() for uniqueness TreeSet<
String>
set = new TreeSet<
>
();
set.add("Apple");
set.add("Apple");
// Duplicate - not added // Custom Comparator TreeSet<
String>
set2 = new TreeSet<
>
((a, b) -> a.length() - b.length());
// Compare by length set2.add("A");
set2.add("BB");
set2.add("A");
// Duplicate length - not added set2.add("CC");
// Different length -
added

7. Set Implementations Comparison

Feature	HashSet	LinkedHashSet	TreeSet
Ordering	No order	Insertion order	Sorted order
Performance	O(1) average	O(1) average	O(log n)
Null Elements	One null allowed	One null allowed	No null allowed
Uniqueness	equals()/hashCode()	equals()/hashCode()	compareTo()/Comparator
When to Use	General purpose	Need insertion order	Need sorted order

8. Exam Key Points

Critical Concepts for OCP 21 Exam:

• Set Interface: No duplicates, no index access
• HashSet: Hash table, no order, O(1) operations
• LinkedHashSet: Maintains insertion order, O(1) operations
• TreeSet: Sorted order, O(log n) operations, NavigableSet
• Uniqueness: HashSet/LinkedHashSet use equals()/hashCode()
• TreeSet Uniqueness: Uses compareTo() or Comparator (not equals())
• add(): Returns true if added, false if duplicate
• remove(): Removes element, returns true if removed
• contains(): Checks if element exists
• No Index: Cannot access elements by index
• Null Elements: HashSet/LinkedHashSet allow one null, TreeSet doesn't
• equals() and hashCode(): Must be overridden together for custom classes
• Set Operations: addAll (union), retainAll (intersection), removeAll (difference)
• TreeSet Navigation: lower(), floor(), higher(), ceiling(), first(), last()
• TreeSet Views: headSet(), tailSet(), subSet()
• Comparable: TreeSet requires Comparable elements or Comparator
• No Duplicates: Adding duplicate returns false, doesn't throw exception
• Iteration Order: HashSet - no order, LinkedHashSet - insertion order, TreeSet - sorted