705. Design HashSet - Solution & Explanation

Q: Is Design HashSet easy or hard?

Design HashSet is classified as an Easy problem because the required operations are straightforward. The challenge mainly checks whether you understand hashing basics and how to implement set behavior without relying on built‑in libraries.

Q: Design HashSet Python/Java solution

Python and Java solutions typically implement a bucket array with a simple modulo hash function. Each bucket stores keys in a list or linked structure. Methods add, remove, and contains compute the hash index and then operate only within that bucket, giving O(1) average complexity.

Q: How to solve Design HashSet in O(n)?

Operations themselves should run in O(1) average time rather than O(N). Using a hash table with buckets ensures constant-time lookups and updates. The overall structure stores up to N elements, giving O(N) space while each individual operation remains constant on average.

Q: What is the best approach for Design HashSet?

The hashing approach with bucket arrays and chaining is the most practical solution. Keys are mapped to buckets using a hash function such as key % bucketSize, and collisions are handled using a list inside each bucket. Average time for add, remove, and contains becomes O(1) with O(N) total space.

Q: Is Design HashSet asked at Google/Amazon/Meta?

Hash table design questions like Design HashSet frequently appear in interviews at companies such as Amazon, Meta, and Google because they test understanding of hashing, collision handling, and data structure design. Candidates are often asked to explain tradeoffs between direct addressing and bucket-based hashing.

Q: What data structure is used in Design HashSet?

The core data structure is a hash table. It typically consists of an array of buckets combined with a hash function to map keys to indices. Buckets may store elements using linked lists or dynamic arrays to resolve collisions.

Q: What is the time complexity of Design HashSet?

Most implementations achieve average O(1) time for add, remove, and contains operations using hashing. When chaining is used for collision resolution, worst‑case time becomes O(N) if many keys fall into the same bucket. Space complexity is O(N) for storing the keys.

The problem

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

Implement MyHashSet class:

void add(key) Inserts the value key into the HashSet.
bool contains(key) Returns whether the value key exists in the HashSet or not.
void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

Constraints:

0 <= key <= 10⁶
At most 10⁴ calls will be made to add, remove, and contains.

Approach overview

Problem Overview: Build a HashSet from scratch without using built‑in hash table libraries. The structure must support three operations: add(key), remove(key), and contains(key). Each operation should run efficiently while handling potential key collisions.

Approach 1: Direct Address Table (Time: O(1), Space: O(N))

The simplest design maps every possible key directly to an index in an array. Since the problem constraints limit keys to a known range (typically 0 ≤ key ≤ 10^6), you allocate a boolean array where the index represents the key itself. add(key) sets the slot to true, remove(key) sets it to false, and contains(key) checks the value at that index. Every operation becomes a constant-time array lookup or update. This approach avoids collisions entirely because each key has a unique slot. The tradeoff is memory usage: space complexity is O(N) for the full key range even if only a few keys are stored. It works well when the key range is small and predictable and relies purely on an array rather than a true hash structure.

Approach 2: Chaining Using Arrays for Collision Resolution (Average Time: O(1), Worst: O(N), Space: O(N))

A more realistic hash set uses a hash function and buckets. Create an array of buckets, then compute the bucket index with a simple hash = key % bucketSize. Each bucket stores multiple keys using a small list or linked list. When you call add, compute the hash index and append the key if it does not already exist in that bucket. remove searches the bucket and deletes the key, while contains scans the bucket to check membership. Average time remains O(1) if the hash function distributes keys evenly. In the worst case, when many keys collide into the same bucket, operations degrade to O(N). This design demonstrates how real hash tables handle collisions and is closer to production implementations.

Recommended for interviews: Interviewers typically expect the hashing approach with buckets because it shows you understand collision handling and the role of a hash function. The direct address table is still useful to mention first since it proves you recognize the constant-time lookup property. Moving from the direct mapping idea to a bucketed hash structure demonstrates stronger system design and data structure fundamentals.

Approach 1: Approach 1: Direct Address Table

The direct address table approach is simple and efficient for this problem since the maximum key size is limited to 10⁶. We can use a boolean array of size 10⁶+1 where each index represents a key. The value stored at a given index indicates whether the key is present in the HashSet. This allows for O(1) time complexity for the 'add', 'remove', and 'contains' operations.

Python

class MyHashSet:
    def __init__(self):
        self.container = [False] * 1000001

    def add(self, key: int) -> None:
        self.container[key] = True

    def remove(self, key: int) -> None:
        self.container[key] = False

    def contains(self, key: int) -> bool:
        return self.container[key]

Java

public class MyHashSet {
    private boolean[] container;

    public MyHashSet() {
        container = new boolean[1000001];
    }

    public void add(int key) {
        container[key] = true;
    }

    public void remove(int key) {
        container[key] = false;
    }

    public boolean contains(int key) {
        return container[key];
    }
}

C++

#include <vector>

class MyHashSet {
private:
    std::vector<bool> container;
public:
    MyHashSet() : container(1000001, false) {}

    void add(int key) {
        container[key] = true;
    }

    void remove(int key) {
        container[key] = false;
    }

    bool contains(int key) {
        return container[key];
    }
};

JavaScript

class MyHashSet {
    constructor() {
        this.container = new Array(1000001).fill(false);
    }

    add(key) {
        this.container[key] = true;
    }

    remove(key) {
        this.container[key] = false;
    }

    contains(key) {
        return this.container[key];
    }
}

#include <stdio.h>
#include <stdbool.h>

#define MAX 1000001

typedef struct {
    bool container[MAX];
} MyHashSet;

MyHashSet* myHashSetCreate() {
    MyHashSet* set = (MyHashSet*)malloc(sizeof(MyHashSet));
    for(int i = 0; i < MAX; i++) {
        set->container[i] = false;
    }
    return set;
}

void myHashSetAdd(MyHashSet* obj, int key) {
    obj->container[key] = true;
}

void myHashSetRemove(MyHashSet* obj, int key) {
    obj->container[key] = false;
}

bool myHashSetContains(MyHashSet* obj, int key) {
    return obj->container[key];
}

void myHashSetFree(MyHashSet* obj) {
    free(obj);
}

public class MyHashSet {
    private bool[] container;

    public MyHashSet() {
        container = new bool[1000001];
    }

    public void Add(int key) {
        container[key] = true;
    }

    public void Remove(int key) {
        container[key] = false;
    }

    public bool Contains(int key) {
        return container[key];
    }
}

In Python, we make use of a list (an array-like structure) initialized with False values. The add, remove, and contains functions manipulate or query this list.

Complexity

Time Complexity: O(1) for all operations (add, remove, contains).
Space Complexity: O(MAX), which is O(10^6).

Try this approach in the editor

Approach 2: Approach 2: Chaining using Arrays for Collision Resolution

This approach simulates a hash set using a hash function to assign keys to buckets, dealing with potential collisions using chaining. We create an array of lists, where each list contains keys that hash to the same index. This way, operations require traversing these short lists upon collisions.

Python

class Bucket:
    def __init__(self):
        self.container = []

    def add(self, key):
        if key not in self.container:
            self.container.append(key)

    def remove(self, key):
        if key in self.container:
            self.container.remove(key)

    def contains(self, key):
        return key in self.container

class MyHashSet:
    def __init__(self):
        self.base = 769
        self.buckets = [Bucket() for _ in range(self.base)]

    def add(self, key: int) -> None:
        index = key % self.base
        self.buckets[index].add(key)

    def remove(self, key: int) -> None:
        index = key % self.base
        self.buckets[index].remove(key)

    def contains(self, key: int) -> bool:
        index = key % self.base
        return self.buckets[index].contains(key)

Java

import java.util.LinkedList;

class MyHashSet {
    private Bucket[] buckets;
    private int hash(int key) {
        return key % 769;
    }

    public MyHashSet() {
        buckets = new Bucket[769];
        for (int i = 0; i < 769; i++) {
            buckets[i] = new Bucket();
        }
    }

    public void add(int key) {
        int index = hash(key);
        buckets[index].insert(key);
    }

    public void remove(int key) {
        int index = hash(key);
        buckets[index].delete(key);
    }

    public boolean contains(int key) {
        int index = hash(key);
        return buckets[index].exists(key);
    }

    class Bucket {
        private LinkedList<Integer> container;

        public Bucket() {
            container = new LinkedList<>();
        }

        public void insert(Integer key) {
            int index = container.indexOf(key);
            if (index == -1) {
                container.addFirst(key);
            }
        }

        public void delete(Integer key) {
            container.remove(key);
        }

        public boolean exists(Integer key) {
            int index = container.indexOf(key);
            return index != -1;
        }
    }
}

C++

#include <vector>
#include <list>
using namespace std;

class MyHashSet {
private:
    vector<list<int>> data;
    static const int base = 769;

    static int hash(int key) {
        return key % base;
    }

public:
    MyHashSet() : data(base) {}

    void add(int key) {
        int h = hash(key);
        for (int k : data[h]) {
            if (k == key) return;
        }
        data[h].push_back(key);
    }

    void remove(int key) {
        int h = hash(key);
        data[h].remove(key);
    }

    bool contains(int key) {
        int h = hash(key);
        for (int k : data[h]) {
            if (k == key) return true;
        }
        return false;
    }
};

JavaScript

class MyHashSet {
    constructor() {
        this.base = 769;
        this.buckets = Array.from({ length: this.base }, () => []);
    }

    _hash(key) {
        return key % this.base;
    }

    add(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        if (!bucket.includes(key)) {
            bucket.push(key);
        }
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        const keyIndex = bucket.indexOf(key);
        if (keyIndex !== -1) {
            bucket.splice(keyIndex, 1);
        }
    }

    contains(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        return bucket.includes(key);
    }
}

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define BASE 769

typedef struct Node {
    int key;
    struct Node* next;
} Node;

typedef struct {
    Node* data[BASE];
} MyHashSet;

Node* createNode(int key, Node* next) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = next;
    return newNode;
}

MyHashSet* myHashSetCreate() {
    MyHashSet* obj = (MyHashSet*)malloc(sizeof(MyHashSet));
    for(int i = 0; i < BASE; i++) {
        obj->data[i] = NULL;
    }
    return obj;
}

int hash(int key) {
    return key % BASE;
}

void myHashSetAdd(MyHashSet* obj, int key) {
    int h = hash(key);
    Node* head = obj->data[h];
    Node* current = head;
    while (current) {
        if (current->key == key) return;  // Key already exists
        current = current->next;
    }
    obj->data[h] = createNode(key, head);
}

void myHashSetRemove(MyHashSet* obj, int key) {
    int h = hash(key);
    Node* head = obj->data[h];
    Node* current = head;
    Node* prev = NULL;
    while (current) {
        if (current->key == key) {
            if (prev) {
                prev->next = current->next;
            } else {
                obj->data[h] = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

bool myHashSetContains(MyHashSet* obj, int key) {
    int h = hash(key);
    Node* current = obj->data[h];
    while (current) {
        if (current->key == key) return true;
        current = current->next;
    }
    return false;
}

void myHashSetFree(MyHashSet* obj) {
    for (int i = 0; i < BASE; i++) {
        Node* current = obj->data[i];
        while (current) {
            Node* next = current->next;
            free(current);
            current = next;
        }
    }
    free(obj);
}

using System.Collections.Generic;

public class MyHashSet {
    private LinkedList<int>[] buckets;
    private int GetHash(int key) {
        return key % 769;
    }

    public MyHashSet() {
        buckets = new LinkedList<int>[769];
        for (int i = 0; i < buckets.Length; i++) {
            buckets[i] = new LinkedList<int>();
        }
    }

    public void Add(int key) {
        int index = GetHash(key);
        if (!buckets[index].Contains(key)) {
            buckets[index].AddLast(key);
        }
    }

    public void Remove(int key) {
        int index = GetHash(key);
        if (buckets[index].Contains(key)) {
            buckets[index].Remove(key);
        }
    }

    public bool Contains(int key) {
        int index = GetHash(key);
        return buckets[index].Contains(key);
    }
}

In Python, we use a class 'Bucket' holding keys as lists and another class 'MyHashSet' to manage these buckets. Each bucket corresponds to keys by modulus operation, and operations use list membership test and updates to handle keys in buckets.

Complexity

Time Complexity: O(1) on average, O(n) worst-case in presence of long collision chains.
Space Complexity: O(n), that scales normally with inserted elements.

Try this approach in the editor

Approach 3: Static Array Implementation

Directly create an array of size 1000001, initially with each element set to false, indicating that the element does not exist in the hash set.

When adding an element to the hash set, set the corresponding position in the array to true; when deleting an element, set the corresponding position in the array to false; when checking if an element exists, directly return the value at the corresponding position in the array.

The time complexity of the above operations is O(1).

TypeScript

class MyHashSet {
    data: Array<boolean>;
    constructor() {
        this.data = new Array(10 ** 6 + 1).fill(false);
    }

    add(key: number): void {
        this.data[key] = true;
    }

    remove(key: number): void {
        this.data[key] = false;
    }

    contains(key: number): boolean {
        return this.data[key];
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * var obj = new MyHashSet()
 * obj.add(key)
 * obj.remove(key)
 * var param_3 = obj.contains(key)
 */

type MyHashSet struct {
	data []bool
}

func Constructor() MyHashSet {
	data := make([]bool, 1000010)
	return MyHashSet{data}
}

func (this *MyHashSet) Add(key int) {
	this.data[key] = true
}

func (this *MyHashSet) Remove(key int) {
	this.data[key] = false
}

func (this *MyHashSet) Contains(key int) bool {
	return this.data[key]
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(key);
 * obj.Remove(key);
 * param_3 := obj.Contains(key);
 */

Try this approach in the editor

Approach 4: Array of Linked Lists

We can also create an array of size SIZE=1000, where each position in the array is a linked list.

type MyHashSet struct {
	data []list.List
}

func Constructor() MyHashSet {
	return MyHashSet{make([]list.List, 1000)}
}

func (this *MyHashSet) Add(key int) {
	if this.Contains(key) {
		return
	}
	idx := this.hash(key)
	this.data[idx].PushBack(key)
}

func (this *MyHashSet) Remove(key int) {
	idx := this.hash(key)
	for e := this.data[idx].Front(); e != nil; e = e.Next() {
		if e.Value.(int) == key {
			this.data[idx].Remove(e)
		}
	}
}

func (this *MyHashSet) Contains(key int) bool {
	idx := this.hash(key)
	for e := this.data[idx].Front(); e != nil; e = e.Next() {
		if e.Value.(int) == key {
			return true
		}
	}
	return false
}

func (this *MyHashSet) hash(key int) int {
	return key % len(this.data)
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(key);
 * obj.Remove(key);
 * param_3 := obj.Contains(key);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Direct Address Table	Time Complexity: O(1) for all operations (add, remove, contains). Space Complexity: O(MAX), which is O(10^6).
Approach 2: Chaining using Arrays for Collision Resolution	Time Complexity: O(1) on average, O(n) worst-case in presence of long collision chains. Space Complexity: O(n), that scales normally with inserted elements.
Static Array Implementation	–
Array of Linked Lists	–

Complexity analysis

Approach	Time	Space	When to Use
Direct Address Table	O(1)	O(N)	When the key range is small and known in advance; simplest constant-time implementation
Hashing with Chaining (Bucket Array)	Average O(1), Worst O(N)	O(N)	General hash set design when keys may collide and memory must scale with stored elements

Frequently asked questions

Is Design HashSet easy or hard?

Design HashSet is classified as an Easy problem because the required operations are straightforward. The challenge mainly checks whether you understand hashing basics and how to implement set behavior without relying on built‑in libraries.

Design HashSet Python/Java solution

Python and Java solutions typically implement a bucket array with a simple modulo hash function. Each bucket stores keys in a list or linked structure. Methods add, remove, and contains compute the hash index and then operate only within that bucket, giving O(1) average complexity.

How to solve Design HashSet in O(n)?

Operations themselves should run in O(1) average time rather than O(N). Using a hash table with buckets ensures constant-time lookups and updates. The overall structure stores up to N elements, giving O(N) space while each individual operation remains constant on average.

What is the best approach for Design HashSet?

The hashing approach with bucket arrays and chaining is the most practical solution. Keys are mapped to buckets using a hash function such as key % bucketSize, and collisions are handled using a list inside each bucket. Average time for add, remove, and contains becomes O(1) with O(N) total space.

Is Design HashSet asked at Google/Amazon/Meta?

Hash table design questions like Design HashSet frequently appear in interviews at companies such as Amazon, Meta, and Google because they test understanding of hashing, collision handling, and data structure design. Candidates are often asked to explain tradeoffs between direct addressing and bucket-based hashing.

What data structure is used in Design HashSet?

The core data structure is a hash table. It typically consists of an array of buckets combined with a hash function to map keys to indices. Buckets may store elements using linked lists or dynamic arrays to resolve collisions.

What is the time complexity of Design HashSet?

Most implementations achieve average O(1) time for add, remove, and contains operations using hashing. When chaining is used for collision resolution, worst‑case time becomes O(N) if many keys fall into the same bucket. Space complexity is O(N) for storing the keys.

Design HashSet solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Direct Address Table

Approach 2: Approach 2: Chaining using Arrays for Collision Resolution

Approach 3: Static Array Implementation

Approach 4: Array of Linked Lists

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design HashSet solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Direct Address Table

Approach 2: Approach 2: Chaining using Arrays for Collision Resolution

Approach 3: Static Array Implementation

Approach 4: Array of Linked Lists

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems