Java sets

HashSet<E> stores each element once and answers contains in expected O(1). add returns true if the element was new and false if it was already present, which makes duplicate detection a one-liner. Iteration order is unspecified.

Elements need consistent hashCode and equals, exactly like map keys.

1static boolean hasDuplicate(int[] a) {
2    Set<Integer> seen = new HashSet<>();
3    for (int x : a) if (!seen.add(x)) return true;      // add returns false when x was already there
4    return false;
5}

LinkedHashSet is a HashSet that also threads a linked list through its elements, so iteration follows insertion order. Re-adding an element that is already present does not move it. Use it to remove duplicates while keeping the first-seen order, or when output must be reproducible.

1static List<Integer> dedupe(int[] a) {
2    Set<Integer> seen = new LinkedHashSet<>();
3    for (int x : a) seen.add(x);
4    return new ArrayList<>(seen);                       // first-seen order: [42, 7, 19, 3, 25, 16, 33] for the animation's input
5}

TreeSet keeps its elements sorted in a red-black tree: add, contains and remove are O(log n). It adds order-based queries: first, last, floor(x) (largest element ≤ x), ceiling(x) (smallest ≥ x), headSet, tailSet and subSet.

A TreeSet decides two elements are the same when its comparator returns 0, not when equals says so. With String.CASE_INSENSITIVE_ORDER, adding "a" and then "A" leaves a one-element set [a].

1static void sortedSet() {
2    TreeSet<Integer> s = new TreeSet<>(List.of(10, 20, 30));
3    System.out.println(s.floor(25) + " " + s.ceiling(25) + " " + s.first() + " " + s.headSet(20));   // 20 30 10 [10]
4    TreeSet<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
5    ci.add("a"); ci.add("A");
6    System.out.println(ci);                                                                          // [a]
7}

HashSet is a thin wrapper around a HashMap: every element is a key and every value is the same dummy object. add(e) is map.put(e, PRESENT) == null, contains(e) is map.containsKey(e) and remove(e) is map.remove(e) == PRESENT. LinkedHashSet wraps a LinkedHashMap and TreeSet wraps a TreeMap in the same way.

This explains why a set has the same costs, the same iteration order and the same hashCode/equals requirements as the corresponding map, and why a set uses more memory than the stored elements alone suggest.

1final class MiniSet<E> {
2    private static final Object PRESENT = new Object();
3    private final HashMap<E, Object> map = new HashMap<>();
4    boolean add(E e) { return map.put(e, PRESENT) == null; }          // null means the key was new
5    boolean contains(Object e) { return map.containsKey(e); }
6    boolean remove(Object e) { return map.remove(e) == PRESENT; }
7    int size() { return map.size(); }
8}

Three words are often confused. **Unordered**: no promise about iteration order (HashSet). **Ordered** (insertion-ordered): iteration follows the order in which elements were added (LinkedHashSet, ArrayList). **Sorted**: iteration follows a comparison order of the values themselves (TreeSet).

Run the animation and compare the three outputs for the same input values. Sorting costs O(log n) per operation; insertion order costs only memory.

1List<Integer> list = new ArrayList<>();
2Set<Integer> linked = new LinkedHashSet<>();
3Set<Integer> hash = new HashSet<>();
4Set<Integer> tree = new TreeSet<>();
5PriorityQueue<Integer> heap = new PriorityQueue<>();
6for (int x : arr) {
7    list.add(x);        // keeps insertion order, keeps duplicates
8    linked.add(x);      // keeps insertion order, drops duplicates
9    hash.add(x);        // order decided by hash buckets
10    tree.add(x);        // always sorted
11    heap.add(x);        // heap array: only the smallest is guaranteed first
12}
13System.out.println(list + " " + linked + " " + hash + " " + tree + " " + heap);