Skip to content

Hash Table

Medium ~40 min

What you'll build

A HashTable class with set, get, delete, and keys methods, using a simple hash function and separate chaining for collisions.

Goals

  • Implement a hash function mapping string keys to bucket indices
  • Handle collisions with separate chaining (arrays per bucket)
  • Provide get/set/delete/keys operations
  • Understand why hash tables give O(1) average lookup

Prerequisites

  • Objects and property access
  • Arrays and array methods
  • String methods (charCodeAt)

Steps

  1. 1

    Design the bucket array

    A hash table is an array of buckets. Each bucket is an array of [key, value] pairs. Pick a fixed capacity (e.g. 53) and initialize all buckets as empty arrays.

    Code
    class HashTable {
      constructor(capacity = 53) {
        this.capacity = capacity;
        this.buckets = Array.from({ length: capacity }, () => []);
      }
    }

    Expected result

    A HashTable with 53 empty buckets.

  2. 2

    Write the hash function

    Implement a hash function that converts a string key to a bucket index. A common approach: sum char codes, multiply by a prime, then mod by capacity.

    Code
    _hash(key) {
      const PRIME = 31;
      let total = 0;
      for (let i = 0; i < Math.min(key.length, 100); i++) {
        total = (total * PRIME + key.charCodeAt(i)) % this.capacity;
      }
      return total;
    }

    Expected result

    _hash('name') returns a number in [0, capacity).

  3. 3

    Implement set with collision handling

    To set a key, hash it to find the bucket, then check if the key already exists in that bucket. If so, update the value; otherwise push a new [key, value] pair.

  4. 4

    Implement get and delete

    get hashes the key, walks the bucket, and returns the matching value (or undefined). delete finds and removes the matching pair. Both rely on the same bucket-walk logic.

  5. 5

    Test with collisions

    Insert several key/value pairs, retrieve them, delete one, and confirm the rest are intact. Verify that keys hashing to the same bucket still work (collision handling).

    Code
    const ht = new HashTable();
    ht.set('name', 'Alice');
    ht.set('age', 30);
    ht.set('city', 'Beijing');
    console.log(ht.get('name')); // Alice
    console.log(ht.get('age'));  // 30
    ht.delete('age');
    console.log(ht.get('age'));  // undefined

    Expected result

    get returns Alice, 30, then undefined after delete.

Try it yourself

What you learned

You built the data structure that powers JavaScript objects and Map — and saw how a hash function plus collision handling gives near O(1) lookups.

Related Resources

Related Lessons

  • Objects

    Objects are hash tables under the hood.

  • Arrays

    Buckets are arrays of key/value pairs.

Related Glossary

  • Hash Table

    Key-value store with O(1) average lookup.

Related Glossary

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

  • Hash Table

    Key-value store with O(1) average lookup.

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors

← Back to topic