Design HashSet

Problem Description

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

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.
• boolean 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.

Examples

Constraints

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

Buckets and Chaining

To design a scalable HashSet, avoid allocating a boolean array for the entire range of potential keys, which consumes excessive memory. Instead, use an array of buckets. Each bucket contains a list (chain) of elements that hash to the same bucket index. When a key is inserted, compute its hash code modulo the number of buckets, and add the key to the corresponding list if it is not already present.

Solution 1: Hash Chaining with Linked Lists

Maintain an array of linked list buckets to resolve key collisions.

import java.util.LinkedList;

class MyHashSet {
    private static final int BUCKET_SIZE = 1009; // Prime number to reduce collisions
    private LinkedList<Integer>[] buckets;

    @SuppressWarnings("unchecked")
    public MyHashSet() {
        buckets = new LinkedList[BUCKET_SIZE];
        for (int i = 0; i < BUCKET_SIZE; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(int key) {
        return key % BUCKET_SIZE;
    }

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

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

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

class MyHashSet:
    def __init__(self):
        self.bucket_size = 1009  # Prime number
        self.buckets = [[] for _ in range(self.bucket_size)]

    def _hash(self, key: int) -> int:
        return key % self.bucket_size

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

    def remove(self, key: int) -> None:
        index = self._hash(key)
        if key in self.buckets[index]:
            self.buckets[index].remove(key)

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

#include <vector>
#include <list>
#include <algorithm>

class MyHashSet {
private:
    int bucket_size;
    std::vector<std::list<int>> buckets;

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

public:
    MyHashSet() {
        bucket_size = 1009; // Prime number
        buckets.resize(bucket_size);
    }

    void add(int key) {
        int index = hash(key);
        auto& cell = buckets[index];
        auto it = std::find(cell.begin(), cell.end(), key);
        if (it == cell.end()) {
            cell.push_back(key);
        }
    }

    void remove(int key) {
        int index = hash(key);
        auto& cell = buckets[index];
        auto it = std::find(cell.begin(), cell.end(), key);
        if (it != cell.end()) {
            cell.erase(it);
        }
    }

    boolean contains(int key) {
        int index = hash(key);
        auto& cell = buckets[index];
        auto it = std::find(cell.begin(), cell.end(), key);
        return it != cell.end();
    }
};

Complexity Analysis

• Time Complexity: O(1) average case lookup, insert, and delete operations. Worst case degrades to O(k) where k is the size of the bucket chain if all keys collide.
• Space Complexity: O(n + b) where n is the number of keys inserted and b is the bucket size.

Where It Breaks

If the hash function produces many collisions (e.g. inserting keys that are all multiples of the bucket size), performance degrades to O(n) for operations. A prime bucket size helps avoid this.

Common Mistakes

• Incorrect deletion logic: In Java, passing the primitive int key to list.remove() removes the element at that index rather than removing the value. You must convert it to Integer.valueOf(key).
• Using non-prime bucket sizes: High collision rates on keys with regular intervals if bucket size is a power of two.

Frequently Asked Questions

Why use a prime number for the bucket count? A prime number reduces the likelihood of hash collisions when keys form arithmetic progressions (e.g., keys like 10, 20, 30 if bucket size is 10).

How do you handle resizing? In production implementations, if the load factor (elements / buckets) exceeds a threshold, you allocate a larger bucket array (usually double the size) and rehash all keys.

← All Problems