Back to blog
7 min read

Hash Tables Under the Hood: Why Object Lookup is O(1)

Hash tables power objects, dictionaries, sets, and caches. Here's what actually happens when you write obj[key], and when O(1) breaks down.

algorithms data-structures

Hash Tables Under the Hood: Why Object Lookup is O(1)

When someone asks “what’s the time complexity of accessing a property on a JavaScript object?” the answer is O(1). But that answer hides a lot of machinery. What actually happens between obj['name'] and getting the value back? Understanding this made me a better engineer, not because I build hash tables, but because I stopped misusing them.

The Core Idea

A hash table stores key-value pairs. When you insert ('name', 'Alice'), the hash table:

  1. Runs the key 'name' through a hash function to get a number
  2. Uses that number to compute an index into an internal array
  3. Stores the value at that index

When you look up obj['name'], it runs the same hash function, computes the same index, and goes directly to that slot. No searching. That is why it is O(1).

Hash function: "name" → 2938471023
Index:         2938471023 % arraySize → 7
Array[7]:      { key: "name", value: "Alice" }

Hash Functions: The Engine

A hash function converts an arbitrary key into a fixed-size integer. It must be:

  • Deterministic: Same input always produces same output
  • Fast: Computed in constant time
  • Uniform: Distributes keys evenly across the output range

Here is a simple (bad) hash function and a better one:

// Terrible hash function: just sums char codes
function badHash(key) {
  let hash = 0;
  for (const char of key) hash += char.charCodeAt(0);
  return hash;
}
// badHash('abc') === badHash('cba') === badHash('bac') → collisions!

// Better: DJB2 hash (widely used, simple, good distribution)
function djb2(key) {
  let hash = 5381;
  for (const char of key) {
    hash = (hash * 33) ^ char.charCodeAt(0);
  }
  return hash >>> 0; // Ensure unsigned 32-bit integer
}

The magic number 5381 and the multiply-by-33-then-XOR pattern in DJB2 were chosen empirically. They produce a good distribution for typical string inputs.

Building a Hash Table From Scratch

Let me build one so you can see every moving part:

class HashTable {
  constructor(size = 53) {
    this.buckets = new Array(size);
    this.size = size;
    this.count = 0;
  }

  _hash(key) {
    let hash = 5381;
    for (const char of String(key)) {
      hash = (hash * 33) ^ char.charCodeAt(0);
    }
    return (hash >>> 0) % this.size;
  }

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

    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }

    // Check if key already exists in this bucket
    for (const pair of this.buckets[index]) {
      if (pair[0] === key) {
        pair[1] = value; // Update existing
        return;
      }
    }

    this.buckets[index].push([key, value]);
    this.count++;

    // Resize if load factor exceeds 0.75
    if (this.count / this.size > 0.75) {
      this._resize(this.size * 2);
    }
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (!bucket) return undefined;

    for (const [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }

  delete(key) {
    const index = this._hash(key);
    const bucket = this.buckets[index];
    if (!bucket) return false;

    const pairIndex = bucket.findIndex(([k]) => k === key);
    if (pairIndex === -1) return false;

    bucket.splice(pairIndex, 1);
    this.count--;
    return true;
  }

  _resize(newSize) {
    const oldBuckets = this.buckets;
    this.buckets = new Array(newSize);
    this.size = newSize;
    this.count = 0;

    for (const bucket of oldBuckets) {
      if (bucket) {
        for (const [key, value] of bucket) {
          this.set(key, value);
        }
      }
    }
  }
}

Collision Resolution: Two Schools

Two keys can hash to the same index. This is a collision. There are two main strategies to handle it.

Chaining (Separate Chaining)

Each slot in the array holds a linked list (or array) of all key-value pairs that hashed to that index. This is what the code above uses.

Index 0: → null
Index 1: → [("name", "Alice")] → [("mane", "Horse")]
Index 2: → null
Index 3: → [("age", 30)]

Pros: Simple, never fills up, degrades gracefully. Cons: Uses more memory (pointers), cache-unfriendly.

Open Addressing (Linear Probing)

When a collision happens, look at the next slot. If that is taken, look at the next one. Keep going until you find an empty slot.

class OpenAddressedTable {
  constructor(size = 53) {
    this.keys = new Array(size).fill(undefined);
    this.values = new Array(size).fill(undefined);
    this.size = size;
    this.count = 0;
    this.DELETED = Symbol('deleted');
  }

  set(key, value) {
    if (this.count / this.size > 0.7) this._resize(this.size * 2);

    let index = this._hash(key);
    let firstDeleted = -1;

    while (this.keys[index] !== undefined) {
      if (this.keys[index] === key) {
        this.values[index] = value;
        return;
      }
      if (this.keys[index] === this.DELETED && firstDeleted === -1) {
        firstDeleted = index;
      }
      index = (index + 1) % this.size; // Linear probe
    }

    const insertAt = firstDeleted !== -1 ? firstDeleted : index;
    this.keys[insertAt] = key;
    this.values[insertAt] = value;
    this.count++;
  }

  get(key) {
    let index = this._hash(key);

    while (this.keys[index] !== undefined) {
      if (this.keys[index] === key) return this.values[index];
      index = (index + 1) % this.size;
    }
    return undefined;
  }

  // ... _hash and _resize same as before
}

Open addressing is more cache-friendly (data is in contiguous memory) but degrades badly when the table gets full. The DELETED sentinel is necessary because you cannot just empty a slot on deletion — it would break the probe chain for keys that were inserted after the deleted one.

Load Factor: When O(1) Becomes O(n)

The load factor is count / tableSize. As it approaches 1.0, collisions increase. For chaining, the average chain length equals the load factor. For open addressing, clustering gets exponentially worse past 0.7.

// Simulating lookup times at different load factors
function benchmark() {
  const sizes = [0.3, 0.5, 0.7, 0.9, 0.95];

  for (const loadFactor of sizes) {
    const tableSize = 10000;
    const numKeys = Math.floor(tableSize * loadFactor);
    const table = new HashTable(tableSize);

    // Insert keys
    for (let i = 0; i < numKeys; i++) {
      table.set(`key_${i}`, i);
    }

    // Measure lookup time
    const start = performance.now();
    for (let i = 0; i < 10000; i++) {
      table.get(`key_${i % numKeys}`);
    }
    const elapsed = performance.now() - start;

    console.log(`Load factor ${loadFactor}: ${elapsed.toFixed(2)}ms for 10k lookups`);
  }
}

Typical results:

Load factor 0.3: 1.2ms for 10k lookups
Load factor 0.5: 1.4ms for 10k lookups
Load factor 0.7: 1.8ms for 10k lookups
Load factor 0.9: 4.2ms for 10k lookups
Load factor 0.95: 11.7ms for 10k lookups

This is why hash tables resize. When the load factor crosses a threshold (typically 0.75), the table doubles in size and rehashes everything. The resize is O(n), but it happens infrequently enough that the amortized cost per operation stays O(1).

JavaScript’s Map vs Object: A Real Difference

In V8 (Node.js and Chrome), Object and Map use different internal implementations:

Object uses hidden classes and inline caches for known property shapes. If you create many objects with the same properties in the same order, V8 optimizes them into struct-like memory layouts. But if you use an object as a dynamic dictionary (arbitrary string keys added at runtime), V8 falls back to a hash table, and performance drops.

Map is always a hash table, optimized for frequent additions and deletions.

// Benchmark: Object vs Map for dictionary use
function benchmarkDictionary() {
  const iterations = 1_000_000;

  // Object as dictionary
  const obj = {};
  console.time('Object set');
  for (let i = 0; i < iterations; i++) obj[`key_${i}`] = i;
  console.timeEnd('Object set');

  console.time('Object get');
  for (let i = 0; i < iterations; i++) obj[`key_${i}`];
  console.timeEnd('Object get');

  console.time('Object delete');
  for (let i = 0; i < iterations; i++) delete obj[`key_${i}`];
  console.timeEnd('Object delete');

  // Map as dictionary
  const map = new Map();
  console.time('Map set');
  for (let i = 0; i < iterations; i++) map.set(`key_${i}`, i);
  console.timeEnd('Map set');

  console.time('Map get');
  for (let i = 0; i < iterations; i++) map.get(`key_${i}`);
  console.timeEnd('Map get');

  console.time('Map delete');
  for (let i = 0; i < iterations; i++) map.delete(`key_${i}`);
  console.timeEnd('Map delete');
}

On Node.js 20, typical results with 1M entries:

Object set:    420ms
Object get:    180ms
Object delete: 950ms    ← delete on Objects is notoriously slow

Map set:       290ms
Map get:       150ms
Map delete:    210ms    ← Map handles deletion efficiently

Use Map when:

  • Keys are added and removed frequently
  • Keys are not strings (Map supports any key type)
  • You need to iterate in insertion order
  • You need .size without counting manually

Use Object when:

  • The shape is known at creation time (fixed properties)
  • You need JSON serialization
  • You are using it as a record/struct, not a dictionary

Hash Tables in the Wild

Hash tables are everywhere once you start looking:

  • Database indexes: Hash indexes provide O(1) exact-match lookups
  • Caches: LRU caches use a hash table + doubly linked list
  • Routers: Express stores route handlers in a structure that uses hashing
  • Deduplication: new Set() is a hash table that only stores keys
  • Compilers: Symbol tables map variable names to their metadata

Understanding the internals explains otherwise mysterious behaviors: why delete obj.key is slow, why V8 deoptimizes objects with too many dynamic properties, why hash-based data structures do not maintain sorted order, and why the same code performs differently with 100 keys versus 10 million.

The O(1) lookup is not magic. It is a hash function, an array index, and a strategy for handling the cases where two keys want the same slot. Simple machinery, but it powers half of computer science.