← Back to DevBytes
JavaScript August 05, 2026 9 min read

Solving Design a HashMap in JavaScript: Step-by-Step Guide

Introduction to Designing a HashMap in JavaScript

A HashMap (also known as a hash table or dictionary) is one of the most fundamental data structures in computer science. It stores key-value pairs and provides near constant-time complexity for insertions, deletions, and lookups. While JavaScript provides a native Map object and plain objects, building your own HashMap from scratch is a classic interview question that tests your understanding of hashing, collision resolution, and dynamic resizing.

In this tutorial, we will walk through designing a fully functional HashMap in JavaScript, covering the underlying mechanics, collision handling strategies, and best practices for production-quality code.

What Is a HashMap?

A HashMap is a data structure that maps keys to values using a hash function. The hash function converts a given key into an integer index within an underlying array (often called a "bucket array"). This index determines where the value is stored, enabling fast access without scanning every element.

The core operations of a HashMap include:

The Role of the Hash Function

The hash function is the heart of a HashMap. A good hash function distributes keys uniformly across the available buckets, minimizing collisions. For string keys, a common approach is to use a polynomial rolling hash, where each character contributes to the final hash value based on its position.

Why Designing a HashMap Matters

Understanding how a HashMap works internally is crucial for several reasons:

Step 1: Designing the Basic Structure

Let us start by creating a simple HashMap class with an underlying array of fixed size. We will use separate chaining for collision resolution, where each bucket holds a list of entries.

class MyHashMap {
  constructor(initialCapacity = 16) {
    this.capacity = initialCapacity;
    this.size = 0;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
  }

  // Simple hash function for string and number keys
  _hash(key) {
    const keyStr = String(key);
    let hash = 0;
    for (let i = 0; i < keyStr.length; i++) {
      hash = (hash * 31 + keyStr.charCodeAt(i)) % this.capacity;
    }
    return hash;
  }
}

The _hash method converts any key to a string, then computes a hash using a polynomial approach with a prime multiplier (31). The modulo operation ensures the index falls within the bucket array bounds.

Step 2: Implementing the Put Operation

The put method inserts a new key-value pair or updates an existing key. We compute the bucket index, then iterate through the chain to check if the key already exists. If it does, we update the value; otherwise, we append a new entry.

put(key, value) {
  const index = this._hash(key);
  const bucket = this.buckets[index];

  for (let entry of bucket) {
    if (entry[0] === key) {
      entry[1] = value;
      return;
    }
  }

  bucket.push([key, value]);
  this.size++;

  // Trigger resize if load factor exceeds threshold
  if (this.size / this.capacity > 0.75) {
    this._resize();
  }
}

Notice the load factor check at the end. The load factor is the ratio of stored entries to bucket capacity. When it exceeds 0.75, we resize the underlying array to maintain performance.

Step 3: Implementing the Get Operation

The get method retrieves the value for a given key. We hash the key, find the corresponding bucket, and search the chain for a matching key.

get(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];

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

  return -1; // Return -1 if key not found, common in interview problems
}

Returning -1 for missing keys is a common convention in coding interview problems (such as LeetCode 706). In production code, you might return undefined or throw an error instead.

Step 4: Implementing the Remove Operation

The remove method deletes a key-value pair. We locate the bucket, find the entry index, and splice it out of the chain.

remove(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];

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

Step 5: Implementing Helper Methods

Let us add utility methods for checking key existence and retrieving the current size.

contains(key) {
  const index = this._hash(key);
  const bucket = this.buckets[index];

  for (let entry of bucket) {
    if (entry[0] === key) {
      return true;
    }
  }

  return false;
}

getSize() {
  return this.size;
}

isEmpty() {
  return this.size === 0;
}

Step 6: Implementing Dynamic Resizing

Without resizing, a HashMap degrades into linked lists as more entries are added. Resizing doubles the capacity and rehashes all existing entries into new buckets. This keeps the average time complexity at O(1).

_resize() {
  const oldBuckets = this.buckets;
  this.capacity *= 2;
  this.size = 0;
  this.buckets = new Array(this.capacity).fill(null).map(() => []);

  for (let bucket of oldBuckets) {
    for (let entry of bucket) {
      this.put(entry[0], entry[1]);
    }
  }
}

Although resizing is an O(n) operation, it happens infrequently. Amortized over many insertions, the average cost per insertion remains O(1).

Complete HashMap Implementation

Here is the full implementation combining all the pieces:

class MyHashMap {
  constructor(initialCapacity = 16) {
    this.capacity = initialCapacity;
    this.size = 0;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
  }

  _hash(key) {
    const keyStr = String(key);
    let hash = 0;
    for (let i = 0; i < keyStr.length; i++) {
      hash = (hash * 31 + keyStr.charCodeAt(i)) % this.capacity;
    }
    return hash;
  }

  put(key, value) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (let entry of bucket) {
      if (entry[0] === key) {
        entry[1] = value;
        return;
      }
    }

    bucket.push([key, value]);
    this.size++;

    if (this.size / this.capacity > 0.75) {
      this._resize();
    }
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

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

    return -1;
  }

  remove(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

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

  contains(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];

    for (let entry of bucket) {
      if (entry[0] === key) {
        return true;
      }
    }

    return false;
  }

  getSize() {
    return this.size;
  }

  isEmpty() {
    return this.size === 0;
  }

  _resize() {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.size = 0;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);

    for (let bucket of oldBuckets) {
      for (let entry of bucket) {
        this.put(entry[0], entry[1]);
      }
    }
  }
}

Testing the HashMap

Let us verify our implementation with a few test cases:

const map = new MyHashMap();

map.put("apple", 100);
map.put("banana", 200);
map.put("cherry", 300);

console.log(map.get("apple"));   // 100
console.log(map.get("banana"));  // 200
console.log(map.get("grape"));   // -1

map.put("apple", 150);           // Update existing key
console.log(map.get("apple"));   // 150

console.log(map.contains("cherry")); // true
console.log(map.getSize());          // 3

map.remove("banana");
console.log(map.contains("banana")); // false
console.log(map.getSize());          // 2

Collision Resolution Strategies

Collisions occur when two different keys hash to the same index. There are two primary strategies for handling them:

Separate Chaining

This is the approach we used above. Each bucket holds a list (or linked list) of entries. When a collision occurs, the new entry is appended to the chain. This approach is simple and handles high load factors gracefully.

Open Addressing

In open addressing, all entries live directly in the bucket array. When a collision occurs, the HashMap probes for the next available slot using strategies such as linear probing, quadratic probing, or double hashing. Here is a brief example using linear probing:

class LinearProbingHashMap {
  constructor(capacity = 16) {
    this.capacity = capacity;
    this.size = 0;
    this.keys = new Array(capacity).fill(null);
    this.values = new Array(capacity).fill(null);
    this.DELETED = Symbol("deleted");
  }

  _hash(key) {
    let hash = 0;
    const keyStr = String(key);
    for (let i = 0; i < keyStr.length; i++) {
      hash = (hash * 31 + keyStr.charCodeAt(i)) % this.capacity;
    }
    return hash;
  }

  put(key, value) {
    let index = this._hash(key);
    let startIndex = index;

    while (this.keys[index] !== null && this.keys[index] !== this.DELETED) {
      if (this.keys[index] === key) {
        this.values[index] = value;
        return;
      }
      index = (index + 1) % this.capacity;
      if (index === startIndex) {
        throw new Error("HashMap is full");
      }
    }

    this.keys[index] = key;
    this.values[index] = value;
    this.size++;
  }

  get(key) {
    let index = this._hash(key);
    let startIndex = index;

    while (this.keys[index] !== null) {
      if (this.keys[index] === key) {
        return this.values[index];
      }
      index = (index + 1) % this.capacity;
      if (index === startIndex) break;
    }

    return -1;
  }
}

Open addressing can be more cache-friendly since all data lives in a single contiguous array, but it suffers from clustering issues and requires careful handling of deletions using tombstone markers.

Best Practices

Time and Space Complexity Analysis

Understanding the complexity of each operation is essential:

Common Interview Variations

Interviewers often extend the basic HashMap problem with additional constraints:

Conclusion

Designing a HashMap from scratch is an excellent exercise that deepens your understanding of one of the most widely used data structures in software development. By implementing the hash function, collision resolution, and dynamic resizing yourself, you gain insight into the trade-offs that shape real-world performance. Whether you are preparing for a coding interview or simply want to understand how JavaScript's Map works under the hood, mastering HashMap implementation equips you with knowledge that applies across countless programming scenarios. Start with the basic separate chaining approach, experiment with open addressing, and always remember that a well-designed hash function and a sensible load factor threshold are the keys to a performant HashMap.

— Ad —

Google AdSense will appear here after approval

← Back to all articles