Design HashSet

87.5k
0

Design a HashSet for non-negative integer keys without using any built-in hash-table library.

Implement the MyHashSet class with the following operations:

  • MyHashSet() initializes an empty HashSet.

  • add(int key) inserts key into the set. Adding an existing key causes no change.

  • contains(int key) returns true when key exists and false otherwise.

  • remove(int key) removes key from the set. Removing a missing key causes no change.

The valid key range extends from 0 to 10⁶.

Example 1

Input: operations = ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]

Arguments: [[], [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)

Brute Force Approach

A known and bounded key range allows every key to act as a direct array index. No hash function or collision-handling logic becomes necessary. Presence at index key can be represented through a Boolean value.

Direct addressing provides constant-time operations, but memory usage depends on the complete key universe rather than the number of stored keys. A set containing only one key still reserves positions for every key from 0 to 10⁶. Sparse key usage therefore causes unnecessary memory allocation.

Algorithm

  • Create a Boolean array present of size 1,000,001, covering every valid key.

For the constructor:

  • Initialize every position with false, representing an empty set.

For add(key):

  • Set present[key] to true.

  • Preserve the same state when key already exists, because a set stores each key only once.

For contains(key):

  • Return the Boolean value stored at present[key].

For remove(key):

  • Set present[key] to false.

  • Preserve the empty state when key does not exist.

Dry Run

h

h

Solution

#include <bits/stdc++.h>
using namespace std;
class MyHashSet {
private:
static const int MAX_KEY = 1000000;
vector<bool> present;
public:
/* Initializes direct-address storage
for every valid key. */
MyHashSet()
: present(MAX_KEY + 1, false) {
}
/* Inserts key into the set. */
void add(int key) {
present[key] = true;
}
/* Removes key from the set. */
void remove(int key) {
present[key] = false;
}
/* Checks whether key exists in the set. */
bool contains(int key) {
return present[key];
}
};
// Driver code to execute the design.
int main() {
MyHashSet myHashSet;
myHashSet.add(1);
myHashSet.add(2);
cout << boolalpha;
cout << myHashSet.contains(1) << endl;
cout << myHashSet.contains(3) << endl;
myHashSet.add(2);
cout << myHashSet.contains(2) << endl;
myHashSet.remove(2);
cout << myHashSet.contains(2) << endl;
return 0;
}

Complexity Analysis

Time Complexity: The constructor requires O(K) time, where K = 1,000,001 represents the complete key-universe size. Every add, contains, and remove operation requires O(1) time through direct array indexing.

Space Complexity: O(K), because one Boolean position is reserved for every valid key regardless of the number of stored keys.

Better Approach

Direct addressing reserves one position for every possible key. Separate chaining reduces primary-array size by mapping many possible keys into a smaller collection of buckets.

The expression key % B maps a key into a bucket index from 0 to B - 1, where B represents the bucket count. Different keys can produce the same bucket index. Every bucket therefore stores a dynamic list containing all colliding keys.

Memory usage now depends mainly on the number of stored keys. However, a fixed bucket count allows individual buckets to grow as more keys are added. Operations become slower when many keys belong to the same bucket.

Algorithm

  • Choose a fixed bucket count B.

  • Create an array containing B empty dynamic lists.

  • Calculate every bucket index using key % B.

For the constructor:

  • Initialize all B buckets as empty lists.

For add(key):

  • Calculate the target bucket.

  • Traverse the selected bucket.

  • Stop without insertion when a matching key already exists.

  • Append key when the complete bucket contains no match.

For contains(key):

  • Calculate the target bucket.

  • Traverse only the selected bucket.

  • Return true after finding key.

  • Return false after reaching the end without a match.

For remove(key):

  • Calculate the target bucket.

  • Search for the matching key.

  • Delete the matching entry after discovery.

  • Perform no change when the selected bucket contains no matching key.

Dry Run

kl

kl

Solution

#include <bits/stdc++.h>
using namespace std;
class MyHashSet {
private:
static const int BUCKET_COUNT = 1009;
vector<vector<int>> buckets;
/* Converts a key into
a fixed bucket index. */
int bucketIndex(int key) const {
return key % BUCKET_COUNT;
}
public:
/* Initializes the fixed
collection of buckets. */
MyHashSet()
: buckets(BUCKET_COUNT) {
}
/* Inserts key when no
matching entry exists. */
void add(int key) {
int index = bucketIndex(key);
vector<int>& bucket =
buckets[index];
// Avoid storing duplicate keys.
for (int storedKey : bucket) {
if (storedKey == key) {
return;
}
}
// Append a new key after no match.
bucket.push_back(key);
}
/* Removes key from
the selected bucket. */
void remove(int key) {
int index = bucketIndex(key);
vector<int>& bucket =
buckets[index];
// Locate the key before erasing it.
for (
int position = 0;
position < (int)bucket.size();
position++
) {
if (bucket[position] == key) {
bucket.erase(
bucket.begin() +
position
);
return;
}
}
}
/* Checks whether key
exists in the set. */
bool contains(int key) {
int index = bucketIndex(key);
const vector<int>& bucket =
buckets[index];
// Search only the selected bucket.
for (int storedKey : bucket) {
if (storedKey == key) {
return true;
}
}
return false;
}
};
// Driver code to execute the design.
int main() {
MyHashSet myHashSet;
myHashSet.add(1);
myHashSet.add(2);
cout << boolalpha;
cout << myHashSet.contains(1) << endl;
cout << myHashSet.contains(3) << endl;
myHashSet.add(2);
cout << myHashSet.contains(2) << endl;
myHashSet.remove(2);
cout << myHashSet.contains(2) << endl;
return 0;
}

Complexity Analysis

Let:

  • N represent the number of stored keys.

  • B represent the fixed bucket count.

  • α = N / B represent the load factor.

Time Complexity: The constructor requires O(B) time. add, contains, and remove require expected O(1 + α) time under a well-distributed hash function. A bucket containing every key produces O(N) worst-case time. Dynamic-array removal can also shift the remaining entries of the selected bucket.

Space Complexity: O(B + N), because the primary array contains B buckets and all dynamic lists together store N keys.

Optimal Approach

Fixed separate chaining avoids direct-address memory usage, but a fixed bucket count cannot control chain growth. The relevant measurement is the load factor:

load factor = stored keys / bucket count

A growing load factor increases the expected number of nodes inside each collision chain. Dynamic resizing keeps the load factor below a selected threshold. When a new insertion would cross the threshold, the bucket count doubles and every existing key receives a new bucket index.

Custom linked lists avoid dynamic-array shifting during removal. A dummy head inside every bucket provides a predecessor even when the first real node requires deletion. Linked-list buckets handle collisions, while resizing and rehashing provide scalable expected performance.

Algorithm

  • Create a custom Node containing:

    • key

    • next

  • Initialize a bucket array with a small starting capacity.

  • Place one dummy head inside every bucket.

  • Maintain:

    • capacity, representing the current number of buckets.

    • entryCount, representing the number of stored keys.

    • MAX_LOAD_FACTOR, representing the resizing threshold.

  • Calculate every bucket index using key % capacity.

For the constructor:

  • Set capacity to an initial value.

  • Set entryCount to 0.

  • Create one dummy head for every bucket.

For add(key):

  • Traverse the selected collision chain.

  • Stop when a matching key already exists.

  • Calculate the load factor after the proposed insertion.

  • Double the capacity and rehash all existing keys when the threshold would be crossed.

  • Recalculate the bucket index after rehashing.

  • Insert the new node directly after the dummy head.

  • Increase entryCount.

For contains(key):

  • Traverse the selected chain after the dummy head.

  • Return true after finding the key.

  • Return false after reaching the end.

For remove(key):

  • Initialize previous with the dummy head.

  • Traverse the chain using current.

  • Bypass the matching node using previous.next = current.next.

  • Decrease entryCount after successful removal.

  • Perform no change when the key is absent.

For rehashing:

  • Double the bucket-array capacity.

  • Create new dummy heads.

  • Traverse every existing collision chain.

  • Recalculate each node’s bucket index using the new capacity.

  • Move every node into the corresponding new chain.

Dry Run

u

u

Solution

#include <bits/stdc++.h>
using namespace std;
class MyHashSet {
private:
struct Node {
int key;
Node* next;
Node(
int key,
Node* next = nullptr
)
: key(key),
next(next) {
}
};
static const int INITIAL_CAPACITY =
16;
constexpr static double
MAX_LOAD_FACTOR = 0.75;
int capacity;
int entryCount;
vector<Node*> buckets;
/* Converts a key into an index
for the current capacity. */
int bucketIndex(int key) const {
return key % capacity;
}
/* Creates one dummy head
for every bucket. */
void createEmptyBuckets(
int bucketCount
) {
buckets.assign(
bucketCount,
nullptr
);
for (
int index = 0;
index < bucketCount;
index++
) {
buckets[index] =
new Node(-1);
}
}
/* Doubles capacity and redistributes
all stored nodes. */
void rehash() {
vector<Node*> oldBuckets =
move(buckets);
int oldCapacity = capacity;
capacity *= 2;
createEmptyBuckets(capacity);
// Move every stored node
// into a new bucket.
for (
int index = 0;
index < oldCapacity;
index++
) {
Node* current =
oldBuckets[index]->next;
while (current != nullptr) {
Node* nextNode =
current->next;
int newIndex =
bucketIndex(
current->key
);
// Insert after
// the new dummy head.
current->next =
buckets[newIndex]->next;
buckets[newIndex]->next =
current;
current = nextNode;
}
// Release the old dummy head.
delete oldBuckets[index];
}
}
/* Releases every dummy head
and stored node. */
void releaseAllNodes() {
for (Node* head : buckets) {
Node* current = head;
while (current != nullptr) {
Node* nextNode =
current->next;
delete current;
current = nextNode;
}
}
}
public:
/* Initializes a resizable

Complexity Analysis

Let N represent the maximum number of keys stored during execution.

Time Complexity:

  • Constructor: O(B₀), where B₀ represents the initial bucket count.

  • contains: Expected O(1) and worst-case O(N).

  • remove: Expected O(1) and worst-case O(N).

  • add: Expected amortized O(1). A single insertion can require O(N) during rehashing.

  • Rehashing: O(N) for an individual resize operation.

Space Complexity: O(N), because stored nodes and the bucket array both grow in proportion to the number of keys. Old and new bucket arrays temporarily coexist during rehashing, but total temporary storage remains O(N).

FAQs about Design HashSet

1. Why is direct addressing classified as the Brute Force Approach despite constant-time operations?

Direct addressing obtains constant-time operations by reserving memory for the complete key universe. The memory cost remains O(K) even when only a few keys are stored.

2. What causes a collision?

A collision occurs when different keys produce the same bucket index.

For bucket count 5, keys 1, 6, and 11 all produce index 1.

3. Why must duplicate keys be checked before insertion?

A set stores every key at most once. Repeated insertion without a duplicate check would create unnecessary nodes and incorrect entry counts.

4. Why does a dummy head simplify removal?

A dummy head guarantees a predecessor for every real node. Deletion of the first real node therefore uses the same pointer-rewiring logic as deletion from the middle or end.

5. Does linked-list removal always require O(1) time?

No. Pointer bypass requires O(1) time after locating the node. Locating the key can require traversal of the complete collision chain.

6. Why is resizing required?

A fixed bucket count allows the load factor and expected chain length to grow. Resizing adds more buckets and redistributes stored keys.

7. Why must every key be rehashed after changing capacity?

The bucket index depends on the capacity:

bucketIndex = key % capacity

A new capacity can produce a different bucket index for the same key.

8. Does dynamic resizing guarantee worst-case O(1) operations?

No. Poor or adversarial key distribution can place many keys inside one bucket. Expected operation time remains constant under a well-distributed hash function and bounded load factor.

9. Is direct mapping faster than resizable separate chaining?

Direct mapping provides simpler worst-case constant-time access for the bounded key range. Resizable chaining uses memory proportional to the number of stored keys and scales better for sparse or much larger key spaces.

10. Can a HashSet be implemented through a HashMap?

Yes. Every key can be stored inside a HashMap with the same dummy value. A key-only implementation avoids storing an unnecessary value for every entry.

11. What happens after removing a missing key?

No collision chain or entry count changes because no matching node exists.

12. Can built-in arrays and linked lists be used?

Yes. The restriction applies to built-in hash-table structures. Arrays, dynamic arrays, and custom linked-list nodes remain valid implementation tools.

ArraysHashingLinked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.8k
HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.4k
Arrays

Row wise traversal

Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then second row prints as 4 5 6 . Input: mat = [[10, 20], [30, 40], [50, 60]] Output: 10 20 30 40 50...

61.7k
Comments0