Design HashSet - Solution & Explanation

Problem Overview: Build a HashSet from scratch without using built‑in hash table libraries. The structure must support three operations: add(key), remove(key), and contains(key). Each operation should run efficiently while handling potential key collisions.

Approach 1: Direct Address Table (Time: O(1), Space: O(N))

The simplest design maps every possible key directly to an index in an array. Since the problem constraints limit keys to a known range (typically 0 ≤ key ≤ 10^6), you allocate a boolean array where the index represents the key itself. add(key) sets the slot to true, remove(key) sets it to false, and contains(key) checks the value at that index. Every operation becomes a constant-time array lookup or update. This approach avoids collisions entirely because each key has a unique slot. The tradeoff is memory usage: space complexity is O(N) for the full key range even if only a few keys are stored. It works well when the key range is small and predictable and relies purely on an array rather than a true hash structure.

Approach 2: Chaining Using Arrays for Collision Resolution (Average Time: O(1), Worst: O(N), Space: O(N))

A more realistic hash set uses a hash function and buckets. Create an array of buckets, then compute the bucket index with a simple hash = key % bucketSize. Each bucket stores multiple keys using a small list or linked list. When you call add, compute the hash index and append the key if it does not already exist in that bucket. remove searches the bucket and deletes the key, while contains scans the bucket to check membership. Average time remains O(1) if the hash function distributes keys evenly. In the worst case, when many keys collide into the same bucket, operations degrade to O(N). This design demonstrates how real hash tables handle collisions and is closer to production implementations.

Recommended for interviews: Interviewers typically expect the hashing approach with buckets because it shows you understand collision handling and the role of a hash function. The direct address table is still useful to mention first since it proves you recognize the constant-time lookup property. Moving from the direct mapping idea to a bucketed hash structure demonstrates stronger system design and data structure fundamentals.