Design HashMap
Problem
Design a HashMap without any built-in libraries. Implement put(key, value), get(key) returning -1 if absent, and remove(key).
put(1,1); put(2,2); get(1); get(3); put(2,1); get(2); remove(2); get(2);1, -1, 1, -1class MyHashMap:
def __init__(self):
self.size = 1009
self.buckets = [[] for _ in range(self.size)]
def _bucket(self, key):
return self.buckets[key % self.size]
def put(self, key, value):
b = self._bucket(key)
for i, (k, _) in enumerate(b):
if k == key:
b[i] = (key, value); return
b.append((key, value))
def get(self, key):
for k, v in self._bucket(key):
if k == key: return v
return -1
def remove(self, key):
b = self._bucket(key)
for i, (k, _) in enumerate(b):
if k == key: b.pop(i); returnclass MyHashMap {
constructor() { this.size = 1009; this.buckets = Array.from({length: this.size}, () => []); }
_b(key) { return this.buckets[key % this.size]; }
put(key, value) {
const b = this._b(key);
for (const pair of b) if (pair[0] === key) { pair[1] = value; return; }
b.push([key, value]);
}
get(key) {
for (const [k, v] of this._b(key)) if (k === key) return v;
return -1;
}
remove(key) {
const b = this._b(key);
const i = b.findIndex(p => p[0] === key);
if (i >= 0) b.splice(i, 1);
}
}class MyHashMap {
int size = 1009;
List<int[]>[] buckets;
public MyHashMap() { buckets = new List[size]; for (int i = 0; i < size; i++) buckets[i] = new ArrayList<>(); }
public void put(int key, int value) {
List<int[]> b = buckets[key % size];
for (int[] p : b) if (p[0] == key) { p[1] = value; return; }
b.add(new int[]{key, value});
}
public int get(int key) {
for (int[] p : buckets[key % size]) if (p[0] == key) return p[1];
return -1;
}
public void remove(int key) {
List<int[]> b = buckets[key % size];
for (int i = 0; i < b.size(); i++) if (b.get(i)[0] == key) { b.remove(i); return; }
}
}class MyHashMap {
int sz = 1009;
vector<list<pair<int,int>>> buckets;
public:
MyHashMap() : buckets(1009) {}
void put(int key, int value) {
auto& b = buckets[key % sz];
for (auto& p : b) if (p.first == key) { p.second = value; return; }
b.push_back({key, value});
}
int get(int key) {
for (auto& p : buckets[key % sz]) if (p.first == key) return p.second;
return -1;
}
void remove(int key) {
auto& b = buckets[key % sz];
for (auto it = b.begin(); it != b.end(); ++it) if (it->first == key) { b.erase(it); return; }
}
};Explanation
We have to build a hash map from scratch. The classic design is an array of buckets, where each bucket is a small list of (key, value) pairs. This approach is called separate chaining.
To find a key's bucket we compute key % size. Many different keys can land in the same bucket, so each bucket holds a list and we walk that short list to find the exact key. Here size is a fixed prime like 1009 to spread keys out evenly.
put: go to the bucket, scan its pairs; if the key already exists we overwrite its value, otherwise we append a new pair. get: scan the bucket and return the matching value, or -1 if the key is not there. remove: scan the bucket and delete the matching pair.
Example: put(1,1) and put(2,2) drop into their buckets. get(1) returns 1, get(3) returns -1. After put(2,1) the pair for key 2 is overwritten, so get(2) is 1; then remove(2) makes the next get(2) return -1.
Because keys spread across many buckets, each chain stays short, so put/get/remove are effectively constant time on average.