Command Palette

Search for a command to run...

Hectal
Problem 40.9 · Designing Data StructuresEasy

Design HashMap

PatternCombine Structures to DesignHash Map Lookup (Complement)

What it teaches: A hash map is a hash set whose bucket entries carry a value: update in place when the key is already there.

Practise it on judges as “Design HashMap”.

In plain words

Same cloakroom as before, but now each hook holds a ticket and a coat. put hangs a coat for a ticket (replacing the old coat if that ticket is already there), get hands back the coat, and remove takes it off the hook.

Build a map from whole-number keys to whole-number values with put, get (return −1 if missing) and remove, without Java's HashMap.

The problem

Design MyHashMap with put(key, value), get(key) (−1 if absent) and remove(key) for keys and values 0..10⁶.

Example 1

Input: put(1,1), put(2,2), get(1), get(3), put(2,1), get(2), remove(2), get(2)
Output: 1, -1, 1, -1

Constraints

  • 0 ≤ key, value ≤ 10⁶
  • Up to 10⁴ calls

Pattern clues in the wording

  • → Implement a key → value table yourself

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

MyHashMap · starter
import java.util.*;

class MyHashMap {
    public MyHashMap() {}
    public void put(int key, int value) {}
    public int get(int key) { return -1; }
    public void remove(int key) {}
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
ops = ["MyHashMap","put","put","get","get","put","get","remove","get"]
args = [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]
[null,null,null,1,-1,null,1,null,-1]

From slow to fast

Approaches

1. Buckets of key-value pairs · O(1) average per call
1

Buckets of key-value pairs

Time O(1) average per call Space O(n + buckets)

Each bucket is a list of int[]{key, value}. put/get/remove search one bucket.

▶ Dry run: 1009 buckets, key % 1009 picks oneput(1,1), put(2,2), get(1), get(3), put(2,1), get(2), remove(2), get(2)

buckets (non-empty)(map)

1: [(1, 1)]2: [(2, 2)]

returned(list)

empty

Step 1/4put(1,1): 1 % 1009 = bucket 1, no key 1 there, so append (1, 1). put(2,2) goes to bucket 2.

Approach 1
import java.util.*;

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

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

    private List<int[]> bucket(int key) { return table.get(key % BUCKETS); }

    public void put(int key, int value) {
        for (int[] e : bucket(key)) if (e[0] == key) { e[1] = value; return; }
        bucket(key).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) {
        bucket(key).removeIf(e -> e[0] == key);
    }
}

Verdict: Java's HashMap does the same, switching long buckets to small balanced trees.

Before you submit

Edge cases and common mistakes

Test these inputs

  • put on an existing key (update, don't duplicate)
  • get after remove

Mistakes people make

  • Appending a second pair for an existing key.

Interview

Follow-up questions

Why do many hash tables use a prime number of buckets?