Hash Table

Hash Table

A Hash Table (or hash map) stores key-value pairs and provides near-O(1) average time for get, set, and delete operations.

How It Works

1. A hash function converts a key into an integer index.
2. The value is stored in a bucket at that index.
3. When two keys hash to the same index, a collision occurs.

Collision Handling: Chaining

The simplest strategy is separate chaining — each bucket holds a linked list (or array) of entries that hashed to that index.

buckets[0] → []
buckets[1] → [["name", "Alice"], ["age", 30]]
buckets[2] → [["city", "Paris"]]
...

Hash Function

A simple string hash function sums character codes and takes the modulus of the bucket count:

hash(key) {
  let h = 0;
  for (const ch of String(key)) h = (h + ch.charCodeAt(0)) % this.size;
  return h;
}

Operations

class HashTable {
  constructor(size = 53) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []);
  }

  hash(key) {
    let h = 0;
    for (const ch of String(key)) h = (h + ch.charCodeAt(0)) % this.size;
    return h;
  }

  set(key, value) {
    const idx = this.hash(key);
    const bucket = this.buckets[idx];
    const entry = bucket.find(e => e[0] === key);
    if (entry) { entry[1] = value; }
    else { bucket.push([key, value]); }
  }

  get(key) {
    const idx = this.hash(key);
    const entry = this.buckets[idx].find(e => e[0] === key);
    return entry ? entry[1] : undefined;
  }

  delete(key) {
    const idx = this.hash(key);
    const bucket = this.buckets[idx];
    const i = bucket.findIndex(e => e[0] === key);
    if (i !== -1) bucket.splice(i, 1);
  }
}

Complexity

Your Task

Implement a HashTable class with hash, set, get, and delete methods using separate chaining.