Data Structureintermediatehashingcollisionopen-addressingchaining

Hash Table

Key-value store with O(1) average lookup using a hash function.

How it works

A hash table achieves amortized O(1) insert, search, and delete by mapping each key through a hash function to a slot in a fixed-size array. The hash function used here is the division method: `hash(key) = key % size`. When two keys map to the same slot — a collision — linear probing resolves it by scanning forward one slot at a time until an empty or deleted slot is found, wrapping around if needed.

Deletions require special care: simply emptying a slot would break probe chains for keys that "passed through" that slot during insertion. Instead, a tombstone (deleted marker) is left behind so probes continue past it during future searches. The load factor (occupied slots ÷ table size) is a critical metric; as it approaches 1.0, probe chains grow long and average-case performance degrades toward O(n). A well-tuned table keeps the load factor below 0.7 and rehashes (doubles capacity, re-inserts all keys) when that threshold is exceeded.

Open-addressing with linear probing exhibits excellent cache locality because probes access contiguous memory — the entire probe sequence often fits in a single cache line. This practical advantage often outweighs its theoretically worse worst-case compared to separate chaining (linked lists per bucket). Real-world implementations like Rust's `HashMap` use a variant called Robin Hood hashing — a form of open addressing that keeps probe distances balanced — while Python's `dict` uses a randomised open-addressing scheme to reduce clustering.

Complexity

Best case

O(1)

Average case

O(1)

Worst case

O(n)

Space

O(n)

Visualizer

Generating steps…

Where it's used in the real world

Python dict / JavaScript objects

O(1) key-value storage underlying all object literals and dictionaries

CPython's dict uses open-addressing with a prime-step probe to maintain O(1) amortized operations. V8 uses hidden classes backed by hash maps for object property lookups. Both rehash at ~2/3 load factor to keep performance predictable.

Database indexes (PostgreSQL hash index)

Equality lookups on indexed columns

PostgreSQL's hash index type uses a multi-level bucket structure built on hashing to deliver O(1) equality lookups on indexed columns — significantly faster than B-tree's O(log n) for pure equality queries on large tables.

Caches — Redis / Memcached

In-memory key-value store serving millions of lookups per second

Redis's main dictionary uses a double-hashing open-addressing table that incrementally rehashes in the background to avoid latency spikes. At 100k+ ops/sec, O(1) lookup with cache-friendly memory layout is non-negotiable.

Implementation

class HashTable<V> {
  private size: number;
  private keys: (number | null)[];
  private vals: (V | null)[];
  private deleted: boolean[];

  constructor(size = 17) {
    this.size = size;
    this.keys = new Array(size).fill(null);
    this.vals = new Array(size).fill(null);
    this.deleted = new Array(size).fill(false);
  }

  private hash(key: number): number {
    return ((key % this.size) + this.size) % this.size;
  }

  insert(key: number, value: V): void {
    let slot = this.hash(key);
    for (let i = 0; i < this.size; i++) {
      const s = (slot + i) % this.size;
      if (this.keys[s] === null || this.deleted[s]) {
        this.keys[s] = key;
        this.vals[s] = value;
        this.deleted[s] = false;
        return;
      }
    }
    throw new Error("Hash table is full");
  }

  search(key: number): V | null {
    let slot = this.hash(key);
    for (let i = 0; i < this.size; i++) {
      const s = (slot + i) % this.size;
      if (this.keys[s] === null && !this.deleted[s]) return null;
      if (this.keys[s] === key && !this.deleted[s]) return this.vals[s];
    }
    return null;
  }

  delete(key: number): boolean {
    let slot = this.hash(key);
    for (let i = 0; i < this.size; i++) {
      const s = (slot + i) % this.size;
      if (this.keys[s] === null && !this.deleted[s]) return false;
      if (this.keys[s] === key && !this.deleted[s]) {
        this.keys[s] = null;
        this.vals[s] = null;
        this.deleted[s] = true; // tombstone
        return true;
      }
    }
    return false;
  }
}

const ht = new HashTable<number>();
ht.insert(5, 50);
ht.insert(16, 160);  // 16 % 11 = 5 → collision → slot 6
console.log(ht.search(16)); // 160
ht.delete(5);
console.log(ht.search(5));  // null

Related algorithms

Binary SearchLive

Find an element in a sorted array by halving the search space each step.

O(log n)