Hash Tables
A Hash Table (or map) is a key-value data structure. It uses a hash function to map key strings/numbers to index positions inside an array, enabling average constant-time lookups.
Why It Exists
Accessing items in arrays is fast only if you know the index. Hash tables allow you to find items in constant time using arbitrary keys like words or email addresses.
Intuition for Beginners
“Think of a filing cabinet. To store a file, you take the first letter of the name (e.g. 'Avick' maps to drawer 'A'). Searching for the file only requires checking the 'A' drawer, bypassing the rest.”
Visual Explanation
Key -> Hash Function -> Array Index -> Value "Avick" -> HashCode(Avick) % 10 -> [3] -> "User Profile Data"
Prefix Sum HashMap
Set running sum = 0. Seed hashmap with prefix sum 0 at index -1.
Complexity Analysis
| Operation | Time (Avg) | Time (Worst) | Notes |
|---|---|---|---|
| Insert | O(1) | O(N) | Worst case occurs on heavy collisions |
| Delete | O(1) | O(N) | Must resolve collision chains |
| Search | O(1) | O(N) | Direct index translation |
| Space | O(N) | O(N) | Requires auxiliary bucket storage |
Production & Real World Applications
- •In-Memory Caches: Redis maps storing sessions against token strings.
- •Unique Registers: Checking username availability in databases.
Algorithmic Patterns
Creating linked list chains at colliding array slots to store overlapping entries.
Probing neighboring slots in the array sequentially until an empty cell is found.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Writing poor hash functions that distribute keys unevenly.
- ⚠️Assuming lookups are always guaranteed O(1) without considering collision chains.