Problem statement

Build a map from integer keys to integer values without using your language's built-in hash table. Write the class MyHashMap:

• MyHashMap() creates an empty map.
• void put(int key, int value) stores the pair (key, value); if key is already present, its value is replaced.
• int get(int key) returns the value stored for key, or -1 if the map holds no entry for it.
• void remove(int key) deletes the entry for key if there is one.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MyHashMap","put","put","get","get","put","get","remove","get"]
[[],[1,10],[2,20],[1],[3],[2,5],[2],[2],[2]]
Output: [null,null,null,10,-1,null,5,null,-1]
Explanation: Key 3 was never stored, so `get(3)` is -1. Putting key 2 again overwrites 20 with 5; after removing key 2, `get(2)` is -1.

Example 2

Input: ["MyHashMap","get","put","put","get","remove","get"]
[[],[7],[7,0],[776,9],[7],[776],[776]]
Output: [null,-1,null,null,0,null,-1]
Explanation: A stored value of 0 is a real value, not "missing". Keys 7 and 776 share a bucket when there are 769 buckets, and removing one leaves the other alone.

Constraints

• 0 <= key, value <= 10^6
• At most 10^4 calls are made to put, get and remove

Hints for Design HashMap

1. Hint 1

   Pick a fixed number of buckets B and send each key to bucket key % B.

2. Hint 2

   Two keys can share a bucket, so a bucket must remember which key each value belongs to: store (key, value) pairs.

3. Hint 3

   put scans its bucket and overwrites the pair with that key if there is one, otherwise appends; get and remove scan the same bucket.

How to solve Design HashMap

Separate chaining with key/value pairs: B buckets, each a short list of (key, value) pairs; a key is only ever stored in bucket key % B.

Approach

1. Create B = 769 empty buckets.
2. put(key, value): in bucket key % B, if a pair has this key set its value; otherwise append (key, value).
3. get(key): return the value of the pair with this key in bucket key % B, or -1.
4. remove(key): delete the pair with this key from bucket key % B, if any.

Why it works

Every operation on a key touches only the bucket its hash selects, and put never creates a second pair for a key already in that bucket, so each key has at most one pair and get finds exactly the value last put.

Complexity

• Time — O(n / B) per operation on average
• Space — O(B + n)

Pitfalls

• Storing only values in the buckets cannot tell colliding keys apart.
• A value of 0 is valid — do not use 0 as the "absent" marker.

Reference solution

Python

class MyHashMap:

    def __init__(self):
        self.size = 769
        self.buckets = [[] for _ in range(self.size)]

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

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

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

Java

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

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

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

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

    public void remove(int key) {
        Iterator<int[]> it = buckets.get(key % SIZE).iterator();
        while (it.hasNext()) if (it.next()[0] == key) { it.remove(); return; }
    }
}

C++

class MyHashMap {
    static const int SIZE = 769;
    vector<list<pair<int, int>>> buckets;
public:
    MyHashMap() : buckets(SIZE) {}

    void put(int key, int value) {
        for (auto& p : buckets[key % SIZE]) if (p.first == key) { p.second = value; return; }
        buckets[key % SIZE].push_back({key, value});
    }

    int get(int key) {
        for (auto& p : buckets[key % SIZE]) if (p.first == key) return p.second;
        return -1;
    }

    void remove(int key) {
        auto& b = buckets[key % SIZE];
        for (auto it = b.begin(); it != b.end(); ++it) if (it->first == key) { b.erase(it); return; }
    }
};

JavaScript

var MyHashMap = function() {
    this.size = 769;
    this.buckets = [];
    for (var i = 0; i < this.size; i++) this.buckets.push([]);
};

MyHashMap.prototype.put = function(key, value) {
    var b = this.buckets[key % this.size];
    for (var i = 0; i < b.length; i++) if (b[i][0] === key) { b[i][1] = value; return; }
    b.push([key, value]);
};

MyHashMap.prototype.get = function(key) {
    var b = this.buckets[key % this.size];
    for (var i = 0; i < b.length; i++) if (b[i][0] === key) return b[i][1];
    return -1;
};

MyHashMap.prototype.remove = function(key) {
    var b = this.buckets[key % this.size];
    for (var i = 0; i < b.length; i++) if (b[i][0] === key) { b.splice(i, 1); return; }
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy
• Convert Sorted Array to Binary Search Tree Easy