Design HashMap

Build a map from integer keys to values with an array of buckets and a short linked list in each one.

Build a map from integer keys to integer values without using any of Java's ready-made hash table classes, such as HashMap. Write a class MyHashMap with three methods:

Keys and values are between 0 and 106, and there are at most 104 calls.

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
Solution

The Idea

Behind a hotel reception desk there is often a wall of small pigeonholes, one per room. A letter for room 12 goes straight into slot 12, and nobody searches the whole wall to find it. MyHashMap does the same with numbers: put(1, 1) stores the value 1 under the key 1, and get(1) later goes straight to it.

Walk through Example 1. After put(1, 1) and put(2, 2), get(1) returns 1. Nothing was stored under 3, so get(3) returns -1. A key holds one value at a time, so put(2, 1) replaces the 2 under key 2, and get(2) returns 1. After remove(2), key 2 is gone and get(2) returns -1.

How many pigeonholes does the map need? Keys go up to 106, so one slot per possible key means 1,000,001 slots, while Example 1 uses two keys. Could a much smaller wall do the job?

Say the map has 10007 slots, called buckets, numbered 0 to 10006. A key goes into the bucket given by key % 10007, the remainder after dividing the key by 10007. Key 1 goes to bucket 1 and key 2 to bucket 2. But key 10008 leaves the remainder 1 as well, so it lands in bucket 1 next to key 1. The rule that turns a key into a bucket number, here key % 10007, is called the hash function, and two keys landing in one bucket is called a collision.

After put(1, 1), put(2, 2) and put(10008, 8), bucket 1 holds a list with key 10008 at the head and key 1 behind it, bucket 2 holds key 2, and the other buckets are empty.

The picture shows the map after put(1, 1), put(2, 2) and put(10008, 8). On the left, under "key % 10007 picks the bucket", each key's remainder is worked out. Bucket 1, in orange, holds two small boxes, called nodes: "key 10008, value 8" and, behind it, "key 1, value 1". Each node keeps a key, its value and an arrow to the next node in the same bucket, so the nodes form a linked list. Bucket 2 holds "key 2, value 2", and bucket 0, bucket 3 and bucket 10006 are empty.

So get(1) goes to bucket 1 and reads its two nodes until it meets key 1. It never looks at any other bucket. As long as the keys spread out over the 10007 buckets, each list holds a node or two, and every call stays short.

Solution Approach

The bucket picture leaves four things to settle: why one slot per key falls short, how many buckets to use, how a bucket keeps several keys apart, and how remove unlinks a node.

One slot per key

Why not use that wall of 1,000,001 slots? An int[1000001] filled with -1 does work here, and each call is a single step. But with at most 104 calls, at most 104 keys are ever stored, so almost all of the million slots stay unused. If the keys could be any int, the array would need over four billion slots. Buckets keep the array small whatever the keys are.

How many buckets

Why 10007 and not a round 10000? Keys often follow a pattern. Take the 10000 keys 0, 10, 20 and so on up to 99990. With 10000 buckets, each remainder ends in 0, so the keys pile into 1000 buckets and leave the other 9000 empty. With 10007 buckets, a prime number, the same keys fill 10000 different buckets, one key each. And 10007 is a little more than the 104 calls, so there are more buckets than keys.

Keys that share a bucket

How do keys 1 and 10008 live together in bucket 1? Each bucket holds the head of its linked list, the first node, or null when it is empty. Keeping a list per bucket is called separate chaining. Each method works only on the list in its key's bucket. For put and get, that goes like this:

  • The put method walks the list first. If it meets the key, it replaces that node's value. If not, it adds a new node at the head, as "new key, added at the head" shows for 10008 in the picture.
  • The get method walks the list and returns the value of the node with the key, or -1 when it reaches the end.

The walk in put matters: it is what keeps a key in one node only, so put(2, 1) in Example 1 changes the existing node instead of adding a second one for key 2.

Taking a node out of a list

How does remove take key 1 out of bucket 1? The node "key 10008, value 8" points at the node for key 1. Pointing it past key 1, at whatever comes next, unlinks key 1 from the list. So remove walks the list while keeping hold of the node before the one being checked.

The head has no node before it, though. Removing key 10008 would need its own case that moves the bucket's head instead. A spare node placed in front of the head, called a dummy node, removes that special case: the head now has a node before it too. When the walk is done, the node after the dummy is the bucket's new head.

Java Solution

MyHashMap is built from a constant, a small node class, the bucket array and its methods:

  • SIZE: the number of buckets, 10007.
  • Node: one key, its value, and next, the link to the following node in the same bucket.
  • buckets: the array of 10007 list heads. An empty bucket holds null.
  • index(key): the hash function, key % SIZE. Keys are never negative, so the result is always a bucket from 0 to 10006.
  • put and get: walk the key's list, to update or add a node, or to read a value.
  • remove: unlinks the key's node. It starts from a node named dummy in front of the head, walks with prev one node behind the node being checked, and stores dummy.next back as the head.
  • bucketToString(i): lists bucket i's nodes from head to end, for main only.

The main method runs Example 1, then builds the picture on a second map, named shared. It removes the two keys in bucket 1 one at a time, then adds the largest key, 1000000, and removes key 5, which was never added.

Java
public class MyHashMap {
    private static final int SIZE = 10007;  // a prime number of buckets

    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;                   // keys are never negative
    }

    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 is there: update its value
                return;
            }
        }
        buckets[i] = new Node(key, value, buckets[i]);   // new key: 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]);       // sits in front of the head
        for (Node prev = dummy; prev.next != null; prev = prev.next) {
            if (prev.next.key == key) {
                prev.next = prev.next.next;  // unlink the node
                break;
            }
        }
        buckets[i] = dummy.next;             // the head may have changed
    }

    String bucketToString(int i) {
        StringBuilder sb = new StringBuilder("bucket " + i + ":");
        for (Node n = buckets[i]; n != null; n = n.next) {
            sb.append(" [").append(n.key).append(" = ").append(n.value).append("]");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        MyHashMap map = new MyHashMap();     // Example 1
        map.put(1, 1);
        map.put(2, 2);
        System.out.println("get(1) = " + map.get(1));
        System.out.println("get(3) = " + map.get(3));
        map.put(2, 1);
        System.out.println("get(2) = " + map.get(2));
        map.remove(2);
        System.out.println("get(2) = " + map.get(2) + " after remove(2)");

        MyHashMap shared = new MyHashMap();  // two keys in one bucket
        shared.put(1, 1);
        shared.put(2, 2);
        shared.put(10008, 8);
        System.out.println(shared.bucketToString(1));
        System.out.println(shared.bucketToString(2));
        System.out.println("get(10008) = " + shared.get(10008) + ", get(1) = " + shared.get(1));
        shared.remove(1);
        System.out.println(shared.bucketToString(1));
        shared.remove(10008);
        System.out.println(shared.bucketToString(1));
        System.out.println("get(1) = " + shared.get(1) + ", get(10008) = " + shared.get(10008));

        shared.put(1000000, 7);              // the largest key
        shared.remove(5);                    // a key that was never added
        System.out.println(shared.bucketToString(1000000 % SIZE));
        System.out.println(shared.bucketToString(5));
    }
}

Running it prints:

Output
get(1) = 1
get(3) = -1
get(2) = 1
get(2) = -1 after remove(2)
bucket 1: [10008 = 8] [1 = 1]
bucket 2: [2 = 2]
get(10008) = 8, get(1) = 1
bucket 1: [10008 = 8]
bucket 1:
get(1) = -1, get(10008) = -1
bucket 9307: [1000000 = 7]
bucket 5:

The four answers for Example 1 match its expected output: get(2) gives 1 after put(2, 1) replaced the value, and -1 once remove(2) took the key out. Look at the line bucket 1: [10008 = 8] [1 = 1]: it is bucket 1 from the picture, with 10008 at the head. The next line shows both keys still found, get(10008) = 8, get(1) = 1, even though they share a bucket.

Then remove(1) unlinks the second node and leaves [10008 = 8]. Next, remove(10008) unlinks the head through the dummy node, and bucket 1 prints empty. The line after it confirms that neither key is found any more. The largest key, 1000000, lands in bucket 9307, because 1000000 is 99 × 10007 + 9307. Bucket 5 stays empty: removing a key that was never added changes nothing.

What if put skipped its walk and always added a new node at the head? A version written that way still prints 1, -1 and 1 for the first three get calls of Example 1, because get stops at the newest node for key 2. But remove(2) unlinks only that newest node, the old node behind it shows up again, and its last line reads get(2) = 2 after remove(2) instead of -1.

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

Complexity

Every call works on one bucket, so its cost is the length of that bucket's list.

  • Time: O(1) on average per call, because at most 104 keys spread over 10007 buckets leave a node or two in each list. In the worst case it is O(n) for n stored keys, when they all share one bucket, like 1, 10008, 20015 and so on, and a call walks every node.
  • Space: O(10007 + n), because the bucket array keeps its 10007 slots even when they are empty, and each of the n stored keys adds one Node with a key, a value and a next link.

Java's own HashMap goes further than this fixed table: it grows its bucket array as it fills, and turns a bucket's list into a tree once the list gets long. The set version of this problem is Design HashSet.