HashSet

A HashSet is a collection that stores unique elements with no defined order. Adding a value that is already present has no effect. Its main strength is speed: checking whether an element is in the set, adding one, and removing one all take constant time on average, no matter how large the set grows. HashSet is the standard tool for removing duplicates, tracking what has already been seen, and fast membership tests.

Creating and Using a HashSet

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

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("backend");
tags.add("java");                     // duplicate: ignored

System.out.println(tags.size());      // 2
System.out.println(tags.contains("backend"));   // true
tags.remove("backend");
System.out.println(tags);             // [java]

As with lists, declare the variable using the interface type, Set<String>, and choose the implementation on the right-hand side.

add returns whether the set changed

add returns true if the element was added and false if it was already present. This makes "check and insert" a single, efficient operation:

Set<String> seen = new HashSet<>();
for (String word : "to be or not to be".split(" ")) {
    if (!seen.add(word)) {
        System.out.println("Repeated: " + word);
    }
}
// Repeated: to
// Repeated: be

remove similarly returns true only if the element was present.

Core Methods

Compare contains on a HashSet with contains on an ArrayList: the list must scan every element, while the set jumps almost directly to the right place. For 1 million elements, that is the difference between up to 1,000,000 comparisons and typically one or two.

Removing Duplicates

Passing a collection to the HashSet constructor removes its duplicates:

List<Integer> withDupes = List.of(3, 1, 3, 2, 1, 3);
Set<Integer> unique = new HashSet<>(withDupes);
System.out.println(unique.size());     // 3

HashSet does not preserve the original order. When order matters, use LinkedHashSet (insertion order) or TreeSet (sorted order):

Set<Integer> inOrder = new LinkedHashSet<>(withDupes);   // [3, 1, 2]
Set<Integer> sorted = new TreeSet<>(withDupes);          // [1, 2, 3]

No Guaranteed Order

A HashSet stores elements according to their hash codes, not the order in which they were added:

Set<String> fruits = new HashSet<>(List.of("banana", "apple", "cherry", "date"));
System.out.println(fruits);   // e.g. [banana, date, apple, cherry]

The iteration order is an implementation detail. It can change when elements are added (as the internal table grows), and it may differ between Java versions. Never write code that depends on it, such as tests that compare toString() output of a HashSet.

How HashSet Works

Internally, a HashSet is backed by a HashMap: each element is stored as a key, with a shared dummy value. The map holds an array of buckets:

add("java")
  1. "java".hashCode()  → 3254818
  2. bucket index        → hash mixed and reduced to the table size, e.g. 2
  3. look in bucket 2: is there an element that equals "java"?
       no  → store it there
       yes → do nothing (duplicate)

buckets: [0]  [1]  [2]→"java"  [3]  [4]→"go"→"c"  ...

1. hashCode() turns the element into an integer, which selects a bucket.
2. equals() compares the element with any others already in that bucket.

Because only one bucket is examined, the operation does not depend on the total number of elements. When too many elements share a bucket, the bucket is converted to a balanced tree, so even badly distributed data stays reasonably fast. When the set becomes about 75% full (the default load factor of 0.75), the table doubles in size and elements are redistributed.

If you know the approximate number of elements in advance, you can avoid repeated resizing. Since Java 19, HashSet.newHashSet(expectedSize) creates a set sized correctly for that many elements.

equals and hashCode Must Be Correct

A HashSet relies entirely on its elements' equals and hashCode methods. String, wrapper classes, LocalDate, enums, and records implement both correctly. Your own classes must override both, consistently:

class Point {
    final int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }
    // no equals or hashCode
}

Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
System.out.println(points.contains(new Point(1, 2)));   // false: compared by identity

Without overrides, two Point objects with the same coordinates are different elements. Overriding only equals is not enough either: the two objects would almost always have different identity-based hash codes, land in different buckets, and never be compared. The contract is:

• If a.equals(b), then a.hashCode() == b.hashCode().
• hashCode must not change while the object is in the set.

A record satisfies this automatically:

record Point(int x, int y) { }
Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
System.out.println(points.contains(new Point(1, 2)));   // true

Do not mutate elements inside a set

If a field used by hashCode changes after the object is added, the object is now in the wrong bucket. The set can no longer find it, and it cannot be removed:

class Tag {
    String name;
    Tag(String name) { this.name = name; }
    @Override public boolean equals(Object o) { return o instanceof Tag t && t.name.equals(name); }
    @Override public int hashCode() { return name.hashCode(); }
}

Set<Tag> set = new HashSet<>();
Tag t = new Tag("java");
set.add(t);
t.name = "kotlin";                          // mutates a field used in hashCode
System.out.println(set.contains(t));        // false (almost certainly)
System.out.println(set.size());             // 1: a "lost" element

Use immutable objects (records, String, wrapper types) as set elements whenever possible.

Null Elements

HashSet allows a single null element. The immutable sets created by Set.of(...) do not, and throw NullPointerException for null. TreeSet does not accept null with natural ordering either.

Set Operations

Mathematical set operations map onto bulk methods. Because they modify the set they are called on, copy first when you need to keep the original:

Set<String> a = Set.of("java", "sql", "docker");
Set<String> b = Set.of("docker", "bash", "java");

Set<String> union = new HashSet<>(a);
union.addAll(b);                 // {java, sql, docker, bash}

Set<String> intersection = new HashSet<>(a);
intersection.retainAll(b);       // {java, docker}

Set<String> difference = new HashSet<>(a);
difference.removeAll(b);         // {sql}

boolean subset = a.containsAll(Set.of("java", "sql"));   // true

Set.of(...) creates an unmodifiable set, which is why the operations above start by copying into a new HashSet.

HashSet, LinkedHashSet, and TreeSet

Use HashSet by default, LinkedHashSet when insertion order matters (for example, displaying unique items in the order they were first seen), and TreeSet when you need sorted order or range queries. TreeSet is covered in the next lesson.

Practical Example: Course Enrollment

import java.util.*;

public class Enrollment {
    public static void main(String[] args) {
        List<String> signups = List.of(
            "ada@gocourse.in", "Linus@GoCourse.in", "grace@gocourse.in",
            "ada@gocourse.in", " linus@gocourse.in", "alan@gocourse.in");

        Set<String> unique = new LinkedHashSet<>();
        Set<String> duplicates = new LinkedHashSet<>();
        for (String raw : signups) {
            String email = raw.strip().toLowerCase();
            if (!unique.add(email)) {
                duplicates.add(email);
            }
        }

        Set<String> java = Set.of("ada@gocourse.in", "grace@gocourse.in", "alan@gocourse.in");
        Set<String> docker = Set.of("linus@gocourse.in", "grace@gocourse.in");

        Set<String> both = new TreeSet<>(java);
        both.retainAll(docker);

        Set<String> javaOnly = new TreeSet<>(java);
        javaOnly.removeAll(docker);

        Set<String> anyCourse = new TreeSet<>(java);
        anyCourse.addAll(docker);

        System.out.println("Unique sign-ups: " + unique);
        System.out.println("Duplicates:      " + duplicates);
        System.out.println("Both courses:    " + both);
        System.out.println("Java only:       " + javaOnly);
        System.out.println("Any course:      " + anyCourse.size() + " students");
    }
}

Output:

Unique sign-ups: [ada@gocourse.in, linus@gocourse.in, grace@gocourse.in, alan@gocourse.in]
Duplicates:      [ada@gocourse.in, linus@gocourse.in]
Both courses:    [grace@gocourse.in]
Java only:       [ada@gocourse.in, alan@gocourse.in]
Any course:      4 students

Normalizing each email (strip().toLowerCase()) before adding makes "Linus@GoCourse.in" and " linus@gocourse.in" the same element; a set only recognizes duplicates that are equals to each other. The return value of add identifies duplicates in the same step that records unique entries. LinkedHashSet keeps the output in sign-up order. The course comparisons copy each immutable Set.of(...) into a TreeSet before calling retainAll, removeAll, or addAll, which both keeps the originals intact and prints the results in sorted order. Every membership check inside these operations is a constant-time hash lookup, so the same code handles thousands of students as easily as five.