contentintech
Learn/DSA/Hash Tables
Data StructuresBeginner9 min

Hash Tables

O(1) average lookups via a hash function — plus how collisions and load factor are handled.

Hash MapHashingCollisions

A hash table is the workhorse of practical programming — dict in Python, HashMap in Java, Map/objects in JS. It stores key → value pairs and gives you average O(1) insert, lookup, and delete. Half of all "optimize this" interview answers boil down to "use a hash map."

The magic is a hash function that turns any key into an array index. Instead of scanning for a key, you compute where it must live and jump straight there — trading a little memory and a good hash for near-constant time.

Hash Table (chaining)
0
→
∅
1
→
∅
2
→
∅
3
→
∅
4
→
12→
20
5
→
5
6
→
∅
7
→
7
index = hash(key) % 8. Collisions chain in the same bucket.
index = hash(key) % capacity. Keys that collide into the same bucket chain together.

Collisions are inevitable

Many keys, finite buckets — by the pigeonhole principle two keys will eventually hash to the same slot. Two standard fixes:

  • Separate chaining — each bucket holds a small list; colliding keys append to it (shown above).
  • Open addressing — on collision, probe to the next open slot (linear/quadratic probing, double hashing). More cache-friendly, no pointers.

Why O(1) is "average"

If every key collides into one bucket, lookups degrade to O(n). Real implementations keep the load factor (items ÷ buckets) low by resizing, and use good hash functions, so worst cases are rare — but they exist (and hash-flooding attacks exploit them).

Load factor & resizing

When the load factor crosses a threshold (often ~0.75), the table doubles capacity and rehashes every key into the bigger array. That resize is O(n), but amortised across many inserts it keeps operations at O(1).

OperationTime

Hash tables are unordered — if you need sorted keys, use a balanced BST / TreeMap (O(log n)).

The pattern that wins interviews

A hash map trades space for time: remember what you have seen so a second pass becomes a single lookup. Classic Two Sum drops from O(n²) to O(n).

Two Sum in O(n) with a hash map
function twoSum(nums, target) {
  const seen = new Map()          // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}

Interview reflex

Hearing "count frequencies", "find duplicates", "seen before?", "group by", or "O(1) lookup"? Reach for a hash map (or a hash set when you only need membership).

Section navigation