Set Interface

The Set interface represents a collection with no duplicate elements. It models the mathematical concept of a set and is primarily used for membership testing and duplicate elimination.

Set Hierarchy

Set<E>
├── HashSet<E>            — hash table, O(1) ops, no ordering
├── LinkedHashSet<E>      — insertion order preserved
├── SortedSet<E> → NavigableSet<E>
│   └── TreeSet<E>        — red-black tree, sorted order
├── EnumSet<E>            — bit-vector for enum types (fastest)
└── CopyOnWriteArraySet   — thread-safe, optimized for reads

Implementation Comparison

	HashSet	LinkedHashSet	TreeSet	EnumSet
add/remove/contains	O(1)*	O(1)*	O(log n)	O(1)
Ordering	None	Insertion	Sorted	Declaration
Null	1 allowed	1 allowed	No	No
Memory	Medium	High	Medium	Very low
Thread-safe	No	No	No	No

*Average case — O(n) worst case due to hash collisions

Basic Usage

Set<String> set = new HashSet<>();

set.add("Alice");       // true
set.add("Bob");         // true
set.add("Alice");       // false — already exists

set.contains("Alice");  // true
set.remove("Bob");      // true
set.size();             // 1

Mathematical Set Operations

Set<String> a = new HashSet<>(List.of("a", "b", "c", "d"));
Set<String> b = new HashSet<>(List.of("c", "d", "e", "f"));

// Union (A ∪ B)
Set<String> union = new HashSet<>(a);
union.addAll(b);                    // {a, b, c, d, e, f}

// Intersection (A ∩ B)
Set<String> inter = new HashSet<>(a);
inter.retainAll(b);                 // {c, d}

// Difference (A − B)
Set<String> diff = new HashSet<>(a);
diff.removeAll(b);                  // {a, b}

// Subset check
a.containsAll(inter);               // true

HashSet

The default choice for most use cases. Backed by a HashMap internally.

Set<String> set = new HashSet<>();            // capacity 16, load factor 0.75
Set<String> set = new HashSet<>(100);         // pre-size
Set<String> set = new HashSet<>(List.of("a", "b", "c"));

// Remove duplicates from a list in one line
List<String> unique = new ArrayList<>(new HashSet<>(listWithDuplicates));

Important: Objects in a HashSet must properly implement hashCode() and equals(). If two objects are equal, they must have the same hash code.

LinkedHashSet

Same performance as HashSet, but preserves insertion order during iteration.

Set<String> set = new LinkedHashSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");
// Iteration: banana, apple, cherry (insertion order)

Use when you need uniqueness + predictable iteration order.

TreeSet

Keeps elements sorted (natural order or via Comparator). Backed by a red-black tree.

TreeSet<Integer> sorted = new TreeSet<>();
sorted.addAll(List.of(5, 2, 8, 1, 9));
// Iteration: 1, 2, 5, 8, 9

// Navigable methods
sorted.ceiling(6);     // 8   — smallest >= 6
sorted.floor(6);       // 5   — largest <= 6
sorted.higher(5);      // 8   — smallest > 5
sorted.lower(5);       // 2   — largest < 5

// Range views
sorted.subSet(2, true, 8, true);  // [2, 5, 8]
sorted.headSet(5);                 // [1, 2]
sorted.tailSet(5);                 // [5, 8, 9]

// Custom ordering
TreeSet<String> desc = new TreeSet<>(Comparator.reverseOrder());

Note: Elements must be Comparable or you must provide a Comparator. Null is not allowed.

Immutable Sets

// Java 9+ — truly immutable
Set<String> immutable = Set.of("a", "b", "c");

// Unmodifiable wrapper (changes in original reflect here)
Set<String> unmod = Collections.unmodifiableSet(mutableSet);

When to Use Which

Scenario	Use
General-purpose unique collection	HashSet
Need insertion order	LinkedHashSet
Need sorted order or range queries	TreeSet
Enum values only	EnumSet
Thread-safe reads	CopyOnWriteArraySet