Design HashMap

NeetCode: Design HashMap · LeetCode: 706. Design HashMap · Difficulty: Easy

Design a MyHashMap without the built-in HashMap. It supports put(key, value) (insert or overwrite), get(key) (the value, or -1 if absent) and remove(key). Keys and values are integers in 0 to 1000000.

Example

Text

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

Brute force: one list of pairs

Keep a single ArrayList<int[]> where each entry is a two-element array {key, value}, and scan it for every operation. Each operation is linear in the number of entries. remove moves the last entry into the freed slot and drops the last slot, so no later entries shift. The entries are arrays that the list holds by reference, so put can overwrite e[1] in place.

Java

import java.util.ArrayList;
import java.util.List;

class MyHashMap {
    private final List<int[]> items = new ArrayList<>(); // each entry is {key, value}

    public void put(int key, int value) {
        for (int[] e : items) {
            if (e[0] == key) {
                e[1] = value;
                return;
            }
        }
        items.add(new int[]{key, value});
    }

    public int get(int key) {
        for (int[] e : items) {
            if (e[0] == key) {
                return e[1];
            }
        }
        return -1;
    }

    public void remove(int key) {
        for (int i = 0; i < items.size(); i++) {
            if (items.get(i)[0] == key) {
                int[] last = items.remove(items.size() - 1);
                if (i < items.size()) {
                    items.set(i, last); // fill the gap with the last entry
                }
                return;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        MyHashMap m = new MyHashMap();
        m.put(1, 1);
        m.put(2, 2);
        System.out.println(m.get(1));
        System.out.println(m.get(3));
        m.put(2, 1);
        System.out.println(m.get(2));
        m.remove(2);
        System.out.println(m.get(2));
        m.remove(42);
    }
}

Output

1
-1
1
-1

Time: O(n) per operation. Space: O(n).

Optimal: bucketed chaining

Hash each key to one of 769 buckets and keep a short ArrayList<int[]> per bucket. The bucket index is Math.floorMod(key, 769). put scans only that bucket to overwrite or append, get and remove do the same. Operations are expected O(1) while buckets stay short; a production table would resize to keep the load factor bounded.

Java

import java.util.ArrayList;
import java.util.List;

class MyHashMap {
    private static final int BUCKETS = 769;
    private final List<List<int[]>> buckets = new ArrayList<>();

    public MyHashMap() {
        for (int i = 0; i < BUCKETS; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    private List<int[]> bucket(int key) {
        return buckets.get(Math.floorMod(key, BUCKETS));
    }

    public void put(int key, int value) {
        List<int[]> b = bucket(key);
        for (int[] e : b) {
            if (e[0] == key) {
                e[1] = value;
                return;
            }
        }
        b.add(new int[]{key, value});
    }

    public int get(int key) {
        for (int[] e : bucket(key)) {
            if (e[0] == key) {
                return e[1];
            }
        }
        return -1;
    }

    public void remove(int key) {
        List<int[]> b = bucket(key);
        for (int i = 0; i < b.size(); i++) {
            if (b.get(i)[0] == key) {
                int[] last = b.remove(b.size() - 1);
                if (i < b.size()) {
                    b.set(i, last);
                }
                return;
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        MyHashMap m = new MyHashMap();
        m.put(1, 1);
        m.put(2, 2);
        System.out.println(m.get(1));
        System.out.println(m.get(3));
        m.put(2, 1);
        System.out.println(m.get(2));
        m.remove(2);
        System.out.println(m.get(2));
        // 1 and 770 share a bucket but keep separate values
        m.put(770, 7);
        System.out.println(m.get(1) + " " + m.get(770));
        m.remove(1);
        System.out.println(m.get(1) + " " + m.get(770));
    }
}

Output

Time: expected O(1) per operation for a bounded load factor (worst case O(n)). Space: O(BUCKETS + n).