Implementing a Hash Table in JavaScript

A hash table is one of the most powerful and widely used data structures in computer science, offering average-case O(1) time complexity for insertion, lookup, and deletion. JavaScript's built-in objects and Map type are themselves implemented as hash tables under the hood, but building one from scratch reveals exactly how that performance is achieved. In this deep dive you will construct a fully functional HashTable class step by step, implementing every essential operation — hashing, setting, getting, removing, and iterating — while handling the inevitable collisions that arise when two different keys map to the same bucket.

The core idea is straightforward: convert an arbitrary key (typically a string) into an integer index via a hash function, then store the associated value at that index inside a fixed-size array. Because the array provides O(1) random access by index, retrieving a value is nearly instantaneous once you have the index. The engineering challenge is writing a hash function that distributes keys uniformly and handling the cases where two keys inevitably collide at the same index.

Setting Up the HashTable Class

Every implementation begins with a class definition and a constructor that establishes two things: the size of the internal array and the array itself. Choosing a prime number for the size is a deliberate mathematical choice — prime-sized tables reduce clustering because primes share fewer common factors with typical key-hash values, spreading entries more evenly across buckets.

class HashTable {
  constructor(size = 53) {
    this.size  = size;               // prime number → better distribution
    this.table = new Array(this.size); // sparse array; slots start as undefined
  }
}

Storing size as an instance property (this.size) is important because both the hash function and every other method need to know the array's length to compute valid indices and to iterate correctly. Using new Array(53) creates a sparse array with 53 empty slots — none of them are initialised — which is fine because the methods will initialise each bucket on first use.

Common prime choices for the size include 53, 97, 193, 389, and 769. For production tables that grow dynamically, the size would double (to the next prime) and all entries would be rehashed when the load factor exceeds a threshold such as 0.75, but for this implementation the size is fixed.

Writing the Hash Function

The hash function is the engine of the entire structure. A good hash function must satisfy three properties: it must be deterministic (the same key always produces the same index), it must be fast (ideally O(k) where k is the length of the key), and it must distribute keys uniformly to minimise collisions.

class HashTable {
  constructor(size = 53) {
    this.size  = size;
    this.table = new Array(this.size);
  }

  // "Private" convention: prefix with underscore
  _hash(key) {
    let total = 0;
    const PRIME = 31; // small prime multiplier improves distribution

    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const charCode = key.charCodeAt(i) - 96; // 'a' → 1, 'b' → 2, …
      total = (total * PRIME + charCode) % this.size;
    }

    return total; // always in range [0, this.size - 1]
  }
}

Let's unpack every decision in this function:

• charCodeAt(i) − 96 — Subtracting 96 maps lowercase letters to small positive integers ('a' = 97 − 96 = 1, 'z' = 122 − 96 = 26). This isn't strictly necessary but keeps the numbers tidy. For a more general implementation you would omit the subtraction and work with the full Unicode code point.
• Multiplying by a prime (31) — Polynomial rolling hash: each step computes total = total * PRIME + charCode. The prime multiplier ensures that anagram-like keys (e.g., "abc" and "bca") hash to different values because the position of each character influences the accumulated result differently. Java's String.hashCode() uses the same technique with 31.
• Modulo (% this.size) — Applied at every iteration rather than only at the end to prevent integer overflow in environments without big-integer arithmetic. JavaScript numbers are IEEE 754 doubles, which lose integer precision beyond 2⁵³, so keeping the running total small is important.
• Capping at 100 characters — For very long strings the loop is bounded to 100 iterations so the function remains practically O(1) even if keys are lengthy paragraphs.

To see the function in action, consider two keys with a table size of 53:

Two different keys may produce the same index — that is a collision, and it is handled by the set and get methods below.

Implementing the set Method with Chaining

The most common strategy for resolving collisions is separate chaining: each bucket in the table holds an array (a "chain") of all key-value pairs that hashed to that index. When a new key arrives at an already-occupied bucket it is simply appended to that bucket's array. Retrieval then scans the (typically very short) chain for the matching key.

set(key, value) {
  const index = this._hash(key);

  // 1. Initialise the bucket if it does not yet exist
  if (!this.table[index]) {
    this.table[index] = [];
  }

  // 2. Check for an existing entry with the same key (update in place)
  const bucket = this.table[index];
  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i][0] === key) {
      bucket[i][1] = value; // update existing key
      return;
    }
  }

  // 3. No existing entry — append a new [key, value] pair
  bucket.push([key, value]);
}

The three-phase logic is critical:

• Phase 1 — Lazy initialisation: The bucket is created as an empty array only when it is first needed. This keeps the table memory-efficient when most slots are empty.
• Phase 2 — Duplicate check: Before pushing, the code scans the existing pairs. If a pair with the same key already exists its value is overwritten rather than creating a second entry for the same key. This matches the expected behaviour of any key-value store (the last write wins).
• Phase 3 — Insertion: Only if no duplicate is found is the new pair appended. Each pair is stored as a two-element array [key, value], making it easy to destructure during retrieval.

Example of a collision being handled gracefully:

const ht = new HashTable(7); // small size forces collisions quickly

ht.set("grape",  2.99);
ht.set("apple",  1.49);
ht.set("mango",  3.49); // may collide with "grape" or "apple"

// Even if two keys share index 4, both are stored in that bucket's array:
// table[4] → [ ["grape", 2.99], ["mango", 3.49] ]

Implementing the get Method

Retrieving a value mirrors the insertion logic: hash the key to find the bucket, then walk the bucket's chain looking for a matching key.

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

  // Bucket doesn't exist → key was never inserted
  if (!bucket) return undefined;

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

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

The early return when !bucket is an important short-circuit: if the slot was never initialised there is nothing to search. The scan uses strict equality (===) so that keys are compared by value and type without any type coercion that could lead to subtle bugs. In the average case the bucket chain is length 1 so the loop terminates immediately — O(1). In the worst case (every key hashing to the same bucket) it degrades to O(n), which is why a good hash function and an appropriately sized table matter.

console.log(ht.get("grape"));  // 2.99
console.log(ht.get("apple"));  // 1.49
console.log(ht.get("kiwi"));   // undefined — never inserted
console.log(ht.get("Grape"));  // undefined — keys are case-sensitive

Implementing the remove Method

Removal requires finding the entry and then cleanly excising it from the bucket's chain without disrupting the other entries sharing that bucket.

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

  if (!bucket) return false; // nothing to remove

  for (let i = 0; i < bucket.length; i++) {
    if (bucket[i][0] === key) {
      const removed = bucket.splice(i, 1)[0]; // removes 1 element at position i
      // Optional: clean up the bucket reference if now empty
      if (bucket.length === 0) {
        this.table[index] = undefined;
      }
      return removed; // truthy — the removed [key, value] pair
    }
  }

  return false; // key not found — falsy
}

Key design decisions in remove:

• splice(i, 1) mutates the bucket array by removing exactly one element at position i and returns it as a single-element array, hence [0] to unwrap it. An alternative approach using filter() creates a new array (bucket.filter(pair => pair[0] !== key)) and reassigns it to this.table[index] — cleaner but slightly less memory-efficient.
• Clearing empty buckets — Setting the slot back to undefined when the chain becomes empty allows the keys() method (below) to skip it efficiently and keeps memory tidy.
• Return value semantics — Returning the removed pair on success gives callers the old value (useful if they want to do something with it), while returning false for a missing key lets callers distinguish "removed" from "not found" without throwing an error.

console.log(ht.remove("grape"));  // ["grape", 2.99] — success
console.log(ht.remove("grape"));  // false — already removed
console.log(ht.remove("kiwi"));   // false — never existed

Adding a keys Method to Iterate Entries

Because the internal array is sparse and each occupied slot holds a chain of pairs, iterating over all entries requires a two-level loop. A keys() method collects every unique key; an entries() variant collects [key, value] tuples; a values() variant collects just the values.

keys() {
  const results = [];

  for (let i = 0; i < this.table.length; i++) {
    const bucket = this.table[i];
    if (bucket) {                          // skip empty slots
      for (const [key] of bucket) {        // destructure each [key, value] pair
        results.push(key);
      }
    }
  }

  return results;
}

// entries() variant — returns [[key, value], …]
entries() {
  const results = [];

  for (let i = 0; i < this.table.length; i++) {
    const bucket = this.table[i];
    if (bucket) {
      for (const pair of bucket) {
        results.push(pair); // push the full [key, value] pair
      }
    }
  }

  return results;
}

// values() variant — returns values only (may contain duplicates)
values() {
  const seen = new Set();   // deduplicate if multiple keys map to same value
  const results = [];

  for (let i = 0; i < this.table.length; i++) {
    const bucket = this.table[i];
    if (bucket) {
      for (const [, value] of bucket) {
        if (!seen.has(value)) {
          seen.add(value);
          results.push(value);
        }
      }
    }
  }

  return results;
}

Note that the order in which keys are returned is determined by their hash index, not by insertion order. If you need insertion-order iteration, JavaScript's native Map guarantees that, but a hand-rolled hash table does not without extra bookkeeping (such as maintaining a separate doubly linked list of entries, as the LinkedHashMap in Java does).

The Complete Implementation

class HashTable {
  constructor(size = 53) {
    this.size  = size;
    this.table = new Array(this.size);
  }

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

  set(key, value) {
    const index = this._hash(key);
    if (!this.table[index]) this.table[index] = [];
    const bucket = this.table[index];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) { bucket[i][1] = value; return; }
    }
    bucket.push([key, value]);
  }

  get(key) {
    const bucket = this.table[this._hash(key)];
    if (!bucket) return undefined;
    for (const [k, v] of bucket) if (k === key) return v;
    return undefined;
  }

  remove(key) {
    const index  = this._hash(key);
    const bucket = this.table[index];
    if (!bucket) return false;
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        const removed = bucket.splice(i, 1)[0];
        if (bucket.length === 0) this.table[index] = undefined;
        return removed;
      }
    }
    return false;
  }

  keys() {
    const results = [];
    for (const bucket of this.table) {
      if (bucket) for (const [k] of bucket) results.push(k);
    }
    return results;
  }

  entries() {
    const results = [];
    for (const bucket of this.table) {
      if (bucket) for (const pair of bucket) results.push(pair);
    }
    return results;
  }
}

Testing and Validating the Implementation

A rigorous test suite checks not only the happy path but also edge cases that commonly expose bugs in hash table implementations. Work through each category systematically.

Basic operations:

const ht = new HashTable(53);

// Insert several entries
ht.set("name",    "Alice");
ht.set("age",     30);
ht.set("country", "Canada");

// Retrieve them
console.assert(ht.get("name")    === "Alice",  "name should be Alice");
console.assert(ht.get("age")     === 30,        "age should be 30");
console.assert(ht.get("country") === "Canada",  "country should be Canada");

Collision handling — use a small table to force collisions:

const small = new HashTable(7); // only 7 buckets → high collision probability

small.set("a", 1);
small.set("b", 2);
small.set("c", 3);
small.set("d", 4);
small.set("e", 5);
small.set("f", 6);
small.set("g", 7);

// All values must still be independently retrievable
["a","b","c","d","e","f","g"].forEach((key, i) => {
  console.assert(small.get(key) === i + 1, `${key} should be ${i + 1}`);
});

Update an existing key (no duplicate entries):

ht.set("age", 31);           // overwrite the existing "age" entry
console.assert(ht.get("age") === 31, "age should be updated to 31");

// Confirm only one entry for "age" exists
const ageEntries = ht.entries().filter(([k]) => k === "age");
console.assert(ageEntries.length === 1, "no duplicate keys should exist");

Remove operations:

const removed = ht.remove("name");
console.assert(removed[0] === "name" && removed[1] === "Alice",
               "remove should return the removed pair");

console.assert(ht.get("name") === undefined,
               "get after remove should return undefined");

console.assert(ht.remove("name") === false,
               "removing a non-existent key should return false");

Edge cases:

const empty = new HashTable();

// get on a completely empty table
console.assert(empty.get("anything") === undefined,
               "get on empty table should return undefined");

// remove on a completely empty table
console.assert(empty.remove("anything") === false,
               "remove on empty table should return false");

// keys() on an empty table
console.assert(empty.keys().length === 0,
               "keys on empty table should return empty array");

// Case sensitivity
empty.set("Key", "upper");
empty.set("key", "lower");
console.assert(empty.get("Key")  === "upper", "'Key' and 'key' are different");
console.assert(empty.get("key")  === "lower", "'key' entry must not be overwritten");
console.assert(empty.keys().length === 2,      "two distinct entries expected");

The table below summarises the expected time complexity of each operation under the two most important conditions:

The worst case only occurs when every single key hashes to the same bucket, which a well-designed hash function with a prime-sized table makes astronomically unlikely in practice. That is why the choice of hash function, the prime size, and keeping the load factor low are the three pillars of a performant hash table. With those in place the implementation above delivers the near-constant-time performance that makes hash tables indispensable across virtually every domain of software engineering.