Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A hash table (hash map) is a data structure that maps keys to values using a hash function
A hash table (hash map) is a data structure that maps keys to values using a hash function.
It provides near-constant-time average lookup by computing an array index from the key's hash code.
How It Works
A hash function `h(k)` maps each key `k` to an integer index within the table size.
Collisions occur when two keys hash to the same index.
Two strategies resolve collisions: chaining (each bucket holds a linked list of entries) and open addressing (probing finds the next empty slot via linear, quadratic, or double hashing).
Load factor α = n/m where n is entries and m is buckets.
High load factors degrade performance and trigger resizing (rehashing).
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Insert (average) | O(1) | O(1) |
| Insert (worst) | O(n) | O(1) |
| Search (average) | O(1) | O(1) |
| Search (worst) | O(n) | O(1) |
| Delete (average) | O(1) | O(1) |
| Delete (worst) | O(n) | O(1) |
Best Use Cases
- Database indexing and caching (memcached, Redis)
- Symbol tables in compilers and interpreters
- Object property lookup in JavaScript engines
- Counting word frequencies (dictionary pattern)
- Implementing sets for membership testing
- Caching computed results (memoization)
Worked Example
Insert key 42 into a chaining table of 7 buckets
Input: hash(k) = k mod 7; table has 7 buckets; insert key 42- 1 Compute the bucket index: 42 mod 7 = 0.
- 2 Bucket 0 is empty, so append the (42, value) entry to its chain directly.
- 3 Now insert key 7: 7 mod 7 = 0, so it lands in the same bucket 0.
- 4 Because bucket 0 uses chaining, the two entries simply form a chain — no probing or shifting needed.
- 5 Search for 42 hashes to bucket 0 and scans the (short) chain to find the key.
Linear probing: keys 42 then 7 (7 buckets)
Input: hash(k) = k mod 7; insert keys 42 and 7- 1 Key 42 hashes to bucket 0, which is empty — place it there.
- 2 Key 7 also hashes to bucket 0, but it is occupied by 42.
- 3 Probe forward: bucket 1 is free, so key 7 is stored there.
- 4 Search for 7 starts at bucket 0, finds 42 (not it), then bucket 1, where the match is found.
- 5 After many collisions, probes cluster and slow lookups — the motivation for resizing when the load factor rises.
Pseudocode
function insert(table, key, value):
idx = hash(key) mod table.length
bucket = table[idx]
for each entry in bucket.chain:
if entry.key == key:
entry.value = value // update
return
bucket.chain.append({key, value}) function search(table, key):
idx = hash(key) mod table.length
bucket = table[idx]
for each entry in bucket.chain:
if entry.key == key:
return entry.value
return null function insert(table, key, value):
idx = hash(key) mod table.length
for i = 0 to table.length - 1:
probe = (idx + i) mod table.length
if table[probe] is empty or deleted:
table[probe] = {key, value}
return
error "Table full" function search(table, key):
idx = hash(key) mod table.length
for i = 0 to table.length - 1:
probe = (idx + i) mod table.length
if table[probe] is empty:
return null // not found
if table[probe].key == key:
return table[probe].value
return null // not found function delete(table, key):
idx = hash(key) mod table.length
for i = 0 to table[idx].chain.length - 1:
if table[idx].chain[i].key == key:
table[idx].chain.remove(i)
return
// Key not found function delete(table, key):
idx = hash(key) mod table.length
for i = 0 to table.length - 1:
probe = (idx + i) mod table.length
if table[probe] is empty:
return // not found
if table[probe].key == key:
table[probe].deleted = true
return Chaining
Select an operation to begin.