Design HashMap - Practice Coding Problems

Design HashMap - Problem

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

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(int key) removes the key and its corresponding value if the map contains the mapping for the key.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MyHashMap","put","put","get","get","put","get","remove","get"], values = [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]

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

💡 Note: Create empty hashmap, put(1,1), put(2,2), get(1)→1, get(3)→null, put(2,1), get(2)→1, remove(2), get(2)→-1

Example 2 — Key Updates

$ Input: operations = ["MyHashMap","put","get","put","get"], values = [[],[5,10],[5],[5,20],[5]]

› Output: [null,null,10,null,20]

💡 Note: put(5,10) stores key 5 with value 10, get(5) returns 10, put(5,20) updates key 5 to value 20, get(5) returns 20

Example 3 — Non-existent Keys

$ Input: operations = ["MyHashMap","get","remove","get"], values = [[],[1],[2],[1]]

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

💡 Note: Empty hashmap: get(1) returns -1 (not found), remove(2) does nothing, get(1) still returns -1

Constraints

0 ≤ key, value ≤ 10⁶
At most 10⁴ calls will be made to put, get, and remove.

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of put/get/remove operations with key-value pairs

Hash Function

Map keys to bucket indices using key % bucket_size

Result Array

Return values for get operations, null for put/remove

Key Takeaway

🎯 Key Insight: Hash function provides O(1) average access by mapping keys directly to bucket indices

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Facebook 28

Design a HashMap from scratch using either array with linear search (simple but O(n)) or hash table with chaining (optimal O(1) average). The key insight is using a hash function to map keys to bucket indices for direct access. Best approach: Hash table with chaining. Time: O(1) average, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Table with Chaining	O(1)	O(n)	Use hash function to map keys to buckets, handle collisions with chaining
Array of Key-Value Pairs	O(n)	O(n)	Store all key-value pairs in a simple array and search linearly

Hash Table with Chaining — Algorithm Steps

Create array of buckets (linked lists)
Use hash function: key % bucket_size
Chain colliding entries in same bucket
Search/update within the bucket

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash Function

key % bucket_size determines bucket

Direct Access

Jump directly to the right bucket

Chain Search

Search within bucket's linked list

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 1000

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

typedef struct {
    Node* buckets[SIZE];
} MyHashMap;

int hash(int key) {
    return key % SIZE;
}

MyHashMap* myHashMapCreate() {
    MyHashMap* obj = (MyHashMap*)malloc(sizeof(MyHashMap));
    for (int i = 0; i < SIZE; i++) {
        obj->buckets[i] = NULL;
    }
    return obj;
}

void myHashMapPut(MyHashMap* obj, int key, int value) {
    int bucketIdx = hash(key);
    Node* curr = obj->buckets[bucketIdx];
    
    while (curr != NULL) {
        if (curr->key == key) {
            curr->value = value;
            return;
        }
        curr = curr->next;
    }
    
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = obj->buckets[bucketIdx];
    obj->buckets[bucketIdx] = newNode;
}

int myHashMapGet(MyHashMap* obj, int key) {
    int bucketIdx = hash(key);
    Node* curr = obj->buckets[bucketIdx];
    
    while (curr != NULL) {
        if (curr->key == key) {
            return curr->value;
        }
        curr = curr->next;
    }
    
    return -1;
}

void myHashMapRemove(MyHashMap* obj, int key) {
    int bucketIdx = hash(key);
    Node* curr = obj->buckets[bucketIdx];
    Node* prev = NULL;
    
    while (curr != NULL) {
        if (curr->key == key) {
            if (prev == NULL) {
                obj->buckets[bucketIdx] = curr->next;
            } else {
                prev->next = curr->next;
            }
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }
}

void myHashMapFree(MyHashMap* obj) {
    for (int i = 0; i < SIZE; i++) {
        Node* curr = obj->buckets[i];
        while (curr != NULL) {
            Node* temp = curr;
            curr = curr->next;
            free(temp);
        }
    }
    free(obj);
}

int main() {
    printf("[null,null,null,1,null,2,null,-1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Average case O(1) due to hash function direct access, worst case O(n) if all keys collide

✓ Linear Growth

Space Complexity

O(n)

Array of buckets plus storage for n key-value pairs

⚡ Linearithmic Space

78.4K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Table with Chaining — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler