Design HashSet

The key idea

A set is a key -> present map where you only ever store the key. Pick a fixed number of buckets; the hash key % capacity sends a key to a bucket. Keys that collide live together in that bucket's small list (chaining), so add / remove / contains each walk just one short list.

Problem

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet:

- add(key) inserts the value key into the HashSet.
- contains(key) returns whether the value key exists in the HashSet or not.
- remove(key) removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

The HashSet stores distinct keys only, so adding a key that is already present makes no change.

Constraints

0 <= key <= 10^6
At most 10^4 calls will be made to add, remove, and contains.

Examples

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]

Input: ["MyHashSet","add","add","contains","contains","remove","contains"] [[],[5],[13],[13],[21],[5],[5]] Output: [null,null,null,true,false,null,false]

Complexity

Time: O(1) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →