Domain 1EasyCORE

Design HashMap

We need to design a simple HashMap without using any built-in hash table libraries. The `MyHashMap` class should support three operations: `put`, `get`, and `remove`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Design

706. Design HashMap

Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 64.1%


Problem Breakdown

We need to design a simple HashMap without using any built-in hash table libraries. The MyHashMap class should support three operations: put, get, and remove.

  • Inputs:

    • For put(int key, int value): A key-value pair.
    • For get(int key) and remove(key): A single key.
  • Outputs:

    • For put and remove: No output (void).
    • For get: An integer value or -1 if the key is not found.
  • Implicit Constraints:

    • Keys and values are non-negative integers.
    • The maximum number of operations (put, get, remove) is 10,000.

Intuition

A brute-force approach would be to use a list or array where each element represents a key-value pair. However, this approach would have a time complexity of O(n) for all operations due to the need to search through the entire list.

The key insight is to use an array (or list) of fixed size and employ a simple hash function to map keys to indices in this array. This allows us to achieve average O(1) time complexity for put, get, and remove operations.

Approach

We will implement the MyHashMap class using an array where each index corresponds to a key. To handle collisions (multiple keys hashing to the same index), we’ll use chaining with linked lists. Each element in the array will be a list that stores all key-value pairs that hash to the same index.

  1. Initialization: Create an array of size 10^6 + 1 (to cover the range of possible keys) where each element is initialized as an empty list.
  2. Put Operation:
    • Compute the hash index using the modulo operation (key % len(self.map)).
    • Check if the key already exists in the linked list at that index. If it does, update its value. Otherwise, append the new key-value pair to the list.
  3. Get Operation:
    • Compute the hash index.
    • Traverse the linked list at that index to find the key. If found, return its value; otherwise, return -1.
  4. Remove Operation:
    • Compute the hash index.
    • Traverse the linked list at that index to find and remove the key-value pair if it exists.

Complexity Analysis

  • Time Complexity:

    • put, get, and remove operations have an average time complexity of O(1) due to the use of a hash function. In the worst case (all keys hashing to the same index), these operations can degrade to O(n).
  • Space Complexity:

    • The space complexity is O(m + n), where m is the size of the array and n is the number of key-value pairs stored in the map.

Solution

class MyHashMap:

    def __init__(self):
        # Initialize an array of size 10^6 + 1 with empty lists for chaining
        self.map = [[] for _ in range(10**6 + 1)]

    def put(self, key: int, value: int) -> None:
        # Compute the hash index
        idx = key % len(self.map)
        
        # Check if the key already exists and update its value
        for i, (k, v) in enumerate(self.map[idx]):
            if k == key:
                self.map[idx][i] = (key, value)
                return
        
        # If the key does not exist, append the new key-value pair
        self.map[idx].append((key, value))

    def get(self, key: int) -> int:
        # Compute the hash index
        idx = key % len(self.map)
        
        # Traverse the linked list to find the key and return its value
        for k, v in self.map[idx]:
            if k == key:
                return v
        
        # If the key is not found, return -1
        return -1

    def remove(self, key: int) -> None:
        # Compute the hash index
        idx = key % len(self.map)
        
        # Traverse the linked list to find and remove the key-value pair
        for i, (k, v) in enumerate(self.map[idx]):
            if k == key:
                del self.map[idx][i]
                return

Edge Cases Handled

  • Key Already Exists: The put method updates the value if the key already exists.
  • Key Not Found: The get and remove methods handle keys that are not present in the map by returning -1 or doing nothing, respectively.
  • Empty Map: All operations work correctly even when the map is initially empty.