DSA Hash Tables
DSA Hash Tables – Complete Beginner Guide
(Concept • Hash Function • Collisions • Operations • Implementation • Complexity)
A Hash Table is one of the fastest data structures for storing and retrieving data.
It provides average O(1) time for search, insert, and delete.
1️⃣ What is a Hash Table?
A Hash Table stores data in key–value pairs.
-
Key → unique identifier
-
Value → data associated with the key
-
Hash Function → converts key into an index
📌 Data is stored in an array-like structure using the computed index.
2️⃣ Why Hash Tables Are Fast
-
Direct access using index
-
No need to traverse like arrays or linked lists
-
Ideal for dictionaries, caches, databases
3️⃣ Hash Function
A hash function:
-
Takes a key
-
Produces a fixed-size integer (index)
-
Distributes keys uniformly
Example
📌 Good hash functions reduce collisions.
4️⃣ What is a Collision?
A collision occurs when two different keys map to the same index.
5️⃣ Collision Resolution Techniques
1. Chaining
-
Each table index stores a linked list
-
All collided elements go into the list
✔ Simple
❌ Extra memory
2. Open Addressing
Store elements in the next available slot.
Types:
-
Linear Probing →
index + 1 -
Quadratic Probing →
index + i² -
Double Hashing → second hash function
✔ No extra memory
❌ Clustering problem
6️⃣ Basic Hash Table Operations
Insert
-
Compute index using hash function
-
Store value at index (handle collision)
Search
-
Compute index
-
Check index (and linked list if chaining)
Delete
-
Find key
-
Remove value safely
7️⃣ Hash Table Using Chaining (C++ Example)
8️⃣ Hash Table Using Open Addressing (Linear Probing)
9️⃣ Time Complexity
| Operation | Average | Worst Case |
|---|---|---|
| Insert | O(1) | O(n) |
| Search | O(1) | O(n) |
| Delete | O(1) | O(n) |
📌 Worst case occurs when many collisions happen.
🔟 Space Complexity
-
O(n) for storing elements
-
Extra space for chaining (if used)
1️⃣1️⃣ Load Factor
📌 High load factor → more collisions
📌 Resize table when load factor increases
1️⃣2️⃣ Real-Life Uses of Hash Tables
✔ Dictionaries & Maps
✔ Database indexing
✔ Caching (LRU Cache)
✔ Symbol tables in compilers
✔ Password verification
1️⃣3️⃣ Hash Table vs Array
| Feature | Hash Table | Array |
|---|---|---|
| Access | O(1) avg | O(1) |
| Key type | Any | Integer index |
| Order | Unordered | Ordered |
| Flexibility | High | Low |
Interview Questions (Hash Tables)
Q1. What is a hash table?
👉 Key–value data structure with fast access
Q2. What is collision?
👉 Two keys map to same index
Q3. Best collision handling technique?
👉 Depends on use case
Q4. Why worst case is O(n)?
👉 Too many collisions
✅ Final Summary
✔ Hash Tables store key–value pairs
✔ Use hash functions for indexing
✔ Collisions handled by chaining or probing
✔ Average time complexity: O(1)
✔ Very important for DSA & interviews
