Design HashMap

Difficulty: Easy | Acceptance: 66.50% | Paid: No Topics: Array, Hash Table, Linked List, Design, Hash Function

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

To be specific, your design should include these functions:

• put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.

• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

• remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

• Examples

• Constraints

• Approach 1: Direct Addressing (Array)

• Approach 2: Separate Chaining (Linked List)

• Approach 3: Open Addressing (Linear Probing)

Examples

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 hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);         // update the existing value
hashMap.get(2);            // returns 1
hashMap.remove(2);         // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)

Constraints

0 <= key, value <= 10^6
At most 10^4 calls will be made to put, get, and remove.

Direct Addressing (Array)

Intuition Since the key range is limited to $10^6$, we can use a direct array where the index corresponds to the key. This avoids collision handling entirely.

Steps

• Initialize an array of size $10^6 + 1$ with -1 (indicating empty).
• For put, simply assign array[key] = value.
• For get, return array[key].
• For remove, set array[key] = -1.

class MyHashMap:

    def __init__(self):
        self.size = 1000001
        self.map = [-1] * self.size

    def put(self, key: int, value: int) -> None:
        self.map[key] = value

    def get(self, key: int) -> int:
        return self.map[key]

    def remove(self, key: int) -> None:
        self.map[key] = -1

Complexity

• Time: $O(1)$ for all operations.
• Space: $O(10⁶)$ to store the array.
• Notes: Extremely fast but memory-intensive. Not suitable if key range is very large.

Separate Chaining (Linked List)

Intuition Use a fixed-size array (buckets) where each index points to a linked list of key-value pairs. Collisions are resolved by appending to the list.

Steps

• Define a ListNode class to store key, value, and next pointer.
• Initialize an array of dummy ListNode heads (size e.g., 1000).
• Hash function: key % size.
• Traverse the list to find, update, or delete a node.

class ListNode:
    def __init__(self, key=-1, val=-1, next=None):
        self.key = key
        self.val = val
        self.next = next

class MyHashMap:

    def __init__(self):
        self.size = 1000
        self.map = [ListNode() for _ in range(self.size)]

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

    def put(self, key: int, value: int) -> None:
        idx = self._hash(key)
        prev = self.map[idx]
        curr = prev.next
        while curr:
            if curr.key == key:
                curr.val = value
                return
            prev = curr
            curr = curr.next
        prev.next = ListNode(key, value)

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

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

Complexity

• Time: $O(N/K)$ on average, where $N$ is number of elements and $K$ is bucket size. Worst case $O(N)$.
• Space: $O(N + K)$.
• Notes: Standard approach for hash maps. Handles collisions gracefully.

Open Addressing (Linear Probing)

Intuition Store all key-value pairs in a single array. If a collision occurs, search for the next available slot (linear probing).

Steps

• Initialize an array of size $N$ (e.g., 20000) with null.
• Hash function: key % size.
• If slot is occupied by a different key, increment index (with wrap-around) until an empty slot or the key is found.

class MyHashMap:

    def __init__(self):
        self.cap = 20000
        self.map = [None] * self.cap

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

    def put(self, key: int, value: int) -> None:
        idx = self._hash(key)
        while self.map[idx] is not None:
            if self.map[idx][0] == key:
                self.map[idx] = (key, value)
                return
            idx = (idx + 1) % self.cap
        self.map[idx] = (key, value)

    def get(self, key: int) -> int:
        idx = self._hash(key)
        while self.map[idx] is not None:
            if self.map[idx][0] == key:
                return self.map[idx][1]
            idx = (idx + 1) % self.cap
        return -1

    def remove(self, key: int) -> None:
        idx = self._hash(key)
        while self.map[idx] is not None:
            if self.map[idx][0] == key:
                self.map[idx] = None
                return
            idx = (idx + 1) % self.cap

Complexity

• Time: $O(1)$ average, $O(N)$ worst case (clustering).
• Space: $O(N)$.
• Notes: Good cache locality, but performance degrades with high load factor.