Hashing
Hashing in DSA
Learn how hash tables enable fast data storage and retrieval.
📌 Topics Covered
🚀 Introduction
Hashing is used to store and retrieve data in constant time using key-value mapping.
💡 Key Insight: Average time complexity of hashing = O(1)
🧠 Core Concepts
Hash Function
Maps input keys to fixed-size indices.
Hash Table
Stores data using computed hash values.
Load Factor
Defines how full the table is → affects performance.
⚡ Collision Handling
Separate Chaining
- Use linked list at each index
Open Addressing
- Linear Probing
- Quadratic Probing
- Double Hashing
💡 Collisions are unavoidable — handling them efficiently is key.
🧪 Important Questions
- How collisions affect performance?
- How to choose hash function?
- Time complexity of hashing?
- When to resize hash table?
☕ Java Implementation
Separate Chaining
class HashTable {
LinkedList[] table;
}
Open Addressing
class HashTable {
int[] table;
}
❓ FAQs
- Q: What is load factor?
- Ratio of elements to table size.
- Q: Can collisions be avoided?
- No, only minimized.
- Q: Why override hashCode()?
- To ensure proper key distribution.
🎯 Conclusion
Hashing is one of the fastest techniques for data access and is heavily used in real-world systems.