Design Hashmap

116.5k
0

Design a HashMap for integer keys and integer values without using any built-in hash-table library.

Implement the MyHashMap class with the following operations:

  • MyHashMap() initializes an empty HashMap.

  • put(int key, int value) inserts a new key-value mapping. An existing key receives the updated value.

  • get(int key) returns the value associated with key. A missing key returns -1.

  • remove(int key) removes the mapping associated with key. A missing key causes no change.

The valid key range extends from 0 to 10^6.

Example 1

Input: ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output: [null, null, null, 1, -1, null, 1, null, -1]

Explanation:

MyHashMap myHashMap = new MyHashMap();

myHashMap.put(1, 1); // The map is now [[1,1]]

myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]

myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]

myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]

myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (update the existing value)

myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]

myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]

myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Brute Force Approach

Direct indexing becomes possible because every valid key belongs to a known bounded range. A key can serve as the array index, removing the need for a hash function, collision handling, or bucket traversal.

Constant-time operations come at a large memory cost. A map containing only one key still reserves storage for every possible key from 0 to 10^6. The approach therefore uses the key range rather than the number of stored mappings to determine memory usage.

Algorithm

  • Create two arrays of size 1,000,001:

    • values stores the value associated with every key.

    • present records whether a mapping currently exists at every key.

  • For the constructor:

    • Initialize every present position with false.

  • For put(key, value):

    • Store value at values[key].

    • Mark present[key] as true.

  • For get(key):

    • Return -1 when present[key] is false.

    • Return values[key] when the mapping exists.

  • For remove(key):

    • Mark present[key] as false.

    • Leave the old value untouched because a cleared presence marker prevents future access.

Dry Run

u

u

Solution

#include <bits/stdc++.h>
using namespace std;
class MyHashMap {
private:
static const int MAX_KEY = 1000000;
vector<int> values;
vector<bool> present;
public:
/* Initializes direct-address storage
for every valid key. */
MyHashMap()
: values(MAX_KEY + 1, 0),
present(MAX_KEY + 1, false) {
}
/* Inserts a new mapping or updates
an existing mapping. */
void put(int key, int value) {
values[key] = value;
present[key] = true;
}
/* Returns the stored value or -1
when the key is absent. */
int get(int key) {
if (!present[key]) {
return -1;
}
return values[key];
}
/* Removes a mapping by clearing
the presence marker. */
void remove(int key) {
present[key] = false;
}
};
// Driver code to execute the design.
int main() {
MyHashMap myHashMap;
myHashMap.put(1, 1);
myHashMap.put(2, 2);
cout << myHashMap.get(1) << endl;
cout << myHashMap.get(3) << endl;
myHashMap.put(2, 1);
cout << myHashMap.get(2) << endl;
myHashMap.remove(2);
cout << myHashMap.get(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 put, get, and remove operation requires O(1) time through direct array indexing.

Space Complexity: O(K), because both arrays reserve one position for every valid key regardless of the number of stored mappings.

Better Approach

Direct addressing reserves memory for every possible key, even when most keys never appear. A smaller primary array can reduce memory usage by mapping many keys into a limited number of buckets.

The expression key % B produces a bucket index from 0 to B - 1, where B represents the bucket count. Different keys can produce the same index. Every bucket therefore stores a dynamic list of key-value entries, allowing all colliding keys to remain available.

A fixed bucket count avoids the huge direct-address array, but growing input can create long bucket lists. Operation cost depends on the number of entries inside the selected bucket.

Algorithm

  • Choose a fixed bucket count B.

  • Create an array containing B empty dynamic lists.

  • Calculate the bucket index using key % B.

  • For put(key, value):

    • Traverse the selected bucket.

    • Update the stored value when a matching key exists.

    • Append a new key-value entry when no matching key exists.

  • For get(key):

    • Traverse the selected bucket.

    • Return the corresponding value after finding the key.

    • Return -1 after reaching the end without a match.

  • For remove(key):

    • Traverse the selected bucket.

    • Delete the matching entry after locating the key.

    • Perform no change when the key is absent.

Dry Run

f

f

Solution

#include <bits/stdc++.h>
using namespace std;
class MyHashMap {
private:
static const int BUCKET_COUNT = 1009;
vector<vector<pair<int, 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 empty buckets. */
MyHashMap()
: buckets(BUCKET_COUNT) {
}
/* Inserts a new mapping or updates
an existing mapping. */
void put(int key, int value) {
int index = bucketIndex(key);
vector<pair<int, int>>& bucket =
buckets[index];
// Search the bucket for an existing key.
for (pair<int, int>& entry : bucket) {
if (entry.first == key) {
entry.second = value;
return;
}
}
// Append a new entry after no match.
bucket.push_back({
key,
value
});
}
/* Returns the stored value or -1
when the key is absent. */
int get(int key) {
int index = bucketIndex(key);
const vector<pair<int, int>>& bucket =
buckets[index];
// Search only the selected bucket.
for (
const pair<int, int>& entry :
bucket
) {
if (entry.first == key) {
return entry.second;
}
}
return -1;
}
/* Removes a mapping from
the selected bucket. */
void remove(int key) {
int index = bucketIndex(key);
vector<pair<int, int>>& bucket =
buckets[index];
// Locate the entry before erasing it.
for (
int position = 0;
position < (int)bucket.size();
position++
) {
if (
bucket[position].first ==
key
) {
bucket.erase(
bucket.begin() +
position
);
return;
}
}
}
};
// Driver code to execute the design.
int main() {
MyHashMap myHashMap;
myHashMap.put(1, 1);
myHashMap.put(2, 2);
cout << myHashMap.get(1) << endl;
cout << myHashMap.get(3) << endl;
myHashMap.put(2, 1);
cout << myHashMap.get(2) << endl;
myHashMap.remove(2);
cout << myHashMap.get(2) << endl;
return 0;
}

Complexity Analysis

Let:

  • N represent the number of stored mappings.

  • B represent the fixed bucket count.

  • α = N / B represent the load factor.

Time Complexity: The constructor requires O(B) time. put, get, and remove require expected O(1 + α) time because only one bucket is searched. A bucket containing every key produces O(N) worst-case time. Dynamic-array deletion can also shift the remaining entries of the selected bucket.

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

Optimal Approach

Fixed-size separate chaining saves memory compared with direct addressing, but a fixed bucket count allows the load factor to grow continuously.

The load factor is:

number of stored mappings / number of buckets

A large load factor increases the expected number of nodes inside each collision chain. Dynamic resizing keeps the load factor bounded. After the next insertion would cross a selected threshold, the bucket array doubles and every stored key receives a new bucket index.

Custom linked lists remove dynamic-array shifting during deletion. A dummy head at every bucket keeps insertion and removal logic uniform, including operations involving the first real node. Linked-list buckets alone do not guarantee short searches; resizing and rehashing provide the important scalability improvement.

Algorithm

  • Create a custom Node containing:

    • key

    • value

    • next

  • Initialize a bucket array with a small starting capacity.

  • Place one dummy head node inside every bucket.

  • Track:

    • capacity, representing the current bucket count.

    • entryCount, representing the number of stored mappings.

    • MAX_LOAD_FACTOR, representing the resize threshold.

  • Calculate the bucket index using key % capacity.

  • For put(key, value):

    • Traverse the selected chain and update the value when the key already exists.

    • Calculate the load factor expected after a new insertion.

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

    • Insert the new node directly after the dummy head.

    • Increase entryCount.

  • For get(key):

    • Traverse the selected chain after the dummy head.

    • Return the stored value after finding the key.

    • Return -1 after reaching the end.

  • For remove(key):

    • Start previous at the dummy head.

    • Traverse the chain with current.

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

    • Decrease entryCount.

  • For rehashing:

    • Double the bucket-array capacity.

    • Create new dummy heads.

    • Recalculate the bucket index for every stored node.

    • Move every node into the corresponding new chain.

Dry Run

g

g

Solution

#include <bits/stdc++.h>
using namespace std;
class MyHashMap {
private:
struct Node {
int key;
int value;
Node* next;
Node(
int key,
int value,
Node* next = nullptr
)
: key(key),
value(value),
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, -1);
}
}
/* Doubles capacity and redistributes
all stored nodes. */
void rehash() {
vector<Node*> oldBuckets =
move(buckets);
int oldCapacity = capacity;
capacity *= 2;
createEmptyBuckets(capacity);
// Move every 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:

Complexity Analysis

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

Time Complexity:

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

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

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

  • put: Expected amortized O(1). A single insertion can require O(N) during rehashing, but geometric capacity growth distributes total rehashing work across many insertions.

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

Space Complexity: O(N) for stored nodes and a bucket array whose capacity grows with the peak number of mappings. During rehashing, old and new bucket arrays briefly coexist, but total space remains O(N).

FAQs about Design HashMap

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

Direct addressing uses the complete key range as memory. Constant-time operations are achieved by reserving storage for every possible key, including keys never inserted.

2. What causes a collision?

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

For bucket count 5:

  • 1 % 5 = 1

  • 6 % 5 = 1

Both mappings must remain inside bucket 1.

3. Why does a dummy head simplify linked-list operations?

A predecessor always exists, including deletion of the first real node. The same pointer-rewiring statement therefore handles every deletion position.

4. Does linked-list deletion always take O(1) time?

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

5. Why is resizing required?

A fixed bucket array can accumulate long chains as the number of entries grows. Resizing increases the number of available buckets and reduces the expected chain length after rehashing.

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

The bucket index depends on the current capacity:

bucketIndex = key % capacity

Changing capacity can change the result of the modulo operation, so old bucket positions are no longer valid.

7. Does separate chaining guarantee worst-case O(1) operations?

No. A poor key distribution can place every mapping inside one bucket, producing O(N) worst-case traversal.

Expected operation cost remains constant when hashing distributes keys well and load factor stays bounded.

8. Why does the Optimal Approach insert after the dummy head?

Head insertion requires no traversal after the absence check and no tail pointer. Chain ordering does not affect HashMap correctness.

9. What happens after removing a missing key?

No chain modification occurs. The stored entry count also remains unchanged.

10. Can built-in arrays and lists be used?

Yes. The restriction applies to built-in hash-table structures such as unordered_map, HashMap, dict, or Map. Arrays, dynamic arrays, and custom linked-list nodes remain valid implementation tools.

HashingArraysLinked 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

Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 and 20 are present twice but counted once. Therefore, the number of distinct elements is...

76.4k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Comments0