Topic 31 of 79

HashSet

Q: How does HashSet internally guarantee uniqueness?

HashSet is backed by a HashMap. When you call `set.add(element)`, it internally calls `map.put(element, DUMMY_OBJECT)`. Because HashMap keys must be unique, the set's elements are inherently unique. The `add()` method returns `true` if the element was new, and `false` if it was a duplicate (the map already had that key).

Q: Why must you override BOTH `hashCode()` and `equals()` when using a custom object in a HashSet?

Java's HashSet (and HashMap) first uses `hashCode()` to find the correct bucket. If two objects share a bucket (same hash), it then uses `equals()` to determine if they are truly the same element. If you override only `equals()` but not `hashCode()`, two logically equal objects may hash to different buckets and both get stored — completely breaking the uniqueness guarantee.

Overview

A HashSet is a collection that stores only unique elements. If you try to add a duplicate, the add() method simply returns false and the set remains unchanged. It is the go-to data structure whenever your primary requirement is "does this item already exist?" or "give me a deduplicated list".

Internally, HashSet is literally implemented as a HashMap where the element you add becomes the Key, and a static dummy Object is always used as the Value. This means HashSet inherits all the performance characteristics of HashMap: O(1) amortized time for add(), remove(), and contains().

Like HashMap, a HashSet makes no guarantees about the order of its elements. If you need a sorted unique collection, use TreeSet. If you need insertion-order uniqueness, use LinkedHashSet.

Syntax

Unique Elements and Set Operations

java

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

public class Main {
    public static void main(String[] args) {
        Set<String> visitedPages = new HashSet<>();
        
        // 1. Adding Elements (Duplicates are silently ignored)
        visitedPages.add("/home");
        visitedPages.add("/products");
        visitedPages.add("/home");   // Duplicate — ignored!
        visitedPages.add("/contact");
        
        System.out.println("Visited: " + visitedPages.size()); // 3, not 4!
        
        // 2. O(1) Membership Check
        if (!visitedPages.contains("/checkout")) {
            System.out.println("First visit to checkout!");
            visitedPages.add("/checkout");
        }
        
        // 3. Set Math Operations
        Set<Integer> setA = new HashSet<>(Set.of(1, 2, 3, 4, 5));
        Set<Integer> setB = new HashSet<>(Set.of(3, 4, 5, 6, 7));
        
        // Union (All elements from both sets)
        Set<Integer> union = new HashSet<>(setA);
        union.addAll(setB); // {1, 2, 3, 4, 5, 6, 7}
        
        // Intersection (Only common elements)
        Set<Integer> intersection = new HashSet<>(setA);
        intersection.retainAll(setB); // {3, 4, 5}
    }
}

Common Pitfalls

Assuming HashSet will maintain insertion order. Like HashMap, HashSet provides no ordering guarantee. If you need predictable iteration order, use LinkedHashSet (preserves insertion order) or TreeSet (natural sort order).
Storing mutable objects without overriding hashCode() and equals(). HashSet uses hashCode() to find the bucket and equals() to confirm a duplicate. If your custom class doesn't override both methods consistently, HashSet may store 'duplicate' objects because it compares memory addresses instead of logical equality.
Using a HashSet to check for duplicates on a List of custom objects without overriding hashCode(). This is an extremely common bug. Even if two objects represent the same real-world entity, without proper equals() and hashCode() overrides, the set treats them as different objects.

Interview Questions

How does HashSet internally guarantee uniqueness?

HashSet is backed by a HashMap. When you call set.add(element), it internally calls map.put(element, DUMMY_OBJECT). Because HashMap keys must be unique, the set's elements are inherently unique. The add() method returns true if the element was new, and false if it was a duplicate (the map already had that key).

Why must you override BOTH hashCode() and equals() when using a custom object in a HashSet?

Java's HashSet (and HashMap) first uses hashCode() to find the correct bucket. If two objects share a bucket (same hash), it then uses equals() to determine if they are truly the same element. If you override only equals() but not hashCode(), two logically equal objects may hash to different buckets and both get stored — completely breaking the uniqueness guarantee.

Real-World Example

Tracking unique website visitors for analytics in real time. For every incoming request, you check whether the user's session ID is in the HashSet. The O(1) lookup means this check adds virtually zero latency to every single page view, even at millions of requests per second.

example

java

Set<String> uniqueVisitors = new HashSet<>();

public void onRequest(HttpRequest req) {
    String sessionId = req.getHeader("Session-ID");
    
    // O(1) uniqueness check
    boolean isNewVisitor = uniqueVisitors.add(sessionId);
    
    if (isNewVisitor) {
        analytics.recordUniqueVisit();
    }
}

Check Your Knowledge

Test your understanding of HashSet with these quick questions.

What does `set.add(element)` return if the element already exists in the HashSet?

Which HashSet variant maintains insertion order?

A HashSet contains `Point(1,1)` and you try to add a new `Point(1,1)`. What happens if `Point` does NOT override `hashCode()`?

Take Java Quiz

Overview

Like HashMap, a HashSet makes no guarantees about the order of its elements. If you need a sorted unique collection, use TreeSet. If you need insertion-order uniqueness, use LinkedHashSet.

Syntax

Unique Elements and Set Operations

java

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

public class Main {
    public static void main(String[] args) {
        Set<String> visitedPages = new HashSet<>();
        
        // 1. Adding Elements (Duplicates are silently ignored)
        visitedPages.add("/home");
        visitedPages.add("/products");
        visitedPages.add("/home");   // Duplicate — ignored!
        visitedPages.add("/contact");
        
        System.out.println("Visited: " + visitedPages.size()); // 3, not 4!
        
        // 2. O(1) Membership Check
        if (!visitedPages.contains("/checkout")) {
            System.out.println("First visit to checkout!");
            visitedPages.add("/checkout");
        }
        
        // 3. Set Math Operations
        Set<Integer> setA = new HashSet<>(Set.of(1, 2, 3, 4, 5));
        Set<Integer> setB = new HashSet<>(Set.of(3, 4, 5, 6, 7));
        
        // Union (All elements from both sets)
        Set<Integer> union = new HashSet<>(setA);
        union.addAll(setB); // {1, 2, 3, 4, 5, 6, 7}
        
        // Intersection (Only common elements)
        Set<Integer> intersection = new HashSet<>(setA);
        intersection.retainAll(setB); // {3, 4, 5}
    }
}

Common Pitfalls

Assuming HashSet will maintain insertion order. Like HashMap, HashSet provides no ordering guarantee. If you need predictable iteration order, use LinkedHashSet (preserves insertion order) or TreeSet (natural sort order).
Storing mutable objects without overriding hashCode() and equals(). HashSet uses hashCode() to find the bucket and equals() to confirm a duplicate. If your custom class doesn't override both methods consistently, HashSet may store 'duplicate' objects because it compares memory addresses instead of logical equality.
Using a HashSet to check for duplicates on a List of custom objects without overriding hashCode(). This is an extremely common bug. Even if two objects represent the same real-world entity, without proper equals() and hashCode() overrides, the set treats them as different objects.

Interview Questions

How does HashSet internally guarantee uniqueness?

Why must you override BOTH hashCode() and equals() when using a custom object in a HashSet?

Real-World Example

example

java

Set<String> uniqueVisitors = new HashSet<>();

public void onRequest(HttpRequest req) {
    String sessionId = req.getHeader("Session-ID");
    
    // O(1) uniqueness check
    boolean isNewVisitor = uniqueVisitors.add(sessionId);
    
    if (isNewVisitor) {
        analytics.recordUniqueVisit();
    }
}

Check Your Knowledge

Test your understanding of HashSet with these quick questions.