HashSet, ordering guarantees and duplicate rules

Understanding HashSet, ordering guarantees and duplicate rules

HashSet's contract covers membership only: it answers "is this element in here" in near constant time and says nothing about arrangement. The mental model is an array of slots, where each element is filed into the slot picked from its hash code, and iteration walks those slots from index 0 upward, emitting whatever it finds. So the order you observe is a by-product of hash values and the array's current length, not of insertion and not of natural ordering, and it changes as soon as the array grows or the element set differs. That order is reproducible on a given run and a given JDK, which is precisely why people mistake it for a promise.

A duplicate is not "the same object" and not "prints the same text"; it is an object for which equals returns true against something already in the set. HashSet only calls equals on candidates filed in the same slot, and the slot comes from hashCode, so two equal objects with different hash codes are usually never compared and both end up stored. That is the whole reason hashCode must agree with equals: equal objects must produce equal hash codes, and that is the direction that matters. add tells you the outcome, returning true when the set changed and false when an equal element was already present, in which case the newcomer is discarded and the first instance stays.

The hash is read once, at insert time, and the set never refiles an element on its own. Mutate a field that hashCode uses and the element is stranded in the slot for its old hash: contains and remove compute the new slot, find it empty, and report the element as absent while it sits in the set forever, which is how caches leak and dedup silently doubles up. Keep set elements immutable, with final fields or a record, and if any behaviour depends on the order elements come out, pick an implementation that specifies one (LinkedHashSet, TreeSet) rather than hoping HashSet preserves yours.

import java.util.HashSet;
import java.util.Set;

public class HashSetDuplicates {

    static final class Tag {
        private final String name;
        private final int addedBy;

        Tag(String name, int addedBy) {
            this.name = name;
            this.addedBy = addedBy;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Tag other && name.equals(other.name);
        }

        @Override
        public int hashCode() {
            return name.hashCode();
        }

        @Override
        public String toString() {
            return name + "/user" + addedBy;
        }
    }

    public static void main(String[] args) {
        Set<Tag> tags = new HashSet<>();

        System.out.println(tags.add(new Tag("java", 7)));
        System.out.println(tags.add(new Tag("java", 42)));
        System.out.println(tags.contains(new Tag("java", 999)));
        System.out.println(tags.size());
        System.out.println(tags);
    }
}

Worked examples

import java.util.HashSet;
import java.util.Set;

public class HashSetOrder {
    public static void main(String[] args) {
        Set<Integer> ids = new HashSet<>();
        for (int id : new int[] {5, 3, 20, 17, 1}) {
            ids.add(id);
        }

        System.out.println(ids);
        System.out.println(ids.equals(Set.of(1, 3, 5, 17, 20)));
    }
}

import java.util.HashSet;
import java.util.Set;

public class MutatedElement {

    static final class Box {
        int value;

        Box(int value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Box other && value == other.value;
        }

        @Override
        public int hashCode() {
            return value;
        }

        @Override
        public String toString() {
            return "Box(" + value + ")";
        }
    }

    public static void main(String[] args) {
        Box box = new Box(1);
        Set<Box> boxes = new HashSet<>();
        boxes.add(box);
        System.out.println(boxes.contains(box));

        box.value = 2;
        System.out.println(boxes.contains(box));
        System.out.println(boxes.remove(box));
        System.out.println(boxes.add(new Box(2)));
        System.out.println(boxes);
    }
}

import java.util.HashSet;
import java.util.Set;

public class FirstRepeat {
    public static void main(String[] args) {
        String[] words = {"the", "cat", "sat", "on", "the", "mat"};

        Set<String> seen = new HashSet<>();
        for (String word : words) {
            if (!seen.add(word)) {
                System.out.println("first repeat: " + word);
                break;
            }
        }

        System.out.println("distinct words before it: " + seen.size());
    }
}

Important notes

Common mistakes

Try it yourself