How does a HashSet ensure that there are no duplicates?

HashSet prevents duplicate elements by internally using a HashMap. When an element is added, HashSet calculates its hash code and determines its storage location. Before inserting the element, it checks whether an equivalent element already exists using the hashCode() and equals() methods. If a matching element is found, the new element is not added.

Key Points: • HashSet stores unique elements only. • Internally, HashSet is backed by a HashMap. • Duplicate detection relies on hashCode() and equals() methods. • If an identical element already exists, the add() operation returns false. • Proper implementation of hashCode() and equals() is essential for custom objects.

How HashSet Works Internally:

When an element is added:

1. HashSet calculates the element's hash code. 2. The hash code determines the bucket location. 3. HashSet checks whether an equal element already exists in that bucket. 4. If no matching element is found, the element is added. 5. If a matching element exists, the insertion is ignored.

Internal Representation:

HashSet<String> names =
        new HashSet<>();

Internally behaves similar to:

HashMap<String, Object> map =
        new HashMap<>();

Each HashSet element becomes a key in the HashMap, while a constant dummy value is stored as the value.

Why Duplicates Are Not Allowed?

HashMap keys must be unique.

Since HashSet stores elements as HashMap keys, duplicate elements cannot exist.

Example:

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

skills.add("Java");
skills.add("Spring");
skills.add("Java");

Output:

[Java, Spring]

The second "Java" is ignored because it already exists.

Code Example:

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

public class Demo {

    public static void main(String[] args) {

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

        System.out.println(
                technologies.add("Java"));

        System.out.println(
                technologies.add("Spring"));

        System.out.println(
                technologies.add("Java"));

        System.out.println(technologies);
    }
}

Output:

true
true
false

[Java, Spring]

Role of hashCode() and equals():

hashCode(): • Determines the bucket location.

equals(): • Confirms whether two objects are actually equal.

For custom classes, both methods should be overridden properly.

Example:

class Employee {

    private int id;

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public boolean equals(Object obj) {

        if (this == obj) {
            return true;
        }

        if (!(obj instanceof Employee)) {
            return false;
        }

        Employee emp = (Employee) obj;

        return this.id == emp.id;
    }
}

Without proper hashCode() and equals() implementations, HashSet may allow logically duplicate objects.

Real-World Example:

Suppose a system stores registered email addresses.

HashSet ensures:

• No duplicate email addresses • Fast lookup performance • Efficient insertion and deletion

Interview Tip: A concise interview answer is:

"HashSet ensures uniqueness by internally using a HashMap. Each element is stored as a key, and before adding a new element, HashSet uses hashCode() to locate the bucket and equals() to check for equality. If an equivalent element already exists, the new element is not added."