5.3 Set Implementations: HashSet vs LinkedHashSet vs TreeSet

← Back to Chapter 5: Collections Framework

A Set is a collection containing no duplicate elements (e1.equals(e2) == false).

---

1. HashSet: Internal Backing by HashMap

Every HashSet<E> instance internally wraps a HashMap<E, Object>:

public class HashSet<E> implements Set<E> {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

• Ordering: Unordered; iteration order depends on bucket hashing and can shift on rehashing.
• Performance: O(1) average time for add(), remove(), and contains().
• Contract: Requires that E properly implements both equals() and hashCode().

---

2. LinkedHashSet: Predictable Insertion Order

• Extends HashSet, backed by an internal LinkedHashMap.
• Maintains a running doubly-linked list through all entries in addition to bucket arrays.
• Iteration order reflects element insertion order.
• Slightly higher memory footprint than HashSet to store forward and backward pointers.

---

3. TreeSet: Sorted & Navigable (Red-Black Tree)

• Implements NavigableSet<E> and SortedSet<E>, backed by a TreeMap.
• Internally organized as a self-balancing Red-Black Binary Search Tree.
• Guarantees O(log n) time cost for add(), remove(), and contains().
• Elements must implement Comparable<E> or provide an explicit Comparator<E> during set instantiation:

NavigableSet<Integer> scores = new TreeSet<>(List.of(88, 42, 95, 71));
int lowest = scores.first();       // 42
int floor = scores.floor(80);      // 71 (greatest element <= 80)
int ceiling = scores.ceiling(80);  // 88 (least element >= 80)