What Is a Hash Table?

A hash table stores key-value pairs and finds a value in about O(1) time by running the key through a hash function to compute where it lives. JavaScript objects and Maps, Python dicts and Java HashMaps are hash tables.

The concept

The hash function turns a key into an integer index into an array of buckets. Two keys may land in the same bucket (a collision), handled by chaining or probing.

When the table gets too full it resizes and rehashes. Good hash functions spread keys evenly.

Key → bucket

Practical examples

Using one

const m = new Map([['ada', 36]])
m.get('ada') // 36 — O(1) average

Count items

counts = {}
for w in words: counts[w] = counts.get(w, 0) + 1

Tiny implementation

class HT {
  b = Array.from({ length: 16 }, () => [])
  h(k) { let x = 0; for (const c of String(k)) x = (x * 31 + c.charCodeAt(0)) % 16; return x }
  set(k, v) { const s = this.b[this.h(k)]; const e = s.find(p => p[0] === k); e ? (e[1] = v) : s.push([k, v]) }
  get(k) { return this.b[this.h(k)].find(p => p[0] === k)?.[1] }
}

Common mistakes

• Using mutable objects as keys.
• Poor hash functions causing many collisions (O(n) lookups).
• Assuming iteration order in all languages.

Key takeaways

• Average O(1) get/set.
• Collisions handled by chaining or probing.
• Resizes automatically.

FAQ

Worst-case complexity?

O(n) if all keys collide, rare with good hashing.

Hash table vs array?

Arrays index by position; hash tables index by arbitrary keys.