Sets: HashSet, LinkedHashSet, EnumSet

Q: What is Sets: HashSet, LinkedHashSet, EnumSet?

A Set holds each element at most once. HashSet is the fast default with no order, LinkedHashSet remembers insertion order, TreeSet keeps it sorted, and EnumSet is a tiny bit-set for enums.

Q: What are the most common mistakes with Sets: HashSet, LinkedHashSet, EnumSet?

Using List.contains in a loop on big data. Elements without equals/hashCode. Expecting HashSet to keep order.

A Set holds each element at most once.

🔎 Unravel this example Prerequisites (1)

Learn these first

Collections: List, Set, Map

At a glance

Mental model

A guest list that refuses duplicates: adding the same name twice changes nothing, and checking "is Alice invited?" is instant.

What happens, in order

1add returns false when the element was already there, which makes dedup easy: if (!seen.add(id)) continue;contains is O(1) for hash sets.
2Set algebra: a.addAll(b) is union, a.retainAll(b) is intersection, a.removeAll(b) is difference, a.containsAll(b) is subsetCopy first if you need the original: new HashSet<>(a).
3To remove duplicates from a list keeping order: new ArrayList<>(new LinkedHashSet<>(list))
4"Same element" means equals and hashCode match (for TreeSet: the comparator returns 0)

Remember

Mutating an element after adding it to a HashSet can make it unfindable, exactly as with HashMap keys
contains on a List is O(n); inside a loop it turns a linear algorithm into a quadratic one
HashSet wraps a HashMap<E, Object> and stores a shared dummy value for each key

Watch out

Using List.contains in a loop on big dataElements without equals/hashCodeExpecting HashSet to keep order

Example (highlighted lines explain it)

import java.util.*;public class Dedup {  static <T> List<T> unique(List<T> in) { return new ArrayList<>(new LinkedHashSet<>(in)); }  static Set<String> common(Set<String> a, Set<String> b) {    Set<String> both = new HashSet<>(a);    both.retainAll(b);    return both;  }  static boolean hasDuplicates(int[] ids) {    Set<Integer> seen = new HashSet<>();    for (int id : ids) if (!seen.add(id)) return true;    return false;  }}

line 3 uses LinkedHashSet, the core of Sets: HashSet, LinkedHashSet, EnumSet
line 5 uses HashSet, the core of Sets: HashSet, LinkedHashSet, EnumSet
line 6 uses retainAll, the core of Sets: HashSet, LinkedHashSet, EnumSet
line 10 uses HashSet, the core of Sets: HashSet, LinkedHashSet, EnumSet

Read the full explanation (about 1 min)

A Set holds each element at most once. HashSet is the fast default with no order, LinkedHashSet remembers insertion order, TreeSet keeps it sorted, and EnumSet is a tiny bit-set for enums.

A mental model

A guest list that refuses duplicates: adding the same name twice changes nothing, and checking "is Alice invited?" is instant.

How it works

add returns false when the element was already there, which makes dedup easy: if (!seen.add(id)) continue;. contains is O(1) for hash sets.

Set algebra: a.addAll(b) is union, a.retainAll(b) is intersection, a.removeAll(b) is difference, a.containsAll(b) is subset. Copy first if you need the original: new HashSet<>(a).

To remove duplicates from a list keeping order: new ArrayList<>(new LinkedHashSet<>(list)).

"Same element" means equals and hashCode match (for TreeSet: the comparator returns 0).

Going deeper

Mutating an element after adding it to a HashSet can make it unfindable, exactly as with HashMap keys. Use immutable elements.

contains on a List is O(n); inside a loop it turns a linear algorithm into a quadratic one. Putting the values into a HashSet first is the usual fix.

EnumSet is backed by one long for up to 64 constants, so it is the best way to hold a set of flags.

Under the hood

HashSet wraps a HashMap<E, Object> and stores a shared dummy value for each key. LinkedHashSet wraps a LinkedHashMap, TreeSet a TreeMap.

Common mistakes

Using List.contains in a loop on big data.
Elements without equals/hashCode.
Expecting HashSet to keep order.

How Unravel recognises it

When you paste code, Unravel looks for these signs of sets: hashset, linkedhashset, enumset. Spotting them yourself is a good habit when you read unfamiliar code:

Method calls: retainAll() removeAll() containsAll() Set.copyOf() EnumSet.of() EnumSet.noneOf() EnumSet.allOf() newKeySet()
Created with new: HashSet LinkedHashSet

Part of a learning path

Collections in depth · previous: Map idioms: merge, compute, entrySet · next: TreeMap, TreeSet and sorted collections

Related concepts

How HashMap worksJava language TreeMap, TreeSet and sorted collectionsJava language EnumsJava language

Frequently asked questions

What is Sets: HashSet, LinkedHashSet, EnumSet?

A Set holds each element at most once. HashSet is the fast default with no order, LinkedHashSet remembers insertion order, TreeSet keeps it sorted, and EnumSet is a tiny bit-set for enums.

What are the most common mistakes with Sets: HashSet, LinkedHashSet, EnumSet?

Using List.contains in a loop on big data. Elements without equals/hashCode. Expecting HashSet to keep order.

How can I see Sets: HashSet, LinkedHashSet, EnumSet in real code?

Paste your own Java into Unravel and it will point out where sets: hashset, linkedhashset, enumset appears, explain how it works at the detail level you choose, and draw the flow of the code around it.