Design a HashSet from Scratch: DSA Guide

A hashset is a hashmap that stores keys only — no values.

Same skeleton as the hashmap lesson:

index = hash(key) % bucketCount, collisions chain inside the bucket.

One shortcut worth knowing:

If keys are small non-negative ints (say < 10^6), skip hashing entirely — a plain boolean array is O(1) everything.

Core Template

Buckets + chaining with a tiny hash you can verify by eye — collisions, probes and removal all in one run:

HashSet with Chaining

Insert/lookup/delete over fixed buckets using key % SIZE.

hash = key % SIZE picks a bucket; collisions are stored as a chain (linked list) in that bucket. add prepends if absent, get walks the chain comparing keys, remove unlinks. Average O(1) if the load factor stays low.

HASH BUCKETS VISUALIZER

Steps –

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

bucket 4

∅

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        bucket = key % SIZE
                      
                        2
                        add(key): if not in chain: prepend
                      
                        3
                        contains(key): walk the chain
                      
                        4
                        remove(key): unlink the node

class MyHashSet {
    private static final int SIZE = 1009;
    private List<Integer>[] buckets;

    public MyHashSet() {
        buckets = new List[SIZE];
    }

    public void add(int key) {
        int h = key % SIZE;
        if (buckets[h] == null) buckets[h] = new ArrayList<>();
        if (!buckets[h].contains(key)) buckets[h].add(key);
    }

    public void remove(int key) {
        List<Integer> chain = buckets[key % SIZE];
        if (chain != null) chain.remove(Integer.valueOf(key));
    }

    public boolean contains(int key) {
        List<Integer> chain = buckets[key % SIZE];
        return chain != null && chain.contains(key);
    }
}

class MyHashSet:
    def __init__(self):
        self.size = 1009
        self.buckets = [[] for _ in range(self.size)]

    def add(self, key: int) -> None:
        chain = self.buckets[key % self.size]
        if key not in chain:
            chain.append(key)

    def remove(self, key: int) -> None:
        chain = self.buckets[key % self.size]
        if key in chain:
            chain.remove(key)

    def contains(self, key: int) -> bool:
        return key in self.buckets[key % self.size]

class MyHashSet {
    static constexpr int SIZE = 1009;
    vector<unordered_set<int>> buckets{SIZE};

public:
    MyHashSet() {}

    void add(int key)      { buckets[key % SIZE].insert(key); }
    void remove(int key)   { buckets[key % SIZE].erase(key); }
    bool contains(int key) { return buckets[key % SIZE].count(key) > 0; }
};

class MyHashSet {
  #size = 1009;
  #buckets = Array.from({ length: this.#size }, () => new Set());

  add(key) {
    this.#buckets[key % this.#size].add(key);
  }

  remove(key) {
    this.#buckets[key % this.#size].delete(key);
  }

  contains(key) {
    return this.#buckets[key % this.#size].has(key);
  }
}

Pattern: The Boolean-Array Shortcut

When constraints bound the keyspace (0 ≤ key ≤ 10^6), the “hash” is the identity function:

class MyHashSet {
    private final boolean[] seen = new boolean[1_000_001];

    public void add(int key)    { seen[key] = true; }
    public void remove(int key) { seen[key] = false; }
    public boolean contains(int key) { return seen[key]; }
}

class MyHashSet:
    def __init__(self):
        self.seen = [False] * 1_000_001

    def add(self, key):       self.seen[key] = True
    def remove(self, key):    self.seen[key] = False
    def contains(self, key):  return self.seen[key]

class MyHashSet {
    vector<bool> seen{vector<bool>(1'000'001, false)};

public:
    void add(int key)      { seen[key] = true; }
    void remove(int key)   { seen[key] = false; }
    bool contains(int key) { return seen[key]; }
};

class MyHashSet {
  #seen = Array(1_000_001).fill(false);

  add(key)         { this.#seen[key] = true; }
  remove(key)      { this.#seen[key] = false; }
  contains(key)    { return this.#seen[key]; }
}

Bounded int keys → direct-address array. Anything else → buckets + chaining.

Common Mistakes

Duplicate adds.

add must check membership first (or use a set structure) — duplicates silently corrupt size-based logic.

Java autobox trap.

chain.remove(key) removes by INDEX for List<Integer> when key is an int. Use remove(Integer.valueOf(key)).

Using the shortcut with unbounded/negative keys.

The boolean array needs a known, modest range. Negative or huge keys need real hashing.

Complexity

Operation	Average	Worst
add	O(1)	O(n)
contains	O(1)	O(n)
remove	O(1)	O(n)
Boolean-array variant	O(1) guaranteed	—

⚠️ Animation & Content Notice

Design a HashSet

Core Template

⚠️ Animation & Content Notice

HashSet with Chaining

Pattern: The Boolean-Array Shortcut

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

HashSet with Chaining

Pattern: The Boolean-Array Shortcut

Common Mistakes

Complexity

Premium Content

My Private Notes