706.Design_HashMap(Easy).md

706. Design HashMap (Easy)

Date and Time: Jun 5, 2026

Link: https://leetcode.com/problems/design-hashmap/

Question:

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.

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
myHashMap.get(3); // return -1 (not found)
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]]
myHashMap.get(2); // return 1
myHashMap.remove(2); // remove the mapping for 2, map is now [[1,1]]
myHashMap.get(2); // return -1 (not found)

Constraints:

• 0 <= key, value <= 10^6

• At most 10^4 calls will be made to put, get, and remove.

Walk-through:

Use array of buckets or linked-list with chaining for collision handling.

1. Initialize an array of 2069 (prime) empty buckets. Using a prime reduces clustering.

2. put: Hash key % 2069 to get the bucket. Scan for existing key and update in-place; otherwise append [key, value].

3. get: Hash to the bucket, scan for key, return its value or -1 if not found.

4. remove: Hash to the bucket, scan for key by index, and del bucket[i] if found.

Python Solution:

class MyHashMap:

    # Initialize an array as table and each bucket with another array for hash collision
    def __init__(self):
        self.hashmap = [[] for _ in range(2069)]  # Pick 2069 prime number to be the whole space length
        self.hashkey = 2069
        
    # Hash the key by the len(table), loop over the bucket array to find key, if key can be found, update value. Otherwise, append [key, value]
    def put(self, key: int, value: int) -> None:
        bucket = self.hashmap[key % self.hashkey]
        # Search if key in bucket already
        for i, lst in enumerate(bucket):
            if lst[0] == key:
                bucket[i][1] = value
                return
        # If key doesn't exist, we append in the end
        bucket.append([key, value])
        
    # Hash key to find the bucket in table, then loop over array to see if key exists. Otherwise, return -1
    def get(self, key: int) -> int:
        bucket = self.hashmap[key % self.hashkey]
        # Search if key in bucket already
        for k, v in bucket:
            if k == key:
                return v
        # If key doesn't exist, return -1
        return -1
        
    # Use hashed key to find bucket in table, then search key and remove
    def remove(self, key: int) -> None:
        bucket = self.hashmap[key % self.hashkey]
        # Search if key in bucket already by using index for later removal
        for i, lst in enumerate(bucket):
            if lst[0] == key:
                del bucket[i]


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

Time Complexity: $O(n/k)$ per operation on average, where n is the number of keys and k = 2069 is the number of buckets.
Space Complexity: $O(n + k)$, for all stored key-value pairs plus the bucket array.