Skip to content
Tutorials Center
My learning

Topics

Lesson 84 of 201 ยท Collections

HashSet

Learn Java HashSet - storing unique values, add/contains/remove, union, intersection and difference, iteration order, and why equals and hashCode matter.

A set is a collection that never holds the same value twice. Add "apple" three times and the set still contains one "apple". That one rule makes sets the right tool for a whole family of everyday problems: removing duplicates, remembering what you've already seen, checking membership quickly, and comparing two groups of things ("which users are in both lists?").

HashSet is Java's general-purpose set. Under the hood it is a HashMap whose keys are your elements, so it inherits the map's speed: add, contains and remove take roughly the same time whether the set holds ten elements or ten million. This lesson covers how to use it, how to do set math, what "the same value" means to a HashSet, and the mistakes that make sets quietly hold duplicates.

Creating a HashSet and adding elements

Declare the variable with the Set interface and pick HashSet as the implementation, the same "program to interfaces" habit you met in The Collections Framework:

Java
Set<String> tags = new HashSet<>();

add returns a boolean: true if the element was new, false if the set already had it. That return value is easy to ignore, but it's useful: it answers "was this the first time?" in the same call that records the value.

Java add, contains, remove and size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The main operations at a glance:

Method What it does Returns
add(e) Adds e if it isn't already there true if the set changed
remove(o) Removes o if present true if the set changed
contains(o) Membership test boolean
size(), isEmpty() Number of elements int, boolean
addAll(c), retainAll(c), removeAll(c) Bulk changes (set math, below) true if the set changed
removeIf(predicate) Removes every element matching a condition true if anything was removed
clear() Removes everything nothing

A HashSet accepts one null element. Other sets, such as Set.of(...) and TreeSet with natural ordering, reject null, so don't build logic around storing it.

Removing duplicates

The most common job for a set is deduplication. The HashSet constructor accepts any collection, and duplicates simply collapse:

Java Deduplicating a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The seen.add(word) trick is worth remembering: one hash lookup both checks and records. Code that calls contains first and then add does two lookups for the same result.

Notice that this example prints sizes and membership instead of the sets themselves. That's deliberate, and the next section explains why.

Iteration order is not guaranteed

A HashSet stores elements in buckets chosen by their hash codes, not in the order you added them. When you print or loop over it, you get bucket order, which:

  • usually differs from insertion order,
  • can change when the set grows and rehashes,
  • can differ between Java versions.
Java Insertion order is lost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The HashSet line comes out in an order that looks random. It isn't random (run it again and you get the same result), but it's not one you chose, and you must never write code or tests that depend on it. If order matters, pick a different set:

Small Integer sets often appear sorted in a HashSet, because an Integer's hash code is the number itself. Don't trust it: negative numbers, large numbers or a different capacity break the pattern immediately. And Set.of(...) goes further: its order is deliberately shuffled differently on every JVM start, precisely so nobody depends on it.

Set operations: union, intersection, difference

Java has no union method. Instead, the bulk methods from Collection do set math in place, modifying the set you call them on. To keep your original sets intact, copy one first:

Math Meaning Java
A โˆช B (union) in A or B copy = new HashSet<>(a); copy.addAll(b);
A โˆฉ B (intersection) in both copy = new HashSet<>(a); copy.retainAll(b);
A โˆ’ B (difference) in A but not B copy = new HashSet<>(a); copy.removeAll(b);
A โ–ณ B (symmetric difference) in exactly one union minus intersection
A โІ B (subset) everything in A is in B b.containsAll(a)
disjoint nothing in common Collections.disjoint(a, b)
Java Course enrollment set math

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The example uses TreeSet so the printed results are sorted and easy to read; the methods are the same on every Set, including HashSet. Each bulk method returns true if it changed the set, so if (a.retainAll(b)) tells you whether anything was dropped.

With streams you can compute the same results without mutating anything, which some people find clearer:

Java
Set<String> both = java.stream()
        .filter(sql::contains)
        .collect(Collectors.toSet());

Streams covers this style in depth.

When you call a.removeAll(b) or a.retainAll(b), make b a Set as well. Each element of a is looked up in b, and looking something up in a List means scanning the whole list. With two lists of 100,000 items that's ten billion comparisons; with a set it's 100,000 quick hash lookups.

What "duplicate" means: equals and hashCode

A HashSet decides whether two objects are the same by asking two questions, in this order:

  1. hashCode(): which bucket should this object go in? Objects with different hash codes are assumed to be different and are never compared.
  2. equals(): inside that bucket, is there an object equal to this one?

Strings, numbers, records and enums already implement both correctly. Your own classes don't: a plain class inherits equals and hashCode from Object, which compare identity (is it the very same object in memory?). Two separately created objects with identical fields are therefore "different", and the set keeps both:

Java Duplicates sneak in without equals and hashCode

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The plain class reports a size of 2 and can't even find a point you're looking for, because a fresh new PointClass(1, 2) is a different object. The record works, because records generate equals and hashCode from their components.

For a regular class, override both methods together. The full contract is in The Object Class; here is the short version that works with sets:

Java
class Point {
    private final int x, y;

    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        return o instanceof Point other && x == other.x && y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Two rules matter most:

  • Equal objects must have equal hash codes. Override equals without hashCode and two equal objects land in different buckets; the set never compares them, and the duplicate stays.
  • Use the same fields in both. If equals compares x and y, hashCode should be built from x and y (or a subset of them, never extra fields).

Never change an element while it's in a set

The set filed each element in a bucket based on its hash code at the moment it was added. If you then change a field that feeds hashCode, the object now belongs in a different bucket, but it's still sitting in the old one. The set can no longer find it:

Java A mutated element gets lost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The set prints [published], yet contains(tag) with the exact same object returns false, remove fails, and adding it again creates a "duplicate" of one object. The fix is to use immutable elements (records, strings, immutable classes), or to remove an element, change it, and add it back. How HashMap Works Inside shows the bucket mechanics behind this bug.

Iterating and removing

A HashSet has no indexes, so there's no get(i). You read it with a for-each loop, forEach, or a stream. To remove elements while looping, don't call set.remove inside a for-each loop (that throws ConcurrentModificationException); use removeIf or an explicit iterator (Iterators and ListIterator):

Java Filtering a set safely

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Performance and capacity

add, remove and contains run in O(1) average time: compute the hash, jump to a bucket, compare a few elements. Compare that with List.contains, which checks every element until it finds a match. For membership tests on anything bigger than a handful of items, a set wins by a wide margin.

Like HashMap, a HashSet starts with 16 buckets and doubles when it is 75% full. Each resize rehashes every element. If you know roughly how many elements you'll add, size it once with HashSet.newHashSet(expectedSize) (Java 19+), which accounts for the load factor for you. The older new HashSet<>(n) constructor takes a bucket count, not an element count, so new HashSet<>(1000) still resizes before it holds 1,000 elements.

Two more practical points:

  • A HashSet uses noticeably more memory than an ArrayList of the same elements, because each element gets a map entry object. For a few million elements, that matters.
  • HashSet is not thread-safe. For shared sets use ConcurrentHashMap.newKeySet() (Concurrent Collections).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does new HashSet<>(List.of("a", "b", "a", "c", "b")).size() return?

    The constructor adds every element, and duplicates collapse. Three distinct values remain.
  2. 2. You add two objects of a plain class with identical fields to a HashSet, without overriding equals or hashCode. What is the size?

    Without overrides, equals and hashCode come from Object and treat separate objects as different. Records, or overriding both methods, fix it.
  3. 3. Sets a = {1, 2, 3} and b = {2, 3, 4}. After a.retainAll(b), what does a contain?

    retainAll keeps only the elements that are also in b, which is the intersection. It modifies a in place.
  4. 4. A class overrides equals but not hashCode. What happens when you put two equal instances in a HashSet?

    HashSet uses hashCode first to pick a bucket. Different hash codes mean equals is never called, so equal objects can both be stored.
  5. 5. Which statement about HashSet iteration order is true?

    Order follows the internal buckets. It is stable for an unchanged set but unspecified. Use LinkedHashSet for insertion order or TreeSet for sorted order.

Summary

  • A Set holds each value at most once; HashSet is the fast, general-purpose implementation, backed by a HashMap.
  • add returns false for duplicates, which lets you check and record in one call; contains, add and remove are O(1) on average.
  • Iteration order is unspecified. Use LinkedHashSet for insertion order and TreeSet for sorted order.
  • Set math is done in place with addAll (union), retainAll (intersection) and removeAll (difference); copy first to keep the originals.
  • Elements need correct equals and hashCode (records get them for free), and must not change while they're in the set.
  • Size big sets with HashSet.newHashSet(n), and use removeIf or an iterator to remove while looping.

Next: LinkedHashMap and LinkedHashSet, where you'll keep insertion order, track access order and build an LRU cache.