Design HashMap

Problem Description

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

Implement the MyHashMap class:

• void put(key, value) Inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
• int get(key) Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) Removes the key and its corresponding value if the map contains the mapping for the key.

Examples

Constraints

• 0 <= key, value <= 10⁶
• At most 10⁴ calls will be made to put, get, and remove.

Key-Value Pair Chaining

To design a HashMap, we use an array of buckets containing lists of key-value nodes. The key determines the bucket index using a modulo hash. If the key exists in the bucket list during insertion, update its value. Otherwise, append a new node to the list. This avoids allocating a giant flat array of size 10^6 and handles collisions gracefully.

Solution 1: Chaining with Key-Value Node Lists

Use linked lists of key-value pairs stored in a bucket array.

import java.util.LinkedList;

class MyHashMap {
    private static class Node {
        int key, val;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private static final int BUCKET_SIZE = 1009;
    private LinkedList<Node>[] buckets;

    @SuppressWarnings("unchecked")
    public MyHashMap() {
        buckets = new LinkedList[BUCKET_SIZE];
        for (int i = 0; i < BUCKET_SIZE; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(int key) {
        return key % BUCKET_SIZE;
    }

    public void put(int key, int value) {
        int index = hash(key);
        for (Node node : buckets[index]) {
            if (node.key == key) {
                node.val = value;
                return;
            }
        }
        buckets[index].add(new Node(key, value));
    }

    public int get(int key) {
        int index = hash(key);
        for (Node node : buckets[index]) {
            if (node.key == key) {
                return node.val;
            }
        }
        return -1;
    }

    public void remove(int key) {
        int index = hash(key);
        Node toRemove = null;
        for (Node node : buckets[index]) {
            if (node.key == key) {
                toRemove = node;
                break;
            }
        }
        if (toRemove != null) {
            buckets[index].remove(toRemove);
        }
    }
}

class MyHashMap:
    def __init__(self):
        self.bucket_size = 1009
        self.buckets = [[] for _ in range(self.bucket_size)]

    def _hash(self, key: int) -> int:
        return key % self.bucket_size

    def put(self, key: int, value: int) -> None:
        index = self._hash(key)
        for item in self.buckets[index]:
            if item[0] == key:
                item[1] = value
                return
        self.buckets[index].append([key, value])

    def get(self, key: int) -> int:
        index = self._hash(key)
        for item in self.buckets[index]:
            if item[0] == key:
                return item[1]
        return -1

    def remove(self, key: int) -> None:
        index = self._hash(key)
        for i, item in enumerate(self.buckets[index]):
            if item[0] == key:
                self.buckets[index].pop(i)
                return

#include <vector>
#include <list>
#include <utility>
#include <algorithm>

class MyHashMap {
private:
    int bucket_size;
    std::vector<std::list<std::pair<int, int>>> buckets;

    int hash(int key) {
        return key % bucket_size;
    }

public:
    MyHashMap() {
        bucket_size = 1009;
        buckets.resize(bucket_size);
    }

    void put(int key, int value) {
        int index = hash(key);
        auto& cell = buckets[index];
        for (auto& pair : cell) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        cell.push_back({key, value});
    }

    int get(int key) {
        int index = hash(key);
        auto& cell = buckets[index];
        for (const auto& pair : cell) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return -1;
    }

    void remove(int key) {
        int index = hash(key);
        auto& cell = buckets[index];
        for (auto it = cell.begin(); it != cell.end(); ++it) {
            if (it->first == key) {
                cell.erase(it);
                return;
            }
        }
    }
};

Complexity Analysis

• Time Complexity: O(1) average case for all operations. Worst case degrades to O(n) if all elements hash to a single bucket.
• Space Complexity: O(n + b) where n is the number of items currently in the map and b is the bucket size.

Where It Breaks

High key collision rates limit search efficiency. In standard systems, when chains grow long, they are often converted to self-balancing binary search trees (e.g. Red-Black trees in Java’s HashMap) to guarantee O(log k) worst-case lookups.

Common Mistakes

• Incorrect node matching: Updating all nodes in the bucket instead of matching the specific key.
• Concurrent modification errors: Attempting to iterate and remove a node from the linked list directly in a single pass without using a clean locator.

Frequently Asked Questions

How does this handle key removal? It computes the bucket index and traverses the chain. If a matching key is found, the node is disconnected from the list.

What is the impact of bucket capacity size? A bucket array that is too small leads to long linked list chains, reducing search speeds. A bucket array that is too large consumes excessive empty memory.

← All Problems