Design HashMap

Design a HashMap without using built-in hash table libraries. Implement put(key, val), get(key), and remove(key).

Example 1

put(1,1), put(2,2), get(1)→1, get(3)→-1, put(2,1), get(2)→1, remove(2), get(2)→-1

Solution Approach

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.

Java

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)