Java Set

›Short versionOpen if you only have a minute.

A set holds each element once. add returns false when an equal element is already present.
There is no index. The main operation is membership: contains, add, and remove(Object).
HashSet decides equality with equals, after hashCode picks a bucket. Average contains is constant time.
TreeSet decides equality with comparison. compare returning 0 means duplicate, even if equals disagrees.
Set promises no iteration order. LinkedHashSet preserves insertion order. TreeSet iterates in sorted order.
Do not mutate fields that equals, hashCode, or the comparator read while the object is in the set.

A is the collection you build when the question is . “Already counted,” “already visited,” “the distinct words” — each of those is a set, and a list would answer them with a linear scan.

The interface is small on purpose. Uniqueness has to mean something precise, and that meaning is together with for the hash implementations, or comparison for the sorted one.

Three implementations, three extra promises

HashSet is the default. is not part of what you may rely on. LinkedHashSet costs a pair of extra links per element and gives insertion order back. TreeSet costs logarithmic time and gives sorted order, plus the navigable methods that ask for the nearest neighbor.

Two sets are equal when they contain the same elements according to equals, regardless of implementation and regardless of order. A HashSet and a TreeSet with the same strings compare equal as sets. That check itself may cost more than a single contains.

Null is allowed once in HashSet and LinkedHashSet. TreeSet with natural ordering rejects null, because null has no compareTo.

One membership test

SetDemo.java

Set<String> seen = new HashSet<>();
seen.add("Ada");
seen.add("Ada");          // false, size stays 1
seen.contains("Ada");     // average O(1)

Set<String> inOrder = new LinkedHashSet<>();
inOrder.add("Grace");
inOrder.add("Ada");       // iteration follows these adds

Set<String> sorted = new TreeSet<>();
sorted.add("Grace");
sorted.add("Ada");        // iteration is Ada, then Grace

You need the distinct words in a paragraph, printed later in the order they first appeared. Which set do you construct?

Construct a LinkedHashSet. HashSet would drop duplicates and could scramble the printout. TreeSet would drop duplicates and print in sorted order, which is a different sequence from first appearance.