Build a Hash Map in JavaScript

Build a hash map from scratch in JavaScript with collision handling.

Introduction

30 Second Summary

Every time you look up a contact by name on your phone, search for a product on a website, or access a value in a JavaScript object, a hash map is doing the heavy lifting behind the scenes. It is the data structure that makes instant lookups possible.

In this project, you will build a hash map from scratch in JavaScript. You will write the hashing algorithm, handle collisions, implement automatic resizing, and prove it all works with a test suite.

What You'll Build

A fully functional hash map data structure with set, get, delete, has, and keys operations, complete with collision handling and dynamic resizing.

By the end of this project, you'll have:

  • A HashMap class with set, get, delete, has, keys, and size methods that you built from scratch.
  • A hash function that converts string keys into array indices, plus collision handling via separate chaining.
  • Automatic resizing that doubles capacity when the load factor exceeds 0.75, maintaining O(1) average-case performance.
  • A test suite using Node.js's built-in test runner that proves everything works, pushed to GitHub.
  • Secret Mission: Add a forEach method, an entries iterator, and benchmark your implementation against JavaScript's built-in Map.

Are there any prerequisites?

You should be comfortable with basic JavaScript concepts like variables, functions, arrays, loops, and classes. No prior data structures knowledge is needed.

Set Up the Project and GitHub Repository

Before you write any code, you need a clean project folder, version control, and a remote repository to back up your work.

In this step, you'll create the project structure, initialize Git, connect to GitHub, and confirm the Node.js test runner is ready to go.

In this step, get ready to:
  • Create the project directory and file structure.
  • Initialize a Git repository and push it to GitHub.
  • Verify the Node.js test runner works.
Create the project directory and files

Every project starts with a folder and some empty files. You'll create a dedicated folder on your Desktop so it's easy to find.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder, initialize Git, and create the project files by running these commands:
mkdir hashmap
cd hashmap
git init -b main
touch hashmap.js hashmap.test.js

What do these commands do?

  • mkdir hashmap creates a new folder called hashmap.
  • cd hashmap moves your terminal inside that folder.
  • git init -b main turns the folder into a Git repository with a default branch called main.
  • touch hashmap.js hashmap.test.js creates two empty files. One for your implementation, one for tests.
  • Confirm the files exist by running:
ls

You should see hashmap.js and hashmap.test.js in the output.

Don't see your files?

  • Make sure you ran all four commands in order. If you skipped the cd command, you might still be on your Desktop instead of inside the hashmap folder.
  • Run pwd to check your current location. It should end with /hashmap.

Help me figure out why my files aren't showing up after running ls.

  • In VS Code, click File in the top menu bar.
  • Click Open Folder.
  • Navigate to your Desktop and select the hashmap folder, then click Open.

You should see hashmap.js and hashmap.test.js listed in the Explorer sidebar on the left.

Create a GitHub repository and connect it

Now you need a remote repository on GitHub to store your code online. You'll create it through the GitHub website, then connect it to your local folder.

  • Go to github.com and sign in.
  • In the upper-right corner, select +, then click New repository.
  • Enter hashmap as the repository name.
  • Leave the visibility as Public.
  • Do not check any boxes for README, .gitignore, or license.
  • Click Create repository.

GitHub shows a setup page with commands. You'll use those commands in a moment.

  • Back in your terminal, stage and commit the empty files by running these commands:
git add .
git commit -m "Initial commit"

What do these commands do?

  • git add . stages all files in the folder, marking them as ready to be saved.
  • git commit -m "Initial commit" saves a snapshot of the staged files with a message describing the change.
  • Connect your local repository to GitHub and push your commit by running these commands:
git remote add origin [[REPO_URL="https://github.com/your-username/hashmap.git"]]
git push --set-upstream origin main

Where do I find my repository URL?

On the GitHub setup page that appeared after you created the repository, look for the HTTPS URL at the top. It follows the pattern https://github.com/your-username/hashmap.git.

  • Refresh your GitHub repository page in the browser.

You should see hashmap.js and hashmap.test.js listed in the repository along with your "Initial commit" message.

Push failed or asked for credentials?

  • If Git asks for a username and password, GitHub no longer accepts passwords for HTTPS. You need a Personal Access Token. Go to GitHub Settings > Developer settings > Personal access tokens > Tokens (classic), generate one with repo scope, and use it as your password.
  • If you see "remote origin already exists," you may have run the command twice. Run git remote -v to check the current remote URL.

Help me fix my git push to GitHub.

Verify the test runner works

Node.js has a built-in test runner that can find and execute test files automatically. You'll use it throughout this project to verify your hash map works correctly.

  • Run the test runner to confirm it works:
node --test

What should I see?

Since your test file is empty, the runner completes with zero tests. You should see output indicating no tests ran and no failures. The important thing is that it finishes without errors.

Seeing an error about node not found?

  • Run node --version to confirm Node.js is installed. You should see v22.14.0 or a similar version number.
  • If the command is not found, you may need to restart your terminal for the Node.js installation to take effect.

Help me get node --test working.

Your project skeleton is ready. Next up, you'll write the hash function that converts string keys into array indices.

Build the Hash Function

Your project is set up and connected to GitHub. Now it's time to build the core engine of your hash map: the hash function.

A hash function takes a key (like a string) and converts it into a numeric array index. The challenge is making this conversion consistent and well-distributed across the available slots.

In this step, get ready to:
  • Build the HashMap class with an internal storage array and size counter.
  • Write a hash function that converts string keys into array indices.
  • Test the hash function for determinism and bounds safety.
Create the HashMap class and hash function

Every hash map needs two things: an array to store data in, and a function to decide which slot each key belongs to. You'll build both inside a single class.

  • Open hashmap.js in VS Code and add the full HashMap class by pasting this code:
class HashMap {
  // Set up the internal storage with a fixed number of buckets
  constructor(initialCapacity = 16) {
    this._capacity = initialCapacity;
    // Create an array of empty arrays (buckets) for storing key-value pairs
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    this._size = 0;
  }

  // Expose size as a read-only property
  get size() {
    return this._size;
  }

  // Expose capacity as a read-only property
  get capacity() {
    return this._capacity;
  }

  // Convert a string key into a numeric index within bounds
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      // Multiply by prime 31 and add character code, then wrap with modulo
      hash = (hash * 31 + key.charCodeAt(i)) % this._capacity;
    }
    return hash;
  }
}

// Export the class so the test file can import it
module.exports = { HashMap };

What does this code do?

The constructor creates an array of 16 empty arrays (called buckets). Each bucket will eventually hold key-value pairs. The _size counter tracks how many entries are stored.

The _hash(key) method loops through each character in the key string. For each character, it multiplies the running total by 31 (a prime number that helps spread values evenly) and adds the character's numeric code. The modulo operator (%) ensures the result always stays within the array bounds.

  • Save hashmap.js.

Seeing a syntax error?

Make sure you have matching curly braces for both the class body and each method. The class has one opening { after class HashMap and one closing } at the very end before module.exports.

help me fix a syntax error in my HashMap class

✔️ Awesome, I've got everything!

Great. Make sure you've saved hashmap.js before moving on.

ⓧ I'd like to double check the full code

class HashMap {
  constructor(initialCapacity = 16) {
    this._capacity = initialCapacity;
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    this._size = 0;
  }

  get size() {
    return this._size;
  }

  get capacity() {
    return this._capacity;
  }

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

module.exports = { HashMap };
Write tests for the hash function

A hash function must guarantee two properties: it always returns the same index for the same key (deterministic), and it never returns an index outside the array (within bounds). You'll write tests that verify both.

  • Open hashmap.test.js and paste the following test code:
const { describe, it } = require('node:test');
const assert = require('node:assert/strict');
const { HashMap } = require('./hashmap.js');

describe('HashMap', () => {
  describe('hash function', () => {
    // Verify the same input always produces the same output
    it('is deterministic - same key always produces same index', () => {
      const map = new HashMap();
      const index1 = map._hash('hello');
      const index2 = map._hash('hello');
      assert.strictEqual(index1, index2);
    });

    // Verify the hash never produces an index outside the array
    it('produces index within bounds', () => {
      const map = new HashMap(16);
      const keys = ['apple', 'banana', 'cherry', 'date', 'elderberry'];
      for (const key of keys) {
        const index = map._hash(key);
        assert.ok(index >= 0 && index < 16, `Index ${index} out of bounds for key "${key}"`);
      }
    });
  });
});

What does this code do?

The first test calls _hash('hello') twice and checks that both calls return the exact same number. If the hash function used randomness, this would fail.

The second test hashes five different keys and asserts that every result is between 0 and 15 (the valid index range for a capacity of 16). This guarantees you'll never try to access an array slot that doesn't exist.

  • Save hashmap.test.js.

Seeing a module not found error?

Check that require('./hashmap.js') matches the exact filename you saved. Both files must be in the same folder.

help me fix a module not found error in my test file

✔️ Awesome, I've got everything!

Great. Make sure you've saved hashmap.test.js before moving on.

ⓧ I'd like to double check the full code

const { describe, it } = require('node:test');
const assert = require('node:assert/strict');
const { HashMap } = require('./hashmap.js');

describe('HashMap', () => {
  describe('hash function', () => {
    it('is deterministic - same key always produces same index', () => {
      const map = new HashMap();
      const index1 = map._hash('hello');
      const index2 = map._hash('hello');
      assert.strictEqual(index1, index2);
    });

    it('produces index within bounds', () => {
      const map = new HashMap(16);
      const keys = ['apple', 'banana', 'cherry', 'date', 'elderberry'];
      for (const key of keys) {
        const index = map._hash(key);
        assert.ok(index >= 0 && index < 16, `Index ${index} out of bounds for key "${key}"`);
      }
    });
  });
});
Run the tests and confirm they pass
  • Run the test suite by entering this command in your terminal:
node --test

You should see output indicating both tests passed, with green checkmarks next to each test name. The output will show your two tests nested under the HashMap and hash function describe blocks.

Tests failing or not running?

If you see zero tests found, confirm your file is named hashmap.test.js (the .test.js suffix is what Node.js looks for automatically).

If a test fails with an assertion error, double-check that module.exports = { HashMap } is at the bottom of hashmap.js. Without this line, the test file can't import your class.

help me debug why my hash function tests are failing

Your hash function is working and proven by tests. Next up, you'll build the set and get methods that actually store and retrieve data, including handling what happens when two keys land in the same bucket.

Implement Set, Get, and Collision Handling

Your hash function can turn any string key into an array index. Now you need the two core operations that make a hash map useful: storing a value at a key, and retrieving it later.

The tricky part is collisions. Two different keys can hash to the same index. Your hash map needs a strategy for handling this without losing data. You'll use separate chaining, where each bucket holds an array of key-value pairs instead of a single value.

In this step, get ready to:
  • Implement a set method that stores key-value pairs using separate chaining.
  • Implement a get method that retrieves values by key.
  • Write tests proving both methods handle collisions correctly.
Implement the set method with separate chaining

Each slot in your storage array is a bucket. A bucket is an array that can hold multiple [key, value] pairs. When two keys hash to the same index, their pairs simply coexist in the same bucket.

  • In hashmap.js, find the closing brace of the _hash(key) method.
  • Add the following set method below it:
  set(key, value) {
    // Hash the key to find which bucket it belongs in
    const index = this._hash(key);
    const bucket = this._storage[index];

    // Check if the key already exists in this bucket
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        // Update the existing value instead of adding a duplicate
        bucket[i][1] = value;
        return;
      }
    }

    // Key not found in the bucket, add a new pair
    bucket.push([key, value]);
    this._size++;
  }

What does this code do?

The set method follows three steps:

  • It hashes the key to get a bucket index, then grabs that bucket from storage.
  • It loops through the bucket looking for an existing entry with the same key. If found, it updates the value in place and returns early.
  • If no match is found, it pushes a new [key, value] pair onto the bucket and increments the size counter.

You won't see a change yet. The next method (get) uses this to retrieve stored values.

Implement the get method
  • Below the set method you just added, add the get method:
  get(key) {
    // Hash the key to find which bucket to search
    const index = this._hash(key);
    const bucket = this._storage[index];

    // Search the bucket for a matching key
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        return bucket[i][1];
      }
    }

    // Key not found anywhere in the bucket
    return undefined;
  }

What does this code do?

  • It hashes the key to find the correct bucket, then loops through that bucket's pairs looking for a key match.
  • If it finds a match, it returns the value (the second element of the pair).
  • If the loop finishes without finding a match, it returns undefined.
  • Save hashmap.js.

You won't see a change yet. The tests in the next chunk will prove both methods work correctly.

Seeing a syntax error when you save?

  • Make sure both methods are inside the class body (between the opening class HashMap { and the final closing }).
  • Check that the module.exports = { HashMap }; line is still at the bottom, outside the class.
  • Confirm each method has matching opening and closing braces.

My set and get methods aren't working. Can you check my hashmap.js for syntax issues?

✔️ Awesome, I've got everything!

Great. Double check you've saved your file before moving on to the tests.

ⓧ I'd like to double check the full code

class HashMap {
  constructor(initialCapacity = 16) {
    this._capacity = initialCapacity;
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    this._size = 0;
  }

  get size() {
    return this._size;
  }

  get capacity() {
    return this._capacity;
  }

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

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

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

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

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

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

    return undefined;
  }
}

module.exports = { HashMap };
Write tests for set, get, and collisions

Your set and get methods need to handle four scenarios: basic storage, updating an existing key, missing keys, and collisions. Each scenario gets its own test.

  • In hashmap.test.js, find the closing }); of the describe('hash function') block.
  • Add the following test suite below it, still inside the outer describe('HashMap') block:
  describe('set and get', () => {
    it('sets and gets a value', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.get('name'), 'Alice');
    });

    it('updates an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      map.set('name', 'Bob');
      assert.strictEqual(map.get('name'), 'Bob');
      // Size should still be 1 since we updated, not added
      assert.strictEqual(map.size, 1);
    });

    it('returns undefined for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.get('ghost'), undefined);
    });

    it('handles collisions correctly', () => {
      // Capacity of 2 forces collisions with 3 keys
      const map = new HashMap(2);
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      assert.strictEqual(map.get('a'), 1);
      assert.strictEqual(map.get('b'), 2);
      assert.strictEqual(map.get('c'), 3);
    });
  });

What do these tests cover?

  • The first test confirms basic round-trip storage: set a value, get it back.
  • The second test proves that setting the same key twice updates the value without increasing size. This validates the "update in place" logic in your for loop.
  • The third test checks that requesting a key that was never stored returns undefined instead of crashing.
  • The fourth test forces collisions by using a capacity of 2. Three keys cannot fit into 2 buckets without sharing, so at least one bucket must hold multiple pairs. If separate chaining works, all three values are still retrievable.
  • Save hashmap.test.js.
  • Run the test suite by running this command:
node --test
  • You should see all 6 tests passing (2 hash function tests + 4 set/get tests).

Tests failing?

  • If the collision test fails, make sure your set method pushes new pairs with bucket.push([key, value]) instead of overwriting the bucket.
  • If the update test fails, check that your for loop compares bucket[i][0] === key (the first element of each pair is the key).
  • If you see a TypeError, make sure the new describe('set and get') block is inside the outer describe('HashMap') block, not after it.

Help me debug my failing hash map tests.

✔️ Awesome, I've got everything!

Great. Double check you've saved your test file before continuing.

ⓧ I'd like to double check the full code

const { describe, it } = require('node:test');
const assert = require('node:assert/strict');
const { HashMap } = require('./hashmap.js');

describe('HashMap', () => {
  describe('hash function', () => {
    it('is deterministic - same key always produces same index', () => {
      const map = new HashMap();
      const index1 = map._hash('hello');
      const index2 = map._hash('hello');
      assert.strictEqual(index1, index2);
    });

    it('produces index within bounds', () => {
      const map = new HashMap(16);
      const keys = ['apple', 'banana', 'cherry', 'date', 'elderberry'];
      for (const key of keys) {
        const index = map._hash(key);
        assert.ok(index >= 0 && index < 16, `Index ${index} out of bounds for key "${key}"`);
      }
    });
  });

  describe('set and get', () => {
    it('sets and gets a value', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.get('name'), 'Alice');
    });

    it('updates an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      map.set('name', 'Bob');
      assert.strictEqual(map.get('name'), 'Bob');
      assert.strictEqual(map.size, 1);
    });

    it('returns undefined for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.get('ghost'), undefined);
    });

    it('handles collisions correctly', () => {
      const map = new HashMap(2);
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      assert.strictEqual(map.get('a'), 1);
      assert.strictEqual(map.get('b'), 2);
      assert.strictEqual(map.get('c'), 3);
    });
  });
});

Why does a capacity of 2 prove collisions work?

With only 2 buckets, any hash modulo 2 produces either 0 or 1. Three keys cannot all land in different buckets. At least two keys must share a bucket, forcing your separate chaining logic to handle multiple pairs in the same array.

Your hash map can now store and retrieve data, even when keys collide. Next up, you'll add the remaining operations that make it a complete data structure: delete, has, and keys.

Add Delete, Has, Keys, and Size

Your hash map can store and retrieve values. That's a solid start, but a real key-value store needs more operations.

In this step, you'll add delete, has, and keys methods to give users full control over the data stored in your hash map. Each method follows the same pattern you already know: hash the key, find the bucket, iterate.

In this step, get ready to:
  • Implement delete, has, and keys methods on the HashMap class.
  • Write tests for each new method.
  • Run all tests, commit, and push to GitHub.
Implement delete, has, and keys

All three methods follow the same core pattern from get: hash the key, look up the bucket, then iterate through the bucket's entries. The only difference is what you do when you find (or don't find) the key.

  • In hashmap.js, find the closing brace of the get(key) method.
  • Add the delete method below it by copying this code:
  delete(key) {
    const index = this._hash(key);
    const bucket = this._storage[index];

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

    return false;
  }

What does this code do?

The delete method hashes the key and finds its bucket, just like get.

When it finds the matching key, it uses bucket.splice(i, 1) to remove that entry from the bucket array, decrements this._size, and returns true. If the key doesn't exist, it returns false.

You won't see a change yet. The next method continues the same pattern.

  • Add the has method directly below delete:
  has(key) {
    const index = this._hash(key);
    const bucket = this._storage[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        return true;
      }
    }

    return false;
  }

What does this code do?

The has method is the simplest variant. It searches the bucket for the key and returns true if found, false otherwise. No modification, no value retrieval.

You won't see a change yet. One more method to go.

  • Add the keys method directly below has:
  keys() {
    const allKeys = [];
    for (const bucket of this._storage) {
      for (const [key] of bucket) {
        allKeys.push(key);
      }
    }
    return allKeys;
  }

What does this code do?

Unlike the other methods, keys() doesn't hash a single key. It loops through every bucket in the storage array and collects the first element of each [key, value] pair. The result is an array of all keys currently stored in the hash map.

  • Save hashmap.js.
  • You'll test all three new methods in the next substep.

Seeing a syntax error?

Make sure each method is inside the HashMap class (before the final closing }) but after the get method's closing brace.

Check that the module.exports = { HashMap }; line is still the very last line of the file, outside the class.

help me debug a syntax error in my HashMap class

✔️ Awesome, I've got everything!

Great. Double check you've saved hashmap.js before moving on.

ⓧ I'd like to double check the full code

Here's what your complete hashmap.js should look like at this point:

class HashMap {
  constructor(initialCapacity = 16) {
    this._capacity = initialCapacity;
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    this._size = 0;
  }

  get size() {
    return this._size;
  }

  get capacity() {
    return this._capacity;
  }

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

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

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

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

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

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

    return undefined;
  }

  delete(key) {
    const index = this._hash(key);
    const bucket = this._storage[index];

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

    return false;
  }

  has(key) {
    const index = this._hash(key);
    const bucket = this._storage[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        return true;
      }
    }

    return false;
  }

  keys() {
    const allKeys = [];
    for (const bucket of this._storage) {
      for (const [key] of bucket) {
        allKeys.push(key);
      }
    }
    return allKeys;
  }
}

module.exports = { HashMap };
Write tests for each new method

Each new method needs tests that cover both the success case (key exists) and the failure case (key doesn't exist). This ensures your hash map behaves predictably in all scenarios.

  • In hashmap.test.js, find the closing }); of the set and get describe block.
  • Add these three new describe blocks below it (still inside the outer describe('HashMap') block):
  describe('delete', () => {
    it('deletes an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      const result = map.delete('name');
      assert.strictEqual(result, true);
      assert.strictEqual(map.get('name'), undefined);
      assert.strictEqual(map.size, 0);
    });

    it('returns false when deleting non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.delete('ghost'), false);
    });
  });

  describe('has', () => {
    it('returns true for existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.has('name'), true);
    });

    it('returns false for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.has('ghost'), false);
    });
  });

  describe('keys', () => {
    it('returns all stored keys', () => {
      const map = new HashMap();
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      const keys = map.keys();
      assert.strictEqual(keys.length, 3);
      assert.ok(keys.includes('a'));
      assert.ok(keys.includes('b'));
      assert.ok(keys.includes('c'));
    });
  });

What do these tests cover?

  • The delete tests verify that deleting a key returns true, makes the key unreachable via get, and decrements the size. Deleting a non-existent key returns false.
  • The has tests confirm it returns true for stored keys and false for keys that were never set.
  • The keys test stores three entries and confirms all three keys appear in the returned array. The order doesn't matter since hash maps don't guarantee ordering.
  • Save hashmap.test.js.

Tests not found or import error?

Make sure the new describe blocks are inside the outer describe('HashMap', () => { ... }) wrapper, not after its closing });.

help me fix my test file structure

✔️ Awesome, I've got everything!

Great. Make sure you've saved hashmap.test.js before running the tests.

ⓧ I'd like to double check the full code

Here's what your complete hashmap.test.js should look like at this point:

const { describe, it } = require('node:test');
const assert = require('node:assert/strict');
const { HashMap } = require('./hashmap.js');

describe('HashMap', () => {
  describe('hash function', () => {
    it('is deterministic - same key always produces same index', () => {
      const map = new HashMap();
      const index1 = map._hash('hello');
      const index2 = map._hash('hello');
      assert.strictEqual(index1, index2);
    });

    it('produces index within bounds', () => {
      const map = new HashMap(16);
      const keys = ['apple', 'banana', 'cherry', 'date', 'elderberry'];
      for (const key of keys) {
        const index = map._hash(key);
        assert.ok(index >= 0 && index < 16, `Index ${index} out of bounds for key "${key}"`);
      }
    });
  });

  describe('set and get', () => {
    it('sets and gets a value', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.get('name'), 'Alice');
    });

    it('updates an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      map.set('name', 'Bob');
      assert.strictEqual(map.get('name'), 'Bob');
      assert.strictEqual(map.size, 1);
    });

    it('returns undefined for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.get('ghost'), undefined);
    });

    it('handles collisions correctly', () => {
      const map = new HashMap(2);
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      assert.strictEqual(map.get('a'), 1);
      assert.strictEqual(map.get('b'), 2);
      assert.strictEqual(map.get('c'), 3);
    });
  });

  describe('delete', () => {
    it('deletes an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      const result = map.delete('name');
      assert.strictEqual(result, true);
      assert.strictEqual(map.get('name'), undefined);
      assert.strictEqual(map.size, 0);
    });

    it('returns false when deleting non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.delete('ghost'), false);
    });
  });

  describe('has', () => {
    it('returns true for existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.has('name'), true);
    });

    it('returns false for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.has('ghost'), false);
    });
  });

  describe('keys', () => {
    it('returns all stored keys', () => {
      const map = new HashMap();
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      const keys = map.keys();
      assert.strictEqual(keys.length, 3);
      assert.ok(keys.includes('a'));
      assert.ok(keys.includes('b'));
      assert.ok(keys.includes('c'));
    });
  });
});
Run all tests, commit, and push to GitHub
  • Run the full test suite by running this command in your terminal:
node --test
  • You should see all 11 tests passing (2 hash function tests, 4 set/get tests, 2 delete tests, 2 has tests, 1 keys test).

Tests failing?

If a delete test fails, check that this._size-- is inside the if block (only decrement when a key is actually found).

If keys() returns an empty array, confirm you're using for (const [key] of bucket) with destructuring brackets to pull the first element of each pair.

help me debug my failing hash map tests

  • Commit your progress and push to GitHub by running these commands:
git add .
git commit -m "Add delete, has, and keys methods with tests"
git push
  • You should see output confirming the push to your remote repository.

Push rejected?

If git push fails, make sure you set the upstream branch in a previous step. Try running git push --set-upstream origin main instead.

help me push my code to GitHub

Your hash map now has a complete API for managing data. Next up, you'll tackle the performance problem: what happens when your hash map gets too full and collisions start piling up.

Implement Dynamic Resizing

Your hash map can store and retrieve data, handle collisions, and manage deletions. But there is a hidden performance problem.

As you insert more entries, buckets get longer. Searching through a long bucket is O(n), not O(1). The fix is dynamic resizing. When the table gets too full, you double its capacity and rehash every entry into the new, larger array.

In this step, get ready to:
  • Add a _resize() method that doubles capacity and rehashes all entries.
  • Write tests that prove resize triggers at the right time and preserves all data.
  • Run the full test suite, commit, and push to GitHub.
Add the _resize() method and trigger it from set()

The load factor is the ratio of stored entries to total capacity. When it exceeds 0.75, collisions become frequent enough to degrade performance. Your _resize() method will double the capacity and reinsert every existing entry so that hash indices spread out again.

  • In hashmap.js, scroll to the bottom of your HashMap class (just before the closing } and the module.exports line).
  • Add the _resize() method by pasting this code above the final closing brace:
  _resize() {
    // Save reference to existing data
    const oldStorage = this._storage;
    // Double the capacity
    this._capacity = this._capacity * 2;
    // Create a fresh, larger storage array
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    // Reset size - set() will re-increment as it reinserts
    this._size = 0;

    // Rehash every existing entry into the new storage
    for (const bucket of oldStorage) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }

What does this code do?

The method saves a reference to the old storage, then creates a brand new array at double the size. It resets this._size to 0 because the loop below calls this.set() for each entry, which increments size as it reinserts.

Because the capacity has changed, _hash() now produces different indices for the same keys. That is exactly why you must rehash everything. Old indices are meaningless in the new array.

You will not see a change yet. The method exists but nothing calls it. The next edit connects it to set().

  • In hashmap.js, find the set(key, value) method. Locate these two lines near the end of the method:
    bucket.push([key, value]);
    this._size++;
  • Add the following load factor check directly after this._size++; so the end of your set() method looks like this:
    bucket.push([key, value]);
    this._size++;

    // Resize when load factor exceeds 0.75
    if (this._size / this._capacity > 0.75) {
      this._resize();
    }

Why 0.75?

A load factor of 0.75 is the industry standard threshold. Below this value, most buckets hold zero or one entry, keeping lookups close to O(1). Above it, collisions spike and bucket chains grow quickly.

Doubling the capacity gives each entry more room to spread out. The cost of one resize is O(n), but it happens infrequently enough that the amortized cost per insertion stays O(1).

  • Save hashmap.js.
  • Run your existing tests to confirm nothing broke by running:
node --test

All previous tests should still pass. The collision test (capacity 2, three entries) now triggers a resize internally, but the assertions still hold because rehashing preserves all data.

Seeing test failures?

Make sure _resize() resets this._size = 0 before the loop. Without this, size gets double-counted because set() increments it during reinsertion.

Also confirm the if condition uses > 0.75 (strictly greater than), not >= 0.75.

Help me debug my _resize() method

✔️ Awesome, I've got everything!

Great. Double check you have saved hashmap.js.

ⓧ I'd like to double check the full code

class HashMap {
  constructor(initialCapacity = 16) {
    this._capacity = initialCapacity;
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    this._size = 0;
  }

  get size() {
    return this._size;
  }

  get capacity() {
    return this._capacity;
  }

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

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

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket[i][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._storage[index];

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

    return undefined;
  }

  delete(key) {
    const index = this._hash(key);
    const bucket = this._storage[index];

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

    return false;
  }

  has(key) {
    const index = this._hash(key);
    const bucket = this._storage[index];

    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        return true;
      }
    }

    return false;
  }

  keys() {
    const allKeys = [];
    for (const bucket of this._storage) {
      for (const [key] of bucket) {
        allKeys.push(key);
      }
    }
    return allKeys;
  }

  _resize() {
    const oldStorage = this._storage;
    this._capacity = this._capacity * 2;
    this._storage = new Array(this._capacity).fill(null).map(() => []);
    this._size = 0;

    for (const bucket of oldStorage) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }
}

module.exports = { HashMap };
Write tests for resize behavior

Your resize logic needs two guarantees: it triggers at the right time, and it does not lose any data in the process.

  • In hashmap.test.js, find the closing }); of the describe('keys', ...) block.
  • Add the following resize test suite below it (still inside the outer describe('HashMap', ...) block):
  describe('resize', () => {
    it('resizes when load factor exceeds 0.75', () => {
      // Start with a tiny capacity to trigger resize quickly
      const map = new HashMap(4);
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      // 3/4 = 0.75, not yet over the threshold
      assert.strictEqual(map.capacity, 4);
      // 4/4 = 1.0, exceeds 0.75 - triggers resize
      map.set('d', 4);
      assert.strictEqual(map.capacity, 8);
    });

    it('all entries are retrievable after resize', () => {
      // Small capacity forces multiple resizes as we insert 20 entries
      const map = new HashMap(4);
      const entries = {};
      for (let i = 0; i < 20; i++) {
        const key = `key${i}`;
        const value = `value${i}`;
        entries[key] = value;
        map.set(key, value);
      }

      // Verify every single entry survived the resizes
      for (const [key, value] of Object.entries(entries)) {
        assert.strictEqual(map.get(key), value, `Failed to retrieve ${key} after resize`);
      }
      assert.strictEqual(map.size, 20);
    });
  });

What do these tests prove?

The first test uses a capacity of 4. After 3 entries (load factor = 0.75), capacity stays at 4. The 4th entry pushes the load factor above 0.75, which triggers a resize to 8.

The second test inserts 20 entries into a capacity-4 map. This forces multiple resizes (4 to 8 to 16 to 32). After all resizes, every entry must still be retrievable. If even one rehash goes wrong, this test catches it.

  • Save hashmap.test.js.
  • Run the full test suite by running:
node --test

You should see all tests pass, including the two new resize tests.

Resize test failing?

If the capacity assertion fails, check that your if condition in set() fires after incrementing this._size, not before. The check must happen after the new entry is already counted.

If entries go missing after resize, confirm that _resize() iterates over oldStorage (the saved reference), not this._storage (which is already the new empty array).

Help me fix my resize tests

✔️ Awesome, I've got everything!

Great. Double check you have saved hashmap.test.js.

ⓧ I'd like to double check the full code

const { describe, it } = require('node:test');
const assert = require('node:assert/strict');
const { HashMap } = require('./hashmap.js');

describe('HashMap', () => {
  describe('hash function', () => {
    it('is deterministic - same key always produces same index', () => {
      const map = new HashMap();
      const index1 = map._hash('hello');
      const index2 = map._hash('hello');
      assert.strictEqual(index1, index2);
    });

    it('produces index within bounds', () => {
      const map = new HashMap(16);
      const keys = ['apple', 'banana', 'cherry', 'date', 'elderberry'];
      for (const key of keys) {
        const index = map._hash(key);
        assert.ok(index >= 0 && index < 16, `Index ${index} out of bounds for key "${key}"`);
      }
    });
  });

  describe('set and get', () => {
    it('sets and gets a value', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.get('name'), 'Alice');
    });

    it('updates an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      map.set('name', 'Bob');
      assert.strictEqual(map.get('name'), 'Bob');
      assert.strictEqual(map.size, 1);
    });

    it('returns undefined for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.get('ghost'), undefined);
    });

    it('handles collisions correctly', () => {
      const map = new HashMap(2);
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      assert.strictEqual(map.get('a'), 1);
      assert.strictEqual(map.get('b'), 2);
      assert.strictEqual(map.get('c'), 3);
    });
  });

  describe('delete', () => {
    it('deletes an existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      const result = map.delete('name');
      assert.strictEqual(result, true);
      assert.strictEqual(map.get('name'), undefined);
      assert.strictEqual(map.size, 0);
    });

    it('returns false when deleting non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.delete('ghost'), false);
    });
  });

  describe('has', () => {
    it('returns true for existing key', () => {
      const map = new HashMap();
      map.set('name', 'Alice');
      assert.strictEqual(map.has('name'), true);
    });

    it('returns false for non-existent key', () => {
      const map = new HashMap();
      assert.strictEqual(map.has('ghost'), false);
    });
  });

  describe('keys', () => {
    it('returns all stored keys', () => {
      const map = new HashMap();
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      const keys = map.keys();
      assert.strictEqual(keys.length, 3);
      assert.ok(keys.includes('a'));
      assert.ok(keys.includes('b'));
      assert.ok(keys.includes('c'));
    });
  });

  describe('resize', () => {
    it('resizes when load factor exceeds 0.75', () => {
      const map = new HashMap(4);
      map.set('a', 1);
      map.set('b', 2);
      map.set('c', 3);
      assert.strictEqual(map.capacity, 4);
      map.set('d', 4);
      assert.strictEqual(map.capacity, 8);
    });

    it('all entries are retrievable after resize', () => {
      const map = new HashMap(4);
      const entries = {};
      for (let i = 0; i < 20; i++) {
        const key = `key${i}`;
        const value = `value${i}`;
        entries[key] = value;
        map.set(key, value);
      }

      for (const [key, value] of Object.entries(entries)) {
        assert.strictEqual(map.get(key), value, `Failed to retrieve ${key} after resize`);
      }
      assert.strictEqual(map.size, 20);
    });
  });
});
Commit and push to GitHub
  • Stage and commit your changes by running:
git add .
git commit -m "Add dynamic resizing with load factor threshold"
  • Push to GitHub by running:
git push

Push rejected?

If you see a rejection message, run git pull --rebase origin main first, then try git push again. This happens when the remote has changes your local branch does not know about.

Help me push my code to GitHub

Secret mission

forEach, Entries Iterator, and Performance Benchmarking

Your hash map works, but can it iterate like a pro? In this bonus mission, you'll add iteration methods and pit your implementation against V8's built-in Map to see how your hand-rolled data structure stacks up against C++ optimizations.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources to reference later, or delete them entirely.

Resources you used:

  • Local project folder containing hashmap.js, hashmap.test.js, and benchmark.js.
  • GitHub repository (remote).

Keep everything running

No action needed. Choose this if you want to keep the project as a reference or continue experimenting with your hash map implementation.

  • Your project folder stays on your Desktop.
  • Your GitHub repository remains accessible at your profile.

Pause - I'll come back to this later

Since this is a local project with no running processes, there is nothing to pause. Your files will stay on disk until you decide to delete them.

  • No ongoing processes to stop.
  • Your files use negligible disk space.

Delete - I don't want to use this again

Remove all project resources and start fresh. This deletes your local files and the remote GitHub repository.

Delete the local project folder:

  • Open your terminal and delete the project folder by running:

macOS

cd ~/Desktop
rm -rf hashmap-project

Windows

cd ~/Desktop
rmdir /s /q hashmap-project

Check your folder name

Replace the folder name in the command above with whatever you named your project folder in Step 1.

Delete the GitHub repository:

  • Go to your repository page on GitHub.com.
  • Click Settings (the tab under your repository name).
  • Scroll down to the Danger Zone section.
  • Click Delete this repository.
  • Click I want to delete this repository, then type the repository name to confirm.

Nice Work!

Nice Work!

You just built the most important data structure in computer science from scratch. Your HashMap class is a fully functional key-value store with O(1) average-case lookups, collision handling, and automatic resizing.

You've learned how to:

  • Build a hash function that converts string keys into array indices, and handle collisions using separate chaining so multiple keys can share the same bucket.
  • Implement dynamic resizing that doubles capacity when the load factor exceeds 0.75, maintaining O(1) average-case performance as the table grows.
  • Write a comprehensive test suite using Node.js's built-in test runner that proves your hash map works correctly across collision and resize scenarios.
  • Benchmarked your implementation against V8's built-in Map and understood the performance tradeoffs between a JavaScript implementation and native C++ internals.

Ready to quiz yourself?