Design HashSet

How it works

We can compress the boolean array approach by using individual bits instead of booleans. Each integer stores 32 bits, so we need only about 31251 integers to cover 1000000+ keys. We use bit operations to set, clear, and check individual bits. This reduces memory usage by a factor of 32 compared to a boolean array.

Steps

1. Initialize an integer array of size 31251 (since 31251 * 32 = 1000032 covers all keys).
2. Define getMask(key) as 1 << (key % 32) to create a bitmask for the key's position within its integer.
3. For add(key): Set the bit using set[key / 32] |= getMask(key).
4. For remove(key): If the key exists, toggle the bit using set[key / 32] ^= getMask(key).
5. For contains(key): Return true if set[key / 32] & getMask(key) is non-zero.

Complexity

• Time complexity: O(1) for each function call.
• Space complexity: O(k)

Where k is the size of the set (31251).

Things to watch for

Adding Duplicate Keys

The add() operation should be idempotent - adding an existing key should have no effect. A common mistake is not checking for duplicates before insertion.

Using XOR for Remove Without Checking Existence

In the bit manipulation approach, using XOR to remove a key that doesn't exist will incorrectly add it instead.

class MyHashSet:

    def __init__(self):
        # key is in the range [0, 1000000]
        # 31251 * 32 = 1000032
        self.set = [0] * 31251

    def add(self, key: int) -> None:
        self.set[key // 32] |= self.getMask(key)

    def remove(self, key: int) -> None:
        if self.contains(key):
            self.set[key // 32] ^= self.getMask(key)

    def contains(self, key: int) -> bool:
        return self.set[key // 32] & self.getMask(key) != 0

    def getMask(self, key: int) -> int:
        return 1 << (key % 32)

class MyHashSet {
private:
    int set[31251];

    int getMask(int key) {
        return 1 << (key % 32);
    }

public:
    MyHashSet() {
        // key is in the range [0, 1000000]
        // 31251 * 32 = 1000032
        memset(set, 0, sizeof(set));
    }

    void add(int key) {
        set[key / 32] |= getMask(key);
    }

    void remove(int key) {
        if (contains(key)) {
            set[key / 32] ^= getMask(key);
        }
    }

    bool contains(int key) {
        return (set[key / 32] & getMask(key)) != 0;
    }
};