Brute Force Approach for Design HashMap

The naive approach to solving this problem is to ignore the hashing mechanism entirely and store all key-value pairs in a single linear data structure, such as a resizable array (ArrayList) or a singular Linked List.

Naive Algorithm

1. Initialize an empty list to store pairs (key, value).
2. Put: Iterate through the entire list. If the key is found, update its value. If the end is reached without finding the key, append the new pair.
3. Get: Iterate through the entire list. If the key is found, return the value. If not found, return -1.
4. Remove: Iterate through the list. If the key is found, remove that element from the list.

Pseudo-code

text
List storage

function put(key, value):
    for pair in storage:
        if pair.key == key:
            pair.value = value
            return
    storage.add((key, value))

function get(key):
    for pair in storage:
        if pair.key == key:
            return pair.value
    return -1

Why this fails

The time complexity for this approach is $O(N)$ for every operation, where $N$ is the number of entries currently in the map. As the number of entries grows, the performance degrades linearly. While the constraints of LeetCode 706 ($10^4$ calls) might allow this to pass without a Time Limit Exceeded (TLE) depending on the test cases, it fails the interview requirement of designing an efficient data structure. A proper HashMap must offer $O(1)$ average time complexity.

Core Insight for Design HashMap

The transition from the brute force linear search to an optimal solution relies on Hashing. Instead of searching a single large list, we can divide the data into many smaller lists (buckets) based on the key.

The fundamental insight is Collision Resolution via Separate Chaining.

1. Hash Function: We need a way to map a large range of integer keys ($0$ to $10^6$) to a smaller set of indices (buckets). A simple modulo operator (key % M) serves as an effective hash function, where M is the number of buckets.
2. Buckets: We create a fixed-size array of "buckets". Each bucket is responsible for a subset of the keys.
3. Separate Chaining: Since multiple keys might map to the same bucket (a collision), each bucket acts as the head of a Linked List. All keys hashing to index i are stored in the Linked List at buckets[i].

Visual Description: Imagine a vertical array of size 1000. This is the "backbone" of the HashMap.

• When we insert key = 1, it maps to index 1 % 1000 = 1. We place a node [1, val] at index 1.
• When we insert key = 1001, it also maps to index 1001 % 1000 = 1. This is a collision. We do not overwrite the existing node. Instead, we append a new node [1001, val] to the linked list starting at index 1.
• The structure looks like an array where some slots branch out horizontally into chains of nodes.

Execution Flow

Let's trace the execution for put(1, 1), put(2, 2), and put(2, 1) with a bucket size of 10.

1. Initialize: An array buckets of size 10 is created. All indices are null.
2. put(1, 1):
   • Hash: 1 % 10 = 1.
   • Check buckets[1]. It is null.
   • Create a new Node (1, 1).
   • Set buckets[1] to point to this new Node.
3. put(2, 2):
   • Hash: 2 % 10 = 2.
   • Check buckets[2]. It is null.
   • Create a new Node (2, 2).
   • Set buckets[2] to point to this new Node.
4. put(2, 1) (Update):
   • Hash: 2 % 10 = 2.
   • Traverse the list at buckets[2].
   • First node is (2, 2). The key 2 matches the input key.
   • Update the value of this node to 1.
   • The list at buckets[2] is now (2, 1).
5. get(1):
   • Hash: 1 % 10 = 1.
   • Traverse buckets[1]. Found node (1, 1).
   • Return 1.

Proof of Correctness

The correctness of this design relies on two properties:

1. Deterministic Hashing: The hash function key % M is deterministic. The same key will always map to the same bucket index. This guarantees that if we put a key, we will look in the exact same place to get or remove it.
2. List Integrity: By using a Linked List for collisions, we ensure no data is lost when two keys map to the same index. The traversal logic linearly scans the chain, guaranteeing that we find the specific key if it exists. Since keys are unique (we update values if a key repeats), there is no ambiguity during retrieval.

Reference Implementation

C++ Solution for LeetCode 706

cpp
class MyHashMap {
private:
    struct Node {
        int key;
        int val;
        Node* next;
        Node(int k, int v) : key(k), val(v), next(nullptr) {}
    };
    
    // Use a fixed size for buckets. 
    // 1000 is chosen based on the constraint of 10^4 calls.
    const static int SIZE = 1000;
    vector<Node*> buckets;
    
    int hash(int key) {
        return key % SIZE;
    }

public:
    MyHashMap() {
        buckets.resize(SIZE, nullptr);
    }
    
    void put(int key, int value) {
        int i = hash(key);
        Node* curr = buckets[i];
        
        // If bucket is empty, insert new node
        if (curr == nullptr) {
            buckets[i] = new Node(key, value);
            return;
        }
        
        // If key matches head, update
        if (curr->key == key) {
            curr->val = value;
            return;
        }
        
        // Traverse the chain
        while (curr->next != nullptr) {
            if (curr->next->key == key) {
                curr->next->val = value;
                return;
            }
            curr = curr->next;
        }
        
        // Key not found, append to end
        curr->next = new Node(key, value);
    }
    
    int get(int key) {
        int i = hash(key);
        Node* curr = buckets[i];
        
        while (curr != nullptr) {
            if (curr->key == key) {
                return curr->val;
            }
            curr = curr->next;
        }
        return -1;
    }
    
    void remove(int key) {
        int i = hash(key);
        Node* curr = buckets[i];
        
        if (curr == nullptr) return;
        
        // Special case: removing head
        if (curr->key == key) {
            buckets[i] = curr->next;
            delete curr; // Good practice in C++
            return;
        }
        
        while (curr->next != nullptr) {
            if (curr->next->key == key) {
                Node* temp = curr->next;
                curr->next = temp->next;
                delete temp;
                return;
            }
            curr = curr->next;
        }
    }
};

Java Solution for LeetCode 706

java
class MyHashMap {
    
    private class Node {
        int key, val;
        Node next;
        
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    private static final int SIZE = 1000;
    private Node[] buckets;

    public MyHashMap() {
        buckets = new Node[SIZE];
    }
    
    private int hash(int key) {
        return key % SIZE;
    }
    
    public void put(int key, int value) {
        int index = hash(key);
        Node curr = buckets[index];
        
        if (curr == null) {
            buckets[index] = new Node(key, value);
            return;
        }
        
        // Check head
        if (curr.key == key) {
            curr.val = value;
            return;
        }
        
        while (curr.next != null) {
            if (curr.next.key == key) {
                curr.next.val = value;
                return;
            }
            curr = curr.next;
        }
        
        curr.next = new Node(key, value);
    }
    
    public int get(int key) {
        int index = hash(key);
        Node curr = buckets[index];
        
        while (curr != null) {
            if (curr.key == key) {
                return curr.val;
            }
            curr = curr.next;
        }
        return -1;
    }
    
    public void remove(int key) {
        int index = hash(key);
        Node curr = buckets[index];
        
        if (curr == null) return;
        
        if (curr.key == key) {
            buckets[index] = curr.next;
            return;
        }
        
        while (curr.next != null) {
            if (curr.next.key == key) {
                curr.next = curr.next.next;
                return;
            }
            curr = curr.next;
        }
    }
}

Python Solution for LeetCode 706

python
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

class MyHashMap:

    def __init__(self):
        self.size = 1000
        self.buckets = [None] * self.size

    def _hash(self, key):
        return key % self.size

    def put(self, key: int, value: int) -> None:
        idx = self._hash(key)
        
        if self.buckets[idx] is None:
            self.buckets[idx] = Node(key, value)
            return
        
        curr = self.buckets[idx]
        while True:
            if curr.key == key:
                curr.val = value
                return
            if curr.next is None:
                break
            curr = curr.next
            
        curr.next = Node(key, value)

    def get(self, key: int) -> int:
        idx = self._hash(key)
        curr = self.buckets[idx]
        
        while curr:
            if curr.key == key:
                return curr.val
            curr = curr.next
            
        return -1

    def remove(self, key: int) -> None:
        idx = self._hash(key)
        curr = self.buckets[idx]
        
        if curr is None:
            return
        
        if curr.key == key:
            self.buckets[idx] = curr.next
            return
            
        while curr.next:
            if curr.next.key == key:
                curr.next = curr.next.next
                return
            curr = curr.next

Why does the solution sometimes fail to update existing keys?

Mistake: In the put method, always appending a new node without checking if the key already exists in the chain. Why: The developer assumes that put implies "insert new". Consequence: The map will contain duplicate keys with different values. A subsequent get might return the old value (the first one found in the list) instead of the updated one, breaking the HashMap contract.

Why is removing nodes tricky in Linked Lists?

Mistake: Forgetting to handle the case where the node to be removed is the head of the list. Why: Removing a middle node involves prev.next = curr.next, but the head has no prev. Consequence: The code crashes or fails to remove the element if it sits at the start of a bucket chain. Special handling for the head node is mandatory.