medium

Design HashMap

Build a hash map from scratch with put, get and remove, using a fixed set of buckets and a list in each bucket to handle collisions.

1. Define the problem

Design HashMap

Build a hash map from scratch, without using any built in map type. It must support put(key, value), get(key) and remove(key) , where get returns -1 when the key is not stored. The entry function takes two arrays so the result can be checked easily: operations is a list of names such as "put" or "get", and values holds the arguments for each one. It returns a list of results, using null for the calls that answer nothing. Inside, keep a fixed number of buckets . A key is turned into a bucket number by taking the remainder after dividing by the bucket count. Keys that land in the same bucket are simply stored side by side in it and compared one by one, which is called chaining.

Constraints

  • 0 ≤ key, value ≤ 106
  • At most 104 calls are made to put, get and remove
  • get returns -1 when the key is not in the map

Example

Inputoperations = ["put", "put", "get", "get", "put", "get"], values = [[1, 1], [2, 2], [1], [3], [2, 1], [2]]
Output[null, null, 1, -1, null, 1]

Explanation Key 1 is stored with value 1 and key 2 with value 2. get(1) answers 1, get(3) answers -1 because key 3 was never stored, then key 2 is overwritten with 1 and get(2) answers 1.

2. Know the words first

In plain terms

Bucket
One slot of the underlying array. Every key is sent to exactly one bucket, and that bucket holds a small list of the key and value pairs that landed there.
Hash function
The rule that turns a key into a bucket number. Here it is the remainder after dividing the key by the number of buckets, so key 9 with 8 buckets lands in bucket 1.
Collision
Two different keys landing in the same bucket. Nothing is lost: the bucket holds both pairs, and a lookup checks them one after another.
Chaining
The way of handling collisions used here, where each bucket keeps a list of everything that landed in it.
3. Visualize the solution

One cell per bucket of the table, value = the pairs stored there

One cell per bucket of the table, value = the pairs stored there
Statusinit

The table starts as eight empty buckets.

What happens in this step

BUCKET_COUNT = 8
Every bucket starts as an empty list, drawn here as a dash.

No keys are stored yet.
Buckets are numbered b0 to b7.
Step 1 of 7

Steps to visualize

  1. The eight cells below are the eight buckets. A dash means the bucket is empty.
  2. The bucket for a key is the remainder of that key divided by 8.
  3. put stores a key and value pair in its bucket, replacing the value if the key is already there.
  4. Two keys can share a bucket, and then both pairs sit in it.
  5. get walks the pairs in one bucket only, which is why the table stays fast.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per bucket of the table, value = the pairs stored there
Statusinit

The table starts as eight empty buckets.

What happens in this step

BUCKET_COUNT = 8
Every bucket starts as an empty list, drawn here as a dash.

No keys are stored yet.
Buckets are numbered b0 to b7.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function designHashMap(operations, values) {
  const BUCKET_COUNT = 8;

  function MyHashMap() {
    this.buckets = [];

    for (let i = 0; i < BUCKET_COUNT; i++) {
      this.buckets.push([]);
    }
  }

  MyHashMap.prototype.bucketFor = function (key) {
    return this.buckets[key % BUCKET_COUNT];
  };

  MyHashMap.prototype.put = function (key, value) {
    const bucket = this.bucketFor(key);

    for (const pair of bucket) {
      if (pair[0] === key) {
        pair[1] = value;
        return null;
      }
    }

    bucket.push([key, value]);
    return null;
  };

  MyHashMap.prototype.get = function (key) {
    const bucket = this.bucketFor(key);

    for (const pair of bucket) {
      if (pair[0] === key) {
        return pair[1];
      }
    }

    return -1;
  };

  MyHashMap.prototype.remove = function (key) {
    const bucket = this.bucketFor(key);

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        break;
      }
    }

    return null;
  };

  const map = new MyHashMap();
  const results = [];

  for (let i = 0; i < operations.length; i++) {
    const name = operations[i];
    const args = values[i];

    if (name === 'put') {
      results.push(map.put(args[0], args[1]));
    } else if (name === 'get') {
      results.push(map.get(args[0]));
    } else {
      results.push(map.remove(args[0]));
    }
  }

  return results;
}
Time
O(1) on average per call, O(n) in the worst case when every key shares a bucket
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
operations = ["put", "put", "get", "get", "put", "get"], values = [[1, 1], [2, 2], [1], [3], [2, 1], [2]][null, null, 1, -1, null, 1]example from the description
operations = ["put", "put", "get", "get"], values = [[1, 1], [9, 9], [1], [9]][null, null, 1, 9]two keys share a bucket and both stay reachable
operations = [], values = [][]nothing is called at all
operations = ["put", "remove", "get", "remove"], values = [[5, 50], [5], [5], [77]][null, null, -1, null]removing a stored key, then removing a key that was never there
operations = ["put", "put", "get"], values = [[3, 3], [3, 7], [3]][null, null, 7]putting the same key twice replaces the value instead of adding a second pair
operations = ["put", "get", "get"], values = [[1000000, 4], [1000000], [999999]][null, 4, -1]large key values still land in a bucket

Keep reading