ComparisonDifficulty: Intermediate1 min

HashSet vs LinkedHashSet vs TreeSet

The same promise, three iteration orders, and three different costs.

HashSet, LinkedHashSet and TreeSet all implement Set and all keep each element once. They differ in something the interface does not mention: the order you get elements back in, and what that costs.

The three sets on iteration order, cost and what they require of elements
Class	Iterates in	Add and contains	Requires of elements
`HashSet`	No promised order at all	Constant	`hashCode` and `equals`
`LinkedHashSet`	The order you added them	Constant, plus two pointers each	`hashCode` and `equals`
`TreeSet`	Sorted	Proportional to the logarithm of the size	`Comparable`, or a `Comparator`

The same three words added to each set, in the same order:

java

for (Set<String> s : List.of(new HashSet<String>(), new LinkedHashSet<String>(), new TreeSet<String>())) {
    s.addAll(List.of("pear", "apple", "fig"));
    System.out.println(s);
}

text

[apple, pear, fig]
[pear, apple, fig]
[apple, fig, pear]

The decision rule. Use HashSet unless you need an order. Use LinkedHashSet when the output should match the input order or be reproducible. Use TreeSet when you need the elements sorted, or the questions only a sorted set can answer, such as first, last, headSet and ceiling. All three share add, contains and remove, so switching between them is one word after new.

← → move through sections and cards