Design HashMap

Easy Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Design HashMap is a easy design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (separate chaining), runs in O(1) average per operation time and O(B + n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (one list of pairs) up.

Problem

Build your own key-value map, MyHashMap, for integer keys and values without using any built-in hash table.

put(key, value) stores the pair, replacing the old value if key is already present. get(key) returns the value stored for key, or -1 if there is none. remove(key) deletes key and its value if it is present, and does nothing otherwise.

Examples

Example 1

Input
put(7, 70), put(12, 5), get(7), get(3), put(7, 11), get(7), remove(12), get(12)
Output
70, -1, 11, -1
Why
Key 3 was never stored, putting 7 again overwrites 70 with 11, and 12 is gone after remove.

Example 2

Input
put(0, 0), get(0), remove(0), remove(0), get(0)
Output
0, -1
Why
A value of 0 is a real value, not "missing". Removing an absent key does nothing.

Constraints

  • 0 <= key, value <= 10^6
  • At most 10^4 calls in total to put, get and remove.
  • Do not use a built-in hash table library.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (one list of pairs)O(n) per operationO(n)
Optimal (separate chaining)O(1) average per operationO(B + n)

1Brute force (one list of pairs)

TimeO(n) per operationEvery operation may look at all n stored pairs.
SpaceO(n)One pair per stored key.

Keep every stored (key, value) pair in a single list. Each operation scans the list for the key.

  1. put: scan for the key; overwrite its value if found, otherwise append a new pair.
  2. get: scan for the key and return its value, or -1.
  3. remove: scan for the key and delete that pair if found.
class MyHashMap {
    private final List<int[]> pairs = new ArrayList<>();

    public MyHashMap() {}

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

    public int get(int key) {
        for (int[] p : pairs) if (p[0] == key) return p[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; }
        }
    }
}

2Optimal (separate chaining)

TimeO(1) average per operationEach bucket holds about n / B pairs; with B larger than the number of keys that is O(1) on average.
SpaceO(B + n)B bucket lists plus one pair per stored key.

Use a fixed array of B buckets (a prime such as 10007 spreads keys well). Key k always lives in bucket k % B, which holds a short list of (key, value) pairs. With n keys spread over B buckets, each bucket holds about n / B pairs, so every operation only scans a handful of entries.

  1. Create B empty buckets.
  2. put: find bucket key % B; overwrite the pair with this key, or append a new pair.
  3. get: scan only bucket key % B; return the value or -1.
  4. remove: scan only bucket key % B and delete the matching pair.
class MyHashMap {
    private static final int B = 10007;
    private final List<List<int[]>> buckets = new ArrayList<>();

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

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

    public int get(int key) {
        for (int[] p : buckets.get(key % B)) if (p[0] == key) return p[1];
        return -1;
    }

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

Edge cases to test

  • Overwriting the value of a key that already exists
  • Removing a key that is not present
  • Storing the value 0, which must not be confused with "absent"
  • Several keys that land in the same bucket (for example keys that differ by the bucket count)
  • Re-inserting a key after removing it

Hints

Hint 1

The simplest correct map is a list of (key, value) pairs that you scan. What does each operation cost?

Hint 2

Split the pairs into many small lists (buckets) and choose the bucket from the key, e.g. key % B. Only that bucket needs to be scanned.

FAQ

What is the best time complexity for Design HashMap?

Optimal (separate chaining) runs in O(1) average per operation time and O(B + n) extra space. Each bucket holds about n / B pairs; with B larger than the number of keys that is O(1) on average.

Which pattern does Design HashMap use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Design HashMap?

Yes. Brute force (one list of pairs) takes O(n) per operation time and O(n) space. Keep every stored (key, value) pair in a single list.

Which edge cases should I test for Design HashMap?

Overwriting the value of a key that already exists; Removing a key that is not present; Storing the value 0, which must not be confused with "absent"; Several keys that land in the same bucket (for example keys that differ by the bucket count); Re-inserting a key after removing it.