Hash Tables Explained Visually — Hashing, Collisions, Chaining

Every time you write user["email"] in Python, map.get(key) in Java, or obj.name in JavaScript, a hash table answers in what feels like no time at all — regardless of whether it holds ten entries or ten million. That near-constant lookup is not magic, and it is not free. It rests on one clever trick, and on a series of careful engineering decisions that keep the trick from falling apart.

This guide walks through that trick visually: how a hash function turns a key into a bucket index, why collisions are mathematically unavoidable, how separate chaining and linear probing resolve them, and what load factor and resizing have to do with keeping lookups fast.

The core trick: compute where to look

Every other lookup structure *searches* for a key — a BST compares its way down a tree, a sorted array binary-searches. A hash table does something categorically different: it computes where the key must be. A hash function converts the key into a number, that number is reduced modulo the number of buckets, and the result is an array index. Jump straight there. No comparisons against other keys, no walking anything — which is why the average cost is O(1), independent of how many entries the table holds.

put(key, value):
  index = hash(key) mod bucket_count
  append (key, value) to buckets[index]   // chain handles collisions

get(key):
  index = hash(key) mod bucket_count
  for each (k, v) in buckets[index]:      // usually 0 or 1 entries
    if k == key: return v
  return not_found

What makes a good hash function

The whole scheme lives or dies on the hash function. It needs three properties:

• Deterministic — the same key must always hash to the same index, or you will store a value in one bucket and look for it in another.
• Uniform — keys should spread evenly across buckets. A function that funnels most keys into a few buckets recreates the very linear search the table exists to avoid.
• Fast — the hash is computed on every single operation; an expensive hash taxes every lookup.

A classic bad example: hashing strings by summing their character codes. "listen", "silent", and "enlist" all sum identically, so every anagram lands in the same bucket. Real string hashes (like the multiply-and-add family used in most language runtimes) mix each character with the running result so that order matters and small input changes scatter to distant outputs.

Collisions are inevitable

Two different keys landing in the same bucket is called a collision, and no clever function can eliminate them: if you have more possible keys than buckets — and you always do, since keys are drawn from an effectively unlimited space while buckets are a small array — the pigeonhole principle guarantees that some keys must share. Collisions are not a failure mode to be avoided; they are a certainty to be *handled*. The two classic strategies are separate chaining and open addressing.

Separate chaining, traced

In separate chaining, each bucket holds a small linked list of every entry that hashed there. Take a table with 8 buckets and a toy hash, and insert five keys:

1. "cat" hashes to 34 → 34 mod 8 = 2 → bucket 2 gets the chain [cat].
2. "dog" hashes to 53 → 53 mod 8 = 5 → bucket 5: [dog].
3. "fox" hashes to 18 → 18 mod 8 = 2 → collision! Bucket 2 chains it: [cat → fox].
4. "owl" hashes to 47 → 47 mod 8 = 7 → bucket 7: [owl].
5. "elk" hashes to 26 → 26 mod 8 = 2 → bucket 2 again: [cat → fox → elk].

A lookup for "fox" hashes to bucket 2, then walks the chain comparing keys: cat? No. fox? Found, after one hash and two comparisons. This is the crucial nuance behind "O(1) average": the cost is really *O(1 + chain length)*. As long as the hash spreads keys uniformly and the table is sized sensibly, chains average out to a handful of entries at most — but that qualifier is doing real work, as we are about to see.

Open addressing: the other way out

Open addressing stores everything directly in the bucket array, no chains. On a collision, linear probing simply tries the next slot, then the next, wrapping around until it finds an empty one; lookups retrace the same probe path. The appeal is memory locality — consecutive array slots are cache-friendly in a way scattered list nodes are not, and there are no pointers to store.

Load factor and resizing

The load factor is entries divided by buckets, and it is the single dial that controls hash table health. Low load factor: wasted memory. High load factor: chains lengthen (or probe runs cluster) and O(1) quietly erodes toward O(n). Most implementations resize when the load factor crosses a threshold around 0.75 — a hedge that keeps expected chain lengths near one while tolerating some memory overhead. Push much past that and, especially with open addressing, collision costs start compounding quickly.

Resizing means allocating a bucket array roughly twice the size and rehashing every entry — the modulus changed, so old positions are meaningless. A single resize is O(n), which sounds alarming, but doubling means an item is only rehashed when the table has doubled since the last time: spread across all the cheap inserts in between, the average cost per insert stays O(1). This is the same *amortized* accounting that makes dynamic arrays cheap.

The worst case is real

If every key lands in one bucket, the table degenerates into a single linked list and every operation costs O(n). This is not just theoretical bad luck. If an attacker knows your hash function, they can construct thousands of keys that deliberately collide — a hash-flooding attack that turns a web server parsing request parameters into a quadratic-time tarpit. It is why modern language runtimes seed their string hashes with a random per-process value: the attacker can no longer predict which keys collide.

Hash table or BST?

The last row of that table is the honest weakness. Hashing deliberately destroys ordering — that scattering *is* the speed — so a hash table cannot answer "smallest key above 40" or iterate keys in sorted order without collecting and sorting everything. A binary search tree keeps keys ordered at all times: lookups cost O(log n) instead of O(1), but range queries, sorted iteration, and predecessor/successor queries come built in, and a balanced tree has no O(n) blowup to worry about. The rule of thumb: if you only ever ask "exact key in or out?", hash it; the moment order or ranges matter, use a tree.

Where you use hash tables every day

• Language built-ins — Python dicts and sets, JavaScript objects and Maps, Java HashMap, Go maps, Ruby hashes: the default associative container everywhere is a hash table.
• Caches — from CPU-adjacent memoization to Redis and Memcached, "have I computed this before?" is a hash lookup.
• Sets and deduplication — membership tests, seen-lists in graph traversal, counting distinct items.
• Indexing by anything — sessions by token, users by email, DNS names to addresses: any key → value mapping with no ordering requirement.

Try it yourself

The mental model clicks when you watch it: keys hashing to indices, a collision forcing a chain to grow, the same bucket absorbing entry after entry. Run the visualizer, follow a key from hash to bucket to chain, and then imagine the load factor creeping up — you will understand resizing better than any paragraph can teach it.