jd five

Sets

Learning goals

By the end of this chapter you should be able to:

  • Explain the Set contract: at most one element per equals value
  • Pick HashSet, LinkedHashSet, or TreeSet by membership vs order vs sorting needs
  • Implement correct equals / hashCode for set elements (and map keys)
  • Build a concurrent unordered set without a dedicated ConcurrentHashSet class

Sets: membership, not sequence

A Set answers “have I seen this before?” — not “what is at index 3?”

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java");   // second add returns false — already present
tags.contains("java");  // true

Duplicates are defined by equals, not reference identity (unless you deliberately use IdentityHashMap-style patterns — not covered here).

If you need insertion order or sorting, the same Set interface has implementations with different iteration guarantees — choose the implementation, not a different abstraction.

A Set holds at most one element that equals a given value. HashSet needs correct equals and hashCode on the element type.

This guide keeps three mutable shapes that solve different problems: fast membership (HashSet), stable iteration order (LinkedHashSet), sorted keys + ranges (TreeSet). For a concurrent, unordered set, use the ConcurrentHashMap-backed idiom below—there is no ConcurrentHashSet class.

Each section includes Why / vs alternatives.

HashSet — not concurrent

Backed by a HashMap: set elements are keys, values are a shared dummy object. Order is not defined. Average add, remove, and contains are O(1) if the hash function spreads keys well.

Initialize: Set<T> s = new HashSet<>(); — or new HashSet<>(initialCapacity) / new HashSet<>(collection).

Sharing across threads:

Set<String> s = Collections.synchronizedSet(new HashSet<>());

For an unordered concurrent set without wrapping, prefer Collections.newSetFromMap(new ConcurrentHashMap<>()) below.

Why / vs alternatives: Default when you only need membership and speed, not order or sorting. LinkedHashSet if iteration order must match insertion; TreeSet if you need sorted order or range queries.

  • add(e) — inserts e if not already present; returns true if the set changed.
  • remove(e) — removes an element equal to e; returns whether it was present.
  • contains(e) — whether some element equals e.
  • size() — number of elements.
  • isEmpty() — whether the set is empty.
  • clear() — removes all elements.
  • iterator() — unordered iteration; fail-fast if the set is modified during iteration (except via iterator remove).
  • stream() / parallelStream() — stream over elements.

LinkedHashSet — not concurrent

Same contract as HashSet, but iteration order follows insertion order (LinkedHashMap under the hood, always in insertion-order mode). Slightly more memory and work per operation than HashSet.

Not like LinkedHashMap’s optional access order: The Set API does not expose an LRU / access-order switch. Only LinkedHashMap lets you opt into accessOrder = true for recency; LinkedHashSet cannot.

Initialize: Set<T> s = new LinkedHashSet<>(); — or new LinkedHashSet<>(collection).

Sharing across threads:

Set<String> s = Collections.synchronizedSet(new LinkedHashSet<>());

Keeps insertion-order iteration under the wrapper’s lock.

Why / vs alternatives: HashSet iteration order is undefined—bad for logs, tests, or APIs that promise a stable visit order. You pay extra links for that predictability. For sorted order, use TreeSet.

Same methods as HashSet; iterator() visits entries in insertion order.

Java 21+: LinkedHashSet implements SequencedSet — getFirst() / getLast(), removeFirst() / removeLast(), reversed(), aligned with insertion order (first = oldest inserted, not LRU-by-access). Not the same as TreeSet’s first()/last() (sorted order).

TreeSet — not concurrent

Backed by a TreeMap (a red-black tree). Elements are sorted by natural order or a Comparator. add, remove, contains are O(log n). Implements NavigableSet: nearest element and sub-ranges.

Initialize: Set<T> s = new TreeSet<>(); — natural order; or new TreeSet<>(comparator) / new TreeSet<>(existingSortedSet).

Sharing across threads: use the NavigableSet wrapper so you keep subSet / floor / lower:

NavigableSet<String> s = Collections.synchronizedNavigableSet(new TreeSet<>());

(Collections.synchronizedSortedSet works if you only need SortedSet.)

Why / vs alternatives: HashSet cannot answer “next greater” or subSet/headSet/tailSet—you need a total order in the structure. Cost: O(log n) vs HashSet’s average O(1). Multi-threaded writers need external synchronized/Lock around TreeSet or a different design (e.g. ConcurrentHashMap keys only if order is not required).

  • All HashSet methods, plus navigation:
  • first() / last() — smallest / largest element.
  • lower(e) — greatest element strictly less than e.
  • floor(e) — greatest element ≤ e.
  • ceiling(e) — least element ≥ e.
  • higher(e) — least element strictly greater than e.
  • pollFirst() / pollLast() — remove and return smallest / largest.
  • descendingSet() — view with reversed order.
  • subSet(from, to) / headSet(to) / tailSet(from) — views over ranges (see NavigableSet javadoc for boundary rules).

Set built from ConcurrentHashMap — concurrent

Initialize: Set<E> s = Collections.newSetFromMap(new ConcurrentHashMap<>()); — only keys matter; map values are ignored.

Tuning (optional): pass ConcurrentHashMap sizing into newSetFromMap when you know roughly how many keys:

Set<E> tuned = Collections.newSetFromMap(new ConcurrentHashMap<>(expectedSize));

Same ConcurrentHashMap constructors as in Maps.

Why / vs alternatives: Shared unordered Set under concurrent add/remove/contains without wrapping HashSet in one big lock. Does not give sorted traversal—use TreeSet + coordination if you need order and can afford locking.

  • Normal Set operations; concurrency comes from the backing ConcurrentHashMap.

Shared Collection / Set behavior — per type

  • addAll, removeAll, retainAll — bulk add/remove/intersect with another collection.
  • containsAll(c) — whether this set contains every element of c.
  • toArray() — order follows LinkedHashSet / TreeSet rules when applicable.

Initialize (immutable): Set<T> s = Set.of(a, b); — varargs overloads; or Set.copyOf(collection).

Why / vs alternatives: Read-only constants—callers cannot add. Not for large evolving sets; use HashSet.

Next: Maps

Practice checkpoint

  1. Log lines must dedupe while preserving first-seen order — which set? Answer: LinkedHashSet.

  2. Range query: all IDs strictly between 1000 and 2000 — which set? Answer: TreeSet with subSet / navigable methods.

  3. Two User objects with same id but different hashCode — can both live in a HashSet? Answer: contract violation — behavior undefined; may appear as duplicates or lost entries.

  4. Concurrent writers, order irrelevant — how to get a Set? Answer: Collections.newSetFromMap(new ConcurrentHashMap<>()).

Interview angles

  • HashSet internals: backed by HashMap (keys = elements, dummy value).
  • LinkedHashSet vs TreeSet iteration: insertion order vs total sorted order — not the same as “LRU” (that is access-order LinkedHashMap).
  • O(1) vs O(log n): HashSet average constant time; TreeSet red-black tree.
  • Immutable: Set.of(a, b, c) — duplicate arguments throw at creation time.

Next: /java/learn/collections/maps/