HashSet, LinkedHashSet and TreeSet

Every Set in the JDK is a thin wrapper over the corresponding Map, which means everything you know about HashMap and TreeMap applies directly. What differs is the ordering guarantee and, in two special cases, the underlying representation.

Every Set is a Map#

public class HashSet<E> extends AbstractSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();   // one instance, for every element
 
    public boolean add(E e)      { return map.put(e, PRESENT) == null; }
    public boolean remove(Object o) { return map.remove(o) == PRESENT; }
    public boolean contains(Object o) { return map.containsKey(o); }
    public int size()            { return map.size(); }
    public Iterator<E> iterator(){ return map.keySet().iterator(); }
}

LinkedHashSet extends HashSet and simply calls a package-private superclass constructor that builds a LinkedHashMap instead. TreeSet wraps a TreeMap the same way.

The practical consequence is that everything from HashMap internals transfers: the same 0.75 load factor, the same resize behaviour, the same treeification at eight collisions, the same absolute requirement for a correct and stable hashCode. A HashSet of objects with a broken hashCode accepts duplicates for exactly the same reason a HashMap fails to find a key.

It also means the memory cost is a HashMap entry per element — around 32–48 bytes each — which is why a Set of a million boxed Integers costs far more than the 4MB an array would.

Choosing between the three#

List<String> input = List.of("delta", "alpha", "charlie", "bravo", "alpha");
 
new HashSet<>(input);        // [bravo, alpha, charlie, delta] — hash order, do not rely on it
new LinkedHashSet<>(input);  // [delta, alpha, charlie, bravo] — first-insertion order
new TreeSet<>(input);        // [alpha, bravo, charlie, delta] — sorted

Note that the duplicate alpha does not move in LinkedHashSet: re-adding an existing element is a no-op and does not refresh its position. That is the Set analogue of LinkedHashMap's insertion-order behaviour, and it differs from access order, which LinkedHashSet does not expose at all.

TreeSet inherits the full NavigableSet API — first, last, ceiling, floor, higher, lower, headSet, tailSet, subSet, descendingSet, pollFirst, pollLast. Those are the reason to accept O(log n):

NavigableSet<Integer> tiers = new TreeSet<>(List.of(0, 100, 500, 1000, 5000));
 
tiers.floor(750);        // 500 — the tier this order qualifies for
tiers.ceiling(750);      // 1000 — the next tier up
tiers.headSet(1000);     // [0, 100, 500]
tiers.subSet(100, true, 1000, true);   // [100, 500, 1000]

The TreeSet trap#

Set<Employee> byDept = new TreeSet<>(Comparator.comparing(Employee::department));
byDept.add(new Employee("ada", "engineering"));
byDept.add(new Employee("grace", "engineering"));   // returns false, discarded
byDept.size();                                       // 1

The fix is always the same: end the comparator with a tie-break that is unique per element.

Set<Employee> safe = new TreeSet<>(
        Comparator.comparing(Employee::department)
                  .thenComparing(Employee::name)
                  .thenComparing(Employee::id));     // guaranteed unique

The same rule applies to sorting a list before deduplicating it, and to Collectors.toCollection(() -> new TreeSet<>(cmp)). Whenever a set "loses" elements, check the comparator first.

EnumSet and EnumMap#

For enum keys the JDK provides specialised implementations that are not hash-based at all.

enum Permission { READ, WRITE, DELETE, ADMIN, AUDIT }
 
EnumSet<Permission> granted = EnumSet.of(Permission.READ, Permission.WRITE);
EnumSet<Permission> all     = EnumSet.allOf(Permission.class);
EnumSet<Permission> none    = EnumSet.noneOf(Permission.class);
EnumSet<Permission> rest    = EnumSet.complementOf(granted);
EnumSet<Permission> range   = EnumSet.range(Permission.READ, Permission.DELETE);
 
granted.contains(Permission.WRITE);   // a single bit test
granted.retainAll(required);          // a single AND
granted.addAll(extra);                // a single OR

EnumSet stores membership as bits in one long (a RegularEnumSet) for enums with up to 64 constants, or an array of longs beyond that. Membership testing is one bitwise AND. Union, intersection and difference are one instruction each rather than n hash lookups. Memory is a single 64-bit word rather than 40 bytes per element.

EnumMap is the same idea for maps: an array indexed by ordinal(), so get is an array access with no hashing at all, and iteration follows declaration order.

The rule is simple and worth stating in an interview: if the key type is an enum, use EnumSet or EnumMap. There is no case where HashSet of an enum is a better choice, and reviewers notice.

Concurrent sets#

There is no ConcurrentHashSet class, which is a common source of confusion. The three real options:

// Best general choice — a Set view over a ConcurrentHashMap, all its properties apply.
Set<String> concurrent = ConcurrentHashMap.newKeySet();
 
// Read-mostly. Every mutation copies the whole array; iteration is a snapshot
// and never throws ConcurrentModificationException.
Set<Listener> listeners = new CopyOnWriteArraySet<>();
 
// Sorted and concurrent — a skip list, O(log n), lock-free.
NavigableSet<Long> sorted = new ConcurrentSkipListSet<>();

CopyOnWriteArraySet deserves the caveat that it is backed by an array and contains is O(n), so it is only appropriate for small sets that are read far more often than written — a listener registry is the canonical example. ConcurrentHashMap.newKeySet() is the right default everywhere else.

Set operations#

Set<String> a = new HashSet<>(Set.of("x", "y", "z"));
Set<String> b = Set.of("y", "z", "w");
 
Set<String> union = new HashSet<>(a); union.addAll(b);          // x y z w
Set<String> inter = new HashSet<>(a); inter.retainAll(b);       // y z
Set<String> diff  = new HashSet<>(a); diff.removeAll(b);        // x

All three mutate the receiver, which is why each line copies first. There is no built-in non-destructive form; the stream equivalent (a.stream().filter(b::contains).collect(toSet())) is clearer for intersection and difference but allocates more.

One performance note that occasionally appears as a puzzle: removeAll switches strategy based on relative sizes. If the receiver is larger than the argument it iterates the argument; otherwise it iterates itself and calls contains on the argument. Passing a List as the argument therefore turns an O(n) operation into O(n·m). Always pass a Set.

What gets asked#

Usually: name the three implementations and their ordering; explain what backs each; and "what would you use for a set of enum values?" The EnumSet answer is a good differentiator, as is knowing that ConcurrentHashSet does not exist and ConcurrentHashMap.newKeySet() is the replacement.