How Does HashSet Enforce Uniqueness so Fast?

A HashSet in Java is a hash table that refuses to hold two elements it considers the same. Two elements are "the same" when they are equal according to their own equals method, and the set finds them in roughly constant time because it hashes each element to find the right bucket instead of comparing against everything it holds.

How does a set decide that two things are the same?

Not by object identity, but by the equals contract. If your element type does not override equals and hashCode, two objects with identical contents are still two different elements as far as the set is concerned, and it will happily store both.

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

public class HashSetEqualsDemo {
    static class Tag {
        private final String name;

        Tag(String name) {
            this.name = name;
        }
    }

    static class ProperTag {
        private final String name;

        ProperTag(String name) {
            this.name = name;
        }

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

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

    public static void main(String[] args) {
        Set<Tag> plain = new HashSet<>();
        plain.add(new Tag("java"));
        plain.add(new Tag("java"));
        System.out.println("without equals and hashCode the set holds: " + plain.size());

        Set<ProperTag> proper = new HashSet<>();
        proper.add(new ProperTag("java"));
        proper.add(new ProperTag("java"));
        System.out.println("with equals and hashCode the set holds: " + proper.size());
    }
}

without equals and hashCode the set holds: 2
with equals and hashCode the set holds: 1

Both tags hold the string "java", yet the first set has two elements. The second set has one because the overrides let the set recognise that the two objects stand for the same thing. The same rule governs a HashMap's keys, and it applies to strings and boxed numbers out of the box, which is why new HashSet<>(List.of("a", "b", "a")) has two elements without any extra work from you.

What does add return, and why should you care?

add returns a boolean that says whether the element was new. It is false when an equal element was already present. Most code ignores the result, but it is the natural way to notice a duplicate without paying for a separate contains call.

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

public class HashSetBasicsDemo {
    public static void main(String[] args) {
        Set<String> languages = new HashSet<>();
        System.out.println("add java: " + languages.add("java"));
        System.out.println("add python: " + languages.add("python"));
        System.out.println("add java again: " + languages.add("java"));

        System.out.println("size: " + languages.size());
        System.out.println("contains java: " + languages.contains("java"));
        System.out.println("contains ruby: " + languages.contains("ruby"));

        System.out.println("remove java: " + languages.remove("java"));
        System.out.println("remove java again: " + languages.remove("java"));
        System.out.println("left inside: " + languages);

        Set<String> frozen = Set.of("a", "b");
        try {
            frozen.add("c");
        } catch (UnsupportedOperationException e) {
            System.out.println("Set.of is fixed size: " + e.getClass().getSimpleName());
        }
    }
}

add java: true
add python: true
add java again: false
size: 2
contains java: true
contains ruby: false
remove java: true
remove java again: false
left inside: [python]
Set.of is fixed size: UnsupportedOperationException

Both add and remove report whether they changed anything, which makes a set usable as a quick duplicate detector. The last line is a separate point: the set returned by Set.of is immutable, so an attempt to modify it throws UnsupportedOperationException rather than silently doing nothing.

How do the three set types differ?

All three enforce uniqueness. They differ in the order they hand their elements back to you, and that is the only thing to choose on.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class SetOrderingDemo {
    public static void main(String[] args) {
        List<String> words = List.of("delta", "alpha", "charlie", "bravo", "alpha");

        Set<String> hashed = new HashSet<>(words);
        Set<String> linked = new LinkedHashSet<>(words);
        Set<String> sorted = new TreeSet<>(words);

        System.out.println("HashSet order: " + hashed);
        System.out.println("LinkedHashSet order: " + linked);
        System.out.println("TreeSet order: " + sorted);
        System.out.println("sizes: " + hashed.size() + " " + linked.size() + " " + sorted.size());

        Set<String> unique = new LinkedHashSet<>(new ArrayList<>(words));
        System.out.println("deduplicated but still in first-seen order: " + unique);
    }
}

HashSet order: [bravo, alpha, delta, charlie]
LinkedHashSet order: [delta, alpha, charlie, bravo]
TreeSet order: [alpha, bravo, charlie, delta]
sizes: 4 4 4
deduplicated but still in first-seen order: [delta, alpha, charlie, bravo]

The LinkedHashSet line is the insertion order, and the TreeSet line is alphabetical. The HashSet line is neither, and that is not a bug: a hash set makes no promise about order, and the order you see depends on the hash codes of the elements and the size of the table. Write the test, not the order.

How do you remove duplicates from a list?

Pass the list to a set and take the result back as a list. Using LinkedHashSet keeps the first-seen order, which is usually what a person means by "remove duplicates".

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;

public class DedupDemo {
    public static void main(String[] args) {
        List<String> raw = new ArrayList<>(List.of("fig", "apple", "fig", "date", "apple"));
        List<String> unique = new ArrayList<>(new LinkedHashSet<>(raw));
        System.out.println("original: " + raw);
        System.out.println("deduplicated: " + unique);
        System.out.println("removed " + (raw.size() - unique.size()) + " duplicate(s)");
    }
}

original: [fig, apple, fig, date, apple]
deduplicated: [fig, apple, date]
removed 2 duplicate(s)

Swapping LinkedHashSet for HashSet deduplicates just as well but loses the order, and swapping it for TreeSet gives you alphabetical order instead. The set you pick here is a decision about the order you want, not about the duplicates you want to lose.

How do you use a set with other collections?

A set also answers questions about other collections. containsAll tells you whether one collection holds every element of another, retainAll keeps only the elements that appear in both, and removeAll drops the ones that do not. Each of them changes the set in place, so call retainAll on a copy if the original has to survive. These three methods are the clearest way to express "the common tags" or "the students in both groups" without writing a nested loop by hand.

A set is also a good companion to a list. When a list is long and you keep asking whether an item is in it, build a set from it once and test against that instead. The list keeps the order and the duplicates you need for display; the set answers the membership question quickly. That pairing shows up constantly in real code, wherever the same data is both displayed and filtered.

When is a set the wrong tool?

A set cannot hold duplicates and cannot be indexed. If your data legitimately repeats — a list of transactions where the same customer appears several times, a list of scores — then a set is the wrong shape, because building one silently drops data you meant to keep. Use a list for the raw data and a set only when you need a quick membership answer.

There is one more trap: elements must not change while they are in the set, for exactly the same reason map keys must not. If you mutate an element so that its hash code changes, the set can no longer find it. Treat set elements as immutable.

Set rules in brief

• Duplicates are rejected based on equals and hashCode, not on object identity.
• add and remove return whether they changed anything.
• A HashSet makes no promise about iteration order; LinkedHashSet keeps insertion order and TreeSet keeps sorted order.
• Elements must not be mutated while they are in the set.
• A set cannot hold duplicates and cannot be indexed — that is a feature when you want uniqueness and a bug when you do not.

Try it yourself: write a program that reads twelve words from a string array, adds each one to a HashSet and prints the result of every add call, so you can see exactly which words were repeats. Then build a LinkedHashSet from the same array and print it, checking that the first occurrence of each word comes first. Finally, print the size of all three set types and confirm they agree.