DSA Hash Tables — Fundamentals Visualized
Learn hash table fundamentals — hash functions, buckets, collisions, separate chaining, O(1) average operations, interactive visualizer, and real-world examples.
Introduction
Hash tables map keys to array indices via a hash function — giving O(1) average insert,
lookup, and delete. They power JavaScript Map, Python dict, and database indexes.
Unlike arrays (index by number) or binary search trees (O(log n)), hash tables trade a small collision risk for constant-time access.
Quick index
| # | Section |
|---|---|
| 1 | How hash tables work |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Collisions & load factor |
| 5 | Real-life examples |
1. How hash tables work
key "apple" → hash("apple") = 2 → buckets[2] = { apple: 5 }
key "banana" → hash("banana") = 4 → buckets[4] = { banana: 3 }| Step | Action |
|---|---|
| 1 | Hash the key → bucket index |
| 2 | Store key-value at that bucket |
| 3 | Lookup — hash key again, read bucket |
| 4 | Collision — chain or probe if bucket taken |
2. Interactive visualizer
Hash Tables — Fundamentals
Hash function maps keys to bucket indices — O(1) average insert, lookup, and delete.
Hash function maps any key to a bucket index in O(1).
Hash function
function hash(key, capacity) {
let h = 0
for (let i = 0; i < key.length; i++)
h = (h + key.charCodeAt(i) * (i + 1)) % capacity
return h
}Good hash spreads keys evenly — bad hash clusters collisions.
get / set
O(1) avg
Collision
Chaining
Load factor
< 0.75
3. Full implementation
class HashTable {
constructor(capacity = 7) {
this.capacity = capacity
this.buckets = Array.from({ length: capacity }, () => [])
this.count = 0
}
_hash(key) {
let hash = 0
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * (i + 1)) % this.capacity
}
return hash
}
set(key, value) {
const index = this._hash(key)
const bucket = this.buckets[index]
const existing = bucket.find((e) => e.key === key)
if (existing) {
existing.value = value
} else {
bucket.push({ key, value })
this.count++
}
}
get(key) {
const bucket = this.buckets[this._hash(key)]
const entry = bucket.find((e) => e.key === key)
return entry?.value
}
has(key) {
return this.get(key) !== undefined
}
delete(key) {
const index = this._hash(key)
const bucket = this.buckets[index]
const idx = bucket.findIndex((e) => e.key === key)
if (idx === -1) return false
bucket.splice(idx, 1)
this.count--
return true
}
size() {
return this.count
}
}Function calls with output
// ── Demo calls — output shown on the right ──
const table = new HashTable(7)
table.set('apple', 5) // → stored at bucket[hash("apple")]
table.set('banana', 3) // → stored at bucket[hash("banana")]
table.set('cherry', 8) // → stored (may chain on collision)
table.get('apple') // → 5
table.get('fig') // → undefined
table.has('banana') // → true
table.delete('apple') // → true
table.size() // → 24. Collisions & load factor
| Strategy | How it works | Tradeoff |
|---|---|---|
| Separate chaining | Linked list per bucket | Simple, handles high load |
| Open addressing | Probe next empty slot | Less memory, clustering risk |
| Resize / rehash | Double capacity when load > 0.75 | Amortized O(1) |
Load factor = entries / capacity. Keep below 0.75 for O(1) performance.
5. Real-life examples
| Scenario | Hash table role |
|---|---|
| Database index | Primary key → row pointer |
| DNS cache | domain → IP address |
| Symbol table | variable name → memory address |
| Password lookup | username → hashed password |
DNS domain → IP lookup
DNS resolver caches domain names to IP addresses — classic hash table key-value lookup.
Query: api.example.com
hash → bucket[3]
bucket empty → upstream DNS
First lookup misses cache — fetch from DNS server.
Real-world implementation
class DNSCache {
constructor() { this.table = new Map() }
resolve(domain) {
if (this.table.has(domain)) return this.table.get(domain)
const ip = this._queryUpstream(domain)
this.table.set(domain, ip)
return ip
}
}Full working code for the scenario above.
Function calls with output
| // ── Function calls with output ── | |
| dns.resolve("api.example.com") | → cache miss, query upstream |
Side output shows return value after each call — step through to trace execution.
Summary
Hash tables give O(1) average key-value access via hashing. Next: sets (keys only) and maps (key-value pairs).
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime