Hash Map
A Hash Map is a key-value data structure that uses a hash function for fast access.
How It Works
1. Hashing: A hash function converts a key into an array index (a "bucket").
2. Storage: The key-value pair is stored in the bucket at the calculated index.
3. Lookup: To find a value, the key is hashed again to find the correct bucket, allowing for very fast access.
Collision Handling
A collision occurs when two different keys hash to the same index.
Chaining: The most common solution is to store a linked list (or a chain) of key-value pairs in each bucket. When a collision happens, the new entry is simply added to the chain.
When to Use Hash Maps
- For fast key-value lookups, like in caching systems.
- To implement dictionaries or map-like objects in programming.
- Counting frequencies of elements in a collection.
- For database indexing to quickly locate data records.
Complexity Analysis
| Operation | Time Complexity | Notes |
|---|---|---|
| Insert | O(1) avg | O(n) worst case |
| Delete | O(1) avg | O(n) worst case |
| Search | O(1) avg | O(n) worst case (collisions) |