Build a Database from Zero (Part 3): Too Slow? Build a Hash Table Yourself

Database

PostgreSQL

Build from Zero

2 hours ago1169 words·6 min read

What You'll Get Out of This

Replace the "naive loop" with a hash table for exact-key lookups — and feel O(1) for yourself;
Implement a real hash table: hash function, modulo, collision, chaining, load factor;
Discover a sharp limit by yourself: a hash table nails "equal to", but is useless for "less than 50" — the awkwardness that pushes you to Part 4.

Before We Start

Know Parts 1 & 2 (array = table, query = loop, engine decoupled "what" from "how");
Understand the concept "O(1) means: the time has nothing to do with how many items there are."

Where We Left Off

Part 2 ended with the engine being "naive" — it still scans the whole table every time. The classic case that stings the most: "I know the exact id; give me that row."

In real life you'd write SELECT * FROM books WHERE id = 42. Our current engine does it by scanning from the top:

function findById(rows, targetId) {
  for (const row of rows) {
    if (row.id === targetId) return row;
  }
  return null;
}

100k rows, and it may check 100k of them. It's as if you knew the book's exact shelf number, yet you swept every shelf anyway. That's absurd — and a hash table is exactly "mapping a key straight to a location."

Step 1: The Core Idea — Turn a Key into an Array Index

Recall: an array is O(1) if you know the index — you compute the address and jump. So a hash table's trick is: turn an arbitrary key (id, string) into an array index.

That conversion is the hash function. Two steps:

// Step A: hash the key into a number
function hash(key) {
  if (typeof key === "number") return key;
  // for strings, fold chars into a number (simplified on purpose)
  let h = 0;
  for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) | 0;
  return h;
}

// Step B: compress into the array's range by modulo
function indexFor(key, capacity) {
  return hash(key) % capacity;   // 0 .. capacity-1
}

So hash("apple") gives a big number; % capacity gives a slot. Now "find id = 42" is:

hash(42)          // 42
42 % capacity     // some slot, e.g. 2
slots[2]          // jump straight there

Three math operations, no sweeping. That's where O(1) comes from: you didn't "find" — you computed.

Step 2: But Collisions Happen

Here's the catch: two different keys can land on the same slot.

hash("apple")  % 8 === 1
hash("banana") % 8 === 1   // collide: both want slot 1

If you ignored it, you'd overwrite. The textbook fix is chaining: each slot holds a list (a bucket), and colliding entries are strung on that bucket:

// a minimal hash table with chaining
class HashTable {
  constructor(capacity = 8) {
    this.capacity = capacity;
    this.buckets = new Array(capacity).fill(null).map(() => []);
    this.size = 0;
  }

  // insert (key, value)
  set(key, value) {
    const idx = indexFor(key, this.capacity);
    const bucket = this.buckets[idx];
    for (const entry of bucket) {
      if (entry.key === key) {       // key already there → update
        entry.value = value;
        return;
      }
    }
    bucket.push({ key, value });
    this.size++;
    if (this.size / this.capacity > 0.7) this.resize();  // see Step 3
  }

  // find by key
  get(key) {
    const idx = indexFor(key, this.capacity);
    for (const entry of this.buckets[idx]) {
      if (entry.key === key) return entry.value;
    }
    return null;
  }
}

Now findById becomes:

const byId = new HashTable();
books.forEach((b, i) => byId.set(b.id, i));   // build index once

// "SELECT * FROM books WHERE id = 42"
const found = books[byId.get(42)];

Go from "sweep 100k" to "hop straight." That's the whole point of an index.

Step 3: Why O(1) Is Only "Average" — Load Factor & Resize

Is it now really O(1)? Only on average, and only if the hash spreads keys evenly. Two knobs control that:

Load factor — size / capacity. The fuller the buckets, the longer the chains, the closer to O(n). We keep it under ~0.7.

Resize — when the load factor passes the threshold, double the array and rehash everything into the new one. That single resize is O(n), but it happens rarely, so amortized over all operations it stays O(1) on average.

resize() {
  const old = this.buckets;
  this.capacity *= 2;
  this.buckets = new Array(this.capacity).fill(null).map(() => []);
  this.size = 0;
  for (const bucket of old) {
    for (const entry of bucket) this.set(entry.key, entry.value);
  }
}

So the truthful statement: a hash table is average O(1) — given a good hash function and a table that grows.

The Painful Limitation: It Can't Do "Less Than 50"

You've built something genuinely fast — for exact equality. Now try the query from Part 1:

// "SELECT * FROM books WHERE price < 50"

With a hash table, the only thing you can ask is "give me price === 50." You cannot ask "all prices below 50," because the hash table never ordered the keys.

Think about why: the hash function scrambles the key into a pseudo-random slot. 10 and 11 and 12 — their slots have nothing to do with each other. There's no "a region holds all small values."

Here's the moment to remember: a hash table wins at "exactly this key," and loses at "any range." Real databases hit this same wall — it's why nearly all primary indexes aren't hash but a sorted tree. And that's exactly where Part 4 turns.

Hands-On Practice

Feel O(1) yourself: build the HashTable, index 100k books by id, then time byId.get(50000) vs the loop findById. Watch the gap widen as rows grow.
Stare at a collision: insert "apple" and "banana" (make a small capacity), print the bucket chain, and see them shared as intended.
Trigger a resize: lower the load-factor threshold to 0.5, insert many rows, and log when resize() fires and how the total grew.

Summary and Keywords

A hash table turns a key into an array index via hash + modulo — you compute, not search → average O(1);
Collisions are handled by chaining; load factor + resize keep chains short;
The tradeoff: hash gives exact equality, but can't do ranges — the key is never ordered.

Keywords: hash table、hash function、modulo、collision、chaining、load factor、resize、average O(1)

What's Next

You've felt both sides: the naive loop is slow, and the hash table is fast but only for equality. So the question becomes, almost by itself: is there a structure that finds "a specific key" fast and can sweep a range cheaply? A structure that keeps data sorted.

That's Part 4 — a sorted array with binary search. You'll see ranges work, but hit a new pain: insertion must shift. That pain is what will drive you toward a tree.