Associative Array / Map
Overview
An Associative Array, commonly called a Map, is an abstract data type that stores data as key–value pairs. Each key uniquely identifies a value, enabling fast lookup based on the key rather than position.
Maps are fundamental to dictionaries, indexes, and symbol tables.
What Is a Map?
A map:
- Associates unique keys with values
- Does not rely on positional indexing
- Supports efficient lookup, insertion, and deletion
Keys and values can be of different types.
Core Map Operations
| Operation | Description |
|---|---|
| Put | Insert or update a key-value pair |
| Get | Retrieve value by key |
| Remove | Delete a key-value pair |
| Contains | Check if a key exists |
| Iterate | Traverse keys or values |
How It Works
Maps are abstract and can be implemented using:
- Hash tables
- Balanced trees
- Tries
Each implementation offers different performance guarantees.
Example
Pseudocode
map["id"] = 101
map["name"] = "Kiran"
print(map["name"])
Real-world Analogy
A map is like a phone contacts list. You search by name, not by how far down the list the contact appears 📞📘.
Time Complexity (Typical)
| Implementation | Get | Insert | Delete |
|---|---|---|---|
| Hash map | O(1) avg | O(1) avg | O(1) avg |
| Tree map | O(log n) | O(log n) | O(log n) |
Use Cases
- Caches
- Configuration storage
- Database indexing
- Counting and grouping
- Symbol tables
Advantages
- Fast key-based access
- Flexible data association
- Highly expressive
Limitations
- No inherent ordering (hash-based)
- Key uniqueness required
- Higher memory usage