The Phone Book Analogy
A phone book maps names to phone numbers:
- Look up "Alice" → get "555-1234"
- Each name (key) has exactly one number (value)
- Finding a name is fast (alphabetical organization)
Maps work the same way - they store key-value pairs where each key maps to exactly one value.
What Makes Maps Special
Key-Value Association
Map: {
"Alice": "555-1234",
"Bob": "555-5678",
"Carol": "555-9012"
}
Get Alice's number: O(1)
Get Bob's number: O(1)
No scanning required!
Unique Keys, Any Values
Keys must be unique:
"Alice": "555-1234"
"Alice": "555-9999" → Replaces the first!
Values can repeat:
"Alice": "555-1234"
"Bob": "555-1234" → Same number, different people ✓
Map Operations
Core Operations
PUT/SET - Add or update key-value pair (O(1))
map["Alice"] = "555-1234"
GET - Retrieve value by key (O(1))
map["Alice"] → "555-1234"
map["Unknown"] → null/error
CONTAINS KEY - Check if key exists (O(1))
"Alice" in map → true
"Dave" in map → false
REMOVE - Delete key-value pair (O(1))
delete map["Alice"]
SIZE - Count pairs (O(1))
len(map) → 3
KEYS - Get all keys (O(n))
map.keys() → ["Alice", "Bob", "Carol"]
VALUES - Get all values (O(n))
map.values() → ["555-1234", "555-5678", "555-9012"]
Visual Example
Word Frequency Counter:
Text: "the cat sat on the mat"
Process each word:
"the" → {the: 1}
"cat" → {the: 1, cat: 1}
"sat" → {the: 1, cat: 1, sat: 1}
"on" → {the: 1, cat: 1, sat: 1, on: 1}
"the" → {the: 2, cat: 1, sat: 1, on: 1} ← incremented!
"mat" → {the: 2, cat: 1, sat: 1, on: 1, mat: 1}
Most frequent: "the" (2 times)
Where Maps Are Used
1. Counting Frequencies
Count character occurrences:
"hello" → {h: 1, e: 1, l: 2, o: 1}
2. Caching/Memoization
fib_cache = {}
def fib(n):
if n in fib_cache:
return fib_cache[n]
result = fib(n-1) + fib(n-2)
fib_cache[n] = result
return result
3. Configuration
config = {
"host": "localhost",
"port": 8080,
"debug": true
}
4. Grouping
Group students by grade:
{
"A": ["Alice", "Bob"],
"B": ["Carol", "Dave"],
"C": ["Eve"]
}
5. Graph Representation
Adjacency list:
{
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"]
}
Classic Map Problems
1. Two Sum
Find two numbers that add to target.
Array: [2, 7, 11, 15], Target: 9
Use map to store number → index:
See 2, need 7. Store {2: 0}
See 7, need 2. 2 is in map! ✓
Answer: indices [0, 1]
2. First Non-Repeating Character
String: "leetcode"
Count frequency: {l:1, e:3, t:1, c:1, o:1, d:1}
First with count 1: 'l' at index 0
3. Group Anagrams
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Key = sorted letters:
{
"aet": ["eat", "tea", "ate"],
"ant": ["tan", "nat"],
"abt": ["bat"]
}
4. LRU Cache
Least Recently Used cache with O(1) operations.
Uses: Map for O(1) lookup + doubly linked list for ordering
Map Implementations
Hash Map
Based on hash table:
Pros:
- O(1) average for all operations
- Fast and common
Cons:
- Unordered iteration
- O(n) worst case (bad hashing)
Tree Map (Sorted Map)
Based on balanced tree:
Pros:
- Keys maintained in sorted order
- Range queries: "all keys between A and Z"
Cons:
- O(log n) operations
- More overhead
Linked Hash Map
Hash map + linked list:
Pros:
- O(1) operations
- Maintains insertion order
Cons:
- More memory
Map vs Other Structures
| Operation | Map | Array | Set |
|---|---|---|---|
| Get by key | O(1) | O(n) | ❌ |
| Get by index | ❌ | O(1) | ❌ |
| Check existence | O(1) | O(n) | O(1) |
| Store associations | ✓ | ✗ | ✗ |
| Allow duplicates | Values only | ✓ | ❌ |
Map = Set with associated values.
Maps in Different Languages
| Language | Hash Map | Sorted Map |
|---|---|---|
| Python | dict | (use sorted()) |
| JavaScript | Object, Map | -------------- |
| Java | HashMap | TreeMap |
| C++ | unordered_map | map |
| Go | map | -------------- |
Common Mistakes
1. Unhashable Keys
Lists and dicts can't be keys (mutable). Use tuples or strings.
2. Missing Key Access
Accessing non-existent key throws error in some languages. Use .get() with default.
3. Modifying While Iterating
Don't add/remove keys while looping!
4. Assuming Order
Most hash maps don't preserve order. Python 3.7+ dicts do.
FAQ
Q: Map vs object in JavaScript?
Objects have prototype overhead. Map has better performance for many key-value pairs and non-string keys.
Q: When to use map vs set?
Map: need to associate data with keys. Set: just need to track unique keys.
Q: Can map values be null/None?
Usually yes, but be careful - you can't distinguish between "key exists with null value" and "key doesn't exist" easily.
Q: What if I need multiple values per key?
Store a list/array as the value: { "key": [val1, val2, val3] }
Summary
A map is a collection of key-value pairs with O(1) lookup by key.
Key Takeaways:
- Each key maps to exactly one value
- Keys must be unique; values can repeat
- O(1) get, set, delete by key
- Hash map (fast, unordered) vs tree map (sorted)
- Used for: counting, caching, grouping, graph representation
- Foundation of most programming: configs, data, state
Maps are the most commonly used data structure in practice!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.