Java HashSet & LinkedHashSet: Hashing, Buckets and Uniqueness

HashSet is the premier implementation of the Set interface in Java. It models the mathematical set abstraction: it stores strictly unique elements, allows at most one null element, and provides near-instantaneous O(1) time complexity for add, remove, and contains operations.

How HashSet Works Internally (The Secret)

A common interview question asks how HashSet stores data without duplicates. The secret is that HashSet is internally backed by a HashMap:

// Inside JDK java.util.HashSet:
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object(); // Dummy value

public boolean add(E e) {
    // Adds element as KEY into internal HashMap!
    return map.put(e, PRESENT) == null;
}

Code Demonstration: HashSet & LinkedHashSet

import java.util.HashSet;
import java.util.LinkedHashSet;

public class SetDemo {
    public static void main(String[] args) {
        // 1. HashSet: Unordered unique collection
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("Java");
        hashSet.add("Python");
        hashSet.add("JavaScript");
        hashSet.add("Java"); // DUPLICATE: Silently ignored!

        System.out.println("HashSet (No order guaranteed): " + hashSet); // [Java, JavaScript, Python]
        System.out.println("Contains Python? " + hashSet.contains("Python")); // true (O(1))

        // 2. LinkedHashSet: Preserves exact insertion order
        LinkedHashSet<String> orderedSet = new LinkedHashSet<>();
        orderedSet.add("First");
        orderedSet.add("Second");
        orderedSet.add("Third");
        orderedSet.add("First"); // Duplicate rejected!

        System.out.println("LinkedHashSet (Preserves order): " + orderedSet); // [First, Second, Third]
    }
}

The Mandatory hashCode() and equals() Contract