Design HashMap

Design a HashMap without using any built-in hash table library. Implement MyHashMap with:

Keys and values are between 0 and 106, and there are at most 104 calls. This is LeetCode 706.

Example 1
Input: put(1, 1), put(2, 2), get(1), get(3), put(2, 1), get(2), remove(2), get(2)
Output: get(1) = 1, get(3) = -1, get(2) = 1, then get(2) = -1 after the removal

How to Think About It

Step 1: The simplest map: one slot per key

Keys go up to 106, so an int[1000001] filled with -1 already works, with O(1) for everything. It wastes memory when only a few keys are used, and it would not work at all for keys with a huge range. A real hash map avoids both.

Step 2: Buckets

Use a smaller array of buckets, and send each key to bucket key % SIZE. That function is the hash. A prime size, like 10007, spreads keys more evenly than a round number.

Step 3: Collisions

Different keys can land in the same bucket (1 and 10008 both go to bucket 1). So each bucket holds a small linked list of (key, value) nodes, and every operation searches only that one list. This is called separate chaining.

Step 4: The three operations

  • put: walk the bucket's list; if the key is there, update its value, otherwise add a node at the head.
  • get: walk the list and return the value, or -1.
  • remove: unlink the node. A dummy node in front of the list means removing the first node needs no special case.

Walkthrough

The example's calls, with SIZE = 10007, so keys 1 and 2 go to buckets 1 and 2.

CallBucketWhat happensReturns
put(1, 1)1not found: add node (1, 1)
put(2, 2)2not found: add node (2, 2)
get(1)1found1
get(3)3empty list-1
put(2, 1)2found: value becomes 1
get(2)2found1
remove(2)2node unlinked
get(2)2empty list-1

Java Solution

Each bucket is a hand-written singly linked list.

Java
class MyHashMap {
    private static final int SIZE = 10007; // a prime spreads keys evenly

    private static class Node {
        final int key;
        int value;
        Node next;

        Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private final Node[] buckets = new Node[SIZE];

    private int index(int key) {
        return key % SIZE;
    }

    public void put(int key, int value) {
        int i = index(key);
        for (Node n = buckets[i]; n != null; n = n.next) {
            if (n.key == key) {
                n.value = value; // key exists: update
                return;
            }
        }
        buckets[i] = new Node(key, value, buckets[i]); // add at the head
    }

    public int get(int key) {
        for (Node n = buckets[index(key)]; n != null; n = n.next) {
            if (n.key == key) {
                return n.value;
            }
        }
        return -1;
    }

    public void remove(int key) {
        int i = index(key);
        Node dummy = new Node(-1, -1, buckets[i]);
        for (Node prev = dummy; prev.next != null; prev = prev.next) {
            if (prev.next.key == key) {
                prev.next = prev.next.next; // unlink
                break;
            }
        }
        buckets[i] = dummy.next;
    }
}

The original implementation, MyHashMap.java, is on GitHub.

Complexity

  • Time: O(1) on average per call, since keys spread over 10007 buckets; O(n) in the worst case when all keys share one bucket.
  • Space: O(SIZE + number of keys).

Java's own HashMap also grows its bucket array as it fills and turns long lists into trees. The set version of this problem is Design HashSet.