Hash Tables

A data structure that converts any key into an array index using a hash function - giving O(1) average lookup, insert, and delete regardless of how many items are stored.

You need to look up, insert, or check existence by key in constant time. If you are writing a nested loop to find a match - stop. A hash table does it in one pass.

The hash function is what turns scanning into direct access

A hash table exists so you can jump to the right bucket instead of scanning an entire unsorted array. The key idea is not the array itself - it is the hash function that converts a key into a bucket index.

Aspect	Unsorted Array	Hash Table
Find "apple"	Scan every element until found	hash('apple') -> index 3 -> done
Time	O(n) - grows with size	O(1) average - constant regardless
How	Compare each element	Jump directly to the right bucket
Why it matters	Slow at scale	1M items or 10 items - same speed

The hash function is the trick - it converts any key into a number, and that number tells you exactly where to look.

Watch hashing, collisions, and rehashing happen step by step

The card below demonstrates all three behaviors explicitly: how a key becomes a bucket index, how two collision strategies react to the same clash, and why load factor eventually forces a rehash.

O(1) avg timeO(n) space

8 bucketsLive hash computationLoad factor updates live

Load factor = items / buckets

1 / 8 = 0.13

key -> hash(key) -> % table size -> bucket index

Insert

Key

apple

hash(key)

739837

% 8

Result

Written to bucket 5

Table view

8 buckets indexed 0-7

Empty

5OCCUPIED

apple

Empty

Step 1 of 5

What

'apple' hashes to bucket 5. Written to index 5.

Why

The hash function converts the string to a large integer. Modulo 8 maps that integer into our table's range. The same key always produces the same index, which is what makes lookup possible.

Code For This Pattern

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

  hash(key) {
    let hash = 0;
    for (const char of key) {
      hash = (hash * 31 + char.charCodeAt(0)) % this.size;
    }
    return hash;
  }

  insert(key, value) {
    const index = this.hash(key);     // O(1) - jump to bucket
    this.buckets[index] = { key, value };
    this.count++;
    if (this.count / this.size >= 0.75) this.rehash();
  }

  lookup(key) {
    const index = this.hash(key);     // same hash = same bucket
    return this.buckets[index];       // O(1) - direct access
  }
}

Chaining and probing pay the same collision cost differently

Both strategies start with the same hash result. The design difference is what they do next when that bucket is already occupied.

Aspect	Chaining	Linear Probing
Collision handling	Append to a list in the same bucket	Walk forward to the next open slot
Lookup cost at high load	O(k) - scan the chain	O(k) - follow the probe sequence
Clustering	No - each bucket is independent	Yes - nearby buckets fill together
Delete	Remove from chain directly	Needs tombstone markers
Best when	Load factor is unpredictable	Memory locality matters

The short version

A hash function converts any key into an array index - that is what makes O(1) lookup possible.
Collisions are inevitable - there are infinite keys but finite buckets. The collision strategy is the design decision.
Chaining keeps collided items in a list at the same bucket. Linear probing walks forward to find an open slot.
Load factor = items / buckets. Above 0.75, collisions degrade O(1) toward O(n). Rehash before that happens.
Rehashing is O(n) but amortized O(1) per insert - the cost is spread across all future operations.