💬 Discord
Sign In
NeetCode #58LC-705EasyArrays & HashingNC 250
← Back to All Problems

#58 · #705 · Design HashSet(设计哈希集合)

📌 Problem Statement & Constraints

Design a HashSet without using any built-in hash table libraries. Implement add(key), remove(key) and contains(key). Constraints: 0 <= key <= 10^6; at most 10^4 calls will be made.

💡 Core Algorithmic Approaches

  1. The simplest design is separate chaining: an array of B buckets, each holding a list of keys. The bucket index is key % B.
  2. add: compute the bucket and append only if the key is absent.
  3. remove: compute the bucket and delete the key if present (guard with a membership test to avoid a ValueError).
  4. contains: compute the bucket and test membership. Choosing B to be a prime near the expected number of keys keeps the average bucket length near 1.
  5. A bitset of size 1e6 + 1 is also viable given the bounded key range, and is simpler -- worth mentioning as a trade-off.

💻 Benchmark Python3 Implementation

class MyHashSet:
    def __init__(self):
        self.B = 997                        # a prime bucket count reduces clustering
        self.buckets = [[] for _ in range(self.B)]

    def _idx(self, key: int) -> int:
        return key % self.B

    def add(self, key: int) -> None:
        b = self.buckets[self._idx(key)]
        if key not in b:                    # avoid duplicates
            b.append(key)

    def remove(self, key: int) -> None:
        b = self.buckets[self._idx(key)]
        if key in b:                        # guard, otherwise list.remove raises
            b.remove(key)

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


# Alternative given the bounded key range: a plain bitset
class MyHashSet2:
    def __init__(self):
        self.bits = bytearray(10 ** 6 + 1)

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

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

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) average per operation: the bucket lookup is O(1) and the average bucket length stays O(1) with a good modulus and load factor. The bitset variant is O(1) worst case.
💾 Space Complexity
O(n + B) for chaining (n stored keys plus the bucket array). The bitset variant is O(max_key) = O(10^6) regardless of how many keys are stored.

⚠️ Interview Pitfalls & Follow-ups

  • Calling list.remove(key) without a membership test: raises ValueError when the key is absent, which the API contract does not allow.
  • Forgetting to deduplicate in add: the same key would be stored repeatedly, wasting memory and slowing remove.
  • Using a very small bucket count: average chain length grows linearly, degrading every operation toward O(n).
  • Using a fixed-size array of size max_key + 1 without noting the trade-off: it is O(1) worst case but allocates a million slots even for a handful of keys. Mention both designs and pick based on the key range.