Leetcode - Design HashMap Solution

Designing my own HashMap from scratch sounded intimidating at first. An array lookup alone is not enough: keys need to map to buckets, and multiple keys can land in the same bucket. I chose chaining because it stores colliding key value pairs together and keeps the operations easy to follow.

Operations and constraints

The implementation supports three operations:

• put(key, value): Insert or update a key value pair
• get(key): Return the value for a key, or -1 if not found
• remove(key): Remove a key value pair

The keys and values range from 0 to 10^6, with at most 10^4 operations.

My first idea was direct indexing. If the key is 5, store the value at index 5:

class MyHashMapNaive {
  constructor() {
    this.data = new Array(1000001).fill(-1);
  }

  put(key, value) {
    this.data[key] = value;
  }

  get(key) {
    return this.data[key];
  }

  remove(key) {
    this.data[key] = -1;
  }
}

This works for the constraints, but it allocates one million slots even when only a few keys are present.

Buckets and collisions

I instead map each key to a smaller array of buckets. A hash function should produce a valid bucket index, spread keys across buckets, and be cheap to compute. A simple choice is key % bucketSize. The choice of bucket size affects how keys map to buckets.

Two keys can produce the same index. That collision needs an explicit policy:

1. Chaining: Store a list of key value pairs in each bucket
2. Open Addressing: Find the next available slot

I chose chaining. Each bucket is an array of pairs that contain a key and its value. A collision requires a search within that bucket.

Chained implementation

class MyHashMap {
  constructor() {
    this.size = 1000; // Number of buckets
    // Each bucket is an array for chaining
    this.buckets = new Array(this.size).fill(null).map(() => []);
  }

  // Hash function: maps key to bucket index
  _hash(key) {
    return key % this.size;
  }

  // Insert or update a key-value pair
  put(key, value) {
    const hashKey = this._hash(key);
    const bucket = this.buckets[hashKey];

    // Check if key already exists in this bucket
    for (let i = 0; i < bucket.length; i++) {
      const [k, v] = bucket[i];
      if (k === key) {
        // Update existing key
        bucket[i] = [key, value];
        return;
      }
    }

    // Key doesn't exist, add new pair
    bucket.push([key, value]);
  }

  // Get value for a key
  get(key) {
    const hashKey = this._hash(key);
    const bucket = this.buckets[hashKey];

    // Search through the bucket
    for (let [k, v] of bucket) {
      if (k === key) {
        return v;
      }
    }

    // Key not found
    return -1;
  }

  // Remove a key-value pair
  remove(key) {
    const hashKey = this._hash(key);
    const bucket = this.buckets[hashKey];

    // Find and remove the key
    for (let i = 0; i < bucket.length; i++) {
      const [k, v] = bucket[i];
      if (k === key) {
        bucket.splice(i, 1);
        return;
      }
    }
  }
}

Operation flow and tradeoffs

The _hash(key) method maps a key to an index from 0 to 999. put(key, value) searches that bucket and updates an existing pair or appends a new one. get(key) searches the same bucket and returns the stored value or -1. remove(key) removes the matching pair when it exists.

With n stored pairs and m buckets, put, get, and remove average O(1 + n/m) time if keys distribute evenly. This code fixes m at 1,000 and does not resize. Thus, the average bucket length grows with n. A bucket search takes O(n) if all keys select one bucket. Total storage is O(n + m).

Implementing the structure made the role of the hash function and collision policy concrete. Collisions are unavoidable, and the bucket size affects both lookup work and memory use.

The hash function selects a bucket. Chaining stores pairs with the same bucket index, and the bucket count affects the average search cost.