💬 Discord
Sign In
NeetCode #59LC-706EasyArrays & HashingNC 250
← Back to All Problems

#59 · #706 · Design HashMap(设计哈希映射)

📌 Problem Statement & Constraints

Design a HashMap without using any built-in hash table libraries. Implement put(key, value), get(key) and remove(key). Constraints: 0 <= key, value <= 10^6; at most 10^4 calls will be made.

💡 Core Algorithmic Approaches

  1. Same skeleton as the HashSet, but each bucket stores (key, value) pairs instead of bare keys.
  2. put: find the bucket, then either update the existing pair with the same key or append a new one. Updating in place is what distinguishes a map from a set.
  3. get: search the bucket for the key and return its value, or -1 if absent.
  4. remove: find the index of the key inside the bucket and pop that index. Using list.remove((key, value)) is wrong because you would have to know the value.
  5. A bucket can be a dict keyed by the map key, which makes the three operations trivially short while still demonstrating the hash-table design.

💻 Benchmark Python3 Implementation

class MyHashMap:
    def __init__(self):
        self.B = 997
        self.buckets = [[] for _ in range(self.B)]   # each entry: [key, value]

    def _idx(self, key: int) -> int:
        return key % self.B

    def put(self, key: int, value: int) -> None:
        b = self.buckets[self._idx(key)]
        for pair in b:
            if pair[0] == key:
                pair[1] = value          # update in place
                return
        b.append([key, value])           # new key

    def get(self, key: int) -> int:
        for k, v in self.buckets[self._idx(key)]:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        b = self.buckets[self._idx(key)]
        for i, (k, _) in enumerate(b):
            if k == key:
                b.pop(i)                 # remove by index, not by value
                return


# Compact variant: each bucket is a dict
class MyHashMap2:
    def __init__(self):
        self.B = 997
        self.buckets = [{} for _ in range(self.B)]

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

    def get(self, key: int) -> int:
        return self.buckets[key % self.B].get(key, -1)

    def remove(self, key: int) -> None:
        self.buckets[key % self.B].pop(key, None)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) average per operation, assuming a well-distributed modulus and bounded load factor.
💾 Space Complexity
O(n + B) where n is the number of distinct keys.

⚠️ Interview Pitfalls & Follow-ups

  • list.remove((key, value)) in remove: you would need the current value, and duplicates of the key cannot exist anyway. Search by key and pop the index.
  • Appending in put without checking for an existing key: the map would grow duplicates and get could return a stale value.
  • Returning None from get: the contract requires -1 for a missing key.
  • Forgetting that remove on a missing key must be a no-op: use pop(key, None) or an explicit membership test.