DSA Hash Maps
A hash map stores key-value pairs and uses hashing to give average O(1) lookup, insertion, and deletion by key; in Python this structure is built in as the dict type.
What Is a Hash Map?
A hash map, called a dictionary or dict in Python, pairs each key with a value and uses the same hashing mechanism as a hash table to decide where that pair is stored. Given a key, the map hashes it, jumps to the matching bucket, and returns the associated value without scanning the rest of the collection.
Creating and Using Dictionaries
Dictionaries are created with curly braces and colon-separated key-value pairs, or with the dict() constructor. Keys must be hashable (strings, numbers, and tuples of hashable items all qualify), while values can be anything.
Example
scores = {'alice': 92, 'bob': 85, 'carol': 78}
scores['dave'] = 88 # add a new pair
scores['bob'] = 90 # update an existing value
del scores['carol'] # remove a pair
print(scores) # {'alice': 92, 'bob': 90, 'dave': 88}
print(len(scores)) # 3
print('alice' in scores) # True (checks keys, not values)Iterating Over a Hash Map
- for key in d: - iterates over the keys only
- d.keys() - a view of all keys
- d.values() - a view of all values
- d.items() - a view of (key, value) tuples, ideal for unpacking in a loop
Example
inventory = {'pens': 40, 'notebooks': 15, 'erasers': 60}
for item, quantity in inventory.items():
print(f'{item}: {quantity} units')
low_stock = [item for item, qty in inventory.items() if qty < 20]
print(low_stock) # ['notebooks']Handling Missing Keys Safely
Example
from collections import defaultdict
scores = {'alice': 92}
print(scores.get('bob')) # None, no error
print(scores.get('bob', 0)) # 0, explicit default
groups = defaultdict(list)
groups['python'].append('Ada')
groups['python'].append('Grace')
print(dict(groups)) # {'python': ['Ada', 'Grace']}Note: Prefer .get() or defaultdict over checking 'if key in d' and then indexing - it avoids hashing the key twice and reads more clearly.
