HashSet

#Introduction

HashSet is one of the most commonly asked Collection classes in Java interviews. If you understand HashSet properly, you will already understand a large part of:

• Hashing
• hashCode() and equals()
• Hash collisions and buckets
• Load factor and resizing
• Treeification
• HashMap internals

And that's why interviewers love it.

#What is HashSet?

HashSet is a Set implementation that stores unique elements using hashing.

Package:

java.util.HashSet

Declaration:

public class HashSet<E>
        extends AbstractSet<E>
        implements Set<E>,
                   Cloneable,
                   Serializable

Characteristics:

• No duplicate elements
• Allows one null
• No guaranteed ordering
• Average O(1) insertion, deletion and lookup
• Not synchronized
• Backed internally by a HashMap

#HashSet Internally Uses HashMap

You don't need to understand HashSet separately from HashMap. Once you understand HashMap internals, HashSet becomes very easy.

How Does HashSet Store an Element?

Set<String> set = new HashSet<>();
set.add("Java");

Internally, HashSet effectively does something similar to:

map.put("Java", PRESENT);

where:

private static final Object PRESENT = new Object();

The actual element becomes the key of the internal HashMap. The value is simply a dummy object.

Why Does HashSet Use HashMap?

Because HashMap already provides hashing, buckets, collision handling, resizing, hashCode()/equals() usage and treeification. There is no need to implement all of this again. HashSet simply uses the HashMap infrastructure to enforce uniqueness.

Simplified HashSet Source Code

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;
    }
}

#What Happens When We Call add()?

Set<String> set = new HashSet<>();
set.add("Java");

Hashing Process

Java obtains "Java".hashCode(), then HashMap applies its internal hash-spreading function.

#Buckets and Index Calculation

What is a Bucket?

A bucket is a location in the internal hash table where entries can be stored. An element's hash determines which bucket it belongs to.

Bucket Index Calculation

A common simplified explanation is:

index = hash & (n - 1);

where n = table length. For example, with table length 16: index = hash & 15. This works efficiently because HashMap capacities are maintained as powers of two.

Why Power of 2?

Interview favourite. HashMap uses table capacities that are powers of two — 16, 32, 64, 128, 256, …. This allows bucket calculation using hash & (n - 1) instead of the more expensive hash % n. It also works particularly well with the resize algorithm.

#Hash Collisions

What If Two Objects Go to the Same Bucket?

This is called a hash collision.

A good hash function reduces collisions, but cannot eliminate them.

Collision Handling

Modern HashMap handles collisions using a linked list or a Red-Black tree, depending on the number of entries in a bucket.

This process is called treeification. We'll study the exact thresholds below and in the HashMap chapter.

#How Does HashSet Prevent Duplicates?

This is the most important HashSet interview question.

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

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

hashCode() and equals()

Interview favourite. Hash-based collections use hashCode() + equals(). Both are important.

Why Do We Need Both?

Suppose we only used equals(). We would potentially have to compare the new object with every object in the Set — O(n) for every insertion.

Hashing first narrows the search to a particular bucket. Then equals() performs the final equality check among candidates. This gives HashSet its excellent average performance.

The hashCode() Contract

If two objects are equal (a.equals(b) == true), then they must have the same hash code (a.hashCode() == b.hashCode()).

But the reverse is NOT required. Two different objects can have the same hash code — that is a collision.

Same Hash Code Does NOT Mean Equal

Object A with hashCode = 100 and Object B with hashCode = 100 can still be different objects. Therefore:

• Same hashCode ⇏ same object
• equals() == true ⇒ same hashCode

#Custom Objects in HashSet

class Employee {
    int id;
    String name;

    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

Now:

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

employees.add(new Employee(101, "John"));
employees.add(new Employee(101, "John"));

Many beginners expect 1 employee. But without overriding equals() and hashCode(), 2 employees can be stored. Why? Because Object's default equality is based on object identity.

Correct Implementation

If Employee identity is based on id:

class Employee {

    int id;
    String name;

    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof Employee))
            return false;
        Employee other = (Employee) obj;
        return id == other.id;
    }

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

Now only one logical Employee is stored.

Why Must hashCode() Be Overridden Too?

Suppose you override only equals() but not hashCode(). Two logically equal objects may produce different hash codes, so they may go into different buckets. HashSet may never compare them with equals(). Result: a duplicate can be stored.

#Mutable Keys — Dangerous!

This is an advanced interview question.

class Employee {

    int id;

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

    @Override
    public boolean equals(Object obj) {
        // ...
    }
}

Employee e = new Employee(101);
Set<Employee> set = new HashSet<>();
set.add(e);

e.id = 200;   // mutate a field used by hashCode()

Now the object's hash code changes, but the object is still physically located in the bucket determined by the old hash. Therefore set.contains(e) may return false even though the object is physically inside the Set.

Why?

This is why objects used in hash-based collections should ideally have stable equality/hash-code fields while stored.

#Null and Ordering

Null in HashSet

HashSet allows one null.

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

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

[null]

Why only one? Because Set does not allow duplicates — the second null is considered a duplicate.

Ordering

HashSet does not guarantee insertion order.

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

set.add(50);
set.add(10);
set.add(30);
set.add(20);

Do not assume the output will be [50, 10, 30, 20] — it may appear in a different order.

#HashSet vs LinkedHashSet vs TreeSet

HashSet vs LinkedHashSet

Use HashSet when order doesn't matter; use LinkedHashSet when insertion order matters.

HashSet vs TreeSet

Use HashSet for uniqueness + speed; use TreeSet for uniqueness + sorted order.

#Capacity, Load Factor and Resizing

Initial Capacity

Set<Integer> set = new HashSet<>(100);

This creates a HashSet configured with an initial capacity of 100.

Load Factor

Interview favourite. The default load factor of HashMap — and therefore of HashSet — is 0.75. The load factor determines when the hash table should resize.

Threshold = Capacity × Load Factor

Example: Capacity = 16, Load Factor = 0.75 → Threshold = 12. When the number of entries reaches the resizing threshold, the table is resized.

Why 0.75?

It's a practical balance between memory usage and hash collision rate.

0.75 is a commonly effective trade-off.

Resizing

As the table grows and the threshold is exceeded, HashMap expands the table:

This operation is called rehashing / resizing. More precisely, modern HashMap implementations resize and redistribute entries; "rehashing" is commonly used in interview terminology.

Why Does Resizing Cost More?

Existing entries may need to be redistributed, so resizing is more expensive than a normal insertion.

But resizing happens infrequently, so average insertion remains O(1).

#Time Complexity and Treeification

Time Complexity

*For modern Java HashMap buckets that have been treeified. Under certain conditions and pathological/custom scenarios, exact behaviour can differ.

Why O(log n) After Treeification?

Suppose a bucket contains many entries. As a linked list (A → B → C → D → E → F), search is O(n). As a tree, search is O(log n):

This protects HashMap/HashSet from pathological collision chains.

Treeification

Interview favourite. When a bucket becomes sufficiently crowded, Java can convert the linked structure into a Red-Black Tree. Important thresholds in current HashMap implementations:

TREEIFY_THRESHOLD = 8
UNTREEIFY_THRESHOLD = 6
MIN_TREEIFY_CAPACITY = 64

Why Doesn't Java Treeify Immediately?

Tree nodes consume more memory than ordinary linked-list nodes. If the entire table is still small, increasing the table size can reduce collisions more cheaply. Therefore Java uses resizing first in smaller tables.

#Thread Safety and Iteration

HashSet is Not Thread-Safe

Interview favourite.

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

This is not thread-safe. Multiple threads modifying it concurrently can lead to incorrect behaviour.

Making HashSet Synchronized

Set<Integer> set = Collections.synchronizedSet(new HashSet<>());

This wraps the HashSet with synchronized access.

Concurrent Alternative

If you need a highly concurrent Set:

Set<Integer> set = ConcurrentHashMap.newKeySet();

This is generally preferable to synchronizing an entire HashSet when you need scalable concurrent access. We'll study this in the ConcurrentHashMap chapter.

Fail-Fast Iterator

HashSet iterators are generally fail-fast.

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

set.add(10);
set.add(20);
set.add(30);

for (Integer i : set) {
    if (i == 20) {
        set.remove(i);
    }
}

ConcurrentModificationException

because the Set was structurally modified outside the iterator.

Correct Removal During Iteration

Use the Iterator:

Iterator<Integer> itr = set.iterator();

while (itr.hasNext()) {
    Integer value = itr.next();
    if (value == 20) {
        itr.remove();
    }
}

Is Fail-Fast Guaranteed?

Important interview nuance: No. Fail-fast behaviour is a best-effort mechanism. You should not build application logic that depends on ConcurrentModificationException.

#HashSet in Practice

HashSet and Streams

Set<Integer> numbers = new HashSet<>();

numbers.add(10);
numbers.add(20);
numbers.add(30);

numbers.stream()
       .filter(n -> n > 10)
       .forEach(System.out::println);

Removing Duplicates from a List

One of the most common real-world uses of HashSet.

List<Integer> numbers = Arrays.asList(10, 20, 10, 30, 20);

Set<Integer> unique = new HashSet<>(numbers);

[10, 20, 30]

The resulting HashSet does not guarantee the original List's order. If order must be preserved:

Set<Integer> unique = new LinkedHashSet<>(numbers);

Real-World Use Cases

Duplicate Detection Pattern

Set<Integer> seen = new HashSet<>();

for (Integer number : numbers) {
    if (!seen.add(number)) {
        System.out.println("Duplicate: " + number);
    }
}

This works because add() returns true for a new element and false for a duplicate. It gives average O(n) duplicate detection across the entire collection — much better than comparing every pair, which can become O(n²).

HashSet vs ArrayList for contains()

For contains(500000):

If you frequently need membership checks and ordering/indexing isn't required, HashSet is often the better choice.

When Should You Use HashSet?

Need uniqueness + fast lookup + order doesn't matter. Examples: unique IDs, unique usernames, unique permissions, visited nodes, already processed records, duplicate detection.

When Should You NOT Use HashSet?

#The Most Important HashSet Flow

Memorize this — it is the foundation for understanding HashMap.

Interview Trap 1

Interview Trap 2

#Golden Rules

1. HashSet → HashMap internally
2. Element → HashMap key
3. Duplicate detection → hashCode() + equals()
4. Average operations → O(1)
5. No ordering guarantee

Final Mental Model