# Part 5 — HashSet Deep Dive

One of the most common interview questions is:

"Why does HashSet internally use HashMap?"

If you can answer that clearly and explain the implementation, you're already ahead of many candidates.

1. What is HashSet?¶

HashSet is an implementation of the Set interface backed internally by a HashMap.

Characteristics:

• Stores unique elements
• No duplicate elements
• Allows one null element
• Does not maintain insertion order
• Not synchronized
• Average O(1) operations

Example:

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

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

System.out.println(set);

Output:

[Java, Python]

The second "Java" is ignored.

2. Class Hierarchy¶

Object
   │
AbstractCollection
   │
AbstractSet
   │
HashSet

Interfaces:

Iterable
    │
Collection
    │
Set
    │
HashSet

3. Internal Implementation¶

This is the most important interview topic.

Simplified source code:

public class HashSet<E> extends AbstractSet<E> {

    private transient HashMap<E, Object> map;

    private static final Object PRESENT = new Object();
}

Notice:

HashSet contains a HashMap.

It does not implement hashing from scratch.

4. Why Does HashSet Use HashMap?¶

A set only stores keys.

A map stores:

Key -> Value

HashSet simply stores every element as the key.

Example:

set.add("Java");

Internally:

map.put("Java", PRESENT);

where:

private static final Object PRESENT = new Object();

Memory:

HashSet

↓

HashMap

↓

Java

↓

PRESENT

The value is meaningless.

Only the key matters.

5. Why Use a Dummy Object?¶

Suppose we have:

set.add("Apple");

Internally:

map.put("Apple", PRESENT);

Why not store:

map.put("Apple", null);

Because:

• A shared dummy object avoids ambiguity with legitimate null values.
• The same singleton PRESENT object is reused for every entry, so only one dummy object is allocated.

6. add() Operation¶

Example:

set.add("Java");

Internally:

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

Explanation:

If the key didn't exist:

map.put()

↓

returns null

↓

true

If the key already existed:

map.put()

↓

returns old value

↓

false

7. Duplicate Detection¶

Example:

set.add("Java");

set.add("Java");

First insertion:

Bucket

↓

Java

Second insertion:

HashMap:

hashCode()

↓

bucket

↓

equals()

↓

Key already exists

No new node is inserted.

8. contains()¶

Example:

set.contains("Java");

Internally:

map.containsKey("Java");

Complexity:

Average:

O(1)

9. remove()¶

Example:

set.remove("Java");

Internally:

map.remove("Java");

Average complexity:

O(1)

10. Null Element¶

HashSet allows one null.

Example:

set.add(null);

Internally:

map.put(null, PRESENT);

Second insertion:

set.add(null);

Ignored.

Only one null element exists.

11. Memory Layout¶

Suppose:

set.add("A");
set.add("B");
set.add("C");

Internally:

HashMap

A -> PRESENT

B -> PRESENT

C -> PRESENT

There is no separate HashSet storage.

Everything is inside the HashMap.

12. Why Duplicates Are Not Allowed¶

Suppose:

set.add("Apple");

set.add("Apple");

HashMap checks:

hashCode()

↓

bucket

↓

equals()

↓

same key

↓

replace value

Since the value is always PRESENT, nothing changes.

Result:

Only one "Apple".

13. Importance of equals() and hashCode()¶

Consider:

class Employee {

    int id;
}

Employee e1 = new Employee(1);
Employee e2 = new Employee(1);

set.add(e1);

set.add(e2);

Without overriding equals() and hashCode():

Result:

2 elements

Why?

Default implementation compares references.

With proper overrides:

1 element

14. HashSet vs ArrayList¶

15. HashSet vs LinkedHashSet¶

HashSet:

C

A

B

Order is unspecified.

LinkedHashSet:

A

B

C

Maintains insertion order.

Internally:

LinkedHashMap

instead of HashMap.

16. HashSet vs TreeSet¶

17. Time Complexity¶

*Worst case depends on whether the bucket is treeified.

18. Common Interview Questions¶

Q1. Why does HashSet use HashMap?¶

Because a set only needs unique keys.

HashMap already provides:

• Hashing
• Collision handling
• Duplicate detection
• Efficient lookup

Q2. What value does HashSet store?¶

PRESENT

A single shared dummy object.

Q3. How does HashSet detect duplicates?¶

Using:

hashCode()

↓

bucket

↓

equals()

Exactly the same mechanism as HashMap.

Q4. Does HashSet preserve insertion order?¶

No.

Use:

LinkedHashSet

if insertion order matters.

Q5. Why is contains() O(1)?¶

Because it delegates to HashMap.containsKey().

Q6. Can HashSet store duplicate null values?¶

No.

Only one null element.

Q7. Why doesn't HashSet implement its own hashing algorithm?¶

Because HashMap already provides a highly optimized, thoroughly tested hash table implementation.

Reusing it avoids code duplication and maintenance complexity.

Q8. Why is equals() important in HashSet?¶

HashSet relies on equals() to determine whether two elements are logically identical within the same bucket.

Q9. What happens if hashCode() always returns 1?¶

All elements go into the same bucket.

Performance degrades significantly due to collisions.

Q10. Is HashSet thread-safe?¶

No.

For concurrent use, consider:

• ConcurrentHashMap.newKeySet()
• Collections.synchronizedSet(...) (simple synchronization)
• Other concurrent set implementations depending on the use case

Production Examples¶

Removing Duplicates¶

List<String> names = List.of(
    "John",
    "John",
    "Alice",
    "Bob",
    "Alice"
);

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

Result:

John
Alice
Bob

Fast Membership Check¶

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

blockedUsers.add(1001);
blockedUsers.add(2002);

if (blockedUsers.contains(userId)) {
    // deny access
}

Lookup remains efficient even with large datasets.

Senior Interview Scenario¶

Question:

Why doesn't HashSet store elements directly instead of using a HashMap?

Strong Answer:

Because a HashSet and a HashMap share the same underlying requirements:

• Efficient hashing
• Collision resolution
• Duplicate detection
• Resizing
• Treeification
• Load-factor management

Rather than duplicating this complex implementation, HashSet delegates all of it to HashMap and uses the set element as the map key with a single shared dummy value (PRESENT).

This is a classic example of composition over duplication.

Key Takeaways¶

• HashSet is implemented using a HashMap.
• Each element becomes a key in the underlying map.
• The associated value is a shared dummy object called PRESENT.
• Duplicate detection relies on hashCode() and equals().
• Average add(), remove(), and contains() operations are O(1).
• HashSet does not guarantee iteration order.
• Correct implementations of equals() and hashCode() are essential for proper behavior.

Next: Part 6 — TreeMap & TreeSet Deep Dive¶

We'll cover:

• Binary Search Trees vs Red-Black Trees
• Why Java uses Red-Black Trees
• Rotations (left/right)
• Balancing rules
• Comparable vs Comparator
• Internal implementation of TreeMap
• NavigableMap and NavigableSet
• Range queries (floor, ceiling, higher, lower)
• Performance analysis
• Senior-level interview questions