Introduction to Hash Tables

A hash table stores key-value pairs by converting every key into an integer index through a hash function, then placing the value at that index inside an internal array. Because array access by index is O(1), reading and writing a value is also O(1) on average — regardless of how many entries the table holds.

JavaScript’s built-in Map and plain objects are both backed by hash tables, so understanding the internals helps you choose the right tool and predict performance.

How a Hash Function Works

A hash function takes arbitrary input (a string, number, object reference) and returns a fixed-range integer. A minimal string hasher looks like this:

function simpleHash(key, tableSize) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash * 31 + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

console.log(simpleHash("name", 16));   // e.g. 7
console.log(simpleHash("email", 16));  // e.g. 3

The % tableSize keeps the index within the bounds of the backing array.

Collisions and Separate Chaining

Two different keys can produce the same index — this is called a collision. The most common resolution strategy is separate chaining: each slot holds a linked list (or small array) of all entries that hashed to that index.

// Conceptual bucket layout after inserting "name" and "age"
// both hashing to slot 2:
//
// slot 0: null
// slot 1: null
// slot 2: [["name", "Alice"], ["age", 30]]  ← chain
// slot 3: null
// ...

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

  _index(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) % this.buckets.length;
    }
    return h;
  }

  set(key, value) {
    const idx = this._index(key);
    const chain = this.buckets[idx];
    const existing = chain.find(([k]) => k === key);
    if (existing) { existing[1] = value; return; }
    chain.push([key, value]);
    this.count++;
  }

  get(key) {
    const chain = this.buckets[this._index(key)];
    return chain.find(([k]) => k === key)?.[1];
  }
}

const ht = new HashTable();
ht.set("name", "Alice");
console.log(ht.get("name")); // "Alice"

Load Factor and Resizing

The load factor is entries / slots. When it exceeds a threshold (typically 0.75 in Java’s HashMap; V8 uses a similar heuristic), the engine allocates a larger backing array and rehashes every entry. This keeps chains short and preserves O(1) average performance.

In practice the worst case is vanishingly rare with a good hash function and automatic resizing — which is why hash tables are the go-to structure for fast lookups.

Up Next

See how JavaScript’s Map and plain objects compare in iteration order, key types, and real-world performance.