705. Design HashSet

Problem¶

Implement a set of integers from \(0\) through \(10^6\) without using a built-in hash table. Support adding, removing, and checking a key.

add(1), add(1) -> {1}
contains(1) -> True
remove(1) -> {}
contains(1) -> False

class MyHashSet:
    def __init__(self):
        pass

    def add(self, key: int) -> None:
        pass

    def remove(self, key: int) -> None:
        pass

    def contains(self, key: int) -> bool:
        pass

Key trick¶

Use hash(key) to choose a bucket. Store colliding keys in that bucket's list, and resize the bucket array as the set grows.

Trap¶

Check whether the key is already in its bucket before resizing or adding it. When resizing, move every stored key into a bucket chosen using the new bucket count.

Why is it interesting?¶

The same design works for any hashable key, not just integers. For this problem's limited integer range, a bytearray bitset is another option: it avoids hashing by reserving one bit for each possible key.

Python solution¶

# Separate chaining
class MyHashSet:
    def __init__(self):
        self.buckets = [[] for _ in range(8)]
        self.size = 0

    def _bucket(self, key) -> list[list[int]]:
        return self.buckets[hash(key) % len(self.buckets)]

    def _resize(self) -> None:
        old_buckets = self.buckets
        self.buckets = [[] for _ in range(2 * len(old_buckets))]

        for bucket in old_buckets:
            for key in bucket:
                self._bucket(key).append(key)

    def add(self, key: int) -> None:
        if key in self._bucket(key):
            return

        if (self.size + 1) / len(self.buckets) > 0.75:
            self._resize()

        self._bucket(key).append(key)
        self.size += 1

    def remove(self, key: int) -> None:
        bucket = self._bucket(key)
        for i, k in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return

    def contains(self, key: int) -> bool:
        return key in self._bucket(key)

# Bounded integers
class MyHashSet:
    def __init__(self):
        # One bit for each key from 0 through 1_000_000.
        self.bits = bytearray(1_000_000 // 8 + 1)

    def add(self, key: int) -> None:
        i, bit = divmod(key, 8)
        self.bits[i] |= 1 << bit

    def remove(self, key: int) -> None:
        i, bit = divmod(key, 8)
        self.bits[i] &= ~(1 << bit)

    def contains(self, key: int) -> bool:
        i, bit = divmod(key, 8)
        return bool(self.bits[i] & (1 << bit))


# Open addresing
class MyHashSet:
    def __init__(self):
        self.empty = object()
        self.deleted = object()
        self.slots = [self.empty] * 8
        self.size = 0
        self.used = 0  # Slots containing a key or marked deleted.

    def _find(self, key: int) -> tuple[int, bool]:
        idx = hash(key) % len(self.slots)
        first_deleted = -1

        while True:
            val = self.slots[idx]

            if val is self.empty:
                if first_deleted != -1:
                    return first_deleted, False
                return idx, False

            if val is self.deleted:
                if first_deleted == -1:
                    first_deleted = idx
            elif val == key:
                return idx, True

            idx = (idx + 1) % len(self.slots)

    def _resize(self) -> None:
        old_slots = self.slots
        self.slots = [self.empty] * (2 * len(old_slots))
        self.used = 0

        for val in old_slots:
            if val is not self.empty and val is not self.deleted:
                idx, _ = self._find(val)
                self.slots[idx] = val
                self.used += 1

    def add(self, key: int) -> None:
        idx, found = self._find(key)
        if found:
            return

        if (self.used + 1) * 4 > len(self.slots) * 3:
            self._resize()
            idx, _ = self._find(key)

        if self.slots[idx] is self.empty:
            self.used += 1

        self.slots[idx] = key
        self.size += 1

    def remove(self, key: int) -> None:
        idx, found = self._find(key)
        if found:
            self.slots[idx] = self.deleted
            self.size -= 1

    def contains(self, key: int) -> bool:
        _, found = self._find(key)
        return found

Comment on my solution¶

Your solution is a correct separate-chaining hash set, not an open-addressing one. It is easier to reason about, especially for removal. Its main avoidable cost is resizing before checking whether an add is a duplicate.

# WORKS
class MyHashSet:

    def __init__(self):
        self.buckets = [[] for _ in range(8)]
        self.size = 0

    def _index(self, key: int) -> int:
        return hash(key) % len(self.buckets)

    def _resize(self):
        old_buckets = self.buckets
        self.buckets = [[] for _ in range(len(old_buckets) * 2)]
        self.size = 0
        for bucket in old_buckets:
            for key in bucket:
                self.add(key)

    def add(self, key: int) -> None:
        if (self.size + 1) / len(self.buckets) > 0.75:
            self._resize()
        bucket = self.buckets[self._index(key)]
        for k in bucket:
            if k == key:
                return
        bucket.append(key)
        self.size += 1

    def remove(self, key: int) -> None:
        bucket = self.buckets[self._index(key)]
        for i, k in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return


    def contains(self, key: int) -> bool:
        bucket = self.buckets[self._index(key)]
        for k in bucket:
            if k == key:
                return True
        return False

Extra¶

Load factor definition¶

So the quantity (self.size + 1) / len(self.buckets) is called "load factor"?

Why the + 1?

Load factor is the number of stored keys divided by the number of buckets: self.size / len(self.buckets). The expression with + 1 is the projected load factor after adding a new key.
The + 1 lets you resize before inserting that key if the insertion would push the load factor above 0.75. This check belongs after confirming the key is not already present.

Separate chaining and Open addressing¶

Can you give short definition for "Hash set using separate chaining" and "Hash set using open addressing?

The open addressing implementation seems more involved and harder to follow that the separate chaining one. Why/When do we prefer one implementation over the other, given they have the same complexity.

Definitions¶

Separate chaining: Hash each key to a bucket. If keys land in the same bucket, keep them together in a list.
Open addressing: Hash each key to a slot in one array. If that slot is occupied, check other slots until the key or an available slot is found.

Why choose one over the other?¶

They have the same expected \(O(1)\) operation time, but different practical costs:

Choose separate chaining when you want simpler code, especially for removal. It also handles a crowded table more gracefully, but the bucket lists use extra memory.
Choose open addressing when memory use and access speed matter. Keys live in one array, without a list per bucket. The trade-off is more complicated removal and slower searches as the array fills up.

For an interview implementation, I would usually start with separate chaining unless asked specifically for open addressing.