DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Design HashMap

easyArrays and hashing

Problem statement

Build your own hash map class, MyHashMap, without using any built-in hash table library. Keys and values are non-negative integers up to 1,000,000. It must support:

  • put(key, value): store the value for the key, replacing any existing value.
  • get(key): return the stored value, or -1 if the key is not present.
  • remove(key): delete the key if it is present.

Picture a small table from port number to the process ID listening on it.

Examples

Example 1

Input: put(8080, 1), put(443, 2), get(8080), get(22), put(443, 5), get(443), remove(8080), get(8080)

Output: [1, -1, 5, -1]

Explanation: Only the get results are shown. Port 443 is overwritten with 5, and 8080 returns -1 after it is removed.

Example 2

Input: remove(7), put(0, 0), get(0), get(7)

Output: [0, -1]

Explanation: Removing a missing key does nothing. Key 0 with value 0 is a valid entry.

Hints

Approach

This is how a real hash map works: an array of b buckets, where each key goes into bucket key % b, and each bucket holds a short list of pairs (called separate chaining).

  1. Create b empty buckets. A prime such as 1009 spreads keys evenly.
  2. To find a key's bucket, compute key % b.
  3. put, get and remove do the same linear scan as before, but only inside that one bucket.

With n keys spread over b buckets, each bucket holds about n / b pairs, so operations are O(1) on average. The worst case is still O(n) if every key lands in the same bucket.

ComplexityTime O(1) average per operationSpace O(n + b)
Python
class MyHashMap:
SIZE = 1009
def __init__(self):
self.buckets = [[] for _ in range(self.SIZE)]
def _bucket(self, key: int) -> list:
return self.buckets[key % self.SIZE]
def put(self, key: int, value: int) -> None:
bucket = self._bucket(key)
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
def get(self, key: int) -> int:
for k, v in self._bucket(key):
if k == key:
return v
return -1
def remove(self, key: int) -> None:
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i)
return

Follow-up questions

  • Add automatic resizing when the load factor goes above 0.75.
  • Support string keys. How would you hash them?

Frequently asked questions

That also works here, with O(1) worst-case operations, because keys are small non-negative integers. It is called a direct-address table. It uses memory for every possible key, though, and it does not generalise to strings or large keys. Mention it, then show the bucket version.

Real hash maps track the load factor (entries divided by buckets). When it passes a threshold, often around 0.75, they allocate more buckets and move every entry to its new bucket. That keeps the average cost O(1).

Hash maps sit under caches, service registries and routing tables. Knowing about collisions, load factors and resizing helps when you reason about things like consistent hashing across cache nodes or why a lookup table got slow.