Design HashMap

EASY✓ CHIP-TIMEDLC #706 — FULL STATEMENT ↗

The drill: Build a key-value map from scratch over a bounded range of non-negative integer keys — put, get, and remove — without a language's built-in hash map.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A key-value map needs building from scratch over non-negative integer keys — put a value under a key, get the value stored there, and remove a key — without reaching for a language's built-in hash map.

Putting a value under a key that's already in use simply overwrites whatever was there before; getting a key that was never put, or has since been removed, reports a defined 'not found' signal instead of a real value.

This site drives the drill as a sequence of operations against one live instance, each acting only on the map's current contents at the moment it's called.

EX 01

MyHashMap()

put(1, 1)

put(2, 2)

get(1) → 1

get(3) → -1

put(2, 1)

get(2) → 1

remove(2)

get(2) → -1

PUT, OVERWRITE, GET MISSING KEY, REMOVE

EX 02

MyHashMap()

get(5) → -1

GET ON AN EMPTY MAP

EX 03

MyHashMap()

put(10, 100)

get(10) → 100

put(10, 200)

get(10) → 200

put(10, 300)

get(10) → 300

REPEATED PUTS TO THE SAME KEY OVERWRITE THE VALUE

keys are non-negative integers within a bounded, modest range
put on an existing key overwrites its value
get on a missing key returns a defined not-found signal, commonly −1
no built-in hash map type may back the implementation

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A list of [key, value] pairs gets you correctness immediately, but every get or remove means scanning for the key. What would make finding a key stop depending on how many you've stored?

HINT 2 THE STRUCTURE

Keys live in a bounded range, so hashing them into a fixed number of buckets turns 'which bucket holds this key' into one division. Each bucket only ever holds the keys that collide.

HINT 3 ONE STEP FROM THE ANSWER

Store each bucket as a short list of [key, value] pairs. put replaces an existing pair or appends a new one; get and remove scan only that one bucket instead of the whole map.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE BUCKET LEDGERPATTERN · BUCKETED HASH TABLE — OPSput 1:1, put 2:2, get 1, get 3, put 2:1, get 2, remove 2, get 2

put 1,1

put 2,2

get 1

get 3

put 2,1

get 2

remove 2

get 2

MAP — KEY → VALUE

map → {}

STEP 1

Ops run against one live map, each key hashed into a bucket of [key, value] pairs.

STEP 1 / 12 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/design-hashmap.py — RACE PACE

LANG ▸

PACE ▸

class MyHashMap:
    def __init__(self):
        self.buckets = 1000
        self.table = [[] for _ in range(self.buckets)]

    def put(self, key: int, value: int) -> None:
        bucket = self.table[key % self.buckets]
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])

    def get(self, key: int) -> int:
        bucket = self.table[key % self.buckets]
        for k, v in bucket:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        bucket = self.table[key % self.buckets]
        for i, pair in enumerate(bucket):
            if pair[0] == key:
                del bucket[i]
                return

TIME O(1) AVERAGE PER OPSPACE O(N + BUCKETS)PYTHON · RACE PACE · 26 LN

class MyHashMap:
    def __init__(self):
        self.pairs = []  # list of [key, value]

    def put(self, key: int, value: int) -> None:
        for pair in self.pairs:
            if pair[0] == key:
                pair[1] = value
                return
        self.pairs.append([key, value])

    def get(self, key: int) -> int:
        for k, v in self.pairs:
            if k == key:
                return v
        return -1

    def remove(self, key: int) -> None:
        for i, pair in enumerate(self.pairs):
            if pair[0] == key:
                del self.pairs[i]
                return

TIME O(N) PER OPSPACE O(N)PYTHON · TRAINING PACE · 22 LN

class MyHashMap {
    private final List<int[]>[] table;
    private final int buckets = 1000;

    public MyHashMap() {
        table = new List[buckets];
        for (int i = 0; i < buckets; i++) {
            table[i] = new ArrayList<>();
        }
    }

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

    public int get(int key) {
        List<int[]> bucket = table[key % buckets];
        for (int[] pair : bucket) {
            if (pair[0] == key) {
                return pair[1];
            }
        }
        return -1;
    }

    public void remove(int key) {
        List<int[]> bucket = table[key % buckets];
        for (int i = 0; i < bucket.size(); i++) {
            if (bucket.get(i)[0] == key) {
                bucket.remove(i);
                return;
            }
        }
    }
}

TIME O(1) AVERAGE PER OPSPACE O(N + BUCKETS)JAVA · RACE PACE · 42 LN

class MyHashMap {
    private final List<int[]> pairs = new ArrayList<>();

    public MyHashMap() {
    }

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

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

    public void remove(int key) {
        for (int i = 0; i < pairs.size(); i++) {
            if (pairs.get(i)[0] == key) {
                pairs.remove(i);
                return;
            }
        }
    }
}

TIME O(N) PER OPSPACE O(N)JAVA · TRAINING PACE · 34 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED