Design a HashMap without using built-in hash table libraries. Implement put(key, val), get(key), and remove(key).
put(1,1), put(2,2), get(1)→1, get(3)→-1, put(2,1), get(2)→1, remove(2), get(2)→-1
Use an array of buckets with chaining (LinkedList). Hash function: key % buckets.
- Array of LinkedList buckets.
- put: hash key, find bucket, update if exists else append.
- get: hash key, search bucket.
- remove: hash key, remove from bucket.
import java.util.*;
class MyHashMap {
private static final int SIZE = 1024;
private LinkedList<int[]>[] buckets = new LinkedList[SIZE];
private LinkedList<int[]> getBucket(int key) {
int idx = key % SIZE;
if (buckets[idx] == null) buckets[idx] = new LinkedList<>();
return buckets[idx];
}
public void put(int key, int value) {
LinkedList<int[]> b = getBucket(key);
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 : getBucket(key)) if (p[0] == key) return p[1];
return -1;
}
public void remove(int key) {
LinkedList<int[]> b = getBucket(key);
b.removeIf(p -> p[0] == key);
}
}
- Time Complexity: O(N/K) average per op (K=buckets)
- Space Complexity: O(N)