How to Solve Design HashSet

To solve Design HashSet, implement a class with add, remove, and contains operations using array-based buckets and a hash function. The key is mapping input keys to bucket indices to manage collisions via linked lists or dynamic arrays. This approach ensures O(1) average insertion and lookup time while handling duplicates and removals efficiently.

Problem Statement

Design a HashSet without relying on any built-in hash table or set libraries. Implement the MyHashSet class with the following methods: add(key), remove(key), and contains(key) to store integer keys efficiently.

Your implementation should handle collisions, prevent duplicates, and support at most 10^4 method calls with keys in the range 0 to 10^6. Optimize operations using array scanning combined with hash lookup to meet time constraints.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output [null, null, null, true, false, null, true, null, false]

Explanation MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed)

Constraints

• 0 <= key <= 106
• At most 104 calls will be made to add, remove, and contains.

Solution Approach

Choose a bucket structure

Initialize an array of buckets and map each key to a bucket index using a hash function. Use a linked list or dynamic array in each bucket to store actual keys, allowing O(1) average insertion and deletion while scanning the bucket linearly for collisions.

Implement add, remove, and contains

For add, first check if the key exists in the bucket to prevent duplicates, then append if absent. For remove, scan the bucket and delete the key if present. For contains, scan the bucket and return true if the key is found, otherwise return false.

Handle collisions efficiently

When multiple keys map to the same bucket, traverse the linked list or array linearly to check for duplicates and removals. Properly managing collisions ensures consistent performance and prevents overwriting or missing keys.

Complexity Analysis

Time complexity depends on bucket count and hash distribution: average O(1) for add, remove, and contains if collisions are minimal; worst-case O(n) if all keys hash to one bucket. Space complexity is proportional to the number of buckets plus the total stored keys.

What Interviewers Usually Probe

• They may ask about handling collisions and why a linked list in each bucket works.
• Expect questions on trade-offs between array scanning and hash table performance.
• You might be prompted to explain worst-case scenarios when all keys hash to one bucket.

Common Pitfalls or Variants

Common pitfalls

• Not handling duplicate keys correctly in add operations, causing redundant entries.
• Ignoring collision handling, which can lead to incorrect contains or remove results.
• Choosing too few buckets, increasing linear scanning time and degrading performance.

Follow-up variants

• Implement a HashSet with open addressing instead of linked list buckets.
• Support dynamic resizing of buckets when load factor exceeds a threshold.
• Implement a HashMap variant that stores key-value pairs with similar hashing strategy.

How GhostInterview Helps

• GhostInterview provides guided step-by-step bucket and hash function implementation for Design HashSet.
• It detects common mistakes like missing collision checks or duplicate handling during add and remove operations.
• Offers inline verification of contains results and runtime efficiency feedback while practicing with array scanning plus hash lookup.

Topic Pages

• Array
• Hash Table
• Linked List
• Design
• Hash Function

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best bucket size for Design HashSet to minimize collisions?

A bucket size proportional to the expected number of unique keys (around 10^4) ensures minimal collisions and near O(1) performance.

Can I use built-in set or hash table libraries in this problem?

No, the problem explicitly requires implementing a custom HashSet without any built-in hash table or set structures.

How does the array scanning plus hash lookup pattern work here?

Each key is hashed to a bucket index; scanning within the bucket checks for existence, enabling efficient add, remove, and contains operations.

What happens if multiple keys map to the same bucket?

Collisions are resolved by scanning the bucket’s linked list or array, ensuring each key is stored uniquely without overwriting others.

Is dynamic resizing necessary for this HashSet implementation?

It’s optional for this problem due to key constraints, but resizing can improve performance for larger key ranges or frequent insertions.