Hash Tables

A data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found.

What is it?

Hash tables (or hash maps) are optimized for incredibly fast lookups, insertions, and deletions (O(1) on average). They work by using a "hash function" to convert a key (like a username or a URL) into a memory address. A perfect example is a web browser's cache. When you visit a website, the browser stores assets like images. The image's URL is the key. The browser's hashing function converts this URL into an index, and the image data is stored at that index. The next time you visit the site, the browser hashes the URL again, instantly finds the image in the cache at the computed index, and loads the page without re-downloading the image. This is why repeat visits to websites are so much faster.

Time Complexity

AccessN/A

SearchO(1)

InsertionO(1)

DeletionO(1)

Implementation Example

// In JavaScript, Objects and Maps are hash tables.
const map = new Map();

// Set a key-value pair
map.set('name', 'Alex');

// Get a value by key
const name = map.get('name'); // "Alex"
console.log(name);

// Check if a key exists
console.log(map.has('name')); // true

// Delete a key-value pair
map.delete('name');

Hash Tables

Hash Tables Deep Dive

Hash tables provide near-constant operations by translating arbitrary keys into array indices via hash functions.

?But why does this matter?

Load factor and collision strategy (chaining vs open addressing) determine whether you stay close to O(1) in production.

Visual Flow

How it actually moves

Lookup

O(1) average

Compute hash, probe bucket, compare keys.

Insertion

O(1) average

Place key/value and adjust load factor.

Deletion

O(1) average

Remove entry and maintain collision metadata.

Insert with chaining

Compute index = hash(key) mod bucketCount.

Scan the bucket list: if key already exists, update its value.

Otherwise prepend/append a new node containing (key, value).

If load factor exceeds threshold, grow bucket array and rehash items.

Watch the best explainer

Hash Tables and Hash Functions

Computer Science Lessons

The most-viewed conceptual walkthrough of hashing, collisions, and chaining.

Library card catalog vibe

Instead of walking aisle by aisle, you hash the book title into a drawer index and jump right there. Occasionally two titles collide, so the drawer keeps a short list of cards.

Real-world analogy

Browser caches hash URLs to find images instantly during repeat visits.

Takeaway

Investing in a good hash function and load-factor strategy keeps collisions rare and latency predictable.

Practical applications

• API gateway rate limiting keyed by user or token.
• Compilers mapping identifiers to symbol metadata.
• Caching layers (Redis/Memcached) storing session data.

Technical insights

• A good hash spreads keys uniformly; consider SipHash or xxHash for untrusted input.
• Chaining is simple but causes pointer chasing; open addressing stays cache-friendly but needs tombstones.
• Resizing typically doubles buckets; growing too often multiplies GC pressure.

When to reach for it

• Key-value caches
• Symbol tables
• Deduplication

Operations Breakdown

Lookup

O(1) average

Compute hash, probe bucket, compare keys.

Insertion

O(1) average

Place key/value and adjust load factor.

Deletion

O(1) average

Remove entry and maintain collision metadata.

Best practices

• Monitor load factor; rehash before exceeding ~0.75 to keep probes short.
• Use immutable keys (strings, ints) to avoid hash drift.
• Salting hashes defends against collision attacks in multi-tenant systems.

Common pitfalls

• Pathological collisions degrade performance to O(n).
• Forgetting to rehash on resize corrupts data.
• Iteration order is undefined; do not rely on it unless using ordered maps.

Every kind of Hash Tables

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 6

Separate Chaining

→ full page

Each bucket holds a small list of entries that share a hash. Simple, tolerant of high load factors, and easy to delete from.

What to know

Load factor = entries / buckets; chains average that length under a good hash.
Java HashMap converts long chains (≥ 8) into red-black trees to cap worst case at O(log n).
Resizing rehashes every entry into a doubled bucket array.

Algorithms to reach for

Hash + chain walk

O(1) avg, O(chain) worst

Insert/lookup/delete under collisions

Treeify long chains

O(log n) worst

Defend against hash-flood attacks

In the wild: Java HashMap, Python dict history, most textbook implementations.

Practice problems — hints, approach & solution on their own pages

Design HashMapEasy Two SumEasy Group AnagramsMedium

Type 2 of 6

Open Addressing

→ full page

No chains — collisions probe for the next free slot in the same array. One allocation, cache-friendly, but deletion needs tombstones.

What to know

Linear probing scans forward; clustering is the enemy.
Robin Hood hashing steals slots from "rich" entries to flatten probe lengths.
Must resize before load factor gets high (~0.7) or probes explode.

Algorithms to reach for

Linear / quadratic probing

O(1) avg

Find next open slot after collision

Robin Hood insertion

O(1) avg

Minimize variance of probe distances

Tombstone deletion

O(1) avg

Delete without breaking probe chains

In the wild: Python dict, Rust HashMap (SwissTable), Go map internals.

Practice problems — hints, approach & solution on their own pages

Design HashSetEasy Contains DuplicateEasy

Type 3 of 6

Cuckoo Hashing

→ full page

Two hash functions, two possible homes per key; inserts evict squatters to their other home. Lookup is O(1) worst case, not just average.

What to know

Lookup checks exactly two slots — perfect for hardware and latency SLAs.
Insertion may cascade evictions; a cycle forces a rehash.
Keeps load factors ~50% (two tables) or higher with bucketized variants.

Algorithms to reach for

Two-choice lookup

O(1) worst

Guaranteed two-probe reads

Eviction-chain insert

O(1) amortized

Kick keys between homes until stable

In the wild: Network switches/routers, GPU hash tables, high-frequency trading lookups.

Type 4 of 6

Consistent Hashing

→ full page

Hash servers and keys onto a ring; each key belongs to the next server clockwise. Adding or removing a server remaps only ~1/N of keys.

What to know

Virtual nodes (100–200 per server) smooth load imbalance.
Naive mod-N hashing remaps nearly everything on membership change — the problem this solves.
Jump hash and rendezvous hashing are compact alternatives.

Algorithms to reach for

Ring placement + binary search

O(log S)

Route key → owning server

Virtual-node rebalancing

O(1) per key

Even load across heterogeneous servers

In the wild: DynamoDB, Cassandra, Memcached clients, CDN request routing, Kafka partitioners.

Type 5 of 6

Bloom Filter & Sketches

→ full page

Probabilistic cousins of the hash table: answer membership or frequency questions in tiny memory, accepting a small, tunable error.

What to know

Bloom filter: k hash bits per key; "no" is certain, "yes" might be false.
Cannot delete from a plain Bloom filter — counting variants fix that.
Count-min sketch estimates frequencies; HyperLogLog counts distincts in ~1.5 KB.

Algorithms to reach for

Bloom insert/query

O(k)

Skip expensive lookups for absent keys

Count-min updates

O(k)

Heavy-hitter detection on streams

HyperLogLog merge

O(1) per item

Distinct counts across shards

In the wild: RocksDB/Cassandra SSTable filters, Chrome Safe Browsing, Redis PFCOUNT, ad dedup.

Type 6 of 6

HashMap + Structure Combos

→ full page

The interview power move: bolt a hashmap onto another structure to make every operation O(1). LRU cache is the canonical example.

What to know

LRU = hashmap → DLL nodes; recency order lives in the list, lookup in the map.
RandomizedSet = hashmap (value → index) + array (swap-with-last delete).
LFU adds a second map from frequency → DLL of keys.

Algorithms to reach for

LRU cache

O(1)

O(1) get/put with least-recently-used eviction

Insert/Delete/GetRandom O(1)

O(1)

Set with uniform random sampling (LeetCode 380)

LFU cache

O(1)

Evict by frequency then recency (LeetCode 460)

In the wild: Redis eviction policies, CDN caches, database buffer pools.

Practice problems — hints, approach & solution on their own pages

LRU CacheMedium Insert Delete GetRandom O(1)Medium LFU CacheHard

Pseudo Code • Insert with chaining

Flow Diagram

Compute index = hash(key) mod bucketCount.
Scan the bucket list: if key already exists, update its value.
Otherwise prepend/append a new node containing (key, value).
If load factor exceeds threshold, grow bucket array and rehash items.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

class HashTable {
  constructor(capacity = 8) {
    this.capacity = capacity;
    this.buckets = Array.from({ length: capacity }, () => []);
  }

  set(key, value) {
    const idx = this.#hash(key);
    const bucket = this.buckets[idx];
    for (const entry of bucket) {
      if (entry.key === key) {
        entry.value = value;
        return;
      }
    }
    bucket.push({ key, value });
  }

  #hash(key) {
    return [...String(key)].reduce((acc, ch) => acc * 31 + ch.charCodeAt(0), 7) % this.capacity;
  }
}