LeetCode Solutions Blog

Design HashMap

Number: 817

Difficulty: Easy

Paid? No

Problem Description

Design a HashMap without using any built-in hash table libraries. Implement a MyHashMap class with methods to add (or update) a key-value pair, retrieve a value by key, and remove a mapping by key.

Key Insights

Use a fixed-size array of buckets where each bucket uses a linked list to handle collisions.
Choose a simple hash function (e.g., modulo operation) to map a key to its corresponding bucket.
For each bucket, traverse the linked list to update an existing key or append a new node if the key does not exist.
Removal requires updating pointers in the linked list to bypass the removed node.

Space and Time Complexity

Time Complexity: Average O(1) for put, get, and remove; worst-case O(n) when many keys hash to the same bucket.
Space Complexity: O(n), where n is the number of key-value pairs stored.

Solution

We implement the HashMap using an array of fixed size (e.g., 1000). Each array element is the head of a linked list that manages collisions using chaining. The key is hashed using a modulo operation.
For the put operation, if a key already exists in the chain, its value is updated; otherwise, a new node is appended.
The get operation traverses the chain at the computed bucket index to find and return the corresponding value, or returns -1 if not found.
The remove operation also traverses the list, carefully reconnecting the links to remove the target node while handling edge cases such as removal at the head.

Code Solutions

# ListNode class for handling collisions in each bucket
class ListNode:
    def __init__(self, key, value, next=None):
        self.key = key         # Store key
        self.value = value     # Store value
        self.next = next       # Pointer to the next node

class MyHashMap:
    def __init__(self):
        self.size = 1000                     # Define the bucket size
        self.buckets = [None] * self.size    # Initialize buckets as an array of None

    def hash(self, key):
        # Simple modulo based hash function to map keys to bucket indices
        return key % self.size

    def put(self, key: int, value: int) -> None:
        index = self.hash(key)
        if self.buckets[index] is None:
            # If the bucket is empty, create a new node and place it here
            self.buckets[index] = ListNode(key, value)
        else:
            current = self.buckets[index]
            while True:
                if current.key == key:
                    # If key exists, update its value
                    current.value = value
                    return
                if current.next is None:
                    break
                current = current.next
            # Append a new node at the end of the list if key not found
            current.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = self.hash(key)
        current = self.buckets[index]
        while current:
            if current.key == key:
                # Key found; return its value
                return current.value
            current = current.next
        # Key not found; return -1
        return -1

    def remove(self, key: int) -> None:
        index = self.hash(key)
        current = self.buckets[index]
        if current is None:
            return
        if current.key == key:
            # Remove head node if it contains the key
            self.buckets[index] = current.next
        else:
            prev = current
            current = current.next
            while current:
                if current.key == key:
                    # Bypass the node to remove it from the list
                    prev.next = current.next
                    return
                prev, current = current, current.next