Leetcode - Design HashMap Solution

Designing my own HashMap from scratch sounded intimidating at first. Hash maps are everywhere in programming, so how hard could it be to build one? Turns out, there's a lot more to it than just "use an array and index by key." Hash functions, collisions, and chaining - these concepts really clicked when I had to implement them myself.

The key challenge is handling collisions efficiently. When two keys hash to the same bucket, we need a strategy. I chose chaining because it's simpler to implement and understand, storing a list of key-value pairs in each bucket.

The Problem

I needed to implement a HashMap with these 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

Constraints: keys and values are 0 to 10^6, and at most 10^4 operations.

My First (Naive) Attempt

My initial thought was: "Just use a huge array! 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 worked, but it used way too much memory (1 million slots even if I only store 10 items). I needed a better approach.

Learning About Hash Functions

I realized I needed a hash function to map keys to a smaller array of "buckets". The hash function should:

• Map keys to bucket indices
• Distribute keys evenly across buckets
• Be fast to compute

A simple hash function: key % bucketSize. This distributes keys evenly if the bucket size is a prime number.

Handling Collisions

The tricky part: what if two keys hash to the same bucket? This is called a collision. I learned about two main approaches:

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

I chose chaining because it's simpler to implement and understand.

My Solution

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;
      }
    }
  }
}

How It Works

1. Hash Function: _hash(key) maps any key to a bucket index (0 to 999)
2. Put: Hash the key, check if it exists in that bucket, update or add
3. Get: Hash the key, search the bucket for that key
4. Remove: Hash the key, find and remove from the bucket

Why This Is Better

• Memory: Only uses space for actual key-value pairs (plus some overhead for buckets)
• Time: Average O(1) for all operations, worst case O(n) if all keys hash to one bucket (unlikely with good hash function)
• Scalable: Can adjust bucket size based on expected number of elements

What I Learned

This problem taught me:

• Hash functions are crucial for distributing data evenly
• Collisions are inevitable, so you need a strategy (chaining or open addressing)
• The bucket size affects performance. Too small means many collisions, too large wastes memory.
• Understanding how data structures work internally makes you a better programmer

Key Takeaways

• Hash maps use hash functions to map keys to buckets
• Collision handling is essential (I used chaining)
• Average case is O(1), but worst case can be O(n)
• Choosing the right bucket size is a trade-off between memory and performance

Building this from scratch really helped me understand how hash maps work under the hood. It's one thing to use them, but understanding the internals makes you appreciate the design choices!