The Leetcode "Design HashMap" problem asks you to implement a data structure that mimics the behavior of a standard hash map (also known as a dictionary or associative array).
You must create a class MyHashMap with the following methods:
put(key, value): Insert a (key, value) pair into the HashMap. If the key already exists, update its value.get(key): Return the value mapped to key, or -1 if the key does not exist.remove(key): Remove the mapping for key if it exists.You are not allowed to use any built-in hash table libraries. You must design the underlying data structure and collision handling yourself.
Constraints:
The core challenge is to efficiently store and retrieve key-value pairs without using built-in hash maps. We need to think about how to map a potentially large range of keys (e.g., up to 106 or more) into a fixed-size array, and how to handle cases where two keys map to the same array index (collisions).
A brute-force approach might be to use a large array where each index directly corresponds to a key. But this is memory-inefficient if the key space is sparse. Instead, we use a hash function to map keys to array indices and handle collisions using "chaining" (linked lists or arrays at each index) or "open addressing" (probing for empty slots).
We want our operations (put, get, remove) to be fast, so we choose a hash function and collision handling method that keeps the average number of items per bucket low.
To design our own hash map, we'll use the following steps:
(key, value) pairs.index = key % num_buckets.(key, value) pairs in the same bucket (as a list).get and remove, we search the bucket for the key.put: Hash the key, search the bucket, update or insert.get: Hash the key, search the bucket, return value or -1.remove: Hash the key, search the bucket, remove if found.This structure ensures that all operations have average-case O(1) time, assuming a good hash function and a reasonable load factor (number of keys per bucket).
Let's walk through an example with the following operations:
MyHashMap() put(1, 10) put(2, 20) get(1) # returns 10 get(3) # returns -1 (not found) put(2, 30) # update value for key=2 get(2) # returns 30 remove(2) get(2) # returns -1 (removed)
put(1, 10): Hash 1 to an index (e.g., 1 % 1000 = 1). Insert (1, 10) in bucket 1.put(2, 20): Hash 2 to index 2. Insert (2, 20) in bucket 2.get(1): Hash 1 to index 1. Find (1, 10) in bucket 1, return 10.get(3): Hash 3 to index 3. Bucket 3 is empty, return -1.put(2, 30): Hash 2 to index 2. Find (2, 20) in bucket 2, update to (2, 30).get(2): Hash 2 to index 2. Find (2, 30) in bucket 2, return 30.remove(2): Hash 2 to index 2. Remove (2, 30) from bucket 2.get(2): Hash 2 to index 2. Bucket 2 is now empty, return -1.At every step, we only need to look in one bucket, so all operations are fast.
put, get, and remove would be O(1) time, but space would be O(MAX_KEY), which is wasteful if keys are sparse.put, get, remove is O(1), because each bucket contains few items if the hash function is good and the number of buckets is large enough.
In this problem, we built a simple hash map from scratch using an array of buckets and a hash function, handling collisions by chaining. The key insight is that by distributing keys across buckets and resolving collisions locally, we achieve fast average-case operations without excessive memory usage. This approach mirrors how real-world hash tables work and is a fundamental data structure in computer science.
class MyHashMap:
def __init__(self):
self.size = 1009 # use a prime number for better distribution
self.buckets = [[] for _ in range(self.size)]
def put(self, key: int, value: int) -> None:
idx = key % self.size
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value)
return
self.buckets[idx].append((key, value))
def get(self, key: int) -> int:
idx = key % self.size
for k, v in self.buckets[idx]:
if k == key:
return v
return -1
def remove(self, key: int) -> None:
idx = key % self.size
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
del bucket[i]
return
class MyHashMap {
static const int SIZE = 1009; // Use a prime number for hash table size
vector<list<pair<int,int>>> buckets;
public:
MyHashMap() {
buckets.resize(SIZE);
}
void put(int key, int value) {
int idx = key % SIZE;
for (auto& kv : buckets[idx]) {
if (kv.first == key) {
kv.second = value;
return;
}
}
buckets[idx].emplace_back(key, value);
}
int get(int key) {
int idx = key % SIZE;
for (auto& kv : buckets[idx]) {
if (kv.first == key) return kv.second;
}
return -1;
}
void remove(int key) {
int idx = key % SIZE;
for (auto it = buckets[idx].begin(); it != buckets[idx].end(); ++it) {
if (it->first == key) {
buckets[idx].erase(it);
return;
}
}
}
};
class MyHashMap {
private static final int SIZE = 1009; // Prime number for buckets
private LinkedList<int[]>[] buckets;
public MyHashMap() {
buckets = new LinkedList[SIZE];
for (int i = 0; i < SIZE; i++) {
buckets[i] = new LinkedList<>();
}
}
public void put(int key, int value) {
int idx = key % SIZE;
for (int[] pair : buckets[idx]) {
if (pair[0] == key) {
pair[1] = value;
return;
}
}
buckets[idx].add(new int[]{key, value});
}
public int get(int key) {
int idx = key % SIZE;
for (int[] pair : buckets[idx]) {
if (pair[0] == key) return pair[1];
}
return -1;
}
public void remove(int key) {
int idx = key % SIZE;
Iterator<int[]> it = buckets[idx].iterator();
while (it.hasNext()) {
if (it.next()[0] == key) {
it.remove();
return;
}
}
}
}
var MyHashMap = function() {
this.size = 1009; // prime number for bucket size
this.buckets = Array.from({length: this.size}, () => []);
};
MyHashMap.prototype.put = function(key, value) {
const idx = key % this.size;
for (let i = 0; i < this.buckets[idx].length; i++) {
if (this.buckets[idx][i][0] === key) {
this.buckets[idx][i][1] = value;
return;
}
}
this.buckets[idx].push([key, value]);
};
MyHashMap.prototype.get = function(key) {
const idx = key % this.size;
for (const [k, v] of this.buckets[idx]) {
if (k === key) return v;
}
return -1;
};
MyHashMap.prototype.remove = function(key) {
const idx = key % this.size;
for (let i = 0; i < this.buckets[idx].length; i++) {
if (this.buckets[idx][i][0] === key) {
this.buckets[idx].splice(i, 1);
return;
}
}
};