HashSet

TL;DR

• HashSet is a collection that implements the Set interface, ensuring no duplicate elements.
• It does not guarantee any order (insertion order is not maintained).
• Provides $O(1)$ constant time performance for add, remove, and contains.
• Allows exactly one null element.

Concept

Under the hood, a HashSet is literally just a HashMap.

When you add an element to a HashSet (e.g., set.add("Apple")), Java internally stores it in a HashMap. The element you are adding becomes the key in the map, and Java uses a dummy, constant object (new Object()) as the value.

Because HashMaps guarantee unique keys, the HashSet guarantees unique elements.

How it determines uniqueness

It relies strictly on the hashCode() and equals() methods of the objects you insert.

1. It calls hashCode() to find the memory bucket.
2. If the bucket has items, it calls equals() on them to check if the new item is truly a duplicate.

Examples

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

public class HashSetExample {
    public static void main(String[] args) {
        Set<String> colors = new HashSet<>();
        
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        
        // Trying to add a duplicate
        boolean isAdded = colors.add("Red"); 
        System.out.println("Was duplicate added? " + isAdded); // false
        
        // Output order is unpredictable (not necessarily Red, Green, Blue)
        System.out.println(colors); 
        
        // Fast O(1) lookup
        if (colors.contains("Green")) {
            System.out.println("Green exists!");
        }
    }
}

Interview Questions

Q: How does HashSet handle null values?
A: HashSet allows a single null value. In the underlying HashMap, the hash code for null is always hardcoded to 0, meaning the null element is always placed in the very first bucket (index 0) of the map’s internal array.

Q: Why is overriding hashCode and equals mandatory when using custom objects in a HashSet?
A: If you don’t override them, the HashSet uses the default Object implementations (which compare memory addresses). You could add two Person("John", 25) objects, and the HashSet would treat them as two completely different elements and allow the duplicate, because their memory addresses are different.