Definition
- Internal structure:
private transient HashMap– a plain HashMap - Dummy value:
private static final Object PRESENT = new Object()– one object shared by all entries - add(e): calls
map.put(e, PRESENT)and returns true if put returned null (new key), false if key already existed - contains(e): calls
map.containsKey(e)– O(1) hash lookup - remove(e): calls
map.remove(e)– O(1) hash lookup - All HashMap properties are inherited: capacity, load factor, treeification, null handling
HashSet is like a filing cabinet (HashMap) where every drawer has a label (your element as the key) and inside every drawer is the same rubber stamp saying "PRESENT" (the dummy value). You only care about the drawer labels – the set elements. Adding a duplicate label? HashMap says "this key already exists," so HashSet says "rejected."
Understanding the Concepts
How does HashSet work internally?
HashSet delegates everything to a HashMap. Understanding this is the key to understanding all Set behavior.
Here is the actual structure from OpenJDK, simplified:
package com.bank.demo;
import java.util.*;
public class HashSetInternalsDemo {
// Simplified from OpenJDK source
static class SimpleHashSet<E> {
private final HashMap<E, Object> map;
private static final Object PRESENT = new Object();
public SimpleHashSet() {
this.map = new HashMap<>();
}
public SimpleHashSet(int initialCapacity) {
this.map = new HashMap<>(initialCapacity);
}
public boolean add(E e) {
return map.put(e, PRESENT) == null;
// put returns null → key was NEW → return true
// put returns PRESENT → key EXISTED → return false
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
public int size() {
return map.size();
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
}
public static void main(String[] args) {
Set<String> accounts = new HashSet<>();
System.out.println("add SAV2001: " + accounts.add("SAV2001")); // true
System.out.println("add CUR3001: " + accounts.add("CUR3001")); // true
System.out.println("add SAV2001: " + accounts.add("SAV2001")); // false – duplicate!
System.out.println("contains SAV2001: " + accounts.contains("SAV2001")); // true
System.out.println("size: " + accounts.size()); // 2
System.out.println("remove SAV2001: " + accounts.remove("SAV2001")); // true
System.out.println("size after remove: " + accounts.size()); // 1
}
}
add SAV2001: true
add CUR3001: true
add SAV2001: false
contains SAV2001: true
size: 2
remove SAV2001: true
size after remove: 1
Why does the dummy PRESENT value exist?
HashMap requires both a key and a value. Since HashSet only cares about keys (the elements), every entry shares the same value: a single Object instance called PRESENT. This wastes no additional memory per entry because PRESENT is a static final field – one object for the entire application.
The PRESENT object is never returned to user code. It exists solely to satisfy HashMap's key-value contract.
What HashMap properties does HashSet inherit?
Because HashSet delegates to HashMap, it inherits all of HashMap's characteristics:
| Property | Value | Source |
|---|---|---|
| Default capacity | 16 | HashMap default |
| Load factor | 0.75 | HashMap default |
| Resize trigger | size > capacity * 0.75 | HashMap |
| Treeification | Chain >= 8 nodes | HashMap (Java 8+) |
| Null element | One null allowed | HashMap allows one null key |
| Hash function | hashCode() ^ (hashCode >>> 16) | HashMap spreading |
| Iteration order | Unpredictable | HashMap |
package com.bank.demo;
import java.util.*;
public class HashSetPropertiesDemo {
public static void main(String[] args) {
// One null element allowed (HashMap allows one null key)
Set<String> set = new HashSet<>();
set.add(null);
set.add(null); // duplicate null – ignored
System.out.println("Null in set: " + set.contains(null)); // true
System.out.println("Size: " + set.size()); // 1
// Pre-sizing works the same as HashMap
int expected = 10_000;
Set<String> preSized = new HashSet<>(expected * 4 / 3 + 1);
// Avoids resizing for up to 10K elements
}
}
Null in set: true
Size: 1
Why must elements implement hashCode() and equals()?
Since elements are used as HashMap keys, they must implement a proper hashCode() and equals() contract. Without these, two logically equal objects are treated as different set members.
package com.bank.demo;
import java.util.*;
public class HashCodeEqualsDemo {
// WRONG: no hashCode/equals override
static class BadAccount {
String id;
BadAccount(String id) { this.id = id; }
}
// CORRECT: proper hashCode and equals
static class GoodAccount {
final String id;
GoodAccount(String id) { this.id = id; }
@Override public int hashCode() { return id.hashCode(); }
@Override public boolean equals(Object o) {
return o instanceof GoodAccount ga && ga.id.equals(this.id);
}
}
public static void main(String[] args) {
// Without hashCode/equals: duplicates sneak in
Set<BadAccount> bad = new HashSet<>();
bad.add(new BadAccount("SAV2001"));
bad.add(new BadAccount("SAV2001"));
System.out.println("Bad set size: " + bad.size()); // 2 – wrong!
// With hashCode/equals: uniqueness works
Set<GoodAccount> good = new HashSet<>();
good.add(new GoodAccount("SAV2001"));
good.add(new GoodAccount("SAV2001"));
System.out.println("Good set size: " + good.size()); // 1 – correct!
}
}
Bad set size: 2
Good set size: 1
How does the same pattern apply to LinkedHashSet and TreeSet?
| Set | Internal Map | Ordering | Performance |
|---|---|---|---|
| HashSet | HashMap | No ordering | O(1) |
| LinkedHashSet | LinkedHashMap | Insertion order | O(1) |
| TreeSet | TreeMap | Sorted order | O(log n) |
LinkedHashSet extends HashSet but passes a LinkedHashMap to the superclass constructor. TreeSet wraps a TreeMap. The pattern is identical: elements are map keys, values are PRESENT (or the map's internal mechanics).
package com.bank.demo;
import java.util.*;
public class SetOrderingDemo {
public static void main(String[] args) {
List<String> accounts = List.of("CUR3001", "SAV2001", "FD4001");
System.out.println("HashSet: " + new HashSet<>(accounts));
System.out.println("LinkedHashSet: " + new LinkedHashSet<>(accounts));
System.out.println("TreeSet: " + new TreeSet<>(accounts));
}
}
HashSet: [FD4001, CUR3001, SAV2001]
LinkedHashSet: [CUR3001, SAV2001, FD4001]
TreeSet: [CUR3001, FD4001, SAV2001]
What about memory overhead?
Each element in a HashSet is stored as a HashMap Node: object header (12-16 bytes) + hash (4 bytes) + key reference (4 bytes) + value reference to PRESENT (4 bytes) + next pointer (4 bytes) + padding. Total: approximately 32-48 bytes per element.
The PRESENT object itself is a single static instance shared by all entries. It adds no per-element overhead.
For memory-sensitive applications with large sets, consider alternatives like a BitSet (for integers), EnumSet (for enum constants, uses bit vector internally), or a sorted array with binary search.
What are common mistakes?
Mistake 1: Not overriding hashCode when overriding equals
// WRONG: equals overridden but hashCode not
class Account {
String id;
@Override public boolean equals(Object o) {
return o instanceof Account a && a.id.equals(this.id);
}
// No hashCode override – uses Object.hashCode (identity)
// Two equal accounts may have different hash codes → different buckets
// → HashSet treats them as different elements!
}
Mistake 2: Using ArrayList.contains instead of HashSet.contains
// WRONG: O(n) per check for 50K elements
List<String> blockedAccounts = new ArrayList<>(/* 50K entries */);
if (blockedAccounts.contains(accountId)) { } // scans entire list!
// CORRECT: O(1) per check
Set<String> blockedAccounts = new HashSet<>(/* 50K entries */);
if (blockedAccounts.contains(accountId)) { } // hash lookup
What about thread safety?
HashSet is not thread-safe. For concurrent access:
Collections.synchronizedSet(new HashSet<>())– single lock wrapper.ConcurrentHashMap.newKeySet()– lock-free concurrent set backed by ConcurrentHashMap.CopyOnWriteArraySet– for read-heavy, write-rare scenarios.
import java.util.concurrent.ConcurrentHashMap;
// Thread-safe set with ConcurrentHashMap
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();
concurrentSet.add("SAV2001"); // thread-safe
concurrentSet.contains("SAV2001"); // thread-safe, lock-free
What should a senior engineer know?
- EnumSet optimization. When your set contains enum constants, always use EnumSet instead of HashSet. EnumSet uses a bit vector internally (one bit per enum constant) and is far faster and more memory-efficient than any hash-based set.
- Set.of() produces an immutable set. Set.of("A", "B", "C") returns an unmodifiable set that does not allow null, duplicates, or modification. The implementation is not a HashSet – it uses a specialized compact representation.
- Collectors.toUnmodifiableSet(). In streams, collect(Collectors.toUnmodifiableSet()) creates an immutable set. It rejects null and duplicates.
- HashSet serialization. HashSet has custom serialization that writes only the elements (not the HashMap internal structure). On deserialization, it reconstructs the HashMap from the elements.
What are common interview follow-up questions?
- "What is the internal data structure of HashSet?" – A HashMap where elements are keys and values are a dummy PRESENT constant.
- "Can HashSet contain null?" – Yes, one null element (because HashMap allows one null key).
- "What happens if you add a duplicate to HashSet?" – add() returns false and the set is unchanged.
- "Why must elements implement hashCode and equals?" – Because they are used as HashMap keys.
Visual Overview
HashSet = HashMap wrapper
HashSet<String>:
┌─────────────────────────────────────────┐
│ HashMap<String, Object> │
│ │
│ Bucket 2: ["SAV2001" → PRESENT] │
│ Bucket 5: ["CUR3001" → PRESENT] │
│ Bucket 9: ["FD4001" → PRESENT] │
│ │
│ PRESENT = new Object() (shared by all) │
└─────────────────────────────────────────┘
add("SAV2001") → map.put("SAV2001", PRESENT)
→ put returns null (new key)
→ add returns true
add("SAV2001") → map.put("SAV2001", PRESENT)
→ put returns PRESENT (existing)
→ add returns false (duplicate!)
Same pattern:
LinkedHashSet → LinkedHashMap (insertion order)
TreeSet → TreeMap (sorted order)
Key Takeaway
HashSet is one of the simplest classes in the JDK to understand once you know the secret: it is just a HashMap wrapper. Every element you add becomes a key in an internal HashMap, with a shared dummy PRESENT object as the value. add() delegates to put(), contains() delegates to containsKey(), and remove() delegates to remove(). All the HashMap properties – O(1) operations, default capacity 16, load factor 0.75, treeification at 8 collisions – apply to HashSet automatically.
In the National Bank of India's fraud detection system, Rajesh uses HashSet to maintain the set of blocked account numbers. When a transfer request arrives, blockedAccounts.contains(sourceAccount) answers in O(1) time. Using an ArrayList for this check would scan all 50,000 blocked accounts on every transfer – thousands of times slower.
The critical requirement is that elements must implement proper hashCode() and equals(). Without these, two logically identical objects are treated as different set members, allowing duplicates to sneak in.
Remember one sentence: HashSet is a HashMap where elements are keys and values are a shared dummy constant, so all HashMap behavior – hashing, buckets, collisions – applies to HashSet.
---