Design HashSet — Implementing Set Semantics Without Built-ins

Problem Statement#

Design a HashSet without using any built-in hash set libraries.

Implement the MyHashSet class:

• MyHashSet() initialises the object with an empty set.
• void add(int key) inserts the value key into the HashSet.
• bool contains(int key) returns whether key is in the HashSet.
• void remove(int key) removes the value key from the HashSet. If key does not exist, do nothing.

Constraints:

• 0 <= key <= 10^6
• At most 10^4 calls will be made to add, remove, and contains.

Examples:

MyHashSet hashSet = new MyHashSet();
hashSet.add(1);         // set = {1}
hashSet.add(2);         // set = {1, 2}
hashSet.contains(1);    // returns true
hashSet.contains(3);    // returns false
hashSet.add(2);         // set unchanged = {1, 2}
hashSet.remove(2);      // set = {1}
hashSet.contains(2);    // returns false

Why This Problem Matters#

Design HashSet is a companion problem to Design HashMap, and interviewers at Google and Amazon often ask both in sequence to see if candidates understand when to choose a simpler data structure. A HashSet has no values — just keys — which opens the door to a significantly more space-efficient implementation: the bit array.

For this problem's constraints (keys 0 to 10^6), a bit array of size 10^6 + 1 uses only about 125 KB of memory and supports O(1) add, remove, and contains with zero hash collisions. This is a lesson in problem-specific optimisation that interviewers love.

At Microsoft, this problem is used to assess candidates' awareness of trade-offs: "Which is better for this problem — a bit array or a hash table with chaining?" The correct answer depends on the density of the key space. For dense integer ranges (as here), the bit array wins. For sparse or non-integer keys, chaining wins.

Understanding the HashSet implementation also clarifies how languages implement set operations: Python's frozenset, Java's HashSet, and JavaScript's Set all have O(1) average-case operations through hashing, but with memory and load-factor trade-offs that you can now discuss intelligently.

The Core Insight#

Approach 1 — Bit Array (best for this problem):

Since keys are bounded integers (0 to 10^6), allocate a boolean array of size 10^6 + 1. Each index corresponds to a key. add(key) sets arr[key] = true. remove(key) sets arr[key] = false. contains(key) returns arr[key].

This is O(1) exact time with no collisions. The trade-off is fixed memory usage of ~10^6 booleans (about 1 MB in Python, 125 KB as a true bit array).

Approach 2 — Chaining (general-purpose):

For general keys, use the same chaining approach as Design HashMap but without the value component. Each bucket holds a list of keys.

The bit array approach is strictly better for this problem's constraints and should be your default answer. Explaining the chaining approach as the general-purpose alternative shows breadth.

Visual Dry Run#

Bit array approach (array of size 7 for illustration, real size = 10^6 + 1):

Initial state: [F, F, F, F, F, F, F] (all False)

Solution (Optimal)#

Approach 1 — Bit Array (optimal for bounded integer keys):

class MyHashSet:
    def __init__(self):
        # Boolean array for keys 0 to 10^6
        self.data = [False] * 1_000_001
 
    def add(self, key: int) -> None:
        self.data[key] = True
 
    def remove(self, key: int) -> None:
        self.data[key] = False
 
    def contains(self, key: int) -> bool:
        return self.data[key]

class MyHashSet {
    constructor() {
        // Boolean array — Uint8Array for memory efficiency
        this.data = new Uint8Array(1_000_001);
    }
 
    add(key) {
        this.data[key] = 1;
    }
 
    remove(key) {
        this.data[key] = 0;
    }
 
    contains(key) {
        return this.data[key] === 1;
    }
}

Approach 2 — Chaining (general-purpose, works for any key type):

class MyHashSet:
    def __init__(self):
        self.size = 1009  # Prime to reduce clustering
        self.buckets = [[] for _ in range(self.size)]
 
    def _hash(self, key: int) -> int:
        return key % self.size
 
    def add(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        if key not in bucket:
            bucket.append(key)
 
    def remove(self, key: int) -> None:
        h = self._hash(key)
        self.buckets[h] = [k for k in self.buckets[h] if k != key]
 
    def contains(self, key: int) -> bool:
        return key in self.buckets[self._hash(key)]

class MyHashSet {
    constructor() {
        this.size = 1009;
        this.buckets = Array.from({ length: this.size }, () => []);
    }
 
    _hash(key) {
        return key % this.size;
    }
 
    add(key) {
        const bucket = this.buckets[this._hash(key)];
        if (!bucket.includes(key)) bucket.push(key);
    }
 
    remove(key) {
        const h = this._hash(key);
        this.buckets[h] = this.buckets[h].filter(k => k !== key);
    }
 
    contains(key) {
        return this.buckets[this._hash(key)].includes(key);
    }
}

Complexity Analysis:

Bit array approach:

• Time: O(1) exact — direct array index access.
• Space: O(max_key) — proportional to key range, not number of elements.

Chaining approach:

• Time: O(n/b) average per operation.
• Space: O(n + b).

Common Mistakes#

• Not checking for duplicates before add: If you append without checking, contains with a linear scan would still work, but the bucket grows larger than necessary. Always check first.
• Using key in list for the check: For Python lists, in is O(n). For small buckets this is fine, but for large sets use a set of keys per bucket (which is what real hash sets do).
• Memory over-allocation with bit array: Allocating [False] * 10^6 in Python is about 8 MB because Python booleans are full Python objects. Using bytearray(10^6 + 1) or array.array('b', ...) is more space-efficient.
• Off-by-one in bit array size: Keys go up to 10^6, so the array needs size 10^6 + 1 (indices 0 through 10^6 inclusive).
• Thread safety: In concurrent environments, multiple threads calling add and remove simultaneously can corrupt the set. Use locking in production.

Follow-up Questions#

1. When would chaining be better than a bit array? (When keys are strings, objects, or large sparse integers where the bit array would use too much memory.)
2. How would you implement a HashSet for string keys? (Use a hash function like polynomial rolling hash to map strings to integers, then apply chaining.)
3. What is the load factor and why does it matter? (Load factor = n/b. When it exceeds ~0.75, performance degrades and rehashing is needed.)
4. How would you implement set union, intersection, and difference efficiently? (Union: iterate one set, add each element to the other. Intersection/difference: iterate one, check membership in the other.)
5. How is Python's set implemented internally? (Open addressing with compact arrays; resizes when load factor exceeds 2/3.)
6. What is a Bloom filter and how does it relate to HashSet? (A space-efficient probabilistic set that never has false negatives but may have false positives — used in databases and distributed systems.)

Key Takeaways#

• LC 705 Design HashSet is the value-less twin of LC 706 — store keys only, no put value or get return.
• For dense small-integer keys, a bit array gives O(1) ops with 1 bit per key — most space-efficient option.
• For general keys, use buckets-plus-chaining (or a list of lists) with prime bucket count and modular hashing.
• add is idempotent (skip if exists), remove is a no-op when missing, contains returns boolean — match Java/Python Set semantics.
• Always pick a prime modulus (769 is the canonical choice) to reduce clustering for adversarial keys.
• A Bloom filter is the probabilistic relative — never returns false negatives but accepts a tunable false-positive rate for huge memory savings.
• Open addressing (Python set) and chaining (Java HashSet) are equivalent in average performance; choice depends on cache locality goals.

Related Problems#

• [LC 705] Design HashSet — this exact problem.
• [LC 706] Design HashMap — companion problem, adds values to each key.
• [LC 217] Contains Duplicate — uses a set to detect duplicates in O(n).
• [LC 349] Intersection of Two Arrays — uses sets for O(n+m) intersection.
• [LC 202] Happy Number — uses a set to detect cycles.
• [LC 128] Longest Consecutive Sequence — uses a set for O(1) membership queries.