HashSet Internal Working in Java with Examples

HashSet is one of the most commonly used collection classes in Java. It is used whenever we need to store unique elements and want fast lookup performance. Although HashSet appears simple from the outside, its internal implementation is extremely interesting because it is actually backed by a HashMap.

In this article, we will explore how HashSet works internally, how it ensures uniqueness, how hashCode() and equals() play important roles, and common interview questions related to HashSet.

What is HashSet?

HashSet is a collection that implements the Set interface and does not allow duplicate elements. It is part of the Java Collections Framework.

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

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

System.out.println(technologies);

Output

[Java, Spring]

Even though "Java" was added twice, HashSet stored it only once.

Important Characteristics of HashSet

• Stores unique elements only.
• Does not maintain insertion order.
• Allows one null value.
• Provides fast search operations.
• Uses HashMap internally.
• Not thread-safe.

How HashSet Works Internally

Many Java developers are surprised to learn that HashSet internally uses a HashMap. When you add an element to HashSet, it actually becomes a key inside an internal HashMap.

Simplified implementation:

public class HashSet<E> {

    private transient HashMap<E,Object> map;

    private static final Object PRESENT =
            new Object();

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

Notice that:

• HashSet element becomes HashMap key.
• A dummy object is stored as value.
• Uniqueness comes from HashMap key uniqueness.

What Happens When We Add an Element?

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

set.add("Java");

Internally:

map.put("Java", PRESENT);

HashMap stores "Java" as the key and a constant dummy object as the value.

How Duplicate Elements Are Prevented

set.add("Java");
set.add("Java");

HashMap does not allow duplicate keys. Since HashSet uses HashMap keys for storage, duplicate elements are automatically rejected.

The second insertion finds that the key already exists and therefore no new entry is added.

Role of hashCode()

When an object is added to HashSet, Java first calculates its hashCode().

String language = "Java";

int hash = language.hashCode();

System.out.println(hash);

The generated hash value helps determine the bucket location where the object should be stored.

Role of equals()

hashCode() identifies the bucket. equals() identifies the actual object inside the bucket.

Both methods work together to ensure uniqueness.

Example

public class Employee {

    private int id;

    public Employee(int id) {
        this.id = 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;
    }

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

Without properly overriding equals() and hashCode(), duplicate objects may be added unexpectedly.

Example with Custom Objects

Set<Employee> employees =
        new HashSet<>();

employees.add(new Employee(1));
employees.add(new Employee(1));

System.out.println(employees.size());

Output

1

Since equals() and hashCode() are overridden correctly, HashSet identifies both objects as duplicates.

What Happens During Lookup?

set.contains("Java");

HashSet performs:

1. Calculates hashCode().
2. Locates bucket.
3. Uses equals() to verify element.
4. Returns result.

This is why contains() is usually very fast.

Can HashSet Store Null Values?

Yes. HashSet allows only one null value.

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

set.add(null);
set.add(null);

System.out.println(set.size());

Output

1

Iteration Order

HashSet does not guarantee insertion order.

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

set.add("C");
set.add("Java");
set.add("Spring");

System.out.println(set);

The output order may vary.

Time Complexity

Operation	Average Complexity
Add	O(1)
Contains	O(1)
Remove	O(1)

Worst-case performance can degrade when many collisions occur.

HashSet vs ArrayList

Feature	HashSet	ArrayList
Duplicates	Not Allowed	Allowed
Ordering	No	Yes
Search Performance	Fast	Slower

Common Interview Questions

Does HashSet allow duplicate values?

No. HashSet stores only unique elements.

How does HashSet ensure uniqueness?

It uses hashCode() and equals() methods together. Internally uniqueness is maintained by HashMap.

Can HashSet contain null?

Yes. Only one null value is allowed.

Is HashSet ordered?

No. HashSet does not maintain insertion order.

Which collection should be used when uniqueness is required?

HashSet is usually the preferred collection when duplicate values should not be stored.

Add links to the above articles once they are published on JavaCompass.

Frequently Asked Questions (FAQ)

Does HashSet use HashMap internally?

Yes. HashSet stores all elements as keys inside an internal HashMap.

Can HashSet have multiple null values?

No. Only one null value is allowed.

Which methods are important for HashSet?

hashCode() and equals() are crucial because they determine hashing and uniqueness.

Is HashSet thread-safe?

No. For concurrent environments, consider using ConcurrentHashMap-based solutions or synchronized collections.

Keywords

HashSet Internal Working, HashSet Interview Questions, HashSet Example Java, How HashSet Works Internally, HashSet Java Collections, HashSet vs ArrayList, HashSet hashCode equals, Java Collections Framework, HashSet Implementation, HashSet Performance, HashSet Duplicate Elements, HashSet Time Complexity, HashSet Internal Architecture, Java Set Interface, Core Java Collection Questions